Лекция 5.

Алгебра высказываний.

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

Коммутативные законы:

p ∧ q ≡ q ∧ p;

p ∨ q ≡ q ∨ p;

p ⊻ q ≡ q ⊻ p;

p ↔ q ≡ q ↔ р.

Ассоциативные законы:

( p ∧ q) ∧ г ≡ p ∧ ( q ∧ г );

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r);

(p ⊻ q) ⊻ r ≡ p ⊻ (q ⊻ r);

( p ↔q ) ↔ r ≡ p ↔ ( q ↔г ).

Дистрибутивные законы:

p ∧ (q ∨ r) ≡(p ∧ q) ∨ (p ∧ r);

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).

Законы идемпотентности:

p ∧ p ≡ p;

p ∨ p ≡ p.

Законы поглощения (абсорбции):

p ∧ ( p ∨ q ) ≡ p;

p ∨ ( p ∧ q ) ≡ p.

Инволюционный закон (двойное отрицание):

≡ р.

Законы де Моргана:

(p ∨ q) ≡ (p ∧q);

(p ∧ q) ≡ (p ∨ q).

Законы идентичности:

p ∨ f≡ p;

p ∧ t ≡ p;

p ∨ t ≡ t;

p ∧ f ≡ f;

Здесь и далее t - тавтология, f- противоречие. Можем также употреблять нежирный шрифт, хотя это не очень хорошо, так как нежирный шрифт мы обычно применяем для переменных и обычных высказываний, которые (высказывания), в общем случае, могут принимать разные истинностные значения (истина и ложь).

Комплиментарные законы (дополнения)

р ∨ р ≡ t, f = t;

р∧ р ≡f, t = f.

Определение. Для любого составного высказывания содержащего только операции конъюнкции и дизъюнкции, двойственным называется высказывание, которое получается в результате замены всех конъюнкций на дизъюнкции, всех дизъюнкций на конъюнкции, всех tна fи всех fна t.

Например, двойственным высказыванием для (p ∨ f) ∧ q будет (p ∧ t)∨ q.

Принцип двойственности.

Если два высказывания логически эквивалентны, то логически эквивалентными будут и их двойственные формы.

Пример: ( р ↔ q) ∧ q ≡ p ∧ q . Проверяем: ( р ↔ q) ∨ q ≡ p ∨ q .

Если р=И, q=Л, то ( р ↔ q) ∨ q=Л, p ∨ q=И. следовательно ( р ↔ q) ∨ q ≡ p ∨ q – неверно.

У высказываний, из которых делаем двойственное высказывание, не должно быть ↔, ®,…. Только ∧ и ∨.

ТЕОРЕМА (подстановка формулы).Если А и В эквивалентные логические высказывания, содержащие переменную q, то в результате подстановки составного высказывания С вместо всех вхождений переменной q в эквивалентные высказывания А и В их эквивалентность не нарушится.

Доказательство: Действительно, если высказывания А и В эквивалентны, то они принимают одинаковые истинностные значения при любых значениях своих переменных, причем неважно являются ли переменные простыми или определяются в результате вычислений. Следовательно, замена всех вхождений q на формулу С не нарушает эквивалентности высказываний А и В.

ТЕОРЕМА (замена подформул).Предположим составное логическое высказывание Q содержит высказывание Р_1. Если высказывание Р₂ эквивалентно Р₁, то замена для отдельных или для всех вхождений в Q Р₁ на Р₂ приводит к новому высказыванию Q эквивалентному Q (Q ≡ Q).

Доказательство. Так как высказывания Р₁ и Р₂ являются эквивалентными, то для одинаковых наборов простых переменных, входящих в них, их истинностные значения будут совпадать. Поэтому соответствующие истинностные значения высказываний Q и Q будут одинаковыми, то есть Q ≡ Q.