Алгебраический подход

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

Для логических формул важно уметь обнаруживать эквивалентность двух различно представленных объектов.

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

А º В тогда и только тогда, когда ú= АÛ В.

Чтобы преобразовать логическую формулу в равносильную полезно знать «замечательные тождества», которые задают различные способы представления объекта.

Замечательные тождества.

I. Законы булевой алгебры. Математик Джордж Буль (1815–1864) описал алгебру, основанную на операторах И, ИЛИ и НЕ.

Закон двойного отрицания (инволюция): ØØA º A;

Законы коммутативности:

A & B º B & A,

A Ú B º B Ú A;

Законы ассоциативности:

A & (B & C) º (A & B) & C,

A Ú (B Ú C) º (A Ú B) Ú C;

Законы дистрибутивности:

A & (B Ú C) º (A & B) Ú (A & C),

A Ú (B & C) º (A Ú B) & (A Ú C);

Свойства констант:

A &1º A,

A & 0 º 0,

A Ú 1 º 1,

A Ú 0 º A.

Закон идемпотентности: A & A º A; AÚ A º A.

II. Законы де Моргана:

Ø (A & B) º ØA Ú ØB;

Ø (A Ú B) º ØA & ØB.

III. Другие замечательные тождества.

Связь операций:

A Þ B º ØA Ú B,

A Û B º (A Þ B) & (ВÞА),

A & В º Ø(A Þ ØB),

A Ú В º ØA Þ B,

A Þ ØB º В Þ ØА.

Закон контрапозиции: A Þ B º ØB ÞØA.

Закон противоположности: A Û B º ØA Û ØB

Используя эти равносильности можно по данной формуле построить ей равносильные или эквивалентные.

Примеры.

a) (A Ú A) & B Ú A º A & B Ú A º A& B Ú A & 1 º A& (B Ú 1) º A & 1º A.

b) B®(Ø A & B) º ØB Ú (Ø A & B) º (ØB Ú ØA)&(ØB v B) º(ØB Ú ØA) &1º º(ØB Ú ØA) º Ø (B & A).