Математическое введение в декларативное программирование. Зюзысов В.М. - 23 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

3 Исчисление высказываний
3.1 Определение исчисления высказываний
Исчислением высказываний называется формальная теория с языком логики выска-
зываний, со схемами аксиом
A1) A⊃(B⊃A);
A2) (A⊃(B⊃C)) ⊃ ((A⊃B) ⊃ (A⊃C));
A3) (¬B⊃¬A) ⊃ ((¬B⊃A) ⊃B);
и правилом вывода MP (Modus Ponens – обычно переводится как правило отделения):
MP
B
BAA ⊃,
Здесь A, B и C – любые формулы. Таким образом, множество аксиом исчисления
высказываний бесконечно, хотя задано тремя схемами аксиом. Множество правил вывода
также бесконечно, хотя оно задано только одной схемой.
Пример. Для любой формулы A построим вывод формулы A⊃A, т. е. A⊃A –
теорема.
Подставляем в схему аксиом A2 вместо B формулу A⊃A и вместо C формулу A, получаем
аксиому
(A⊃((A⊃A)⊃A))⊃((A⊃(A⊃A))⊃(A⊃A)). (1)
Подставляем в A1 вместо формулы B формулу A⊃A, получаем аксиому
A⊃((A⊃A)⊃A). (2)
Из формул (1) и (2) по правилу MP получаем
(A⊃(A⊃A))⊃(A⊃A). (3)
Подставляем в A1 вместо формулы B формулу A, получаем аксиому
A⊃(A⊃A). (4)
Из формул (3) и (4) по правилу MP получаем A⊃A.
В исчислении высказываний импликация очень тесно связана с выводимостью.
Теорема 1 (о дедукции). Если Γ, A|–B, то Γ|–AB и наоборот.
Теорема 2. (Пост, 1921) Формула A в исчислении высказываний является теоремой
тогда и только тогда, когда A – тавтология.
3.2 Разрешимость и непротиворечивость исчисления
высказываний
Интерпретация формул исчисления высказываний проста − область интерпретации
состоит из двух значений «истина» и «ложь»; поэтому пропозициональная переменная
принимает только значения И и Л и интерпретация составной формулы вычисляется по
известным законам с помощью логических операций над истинностными значениями. По-
скольку любая формула содержит только конечное число пропозициональных перемен-
ных, то формула обладает только конечным числом различных интерпретаций. Следова-
тельно, исчисление высказываний является, очевидно, разрешимой формальной теорией.
Легко убедиться, что исчисление высказываний является формально непротиворе-
чивой теорией. Действительно, все теоремы исчисления высказываний суть тавтологии.
Отрицание тавтологии не есть тавтология. Следовательно, никакая формула не может
быть выведена вместе со своим отрицанием.
23

Страницы