Тема: Исчисление высказываний

Лекция №3

Тема: Исчисление высказываний

План:

1.  Классическое определение исчисления высказываний.

2.  Дедукция.

3.  Полнота исчисления высказываний.

4.  Разрешимость и непротиворечивость.

1.  Классическое определение исчисления высказываний

Исчислением высказываний называется формальная теория с языком логики высказываний, со схемами аксиом

A1)

A2)

A3)

и правилом вывода МР (Modus Ponens - обычно переводится как правило отделения):

Здесь А, В и С - любые формулы. Таким образом, множество аксиом исчисления высказываний бесконечно, хотя задано тремя схемами аксиом. Множество правил вывода также бесконечно, хотя оно задано только одной схемой.

Пример. Для любой формулы А построим вывод формулы , т. е. - теорема.

Подставляем в схему аксиом А2 вместо В формулу и вместо С формулу А, получаем аксиому

Подставляем в А1 вместо формулы В формулу , получаем аксиому

(2)

Из формул (1) и (2) по правилу МР получаем

(3)

Подставляем в А1 вместо формулы В формулу А, получаем аксиому

(4)

Из формул (3) и (4) по правилу МР получаем .

Теорема 4.1. Если Г|- и Г|-A, то Г|-B.

Доказательство. Пусть А1, А2,..., Аn - вывод формулы А из Г, где Аn совпадает с А. Пусть В1, В2,..., Вm - вывод формулы из Г, где Вm совпадает с . Тогда А1, А2,..., Аn, В1, В2,..., Вm, В - вывод формулы В из Г. Последняя формула в этом выводе получена применением правила МР к формулам Аn и Вm.

2. Дедукция

В исчислении высказываний импликация очень тесно связана с выводимостью.

Теорема 4.2 (о дедукции). Если Г, А|-В, то Г|- и наоборот.

Следствие.

1. ,|-.

2. |-.

3. Полнота исчисления высказываний

В исчислении высказываний у нас есть два понятия, касающиеся формул: теорема и тавтология. Аксиомы и правило вывода придуманы так, что эти два понятия совпадают.

Наша цель показать, что формула исчисления высказываний является тавтологией тогда и только тогда, когда она есть теорема. В одну сторону это совсем просто.

Теорема 4.3.

1. Любая аксиома в исчислении высказываний является тавтологией.

2. Любая теорема в исчислении высказываний является тавтологией.

Доказательство. То, что каждая аксиома А1-А3 является тавтологией, легко проверить с помощью таблиц истинности. Для доказательства пункта 2 теоремы, предварительно докажем, что правило МР, примененное к тавтологиям, приводит к тавтологиям.

Действительно, пусть при произвольном распределении истинностных значений формулы А и являются тавтологиями. Тогда формула А истинна и, по свойствам импликации, В истинно. Следовательно, В - тавтология.

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

Лемма 4.3. [21, стр. 41-43]. Для любых формул А, В следующие формулы являются теоремами:

(a)

(b)

(c)

(d)

(e)

(f)

(g)

Лемма 4.4. Если Г, A|-В и Г, А|-В, то Г |- В.

Доказательство. По лемме 4.3(g) формула является теоремой. Таким образом, Г|-. Кроме того, по теореме о дедукции Г|- и Г|-. Теперь дважды воспользуемся теоремой 4.1.

Лемма 4.5. [21, стр. 43] Пусть А содержит пропозициональные переменные Х1, Х2,..., Хm и пусть задано некоторое распределение истинностных значений для Х1, Х2,..., Хm. Пусть тогда Xi’ есть Xi, если Xi принимает значение И, и Xi если Xi принимает значение Л, и пусть, наконец, А' есть А, если при этом распределении А принимает значение И, и А, если А принимает значение Л. Тогда Х’1,Х’2,...,Х’m|-А’.

Если, например, А обозначает , то для каждой строки истинностной таблицы

X1	X2
И	И	Л
Л	И	Л
И	Л	Л
Л	Л	И

лемма 4.5. утверждает факт соответствующей выводимости. Так, в частности, третьей строке соответствует утверждение Х1, Х2|-(), а четвертой строке Х1, Х2|-().

Доказательство. Проведем доказательство с помощью математической индукции по числу n вхождений в А логических связок.

Базис индукции. Если n=0, то А представляет из себя просто пропозициональную переменную Х1 и утверждение леммы сводится к X1|-X1 и X1|-X1.

Индуктивный переход. Допустим теперь, что лемма верна при любом j<n.

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

Случай 1а. Пусть при заданном распределении истинностных значений В принимает значение И. Тогда А принимает значение Л. Таким образом, В’ есть В, а А’ есть А. По индуктивному предположению, примененному к В, мы имеем Х’1, Х’2,...,X'm|-B. Следовательно, по лемме 4.3(b) и РМ, Х’1, Х’2,...,X'm|-B. Но B и есть А'.

Случай 1b. Пусть В принимает значение Л; тогда B' есть B, а А' совпадает с А. По индуктивному предположению, Х’1, Х’2,...,X'm|-B, что и требовалось получить, ибо B есть А'.

Случай 2. Формула А имеет вид . Тогда число вхождений логических связок в В и С меньше, чем в А. Поэтому, в силу индуктивного предположения Х’1, Х’2,...,X'm|-B’, Х’1, Х’2,...,X'm|-C’.

Случай 2а. Формула В принимает значение Л. Тогда А принимает значение И, и В' есть В, а А' есть А. Таким образом, Х’1, Х’2,...,X'm|-B и, по лемме 4.3 (с), Х’1, Х’2,...,X'm|-, но есть А.

Случай 2b. Формула С принимает значение И. Следовательно, А принимает значение И и С’ есть С, а А' есть А. Имеем Х’1, Х’2,...,X'm|-C, и тогда, по схеме аксиом A1, Х’1, Х’2,...,X'm|-, где совпадает с А.

Случай 2с. Формула В принимает значение И и С принимает значение Л. Тогда А' есть А, ибо А принимает значение Л, B' есть В и С’ есть С. Имеем Х’1, Х’2,...,X'm|-B и Х’1, Х’2,...,X'm|-С. Отсюда, по лемме 4.3 (f) получаем Х’1, Х’2,...,X'm|- , где есть А'.

Теорема 4.4. (Пост, 1921) Формула А в исчислении высказываний является теоремой тогда и только тогда, когда А - тавтология.

Доказательство. Нам осталось доказать только половину теоремы, другая половина доказана в теореме 4.3. Итак, пусть А есть тавтология, докажем, что она доказуема. Предположим, что Х1, Х2,...,Xm - все пропозициональные переменные, содержащиеся в А. При каждом распределении истинностных значений для переменных Х1, Х2,...,Xm мы имеем, в силу леммы 4.5, Х’1, Х’2,...,X’m|-А (А' совпадает с А, так как А есть тавтология). Поэтому в случае, когда Хm принимает значение И, мы, применив лемму 4.5, получаем Х’1, Х’2,...,X’m-1|-А когда же Хm принимает значение Л, то по той же лемме получаем Х’1, Х’2,...,X’m|-А. Отсюда, по лемме 4.4, Х’1, Х’2,...,X’m-1|-А. Точно таким же образом, рассмотрев два случая, когда Xm-1 принимает значение И и Л, и снова применив леммы 4.5 и 4.4, мы исключим Xm-1 и так далее; после m таких шагов мы придем к |-A.

4. Разрешимость и непротиворечивость исчисления высказываний

Интерпретация формул исчисления высказываний проста - область интерпретации состоит из двух значений «истина» и «ложь»; поэтому пропозициональная переменная принимает только значения И и Л и интерпретация составной формулы вычисляется по известным законам с помощью логических операций над истинностными значениями. Поскольку любая формула содержит только конечное число пропозициональных переменных, то формула обладает только конечным числом различных интерпретаций. Следовательно, исчисление высказываний является, очевидно, разрешимой формальной теорией.

Легко убедиться, что исчисление высказываний является формально непротиворечивой теорией. Действительно, все теоремы исчисления высказываний суть тавтологии. Отрицание тавтологии не есть тавтология. Следовательно, никакая формула не может быть выведена вместе со своим отрицанием.