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

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

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

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

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

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

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

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

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

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

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

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

7) φ→ψ≡¬φ∨ψ;

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

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

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

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

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

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

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

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