Игошин Математическая логика и теория алгоритмов (1019110), страница 33
Текст из файла (страница 33)
Оказывается, формализованное исчисление высказываний построено так, что всякая его теорема является тавтологией (тождественно истинной формулой) алгебры высказываний, и, обратно, для всякой тавтологии алгебры высказываний можно построить ее вывод из аксиом формализованного исчисления высказываний, т.е. доказать, что она является теоремой исчисления. В этом состоит теорема полноты. Таким образом, теорема полноты как бы свяжет абстрактную аксиоматическую теорию высказываний и содержательную алгебру высказываний, теорию с практикой, и тем самым продемонстрирует адекватность отражения абстрактной теорией наших практических знаний о высказываниях языка.
Сформулируем и докажем первую часть теоремы полноты. Теорема 16.1. Всякая доказуемая в формализованном исчислении высказываний формула является тождественно истинной формулой (или тавтологией) алгебры высказываний. Символически: ь- Г=~ ~ Г. Доказательство. Пустьформула Гдоказуемавформализованном исчислении высказываний и последовательность Вп Вь ..., В, представляет собой вывод формулы Риз аксиом. Покажем, что Г— тавтология.
Доказательство будем вести индукцией по длине з вывода этой формулы: 1) з = 1. Тогда последовательность-вывод состоит из единственной формулы В„которая, следовательно, может быть на основании определения вывода только аксиомой. Все три аксиомы (А1), 134 (А2) и (АЗ) являются тавтологиями алгебры высказываний на основании теорем 3.1, з, 3.3, а, 3.3, л соответственно; 2) в < и.
Предположим теперь, что все формулы, имеющие вывод длины з < и, являются тавтологиями. Это предположение индукции; 3) в = и+ 1. Покажем, что всякая формула, имеющая вывод длины з = и+ 1, также является тавтологией. В самом деле, пусть Г— произвольная формула и Вь В,, ..., В„, В„,, и à — ее вывод длины и+ 1.
На основании предположения индукции первые и членов данной последовательности — тавтологии. Рассмотрим формулу В„„. По определению вывода, она может быть либо аксиомой (и тогда она является тавтологией, как было отмечено в первой части доказательства), либо получена из двух предыдуших членов этой последовательности В, и В~ (1 < 1 < и — 1, 2 <1 < и) по правилу МР. Во втором случае тогда В; и В; -з В„,, и, кроме того, обе формулы В; и В являются тавтологиями на основании предположения индукции.
Итак, ~ В, и - В, — з В„„. Следовательно, по теореме 3.5 (правило заключения) ~ В„,, Итак, какой бы длины ни имела вывод в формализованном исчислении высказываний формула, она будет тавтологией алгебры высказываний. П Для доказательства второй части теоремы полноты (т. е. теоремы, обратной к только что доказанной теореме) понадобится одна лемма, которой и посвящается следующий пункт. Лемма о выводимости.
Пусть о = (оь о,, ..., о„) — упорядоченный набор длины и, составленный из нулей и единиц, т.е. каждое о; = 0 или 1 (1= 1, 2, ..., и). Из доказательства теоремы 10.3 известно, что всего таких наборов имеется 2" штук. Оиределеиие 1б.2. о-Двойником, где о = (оь оз, ..., о„), для формулы Г(Хн Хз, ..., Х„) называется или сама эта формула, если она превращается в истинное высказывание г(Ап Аз, ..., А„) при подстановке вместо ее пропозициональных переменных Х„ Хз, ..., Х„таких высказываний А„А„..., А„соответственно, что ).(А~) = оь ЦАз) = оз, ..., ЦА„) = о„, или формула — Г(Хн Хз, ..., Х), если при указанной подстановке она превращается в ложное высказывание р(Аь А„..., А„).
Обозначение о-двойника для формулы Г(Хн Х„..., Х„) следующее: Г"(Хп Хз, ..., Х„). Тогда символически данное определение можно записать так: (Г(ХпХз,...,Х„), если Г(опоз,...,о„) = 1, Г(ХпХз,...,Х„), если Г(опо„...,о„) =О. Пример 1б.З. Найти о -двойники для формул Р(Хп Хь Хз, Хв) ю (Хз -+ Хз) ч (Хз л (" Хз < з Х4)), 0(Х~ Хз Хз Х4) и (Хз ч ~Хз) + > (Хз л ( Хз + Х4)) если о = (О, 1, 1, 0). 135 Находим сначала значения этих формул при подстановке вместо переменных Х,, Хн Х,, Х4 значений О, 1, 1, 0 соответственно: Г(0, 1, 1, 0) = (О -+ -1) ч (1 л ( 0 +-~ 0)) = (О -+ 0) г ч (1 л (1 +-э 0)) = 1 ч (1 л 0) = 1 г 0 = 1; 6(0, 1, 1, 0) = (О ~ — 1) <-+ (1 л (.
1 -+ — 0)) = (О г 0) +.+ +.+ (! л (О -+ 1)) = 0 +~ (1 л 1) = О +з 1 = О. Тогда, по определению о'-двойника, имеем Г'(Хн Хь ..., Х„) ~ (Х, ъ -~Хз) +-э (Хз л ( — ~Хз -+ -~Х4)), '6 '(Хь Х2, ..., Хп) гя — ~((Л1 ъ' -чХз) <-~ (Х2 л (-~Хз -~ -~14))). Лемма 16А(о выводимости). Дяя всякой формулы Г(Хь Хь ..., Х„) и всякого набора и = (оь он ..., о„), где о; = 0 ияи 1 (1 = 1, 2, ..., и), снраведлива следующая выводимосты ХР, Хз, ..., Х„-.
Р (Хн Х,, ...,Х„), где Х „еслио; =1, -Х;, еслио; = О. Доказательство. Для доказательства применим индукцию по числу 1 логических связок, использованных при построении формулы Г: ! ) 1 = 0 (в формуле Гнет логических связок). В атом случае формула Гесть пропозициональная переменная, например Хь Тогда Г' = Х,, и утверждение леммы принимает следующую очевидную форму: Х, ~ — Х,; 2) 1 < 1с. Предположим, что утверждение леммы справедливо для всех формул с числом логических связок 1 < 1с; 3) 1 = к+ 1. Покажем тогда, что утверждение леммы будет справедливо и для любой формулы с числом логических связок 1= к+ 1. Пусть Г(Хь Х„..., Х„) — произвольная такая формула. Тогда на основании определения формулы формализованного исчисления высказываний (см.
первый пункт В 15) Г имеет один из следующих двух видов: Ги 6 или Гм 6 — ~ Н. Рассмотрим последовательно зти две возможности. Пусть сначала Г=- 6. Тогда формула 6(Хп Х,, ..., Х„) содержит < 1с логических связок, и лля нее, по предположению индукции, будет справедлива выводимость ХР, ХР, ..., ХЫ- 6.(Х, Хм ..., Х„).
Покажем, что 6 ь- г"', т.е. 6 ь- ( 6)'. В самом деле, если набор о = (о,, ог, ..., о„) таков, что 6(он он ..., о„) = О, то — 6(оь он ..., о„) = 1. Далее, по определению !6.2 о-двойника 136 имеем 6'= 6и ( 6)'=~6. В этом случае требуемая выводимость принимает следующую очевидную форму: 6» —,6. Если же набор о = (ап оь ..., о„) таков, что 6(оп оп ..., о„) = 1, то 6(оп аз, ..., о„) = О и соответствующие а-двойники таковы: 6~ = 6 и ( 6)' = 6.
В этом случае требуемая выводимость принимает форму 6» 6. Данная выводимость действительно справедлива на основании теоремы 15.8, б и следствия 15.5 из теоремы о дедукции. Итак, Х, Х~~', ..., Х„'" » 6 (Хп Хп ..., Х„) и 6" » Г'. Тогда, в силу теоремы 15.3, в, Х, Х", ..., Х„" » Г" (Х„Хн ..., Х„). Рассмотрим теперь вторую возможность: Г га 6 -~ Н. Снова каждая из формул 6 и Н содержит < 7г логических связок; для каждой из них будет справедливо предположение индукции: Х$,Хз,"1ХЯ" 6 ( ! н" л)1 Х' Х' ..., Х„'" — Н'(Х„Х, ..., Х„). Покажем„что 6", Н' » Г', т.е. 6", Н" » (6-+ Н) . Расшифруем значения а-двойников во всех случаях, которые могут представиться: 1) набор а = (оь оз, ..., а„) таков, что 6(оь оп ..., а„) = О и Н(оп оз, ..., о„) = О.
Тогда 6(оь аз, ..., а„) — э Н(оь ог, ..., о„) = = Π— ~ О = 1 и а-двойники имеют вид: 6 га 6, Н' и Н, (6 — ~ — > Н)"и 6-~ Н. Требуемая выводимость принимает следующий вид: ~6, ~Н» 6-~ Н. Покажем, что это действительно так. В самом деле, на основании теоремы 15.8, в, имеем» 6 -+ (6 -+ — > Н). Тогда, по следствию 15.5 из теоремы о дедукции, заключаем, что —,6» 6 — > Н.
Применив теорему 15.3, а, получаем — 6, -Н» 6-+Н; 2) набор о = (оь а„..., о„) таков, что 6(о„он ..., о„) = О и Н(аь оп ..., о„) = 1. Тогда 6(оь оп ..., о„) -+ Н(оь аз, ..., о,) = = О -э 1 = 1, и а-двойники имеют в этом случае следующий вид: 6' еа —,6, Н' ьз Н, (6 -~ Н) и 6 -+ Н. Требуемая выводимость принимает следующий вид: ~6, Н» 6 — ~ Н. Ее доказательство ничем не отличается от доказательства выводимости в предыдущем случае; 3) набор о = (оп а„..., о„) таков, что 6(оь о,, ..., а„) = 1 и Н(оь о„..., о„) = О. Тогда 6(оь оп ..., а„) -э Н(а„оп ..., а„) = = 1 -> О = О и о-двойники имеют следующий вид: 6 а 6, Н'= Н, (6-> Н)' и (6 — > Н). Требуемая выводимость принимает следующий вид: 6, Н» — (6-+ Н).
Покажем, что это действительно так. Ясно, что справедливы выводимости 6, Н, 6 — ~ Н» Ни 6, - Н, 6-э Н» Н(первая очевидна, а вторая следует на основе правила МР: 6, 6 — > Н» Н). Из них, по правилу введения отрицания (теорема 15.9, г), получаем 6, — Н» - (6 — > Н); 137 4) набор о = (оь оь ..., о„) таков, что 6(оп о„..., о„) = 1 и Н(пп оз, ..., о„) = 1. Тогда 6(о'ь он ..., о.) — > Н(о„оз, ..., о„) = = 1 — ~ ! = 1 и о-двойники имеют вид: 6 а 6, Н' в Н, (6-~ Н) ° =- 6-~ Н. Требуемая выводимость принимает следующий вид: 6, Н~ — 6 — > Н. Проверим, что это действительно так.
Рассмотрим последовательность формул Н, Н вЂ” > (6 — > Н), 6 — з Н. Первую формулу последовательности будем считать гипотезой. Вторая формула представляет собой аксиому (А1) формализованного исчисления высказываний, а третья получена из двух предыдуших по правилу МР. Следовательно, рассматриваемая последовательность есть вывод ее последней формулы 6 — ~ Низ гипотезы Н. Итак, Н »- 6 — > Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
