Ш.И._Галиев_МЛ_и_ТА_2004

и требовалось. Заметим, что при формальном аксиоматическом подхолв (в теории L) ликаэзкльспю того, что |-Т! А=>А было получено.

Рассмотрим еще один пример на доказательство в естественном

Докажем, что имеет место

}- (Av(B&C))=>(AvS)&(AvC). (4.27)

Вид самой формулы для «ас лвлчетгл подсказкой, гак получить сс вы­ вод (если пк существует). Наи известно, что 4 вводится с помощью правила введения импликации. Следовательно, прежде чем получить (4.27), нужно доказать, ‘гго

(Av(Jf&C)) |-(Avfy&lAvQ.	(4.28)
А [(А'уВЩ А^С)	(4.29)
B&LC[ {AvB)&IA'/Cj	(4.30)
Высказывание (4.29) буцвт доказано правилом ыюдония конъ­
юнкции, если будет доказано, что
A \(AvB)*A \Ш С),	(4.31)
а (4.30) получим правилом введения конъюнкции ич
В&С [-(•''''■В) и В&С\-(А-;С).	(4.32)

Ясно, что оба предложения в (4.31) доказуемы но правилу вве­ дения дизъюнкция. Предложения (4.32) можно получилвведением дизъюнкции из предложений (S&Cj [■В и {В&.С) С. а последнее -

Описанную процедуру можно свести б схему, представленную

Теперь доказательство формулы (427) восстанавливается, если проделать, все рассужденияпо приведенной схеме, начиная снизу.

Отметим, что доказательство предложения (4.27) в формальной аксиоматической теории при обычных аксиомах будет значительно более длтгомм и громоздким.

Для того, чтобы 5адати исчисление предикатов в ви.че естестденного вывода, на заданные правила выюда накладываю! некоторые ограничения и адйзьяяют еще примерно столько *э коаых правил вывода.

182

2. Дедуктивные теории, ireклассификации

независимостьаксиом, раэрешиносг».

4.Полуформальные аксиоыатическке теории. Пример такой теории - геометрия В чем отличие геометрииЕвклидаот геометрии Лобачевскогс—Бойяи-Гаусса?

5.Формальные аксиоматические теории. Их эшние, понятие вывода, теоремы, следствия.

6.Каинесвойства выводииостизнаете?

иий?
Ч.	Укажите, какие из следующих фариул тпяюгсл теоремами
исчислениявысюаымии*:
a)TI5=>а,		б) t e ll S;
л) 1л=>(Л=>в);		в)(1В=Аа)=>(А=>В),
ж) м=>е)=к1в=>Ък		s)л=<1£=>1(4=г)У,
и)	А=>В)=/Ё),	к)^=.5)=15

выскмыааннй.

) I. Эквивалентностьдву*определений непротавовечивоста для

12. Непротиворечивостьисчисления высказываний.

14. HoasHCHHocTbcwM аксиом исчислениявысказывании,

16. Другиеаксиоматизацииисчислениивысказываний

17. Задание теорий первогопорядка.

!8. Исчисление предикатов первого порядка, его непротиворе­ чивость.

19.Формальная прифмоика.

•20. Понятие о теоримахГспеля.

21.Значение аксиоматического иегода.

22.Теория естесгвенного вывода.

I. Являете* ли инодом висчислении высказыванииследующая

2)14=5((,^)^14), 3)(14^(.4=^))= .(1^¼ А) ^=>(Л=14), 5)14^14.

1.Доназать, что для любыхформула, В исчисление вьгекязым-

яследующие формулы являются теоремами исчисления вискозы-

1)(1в=)1й);	2)А^0.А=.В),
3)(1 М у4)ч (/4»й);	4)(H=>fi)=»(lfi=-M);
5).4=-(1.8=-1(,4=-3))1	6)(Л=.й)=>((М=аЯ)=>Л).
1 )A\-AvB;	2)Л\-ВчА;
1)A,B\-A&B:	i)A.£[B&A

4. При uusajaisnicTHe неаавко•шогшЛ) птА2 нЛ1 в ксчаслгНИН высказываний введены «ьиЗтнныч формуяь’ (см. § 11 ГЛ. 4). Составить приграмму на одним к 1 языков прогриммироьанин для выясненил, vto формула исчисления высказываний, содержащая три «роиазвфюн&ггьные вуквы, явл;1егся выделенной. Используя эту программу, пилучить, что аксиома, iюлучекная по А2, ягияется вчде-

денной.

5 При доказательстве незяоис■тасткАг отА1 и А2 в исчислении высказываний введены rporesiciibie формулы (см. § 11 гл. 4). Сосгадить пршрамму на одном ю пы *пв npt'i-раимчрования для выяснения, что формула исчисления аысказыпйнчй, содержащая две пропозициональные букой, является. грогескной. Используя эту про­ грамму, пллучить, что аксиомы, «слученные по Я| либоАТ, являются гротескными.

6, Пусть в ксчислепии высказываний приуитивнами связками являются 1 &, v н тэ. Формулы пол)чены из пропозициональныхбум с помощью этих примитивных свлэов. Каковыбыни были формулыА. В и С, следующие формулысуть олсисмытеории!л-

А):А~>[ВпА):

Al: W=j(B^q)=?((yl:35)S(/(=5C));

Ai: А&&&А; А',-. А&В=>В;

Л5-Л=3(В=»(Л&Я));

Аб: A^(AvB); Al: S-^’JvBy,

А%: (Wr*Q»((S=.C)^(^v5)=»C)}; Л9;М=>В)=э((/1=>1 ВУй>Ъ);

A\(I:V.A^A.

Правилом вывода теприи h служитправило mvituiропепз (МР). Доказать длятеорииU, 'по:

1)формула А=>Аяыиетм теоргмой;

185

2) верна теорема дедукции: если Г - множество формул, А,В -

формулы иTjl Д то: Г

3)(/1=.5),(£=>0 [-(4=>0:

4)формула 2=>(Я=э(/!у8)) являете»теоремой;

'5) формула Si>((4&B)i>4) является теоремой;

6)формула .<{=■(]1 А-^А) является теоремой;

7)формула В=(ПЛ=?Л) являетсятеоремой.

7.Пусть формула А теории первою порядка является частым случаем тавтологии. Доказан., что А является теоремой в теории пер­ вогопорядка.

8.Доказать следующую теорему шукиии для теорий первою

поряди: если Г - множество формул, А,В- формулы и \ В и при этом существует такой вывод В И5 il'rH, в котором нн при каком применении правила обобщения х формулам, зависящим t этой выводе отА, не связывается кванторомникакая свободная переменная формулыА. Тогда: Г |-А=>8.

9. Пусть А, В - формулытеории первого порядка. Доказал., чго 6теории первого порядкаимеем: Vx]/)=>B [•

10, Пусть А - формула теории первого порядка. Доказать, что

втетрки первого порядка имеем: |“Vjr,Vxj^=*Vk2 .

Глава 5. Некласснческис логаки

§ 1. 'Греиначные логики

До сих пор риссматризялксь высказывания, которые могли иринимэть лишь два значения: И либо Л (1 либо 0). Однако оказыва­ ется, что некоторые явления требуют для моего описания угтотребле-

Напримср, гначсиисм высказывание можно считать одно из трех значений: истина, неопределенность (нейтрально) и .ихись, обо: значимые соответственно Я, Ян Л или 1, ’Л и 9. Такие высказывания будем обозначать черва х, у, г и т.д,, а также этики буквами с число­ выми индексами. Их значения в дальнейшей будем запиоыая] ь сим­ волами 1, 'А и 0 соответственно.

R двузначной легкие отрицание истины есть ложь, а отривание лжи ввалится как истина. Эти определения интуитивно очевидны и однозначны Для трехзначной логики уже на этапе определения этоицания интуитивно неясно, как, например, шести отрицание нйопредижнности. В настоящее время имеются разные варианты трехадачных логик. Рассмотрим некоторые трехзначные системы

Трехзначная яогит Яухассяииа. В качестве операций в трех­ значной логике Лукасевича введены отрицание Wi), конъюнкция (Кху\ днэъинкция (Аху), импликация (Сху). Эти операции определены следующим образом:

Л&=1-*, Kxy-minlr-, у),Аху~твх(х. у),

Ci>I=min(!|l-*+j')| т.».: Cxy^l, если x< у; Схуш\-х+у. если х>у. Дчя проведения сравнений различных логик будем исполмовэть обо-

ции—«х&.у», для дизъюнкции «*уу», для импликации -	я для
эквивалентности - <а=у». Согласно введенным сп
чим следующую таблицу истинности. В г-гой таСй

Рассыофим, например, выражение Ь'(х&у). Легко видеть, что

N(x&y)= 1- mill fij-)= miix(!-x.l-jO=№MW Аналогичным образом можно получить, что N(xvy)m(Nx)&{Ny).

Следовательно, в этой логике выполняются законы де Моргана. Имеются идругие сходства: двузначной логикой, но ei

188

например, не выполаяется загон исключенного третьего, т.е. X J(NX) не всегда истинно. Естьи другие различия.

Трехзяачная логика Гейтинга. В двузначной логике являются тавтологиями как х=»1]х, та* и Лх=м. И» предположения, что тавто­ логией можно считать только формулу x=sll х, Гейтинг разработал новуютрехзначную логику.

Операции ГейГЕНгавводятся согласно следующейтаблице:

Из таблицы видно, чтоконъюнкция ндизъюнкция огероделены слелушшим обритом:

*&>“ min(x. у), ^xy^roasfx, у),

а импликация по формуле: если»у, &эу=у, еслих>у.

В yioti логике, как и в догикс Лукасовича, если оставитьтолько значения 0 и 1 (исключить третье значение-значение -А),то получим обычную двузначнум логику.

Трехпшчные логики Рейхеибпха, Ьочбара и Клини. В настояшее врем* имеется много оариангов построения трехзначных логик. Наиболее известными являются петь трехзначных логих. К ним отно­ сятся указанные логики Лукяссвича и Гейтинга, а также трехзначные логики Рсйхенбаха, Бачваро н Клини Для сравнения этих логик по­ ложим, что истина, неопределенность в т м ь обозначены через ], 'А и 0 соответственно. Отметим, что их создатели обозначили ука­ занные значения по разному. Также единым образом обозначим опсрялин: конъюнкцию - &, дизъюнкцию - v, импликацию - =» к экви­ валентность - я. В каждой из .mix логик есть отрицание, такое, что

3t=l-jr (ранее о логиках Лукасевича и Рейтинга отрицания для -Собо­ значались через А'х). Значения для конъюнкция, дизъюнкция, импликации н эквивалентностивысказываний определяются по следующейтаблице [15]:

Из определений операций видно, что во всех этих пяти логиках значения операций совпадают с их значениями идя классиче­ ской двузначнойлогики, когда аргументых н у принимаю] значения из {0, li и различаются когда значение хотя бы одного ичаргументов I, у принимает значениеЛегко убедиться, что ни в одной из этах пята логик не выполняется закон противоречия, т.к. [х&X ) не всегда ложно, также не имеет места законисключенноготретьего, т.с. (xvX ) не всегда истинно.

Указанные логики вводились для различных целей. Например, Рейхенбах построил свою логику для описания явлений квантовой механики,' По его мнению, говорить об истинном или ложном выска­ зывании правомерно лишь тогда, когда возможно осуществив их проверку. Если нельзя пи подгвердтъ истинность виекязывакия, ии опровергнуть его с помощью лрокрки, то такое высказывание долж­ но оцениваться третьим значением - неопределенно. К числу таких высказываний относятся высказывай™ о ненаблюдаемых объектах