1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (Ю.Л. Ершов, Е.А. Палютин - Математическая логика), страница 7

Он является символом языка, на котором мы доказы­ваем утверждения об исчислении. Иногда этот язык называют мета­языком. Понятия схемы и доказательства также являются понятиямиметаязыка.ЛеммаОтношение Ф1.4.2.= w является отношение эквива­w, Х ИВ справедливы следу­лентности, т. е. для любых формул Ф,ющие утверждения:а) Ф= Ф;б) если Фв) если Ф= w то w= Ф;= w и w = Х,то Ф= Х.До к аз ат ель ст в о.

а) следует из того, что Фwвб) следует из симметричности Ф иЕсли секвенции ФФ,w 1- Хи по предложениюлогично, если ХЛемw и w 1- Х1-ЛеммаФ11.3.3 б)секвенция ФАналогично___,Х доказуема. Ана­= W1 и Ф2 = W2, то Ф1 /\ Ф2 = W1Ф2 = w, ___, W2, 'Ф1 = ·w,.Dтогда и/\ W2,Ф1V Ф2=из1-w.доказуемости1-wи1-w 1-Фи ФФ1-w,то по допу­получаемдоказуе­Ф.1-Всилусимметричностизать секвенции ·Ф,Ф11-w.Доказательство.

а). Если доказуемыб).= w.___,стимому правилу б) получаеммостьаксиома.-w, w 1- Ф доказуемы, то Х 1- Ф доказуема.а). Если Ф = w, то Ф доказуема в ИВ1-1.4.3.б). Если Ф1Фдоказуемы, то доказуема секвенциятолько тогда, когда в ИВ доказуема= W1 V W2,1-определении отношения ФФ21-w, ___, W2.1-·w,,Ф1/\wiФiиФ21- W1 /\ W2,Ф1; 'Ф1 1- 'Ф1.W1,·Ф1I-J'1- ''111Ф1ЛФ21- Ф1; Ф1б),достаточноФ11- '111Ф1ЛФ21- Ф2; Ф2Ф1ЛФ2l-'111;1- '112Ф1ЛФ2l-'112)2---'---=----~~--~~'---~Ф1 Л Ф21- '111Л'112дока­V Ф2 1- W1 V W2,Это вытекает из следующих квазивыводов:l) '111 1-'Ф1в§ 1.4.3)Ф1Эквивалентность формул311- Ф1 V Ф2 Ф2 1- Ф1 V Ф2 Ф1VФ21- Ф1 V Ф2Ф1 V Ф2 1- Ф1 V Ф21- Ф1 -+ Ф2 Ф2 1- Ф21lt11- ~Ф2Ф2 -+ Ф24) - - ~ - ~ ~- -1-~-~Ф, -+ Ф2, 1lt 1 1- Ф2Ф1 -+ Ф2 1- 1lt 1 -+ Ф2.1lt 1 1-Ф1; Ф1 -+ Ф2Ф1 -+ Ф2,Теоремао(о замене).

Пусть Ф1.4.4формула ИВ,-\J! -ееподформула. Пусть Ф' получается из Ф путем замены некотороговхождения\J!на формулуТогда если\J!'.\J! =До к аз ат ель ст в о. Если= \J!',\J!то Ф= Ф'.Ф, то теорема тривиальна. Далееиндукцией по длине формулы Ф. Если ФИндукционный шаг распадается на= Qi,то\J! =-Ф.случая:4= Ф1 Л Ф2;Ф = Ф1 V Ф2;Ф = Ф1 -+ Ф2;Ф = ~Ф,.а) Фб)в)r)По предложению1.2.4любое вхождениев Ф 1 , либо в Ф2, поэтому эквивалентность Фонного предположения и леммыПредложение\J!и Х-1.4.51.4.3\J! #-= Ф'Ф содержится либоследует из индукци­б).О(основные эквивалентности ИВ). Пусть Ф,формулы ИВ, т Е {л, V}, А= V, V=л. Тогда имеют местоследующие эквивалентности:= ФтФ;2) Фт\J! = WтФ;3) (Фтw)тХ = Фт(wтХ);4) Фт(wтХ) = (Фтw)т(ФтХ);5) Ф-+ \J! = ~ф V \J!;6) ~~Ф = Ф;7) ~(Фт\J!) = ~ФГw;1)= J;9) ~J Л Ф = Ф;10) ~iv Ф = ~J;11) JV Ф = Ф;12) Ф л ~ф = J;13) Ф V ~ф = ~J;Ф8) J л Ф14)если Ф не содержит пропозицио­нальных переменных, то Фили ф= ~i.До к аз ат ель ст в о.

Эквивалентностилентностейне8)-11), 5)загромождатьности4)при ти6)изложение,=л и14)=Jполучаются из эквива­индукцией по длине формулы Ф. Чтобыприведем5), 9).квазивыводыдляэквивалент­Остальные эквивалентности читательлегко докажет сам, используя навык, приобретенный при разборе ранееприведенных доказательств.32Гл.1.Исчисление высказыванийВ следующих двух деревьях через А будет обозначаеться формула(Ф/\Ф)V(Ф/\Х):Ф А(w v w) 1-- Ф; w 1-- wФФА (w v w). w 1-- ФА wФ /\ (w V Х), w 1-- А;Ф/\ (w V Х) 1-- Ф; Х 1-- Х/\ (w V Х), Х 1-- Ф /\ Хф /\ (w V Х), х 1-- А;Ф /\ (w V Х) 1-- Аф/\ (w V Х) 1-- w V хФАХI--ХФ/\ W 1-- W V Х; Ф /\ W 1-Ф /\ W 1-- Ф /\ (w V Х);ФФХ/\1--Ф;ФХ/\1-- W V ХФАХI--ФА(ФVХ);AI--AА 1-- Ф /\ (w VX)Ф1--Ф; Ф--+ w 1-- Ф --+ ww, ф 1-- wW, Ф 1-- 'Ф V W;1-- 'ф1-- 'Ф V W;Ф--+ Ф 1-- 'ф V Wф--+Ф--+Ф,·w 1--·w 1-·w 1--J'ф 1-- w;Ф; 'Ф,'ф'Ф1--ФV'Ф'фФ, ·Ф,Ф,w 1-- w;'фV w 1--'фVw·Фvw,Фl--w'фV W 1--Ф--+'J /\ ф 1-- 'J /\ ф'J /\ ф 1-- ф.Заметим, что доказуемость1-W1-- ·J; ФI--Ф1-- 'J /\ ф.фФ V ·ф следует из примератеоремы о подстановке.

Секвенция1-·J1.3.4J 1-получается из аксиомыпо допустимому правилу г).иJОУпражненияl.Доказать допустимость оставшихся правил из предложения2.Пусть формулы Ф и Ф ИВ содержат лишь одну пропозициональ­ную переменную Р, и для некоторых подстановокs,3.(Ф)=ФПусть Фи s2(Ф)= Ф.=Ф. Показать, что Ф=s,, s21.4.5.имеемФ.Показать, что существует формула Х, эквивалент­ная формулам Ф и Ф, все пропозициональные переменные которойсодержатся как в Ф, так и в Ф. (Указание.теоремойВоспользоваться1.4 .1.)§ 1.5.Нормальные формыПонятие эквивалентности формул ИВ будет иметь для нас боль­шое значение, так как основные изучаемые нами свойстваформулИВ сохраняются при переходе к эквивалентным формулам.

Поэтому§ 1.5.Нормальные формы33очень важно уметь находить для каждой формулы ИВ эквивалентнуюей формулу, но устроенную по возможности более просто. В этомпараграфе будут определены такие <<канонические,> представители дляформул ИВ.Лемма1.5.1.Любая формула Ф исчисления высказываний экви­валентна формуле Ф, которая не содержит символа импликации.До к аз ат ел ь ст в о индукцей по числу импликаций в формуле Ф.База индукции тривиальна.Так как по определению формулы ИВлюбое вхождение импликации в формулу Ф содержится в подформулеформулы Ф вида Ф1 ----> Ф2, то индукционный шаг вытекает из теоремыо подстановке и эквивалентностиЛемма1.5.2.предложения5)О1.4.5Любая формула Ф ИВ эквивалентна формуле Ф безсимвола импликации, у которой символы отрицания стоят толькоперед атомарными подформулами.До к аз ат ель ст в о. Пусть р->-множество формул, не содержа­щих символа импликации.

Определим отображение/3 : F-,----> р- поиндукции:= Qi,= ~Qi,/З(Ф /\ Ф) = /З(Ф) А/З(Ф),/З(Ф V Ф) = /З(Ф) V /З(Ф),/ЗС(Ф /\ Ф)) = /ЗСФ) v /З(~Ф),/ЗС(Ф V Ф)) = /ЗСФ) /\ /ЗСФ),/ЗС~Ф) = /З(Ф).1) /З(Qi)2) /ЗCQi)3)4)5)6)7)По леммесуществует формула Х1.5.1импликации. Эквивалентность Х= /З(Х)= Ф,где Х не содержитлегко получить индукцией подлине Х, используя основные эквивалентности ИВ. Очевидно, что Ф= /З(Х) удовлетворяет требованиям данной леммы.Опр Определим теперь важные понятия дизъюнктивноготивного члена формулы.

Для любой формулы Ф через=Ои конъюнк­D( Ф)будемобозначать множество всех дизъюнктивных членов формулы Ф, а черезК(Ф)-множество всех ее конъюнктивных членов, которые определиминдукцией по длине Ф:а). Если формула Ф не представима в виде дизъюнкции, т. е. в видеФ=(ФоV Ф1),то D(Ф)={Ф}, т.е. Ф является своим единствен­ным дизъюнктивным членом.б). Если Ф=(ФоV Ф1),то D(Ф)= D(Фо) U D(Ф1).Множество К ( Ф) определяется двойственно:а).

Если формула Ф не имеет вида Фоб). Если Ф2=(Фо/\Ф1), то К(Ф)Ю. Л. Ершов, Е. А. Палютин/\Ф1, то К(Ф)= К(Фо) u К(Ф1).={Ф}.Гл.34ЗамечаниеИсчисление высказываний1.Из1.5.3.предыдущихопределенийиндукциейподлине Ф получаем, что если Ф Е D(Ф) (Ф Е К(Ф)), то D(Ф) ~ D(Ф)(К(Ф) ~ К(Ф)).Предложение1.5.4.~ D(Ф) то секвенция ФПусть Фи Ф -1-формулы ИВ. Если D(Ф) ~Ф доказуема в ИВ.До к аз ат ель ст в о.

Установим, что из Ф Е D(Ф) следует доказуе­мость секвенции ФФ. Докажем это индукцией по длине формулы Ф1-при фиксированной формуле Ф.Ф=ЕслиФатомарная формула, то-Ф и доказывать нечего. В случае, когда Ф не представима в видедизъюнкции, также имеем Ф= Ф.= Ф' V Ф".Пусть ФТогда Ф Е D(Ф')или Ф Е D(Ф"). Если, скажем, Ф Е D(Ф'), то по индукционному пред­положениюФФ-квазивывод секвенции Ф1-Ф'1-Ф' V Ф"1-Ф.Установим теперь предложение индукцией по длине Ф при фиксиро­ванном Ф. Если D(Ф)казуемость Ф= {Ф}, то Ф Е D(Ф)Ф.

Если Ф1-= Ф' V Ф",и выше уже установлена до­то D(Ф') U D(Ф")и по индукционному предложению секвенции Ф'1-= D(Ф)Ф и Ф"1-~ D(Ф)Ф доказу­емы. ТогдаФ'-1-Ф; Ф"1-Ф; Фф1-1-Ф' V Ф"фквазивывод нужной секвенции.Следствие1.5.5.ПолученноеЕсли D(Ф)следствие=оD(Ф), то Фпоказывает,чтос= Ф.точностьюодоэкви­пвалентностиформул можно пользоватьсяФ1 V ... V Фп для формул Ф таких, что D(Ф)обозначением= {Ф1, ...

, Фп},V Фiилиi=lДля конъюнктивных членов ситуация вполне аналогичная. Остав­ляем читателю доказательство следующего предложения.Предложение1.5.6.Пусть Фи Ф~ К (Ф), то доказуема секвенция ФСледствие1.5.7.Если К(Ф)1--формулы ИВ. Если К(Ф) ~Ф.= К(Ф),Ото Ф= Ф.опЭто позволяет использовать обобщенную запись видаФ1 А...А Фп для формул Ф таких, что К(Ф)Лемма1.5.8.Секвенция Гкогда доказуемы секвенции Г= {Ф1, ... , Фп},/\ Фi илиi=l1- Ф доказуема тогда и только1- Ф' для всех Ф' Е К(Ф).тогда,§ 1.5.

Нормальные формы35До к аз ат ель ст в о. В одну сторону лемма вытекает из предложе­нияГ1.5.6и замечания1.5.3.Пусть для любого Ф' Е К(Ф) секвенцияФ' доказуема. Индукцией по длине Ф покажем, что Г1-ма. Если Ф не представима в виде ФоФ=Фо/\Ф1, то по индукционному предположению Гдоказуемы (так как К(Фi)1-Ф доказуе­Ф1, то доказывать нечего. Если/\1-Фо и Г1-Ф1<;;; К(Ф)). Следовательно,Г1Гесть квазивывод секвенции Г1-Фо; Г1-1-Ф1Фо Л Ф1Ф.DОпределение. Вудем говорить, что формула Фэлементарная-дизъюнкция, если каждый дизъюнктивный член Ф есть либо пропо­зициональная переменная, либо отрицание пропозициональной пере­менной.

Будем говорить, что формула Ф находится в конъюнктивнойнормальной форме (к. н. ф.), если каждый конъюнктивный член Ф яв­ляется элементарной дизъюнкцией. Формулу Ф, находящуюся в конъ­юнктивной нормальной форме, с точностью до эквивалентности можноnзаписать в виде-Л (ФЬ V ... V Ф~J, где Ф;атомарные формулыi=Oили отрицания атомарных формул, а Ф~ V ... V Ф~. -обобщенныеобозначения для конъюнктивных членов формулы Ф.Двойственным образом (т. е. заменой/\ наV и V на Л) определяют­ся понятия элементарной конъюнкции и дизъюнктивной нормальнойформы (д. н. ф.).Теорема1.5.9.Для любой формулы Ф ИВ существует эквива­лентная ей формула \[f, находящаяся в к.

н. ф.Доказательство. Пусть ii,, -формула, эквивалентная Ф, несодержащая символа импликации и все символы отрицания которойстоят перед атомарнымиподформулами. Заменивственно на эквивалентные формулы Р 1\ ~р и РJи~Jсоответ­V ~р для некоторойпропозициональной переменной Р, можно считать, что \[т I не содер­жит логическую константу. Будем доказывать теорему индукцией подлине \[т 1.

Если \[т 1 -ние, то\[11пропозициональная переменная или ее отрица­уже находится в к.н.ф. Если\[11=Ф1/\Ф2 и Х1,Х2-формулы, эквивалентные Ф1, соответственно Ф2, находящиеся в к. н. ф.,то по теореме о замене формула Х,/\Х2 эквивалентна \[т I и находитсяв к.н. ф.Пусть ii,,= Ф1 V Ф2.По индукционному предположению существу­= Ф1 и Х2 = Ф2. По= Х1 V Х2. Доказательство того, что Х1 V Х2 экви­ют формулы Х1 и Х2, находящиеся в к. н. ф., Х1теореме о замене \[т 1валентна некоторой \[т, находящейся в к. н.

ф., будем вести индукцией2•Гл.361.Исчисление высказываний= т1 + т2, где mi - число символов Л в Xi, i = 1, 2. Если= т2 = О, то Х1 V Х2, будучи элементарной дизъюнкцией, находит­по пт1ся в к. н. ф. Пусть, например, m2 не равно нулю. Тогда Х2По основной эквивалентности4)= Хз Л Х4.получаемПо индукционному предположению Х1V Хзи Х1V Х4эквивалент­ны Ф2 и соответственно Фз, которые находятся в к. н. ф. Ясно, чтоФ=Ф2 л Фз удовлетворяет требованиям теоремы.ОДоказательство следующей теоремы по существу повторяет доказа­тельство теоремыТеорема1.5.91.5.10.с перестановкой ЛиV.Для любой формулы Ф ИВ существует эквива-лентная ей формула Ф, находящаяся в д. н.