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

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

*Объекты изучения естественных и формальных языков – это синтаксис и семантика.

Синтаксис позволяет распознать фразы среди набора слов, а семантика придает определенное значение формулам. Так как высказывания либо истинны, либо ложно, то семантическая область исчисления высказывания определяется 0 или 1.

Семантика – набор правил интерпретации формул.

Интерпретация – отображение сопоставляющее каждому элементарному высказыванию некоторое значение истинности *

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

Определение. Две формулы назовём равносильными, если для любых наборов значений переменных они принимают одинаковые значения. А≡В тогда и только тогда, когда А⇔В.

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

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

1. Законы булевой алгебры (Математик Джордж Буль (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.

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

(A /\ B) ≡A ∨ B;

(A ∨ B) ≡A /\ B

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

Связь операций: A ⇒ B ≡A ∨ B,

A ⇔ B ≡ (A ⇒ B) & (В⇒А),

A & В≡(A ⇒B),

A ∨В≡A ⇒ B,

A ⇒B ≡В⇒А.

Закон контрапозиции: A ⇒ B ≡B ⇒A.

Закон противоположности: A ⇔ B ≡A ⇔B

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