Семантические таблицы для классической логики

В таблице истинности логического выражения содержится много избыточной информации. Таблицу можно сократить, используя следующие правила: для истинности дизъюнкции достаточно истинности одного из дизъюнктов; для ложности конъюнкции достаточно ложности одного из членов; истина следует из всего что угодно, из лжи следует все что угодно. Приведем полную (табл.4.1) и сокращенную (табл.4.2) таблицы истинности для формулы: . При сокращении самым тонким местом является проверка того, что не упущен ни один случай. Голландский логик Бет в 50-х годах привел формализм, обеспечивающий полноту разбора и выполняющий все сокращения. Этот формализм основан на необходимых и достаточных условиях истинности и ложности формул.

Таблица 4.1. Полная таблица истинности

	-	- -	-

Таблица 4.2. Сокращенная таблица истинности

Рассмотрим формулу . Сначала ищем все возможные случаи, когда формула ложна. Импликация ложна, если ее посылка истина, а заключение ложно. Ниже - символ ложности, - истинности:

Импликация истина тогда и только тогда, когда А ложно, либо В истинно. Формулы семантических таблиц разбиваются на подтаблицы.

В

В Ú C

В двух из 3-х образовавшихся подтаблиц встретились противоречия, такие подтаблицы называются закрытыми и отмечены двойной чертой. Оставшаяся подтаблица выдала тот единственный набор значений, при которых формула ложна: А истинно, В ложно, С истинно. Таким образом, метод проверки истинности формулы основан на построении контрпримера. Предполагается, что формула ложна. Строится семантическая таблица, и если все ее подтаблицы закрылись, предположение о ложности формулы привело к абсурду, следовательно, формула истинна. Иначе незакрытая подтаблица дает контрпример, т.е. значения переменных, при которых исходная формула ложна.