Отношение равносильности формул

Определение. Назовем интерпретацией формулы А логики высказываний всякий набор истинностных значений атомов, входящих в формулу А.

Данная формула в конкретной интерпретации сама принимает одно из истинностных значений И или JI, которое определяется при выполнении в требуемом порядке всех предписываемых формулой логических операций. Пусть, например, необходимо вычислить истинностное значение формулы (¬PÛQÚR)ÞSÙQ при наборе {Р, Q, R, S} = {И, И, Л, И}. Вычисления можно оформить так, что результат выполнения операции подписывается под соответствующим оператором:

Чтобы найти истинностные значения формулы во всех возможных интерпретациях, строят таблицы истинности. Для примера рассмотрим формулу ¬PÙQ ÚR Þ(PÛR).

Чтобы безошибочно выписать все интерпретации формулы, поступаем следующим образом: определяем различные атомы, входящие в формулу. Пусть число этих атомов п. Тогда существует 2 ^п различных интерпретаций.

В таблицу для первого атома выписываем по стро­кам сначала 2 ^п /2=2 ^п -1 И, затем 2 ^п -1 Л, для второго— чередуем 2 ^{п -1}/2 = 2 ^{п -2} значений И и Л и т.д., для п- гoатома чередуем И и Л по одному.

Определение. Таблица, содержащая всевозможные интерпретации формулы и соответствующие этим интерпретациям значения формулы, называется истинностной таблицей формулы.

Например, совокупность столбцов 1, 2, 3, 8 есть истинностная таблица формулы ¬PÙQ ÚR Þ(PÛR), а совокупность столбцов 1, 2, 3, 6 — истинностная таблица формулы ¬PÙQ ÚR.

Всякая формула характеризуется своей истинностной таблицей. Одна и та же таблица может отвечать различным формулам.

Определение. Формулы А и В называются равносильными, если во всех интерпретациях формул А и В, содержащих все атомы формул А и В, истинностные значения этих формул совпадают. Равносильность формул А и В обозначается А≡В. Очевидно, что равносильные формулы имеют одинаковые истинностные таблицы, и наоборот, если истинностные таблицы формул совпадают, то они равносильны.

Пример: PÞQ ≡ ¬PÚQ.

Отношение равносильности формул А и В является отношением эквивалентности (А~В):

а) А≡А для любой формулы А (рефлексивность),

б) если А≡В, то B≡A для любых формул А и В (симметричность),

в) если А≡В и В≡С, то А≡С для любых формул А, В, С (транзитивность).

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