Языки и исчисления




Исчисление высказываний (ИВ) - часть 5


Докажем, например, что (для любых формул и ) формула

("закон контрапозиции") является теоремой исчисления высказываний. В самом деле, по лемме о дедукции достаточно установить, что

Для этого, в свою очередь, достаточно вывести из посылок какую-либо формулу и ее отрицание (в данном случае формулы и ).

25. Выведите формулы и с помощью аналогичных рассуждений.

Последняя аксиома, называемая "законом исключенного третьего", и иногда читаемая как "третьего не дано" (tertium non datur в латинском оригинале), вызвала в первой половине века большое количество споров. (См. раздел об интуиционистской логике,в которой этой аксиомы нет.)

Из нее можно вывести закон "снятия двойного отрицания", имеющий вид . В самом деле, достаточно показать, что . По правилу разбора случаев, достаточно установить, что (это очевидно) и что (а это верно, так как из двух противоречащих друг другу формул выводится что угодно с помощью аксиомы 8).

26. Докажите, что формула является теоремой исчисления высказываний. (Указание: используйте закон исключенного третьего.)

27. Исключим из числа аксиом исчисления высказываний закон исключенного третьего, заменив его на закон снятия двойного отрицания. Покажите, что от этого класс выводимых формул не изменится.

28. Докажите, что при наличии аксиомы исключенного третьего (11) аксиома (10) является лишней — ее (точнее следовало бы сказать: любой частный случай этой схемы аксиом) можно вывести из остальных аксиом.

Теперь уже можно доказать теорему о полноте: всякая тавтология выводима в исчислении высказываний. Идея доказательства состоит в разборе случаев. Поясним ее на примере. Пусть — произвольная формула, содержащая переменные . Предположим, что истинна, когда все три переменные истинны. Тогда, как мы докажем,

Вообще каждой строке таблицы истинности для формулы

соответствует утверждение о выводимости. Например, если

ложна, когда и ложны, а истинно, то

Если формула является тавтологией, то окажется, что она выводима из всех восьми возможных вариантов посылок.


Содержание  Назад  Вперед