Эквивалентные формулы алгебры высказыванийКак показано в примере 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.
|
ψ или ψ 
, т.е. совпадают их таблицы истинности.
