logo
практикум по мат

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

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

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

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

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

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

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

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

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

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

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

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

  7. φ→ψ≡¬φ∨ψ;

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

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

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

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

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

  1. φ∧ φ1≡φ; φ∨ φ0≡φ;

  2. φ∧φ0≡φ0; φ∨φ1≡φ1;

  3. φ∧¬φ≡φ0; φ¬φ≡φ1.