Способы получения эквивалентных формул

Теория

Эквивалентности на основе свойств логических операций (коммутативность, ассоциативность, идемпотентность, дистрибутивность, поглощение). Эквивалентности на основе взаимосвязей операций. Эквивалентности на основе двойственности.

С помощью подстановки можно получать эквивалентные формулы, отталкиваясь от известных свойств логических операций.

Теорема 2.4. Для любых пропозициональных формул X, Y и Z верны следующие эквивалентности: 1) X ∧ X ≡ X; 2) X ∧ Y ≡ Y ∧ X; 3) (X ∧ Y ) ∧ Z) ≡ (X ∧ (Y ∧ Z); 4) X ∨ X ≡ X; 5) X ∨ Y ≡ Y ∨ X; 6) (X ∨ Y ) ∨ Z) ≡ (X ∨ (Y ∨ Z); 7) X ∧ (Y ∨ Z) ≡ (X ∧ Y ) ∨ (X ∧ Z); 8) X ∨ (Y ∧ Z) ≡ (X ∨ Y ) ∧ (X ∨ Z); 9) X ∧ (Y ∨ X) ≡ X; 10) X ∨ (Y ∧ X) ≡ X.
◀ Непосредственно из таблицы для истинностной функции вытекает, что x ∧ x ≡ x. Подставив вместо всех вхождений переменной x формулу X, получим эквивалентность X ∧ X ≡ X. Остальные эквивалентности доказываются аналогично. ▶
Еще один способ получения эквивалентностей — замена одних операций другими по соответствующим формулам. Из теории булевых функций вытекает, что верны следующие эквивалентности:
(¬ (¬ x)) ≡ x,        (¬ (x ∨ y)) ≡ (¬ x) ∧ (¬ y),         (x → y) ≡ ((¬ x) ∨ y).
Отталкиваясь от этих эквивалентностей можно доказать следующее.

Теорема 2.5. Для любых пропозициональных формул X, Y и Z верны следующие эквивалентности:

  1. (¬ (¬ X)) ≡ X (закон двойного отрицания);
  2. (¬ (X ∨ Y )) ≡ (¬X) ∧ (¬Y )) (перенос отрицания через конъюнкцию);
  3. (¬ (X ∧ Y )) ≡ (¬X) ∨ (¬Y )) (перенос отрицания через дизъюнкцию);
  4. (¬ (X → Y )) ≡ (X ∧ (¬Y )) (перенос отрицания через импликацию);
  5. (X → Y ) ≡ ((¬X) ∨ Y ) (представление импликации через дизъюнкцию);
  6. (X → (¬ X)) ≡ (¬X) (закон упрощения); 7) (X → Y ) ≡ ((¬ Y ) → (¬ X) (закон контрапозиции).

◀ Доказывается теорема так же, как и предыдущая. Например, на основании простой эквивалентности (¬ (¬ x)) ≡ x, устанавливаемой непосредственно, путем подстановки вместо переменной x формулы X получаем эквивалентность (¬ (¬ X)) ≡ X. ▶
Понятие двойственности из теории булевых функций переносится на алгебру высказываний. В данном случае речь идет о формулах, содержащих только базовые операции ∨, ∧, ¬. Для любой такой формулы X двойственная формула X* получается взаимной заменой операций ∨ и ∧.
Переход к двойственной формуле соответствует переходу от булевой функции f(x) к двойственной функции f(x). Понятие двойственных функций позволяет ввести понятие двойственности для любых формул алгебры высказываний, однако для произвольных формул двойственность не является такой простой, как вслучае трехбазовых операций. Из понятия двойственных функций вытекает, что двойственность — симметричное отношение, т.е. X** = X (здесь знак равенства означает не эквивалентность формул, а их совпадение). Из понятия двойственности функций вытекает и следующая эквивалентность: