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

Пусть U=U(X,Y,…,Z) – формула алгебры высказываний. Формула

U^* = U(X,Y,…,Z)

называется двойственной к формуле U.

Из закона двойного отрицания следует, что (U^*)^*≅U. Между таблицами истинности исходной формулы и двойственной к ней имеется простая связь. Предположим для определенности, что формула U содержит две переменных, U=U(X,Y), и рассмотрим следующую таблицу истинности:

X Y U U^*

------------------------

0 0 α δ

0 1 β γ

1 0 γ β

1 1 δ α

Несложно заметить, что столбец значений формулы U^* представляет собой перевернутый столбец значений формулы U, снабженных отрицанием. То же справедливо и для формул, содержащих большее число пропозициональных переменных. Из этого замечания вытекает следующее утверждение.

Закон двойственности.Формулы алгебры высказываний равносильны тогда и только тогда, когда равносильны двойственные им формулы: U≅V тогда и только тогда, когда U^*≅V^*.􀀀

Для булевых формул закон двойственности приобретает особенно наглядную форму.

Теорема.Если формула U булева, то двойственная формула U^* равносильна формуле U^∧∨, полученной из U заменой всех конъюнкций на дизъюнкции, а дизъюнкций на конъюнкции.

Доказательство. Воспользуемся индукцией по длине формулы. Предположим сначала, что формула U состоит всего из одного символа. Это означает, что формула имеет вид U=X, где X – некоторая пропозициональная переменная. Ясно, что для такой формулы U^*≅U и U^∧∨=U, так что утверждение теоремы справедливо. Предположим теперь, что утверждение теоремы справедливо для всех формул длины меньше n и покажем, что оно справедливо и для произвольной формулы U=U(X,…,Y) длины n. В соответствии с определением формула U имеет вид

а) U=V; б) U=V∧W или в) U=V∨W,

где V и W – некоторые формулы. Ясно, что в любом случае формула U содержит по крайней мере на один знак больше, чем формулы V и W. Значит, длина V меньше n, и длина W меньше n. Поэтому к формулам V и W применимо заключение теоремы, то есть

V^*≅V^∧∨и W^*≅W^∧∨.

С учетом этого рассмотрим каждый из трех возможных случаев.

а) U^* = (V(X,…,Y)) = V^*, U^∧∨= V^∧∨, откуда U^*≅U^∧∨.

б) U^* = (V(X,…,Y) ∧ W(X,…,Y)), откуда по первой формуле де Моргана U^* ≅ V(X,…,Y)∨W(X,…,Y))≅ V^*∨W^*. С другой стороны, U^∧∨= V^∧∨∧W^∧∨, и, значит, U^*≅U^∧∨.

в) U^* = (V(X,…,Y) ∨ W(X,…,Y)), откуда по второй формуле де Моргана U^* ≅ V(X,…,Y)∨W(X,…,Y))≅ V^*∧W^*. С другой стороны, U^∧∨= V^∧∨∨W^∧∨, и, значит, U^*≅U^∧∨. В соответствии с принципом математической индукции утверждение теоремы верно для формул любой длины, то есть для всех формул.􀀀

Обычно закон двойственности применяют к булевым формулам и в этом случае называют двойственной к формуле U формулу U^∧∨. Следуя этой традиции, мы тем не менее сохраним за двойственной формулой обозначение U^*.

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

Пример.Формулы X(Y∨Y) и X∨(YY) двойственны, поэтому равносильность

X(Y∨Y) ≅ X

получается из равносильности

X∨(YY) ≅ X

по двойственности.􀀀