Лекция 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.

Дата добавления: 2014-01-20