Эквивалентные формулы алгебры высказываний

Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.

Формулы φ и ψ АВ называются эквивалентными (обозначается φ ≡ ψ), если φ ψ или ψ , т.е. совпадают их таблицы истинности.

Примα р 7. Построив таблицы истинности формул x→ y и y→ x, убеждаемся, что (х→ y) ≡ (y→ x).

Легко видеть, что отношение ≡ является отношением эк­вивалентности на множестве формул АВ, т. е. оно рефлексивно (φ ≡ φ), симметрично (если φ ≡ ψ, то ψ ≡ φ), транзитивно (если φ ≡ ψ и ψ ≡ χ, то φ ≡ χ), где φ, ψ, χ – произвольные формулы АВ.

Отметим основные эквивалентности между формулами АВ:

1) φ ∧ φ ≡ φ, φ ∨ φ ≡ φ (законы идемпотентности);

2) φ ∧ ψ ≡ ψ ∧ φ, φ ∨ ψ ≡ ψ ∨ φ (законы коммутативности);

3) (φ ∧ ψ)∧ χ ≡ φ ∧ (ψ ∧ χ), (φ ∨ ψ)∨ χ ≡ φ ∨ (ψ ∨ χ) (законы ассоциативности);

4) φ ∧ (ψ ∨ χ)≡ (φ ∧ ψ)∨ (φ ∧ χ), φ ∨ (ψ ∧ χ)≡ (φ ∨ ψ)∧ (φ ∨ χ) (законы дистрибутивности)

5) (φ ∧ ψ)≡ φ ∨ ψ, (φ ∨ ψ)≡ φ ∧ ψ (законы де Моргана);

6) φ ≡ φ (закон двойного отрицания);

7) φ → ψ ≡ φ ∨ ψ;

8) φ ∧ (φ ∨ ψ)≡ φ, φ ∨ (φ ∧ ψ)≡ φ (законы поглощения);

9) φ ∨ (φ ∧ ψ)≡ φ ∨ ψ, φ ∨ (φ ∧ ψ)≡ φ ∨ ψ;

10) φ ∧ (φ ∨ ψ)≡ φ ∧ ψ, φ ∧ (φ ∨ ψ)≡ φ ∧ ψ.

К перечисленным ранее соглашениям, пользуясь законами ассоциативности, добавляем следующее: в формулах вида (φ ∧ ψ)∧ χ, φ ∧ (ψ ∧ χ), (φ ∨ ψ)∨ χ и φ ∨ (ψ ∨ χ) скобки можно опускать.

Утверждение 1. Если формула φ ₁ тождественно истинна, φ ₀ — тождественно ложна, то для любых формул φ и ψ справедливы следующие эквивалентности:

1) φ ∧ φ ₁≡ φ; φ ∨ φ ₀≡ φ;

2) φ ∧ φ ₀≡ φ ₀; φ ∨ φ ₁≡ φ ₁;

3) φ ∧ φ ≡ φ ₀; φ φ ≡ φ ₁.