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

2)*4=?((.4=>Л)=>.4) является аксиомой, которая получается по схомс ЛI, ссли положить В~А=>А\

3)(.4=>(.4=*.4))=»(,to.4) явлгется непосредствен*™ следстаим из 1) и 2) по МР;

4)А^>1А^А) является аксиомой, полученной по схеме А\ при

В=А\

5)А=>А явтветса непосредственный следствием и» 3) и 4) по

МГ.

Таким образом, получили последовательное формул 1)--5),

да некоторых предыдущих формул 1)-4) по правилу М.Р, причем лоелвцки формула ость A=jA. Следовательно, формулы 1>-5> есть вывод формульЫ=>Л, которая и»в?_яется теоремойв L

	Теорема 4.1 (теорема дедукции). Вели Г - княжество формул,
А,3 -	формулы и ГА |* В, то Г (• А=>В. В частности, еепн А В,
то [А=>8
!	Доказательство, Пусть Я|,&,...Д. есть выгод формулы В из
	гме В,=8. НндухциеЯ no i(l S ; £«) докажем, что 1' \-А=уВ,.

Пусть 1=1. Покажем, что Г [■Л=>Я, Та» как В, является первой из формул в выводе В ш Г и {Aj, то имеем следующие впзиожноети:

В, еГ.

В,“А.

По схеме аксиомЛ1 формула #i=>(<4=? Si) ель аксиома Поэто­ му в первых авух случаях (когдаД аксиома или формула изГ) по МР получим

Г

Втретьем случае, т е. когда В\ совпадает с А (В'=Л), по лемме

4.1имеем

[А;>Ви

следовательно, Г \-AzsB,. Тем самым случай 1=1 исчерпан.

151

Допустим телерц'что Г \- А^>В, для любого к<1 Дне Д и четыре возможности:

В, - следствие по МР из некоторых 5, и Вт т е j<t, т<1 и В„ рмаетБИДЙ,=>Л,.

В первых треп мучих то, что Г j- A=>Б, доказывается также, как дли <“ 1. В последнем tnvqae применим индуктивное предположе­ ние, согласно которому

1)Г \-A=>Sj,

2) г [ Аы.в,=*в).

По схеме аксиомА2:

У) У(_А=ХЙ;=>В^1А=,В^(А^)-,

далее, применяя праеило UP, из 3) и2) получим: 4) r\(A*Bjy=*A=>S)i

сном по МР из 4) и 1) имеем:

Г 1-А=.ВГ

Таким образом, доказательство по индукции завершено и дня !~и получим требуемоеутверждение. Теорема доказан!.

Следстш4.1.А=>В,В=>с\А=£. I

Доказательство.

1)А ^В -гипотеза,

2)Я=>С-гипотеза,

4) В - поМР из 1) и3), 5)С - пом? из2) и4).

Таким образом, АтьВ. В»С, А [• С Отсюда по теореме дедук­ ции A=)B.B=iC \-А^>С. Что итрббоврлосьдоказать.

152

Отметим, что ко докодпиому следствию имеем;

й=>е,в=>с J-lfec.

Исключив импликацию, получим: AvB, I®'-'1 МуС,

дизъюнктов етеорииL

|

Следствие 4.2. А^(В=>С),В |-/toC.

|

Докаигельегво.

1)A=>(B^tC] - гипотеза,

3)3=С-поМ Рш1)и2),

4)8 -гипотеза, 5)С~поМРю 3)и4).

Таким образом, A=s(B=$C),B^i [■С, тогда по теореме дедукции

А=>{В=ьС),В [-А=>С Что и требовалосьдоказать.

Л е м м а 4.2. Для любых формул А,В следующие формулы I

являются тгоремами в L:	I
а)ТЬ=Д;	б)В=>Т1В:
»)1л=»(.4=»Я);	r)(lft*1.4)»(.4=>fl);
д) (.4=.2))=.(1В=^Л)\	е)А=>(:Й=>1(А^Щ);
ж)(Л;=?В)=>((1л=>£)=?5).

Доказательство. а) [-Т1 В=>В:

1)(-1 Ё з 1! 3)=5((1Д=>18)=5) - является иксиомой, полученной по схемеЛЗ при,4=1В.

2)13=>1В имметея теоремой в силулеммы4.1, го. эта формула выводима к прижелании можно выписать весь вывидэгой формулы,

3) (15=.П6)=5 -40 следствию U из 1)и 2),

!53

4) "Г! BzsO ¢=11 В) - «мястся аксиомой, полученной но схеме А]. когда вместо ,4 иВ взятыформулы ;S н 1S соответственно,

5) Т] 3=>S- последствию4.) из4) и3). Угиарадениеа)доказано;

5)|-В=>ПВ;

1)(111 В=>1В)=>((ТЛв=>В)=.Т1аявляется аксиомой, получюкоП аоЛЬ, когдашестой я В взятыформулыВ к 71Всоответственно,

2)ТЛ.В=>1В-теоремасогласно а.),

3)(111 В=.Й)=.Ц8-г.оМ Р ю I) и2),

4)В=>(1Т В=>В) - аксиома, пшучекна* по схеме Л\, ког вместоЛ и В взяты форчулыВ и"Пв соответственно,

5)Sr»Tl£ - согласно следствию 4.1 из4)иЗ).

Утверждение б)доказано;

1)1.4 -гипотеза,

3)А=>(1В=>А)- схемааксиомА1,

4)1Л=>(1C=vn А)-схема аксиомА\,

5)1 Вп>А- no МР из2) и 3),

6)]В=>1л - по МР из 1)и2),

7)(19^1 ,4)=.((1 В=>А)=.а)~«ема аксиомА \

8)(13=>A)=>B - па!А1' ка 6) и 7),

9 )В - по МР из 5) и 8).

ИтаК; в силу 1) - 9)1 А, А В. Тогца по теореме дедукции ЛА \-A—jB и. стовапотой же творемв, далучку что [• A ^fA sB y

Доказательство пп. г)-ж) оставляем читателю в качестве нетривиальны): упражнений.

§ 9. Два определения пепритнворечивостн

Напомним, что дедуктивная теория называется противоречивой.

15+

Ф(T-if’l, и непротиворечивой в противном случае ((Гс Ф) & (Т*Ф)). Будем считать это первым определением (не) противоречивости.

Второе опрмеленис (не) противоречивости. Дедукпшиштеория inumaetci противоречивой, если существует формула А такпя, что в этой -теории выводимо А и выводимо i А; если такой формулы не существует, то теория называется непротиворечивой.

I Теорема 4.2. Л;is теорий, содержащих исчисление высказывгВнгзй, приведенные определения (кс) противоречивости эхеива-тентны.

Доказательство. Покажем, что из второго определенна следует

к

(4-5)

f\A. (4.б>

\-У=>(А=>В). (4.7)

И5(4.6) и (4.7) no AJ? получаем

|-А=рВ,

(4 8)

а из (4.8) и (4.5) снова по МР Hweov: |- В. Пос.хлнее к озндчлет, что доказуема любая формула В, т.е. множество теоргм совпадает с иножество формул.

Если примем первое определение, то в противоречивой теории доказуема любая формула, т. е. для любой формулыА получим, чтоА и 1А являются теоремами, следовательно, теория противоречива

§10. Производные (доказуемые) правила вывода

висчислении высказываний

Висчислении высказываний (теории L) имеется только одно ис­

ходное правило вывода: modus ропепз (МР). При этом доказала тео­ рема дедукции: если G, А |-£, то G \-Аг>В. Последиге представляет тоже некоторое правило вывода, но уже производное (доказуемое) правило, nonywaroiuteca, если принять правило МР. Кроме этого про­ изводного правил» вывода, оказывается, есть и другие. Рассмотрим некоторые из них.

Пусть О- произвольное множество формул из L;A,B,C - произ­ вольные формулы из 1. Имеют ме:то следующие производные прави­ ла твода.

1.Пратйо перевертывания(контрвпозиции):

ОСЯuG J )-Я, то G?.B |- U

1)|-S -n o условию;

2)С	пптеоремвдблукции;
3)(.44,5)=5(1^ ^ ) -теорема согласи п. а) леммы 4.2;
4)(Л»Я)	|- (1я-э1л)- из 3)по |МР;
5)G	h1йгл 1 ^ - из 2) ч 4) по тоггьему свойству выводимости
(см. § 6);
6)G,lB.|-"ls-по определению вывода;
7)С,1В	|-1в=>Ъ-ш5Х
8)1В»1.4,]В f^ -n o K P ;
9)	G,ЛВ [-1.^ - из 7)»8)потрепйму свойству выводимо
Что итребовалось доказать.
2. Правшаудаления& А&В\-А.

Докюательство.

1)Л,В|* А - по опрЕлепению вывода,

2)	A, ..41-1ft -га 1)поправилу перевертывания,
1563)	1А [■Л»1 В-no теореыгдедукции,

4)1(4¾ ;В) (-Tlii - из 3) - по правилу псровсртшания;

5)TU г-5/4 - теорема согласно п. а) леммы4 2;

<5)ТиН-1135) по МР-

7>1<Яа1Л) [-Л -ю 4 )а6 ) пс третьему гвэйству высолимоем. Получили А&В \ Л, что итребовалось

3. Правило введения 8с:А,В |- А&В

1)JM = S1B |-1 В - по МР;

2)Л,Т1я|-1(.4=Л.З)- из 1)-по правилу пгреьертывания;

3)А,в\-	А - гто определению вывода;
4)А=*ПЯ-	теорила согласии п. б)леммы 4.2;

5)Sj-Tl5-m 4) no МР;

6)Л,.?|-71в-иэ 5); Т)А,В )- 1 (Л=>1 #) —из б) к 2) по третьему свойстъ> выводимо­

сти. В результате получили А, В А&В, что и требовалось. Аналогич­ но доказывается, что А. В |-В&Л.

Также можно доказать следующие правила.

4.Правила введения v :

лу л * в .

B[AvB.

5. Правило доказательстваразборомслучаев если А [ С к В [ С, то Лу Вf С.

’К » » л у в , л у 1 в . ъ ^ л .

Иногда правило выяпда modus ponens мтисымют следующим

образом:

А,Л=>В

И^

157

• тоорвмадедукики:	QA |-BG	=ь;
	A ~ S	у
• гтрааилопсревортываниа; GA \-В'’Ъ.1й 1;
^	А&В „	A&S	с
• правилоу/шлення в : ------- &;		— —	S
• правило введения &:			S
	А	А	v
» правила введения v: --—— v,		- —-•

■ правило доказательства разбором случаев:

• правило сведения к нелепости: А |- Я. A |-1fl 1 . 1.4

Отметим, что перечисленные протомимте правила выводи позволяют намного упростить выкладки в теории I Подчеркнем, что я принципе можно и не пользоваться этими производными правилами выводя, а пользоваться только правиломМ?. Однако при этом, может был, придется провонять более громоздкие выкладки. Например, ес­ ли при выяснении, теюрема или нет формула А, пользовались теоре­ мой дедукции, то при отказе от мой теоремы дедукции фшичсскн придется ее докалыватьдля этвго частного случая, Вдругих подобных случаях снова придетсяи доказывать.

§ II. Свойства исчислении высказываний

высказываний, как н любую формальную идиоматическую теорию, содержащую символ 1, будем считать непротиворечивой, если Яи Для

158

кгхоЯ формулы А не имеет места |-А и )-1А, те. неможет бил, что­ бы одяорременно были пыаддимыА и i А. Длз доказательстванепро­ тиворечивости исчисления высказываний (теории L] предварительно докажемтеорему.

Теорема 4.3. Всякая геореыатеории 1-естьтавтология.

Доказательство. Легко убедиться, например, с помощью таб­ лиц истинности, что каждая аксиома теории L есть тавтология. Из­ вестно, что если А п Ат^В тавтолопш, то и5 тааттжогия (см, теорему 1.1),т.е. правило modus ропет, примененное ктавтологиям, приводит к тавтолэгни. Й так кал всякуютеорему можно доказать применением ТОЛЬКО правша modus ропет к аксиоиач, го георема есть тавтология. Что и требовалось доказать.

4.4 Исчисление высхазывалий непротиворечиво, т.е, ;твует формулыЛ такой, чтобыА н~\А бьиш сетеоремами.

Доюзагелмгво. Согласно тоако что доказанной теореме 4.3, нуикдая тгоргуа теории Lлаляетсл тавтологией. СЬрииание тавтологии не являете* тавтологией. Следоаятельно, ни для какой формулы А невозможно, чтобы А и А былитеореками исчисления высказываний Заметим, что все остальные свойства теории I рассматриваем

после выяснения ее непротиворечивости.

Полное w'числен'м бысклямйнкий. При описании формальиьл аксиоматических систем отмечалось, что свойь-тво полноты характе­ ризует достаточноссъ теорем ?т^;й теории для некоторых целей. Ис­ числение высказываний будем считатьпо/мыл«широком смысле, к- л,1 в ней доказуема каждая формула, являющаяся ■тавтологией. Иначе можно сказать, что исчисление высказываний называется полной в широком смысле теорией, если множество теорем покрывает мно­ жество форму;:, являющихся тавтологиями.

Вводят, icpoue того, понятие полнота в узком смысле. Исчисле­ ние высказываний называемся полный аркой смысле, если присоеди­ нение к ее аксиомам какой-нибудь, не выводимой а ней формулы, приводит к противоречивойтеории. Полнотав ужом смысле означает, чтоаксиомытеории ужо нельзя пополнитьнезависимой аксиомой гак, чтобы получить непротиворечивую теорию. Иначе иодано сказать, что множество теорем Ттакой теории еще не покрывает всего множества формул Ф (теория непротиворечива), яо всякие попытки расширить множество Т приводят к тому, что Т покрывает все Ф, т.е. теория ста­ новится противоречивой.

Покажем, иго исчисление висказиианий полно в широком смысле. Докажем сначала вспомогательную лемму.

JI s м м а 4.3. Пусть А есть формула, n 6,,¾.....¾ - пропози­ циональные буквы, вхоеяшне в А, и пусть задано некоторое распреде­ ление истинностных значений для В1.Д1 .,¾. Пустьтогда В', ость В,, чели Э, принимает значениеИ, и 1в„ млн В, принимает значение Л, и пусть, наконец, А' есть А, если при этом распределении А при-

Дикязательство. Будем считать, что формула А записана без сокращений, т.е. без использования символов &, v, =. Доказательство проведем индукцией по числу (и) вхождений вА примитивных связок

вели и—0, то А представляет собой просто пропозициональную букву В\ и утверждение леммы сводится к очевидным угвчряданиим'

Допустимтеперь, чтолемма верна прилюбом/<4.

Случай 1 .А имеет видотрицания 1В. Число вхождений прими­ тивных связок вВ, очевидно, меньше п.

160