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

ф.ООпределение. Будем говорить, что формула Ф ИВ находится в со­вершенной к. н. ф.(д. н. ф.),если Ф= ~i(Ф=J)или выполненыследующие условия:1)2)Ф находится в к. н. ф. (д. н. ф.);любая пропозициональная переменная Р, входящая в формулу Ф,имеет в любом конъюнктивном (дизъюнктивном) члене Ф ровноодно вхождение;3)любые два различных вхождения конъюнктивных (дизъюнктив­ных)членовФимеютразличныемножествадизъюнктивных(конъюнктивных) членов.Например, из формулнаходящихся в д. н. ф., первая находится в совершенной к. н.

ф., а тре­тья-в совершенной д. н. ф.; первая и вторая формулы не находятсяв совершенной д. н. ф. (Почему?)Лемма1).1.5.11.ЕслиПусть Фнайдетсяв частности, секвенция2).формула ИВ.Ф,чтоЕсли К(Ф)1--тоЕсли D(Ф)Ф= ~i,= J, в част­~Ф доказуема.= {~J, Фо, ... , Фп}, то Ф = Ф,= {Фо, ... , Фп}-для которой выполнено К(Ф)4).Ф, ~Ф Е D(Ф),1-- Ф доказуема.Если найдется такая Ф, что Ф, ~Ф Е К(Ф), то Фности, секвенция3).-такая= {J, Фо, ... , Фп},которой выполнено D(Ф)то Ф= {Фо, ... , Фп}-где Ф= Ф, где Ф --формула,формула, для§ 1.5.37Нормальные формыДо к аз ат ель ст в о. Следует из основных эквивалентностей8)-13),теоремы о замене и следствийТеорема1.5.12.2), 3),О1.5.5, 1.5.7.Для любой формулы Ф ИВ существует экви­валентная ей формула Ф, находящаяся в совершенной к.

н. ф. Приэтом, если секвенция1-Ф не доказуема, то Ф не содержит логиче­J.ской константыДо к аз ат ель ст в о. Если секвенцияФ1-Ф доказуема, то выполнено= ~i, а формула ~i по определению находится в совершенной к.н.ф.В дальнейшем будем предполагать, что секвенцияв ИВ. Пусть Ф 1 -1-Ф не доказуемаформула, эквивалентная Ф и находящаяся в к. н. ф.Такая формула существует по теоремеЕсли конъюнктивный член01.5.9.формулы Ф 1 содержит среди своихдизъюнктивных членов формулы Р и ~р, то по леммеполучаем1.5.11,0= ~i.Так как секвенцияэквивалентности3)1- ~i1.5.11.1)мыдоказуема, то в силу леммыи недоказуемости секвенции1-Ф, можно потеореме о замене получить формулу Ф2, эквивалентную формуле Ф1,находящуюся в к. н.

ф. и у которой никакой конъюнктивный член несодержит среди своих дизъюнктивных членов Р и ~ Р ни для какойпропозициональной переменной Р. Из основных эквивалентностей вы­текает эквивалентность0= 0 v (Р /\ ~Р) = (0 v Р) /\ (0 v ~Р).Используя эти эквивалентности и теорему о замене, можно из формулыФ2 получить формулу Фз, эквивалентную формуле Ф2, находящуюсяв к.

н. ф. и у которой любой конъюнктивный член содержит все про­позициональные переменные, входящие в формулу Ф2. Если формулаФ з имеет два конъюнктивных члена с одинаковым множеством дизъ­юнктивных членов, то в силу основных эквивалентностей2), 3), 1)потеореме о замене из формулы Ф з получается формула Ф, эквивалентнаяформуле Фз и удовлетворяющая всем условиям определения совершен­ной к.н.ф.оДоказательство следующей теоремы аналогично предыдущему до­казательству с заменой/\на V, использованием леммыи того факта, что если секвенцияТеорема1.5.13.1-1.5.11~Ф доказуема в ИВ, то Фпп.2), 4)= J.Для любой формулы Ф существует формула Ф,эквивалентная Ф и находящаяся в совершенной д. н. ф. При этомесли секвенцияконстантыJ.1-~Ф не доказуема, то Ф не содержит логическойОГл.381.Исчисление высказыванийУпражнения1.2.Доказать предложение1.5.6, теорему 1.5.10 и теорему 1.5.13.1.5.9 и 1.5.10 можно потребовать, чтобыПоказать, что в теоремахФ и Ф содержали одни и те же переменные, если Ф содержитпеременные.3.Показать, что секвенция Г, Ф1-Ф тогда и только тогда доказуемав ИВ, когда для любого ХЕ D(Ф) секвенция Г,ХФ доказуема1-в ИВ.§ 1.6.ОпрСемантика исчисления высказыванийИсчисление называется непротиворечивым, если не все выраженияэтого исчисления доказуемы.Пусть Хнекоторое множество,-некоторое отображениеfx -пропозициональных переменных ИВ в множество Р(Х) всех подмно­жеств Х.

Такоеfxназовем интерпретацией ИВ в Х. Продолжимдо отображения формул ИВ в Р(Х) (обозначим его также черезfxf x)ПО индукции:= 0,!х(Ф л Ф) = fх(Ф)/х(Ф),3. fх(Ф V Ф) = fх(Ф) U /х(Ф),1. fx(J)n2.4. !хСФ)5.=Х\!х(Ф),= fхСФ) u /х(Ф).fх(Ф-+ Ф)Определим отношение «-+•> на множествах:X1, .. ,,Xn-+У ~(nXi~ У);i~nПри этом, если п= О,тоX1, .. ,,Xn-+ У=-+ У и П XiSИВ сопоставим утверждение= Х.Такимобразом,-+У~ У=Х.Каждой секвенцииfx(S)про под­множества Х следующим образом:/х(Ф1,Теорема... , Фn 1-1.6.1.Ф) ~ /х(Ф1),... , fx(Фn)-+Для любой интерпретациидоказуемой в ИВ секвенцииSутверждениеfxfx(S)fх(Ф).ИВ в Х и любойсправедливо.До к аз ат ель ст в о.

Индукция по числу переходов в доказатель­ствеDсеквенцииS.Очевидно, что еслиS -аксиома, тоно. Поэтому достаточно доказать, что если значениянад чертой дереваDсправедливы, то значениеfxfxfx(S)истин­от секвенцийот секвенции подтой же чертой также справедливо. Пусть, например,Ф1,.. ,,Фп,Фоl-Ф;Ф1,..

,,Фп,Ф1/-Ф;Ф1,,,,,Фпl-ФФ1,... ,Фпl-ФоVФ1§ 1. 6.Семантика исчисления высказываний39- переход в дереве D и утверждения fх(Ф1, ... , Фп, Фо 1- Ф), fх(Ф1, .... . . , Фп, Ф1 1- Ф), fх(Ф1, ... , Фп 1- Фо V Ф1) имеют место. Пусть х ЕЕ П fx(Фi). Так как П fx(Фi) ~ fх(Фо) U fх(Ф1), то х Е fx(Фj) дляi~ni~nнекоторогоj~1.Так как П fx(Фi) П fx(Фj) ~ fх(Ф), то х Е fх(Ф).i~nСледовательно, fх(Ф1,переходовD... , Фп 1-Ф) имеет место. Проверка для другихтакже проста и предоставляется читателю.Следствие1.6.2.ОИВ непротиворечиво.Доказательство.ПустьХ-непустоемножество,fx -некоторая интерпретация ИВ в Х. По определению интерпретацииfx(Qo А ~Qo) = fx(Qo) n (Х \ fx(Qo)) = 121.f x(I- Qo А ~Qo) ложно.

По теореме 1.6.1ниеОчевидно, что утвержде­секвенция1- Qoдоказуема. Следовательно, ИВ непротиворечиво.А~QoнеОМы рассмотрели интерпретацию ИВ, при которой пропозициональ­ныепеременныеинтерпретировалиськакподмножестванекоторогомножества Х, а логические связки как операции на этих подмноже­ствах. Это позволило доказать непротиворечивость ИВ. Представляетинтересисамапараллельностьи логических связоктеоретико-множественных операций1).Конечно, понятие интерпретации выходит за рамки самого исчис­ления.

Оно относится к так называемой семантике исчисления, в от­личие от понятий формулы, правил вывода, доказательства, которыеотносятся к синтаксису исчисления.Сейчас рассмотрим другую интерпретацию ИВ, которая очень тесносвязана с этим исчислением и которую будем называть главной интер­опрпретациейИВ. На множестве {О,1} определим операции А, V, --., ~при помощи следующей таблицы:~хухАуxVyх----, уоооо11оlо1ll1ооlоо11l1lохЭти функции будут значениями логических связок при главнойинтерпретации. Эта таблица соответствует правилам1)-4)определенияf {0 },символов О,слова <<Ложно,> и «истинно,>.

Тогда эта таблица укажет1)к1когда О= 121, 1 = {121}.интерпретацииИногда употребляют вместоПолезное обобщение этой интерпретации приведено в упражнении 2§2.2.401.Гл.правилаприписыванияИсчисление высказыванийзначений истинностидля/\, V, ---+, ~.связокдовольно хорошо согласующиеся с употреблением соответствующихсвязок в русском языке.В дальнейшем для формулы Ф запись Ф(Р1,... , Pk)будет обозна­чать саму эту формулу, а также тот факт, что все ее пропозициональ­ные переменные находятся среди Р1 , ••• ,записьS(P1, ... , Pk)Также для секвенцииPk.Sбудет обозначать саму эту секвенцию, а такжетот факт, что все ее пропозициональные переменные находятся средиP1, ... ,Pk.Значением логической константыJпри главной интерпретации бу­дет О.

Зафиксируем пропозициональные переменные Р1,задано отображениевыше таблице и значению логической константы функцияпродолжается намножество формулменные которых находятся среди Р1,(f(Ф)= О),Если... , Pk.f множества {P1, ... ,Pk} в {О, 1}, то по даннойИВ,однозначноЕсли при этом... , Pk.то будем говорить, что на наборе (!(Р1),ние истинности формулы Ф равноfпропозициональные пере­f (Ф) =... , f(Pk))1значе­(О) или просто, что Ф истин.на1(ложна) на этом наборе.Такимобразом,длялюбойформулыk-местную операцию на множестве {О,истинностиб Е {О,1}б1,...

, бkпеременныхистинностиформулыР1,Ф.Ф(Р1,... , Pk)мыимеем1}, которая заданным значениямсопоставляетзначениефункцию будемназывать... , PkЭтуистинностной функцией формулы Ф и обозначать через Ф[Р1,При этом мы говорим, что функция Ф[Р1,принимает значение б и пишем Ф[б1,Формулу Ф(Р1,... , Pk)... , Pk].... , Pk] на наборе (б1, ... , бk)... , бk]= б.назовем тождествен.но истин.ной (тож­дествен.но ложной), если функция Ф[Р1,... , Pk] принимает значениеистины (лжи) на всех наборах значений переменных Р1,что это понятие не зависит от выбора переменных Р1 , ••• ,...