5.2. Двойственная формула

Определение. Формула F* называется двойственной формуле F, если она получена из F заменой символов функций на символы двойственных им функций.

Пример.

F = x ↓ (y (x y z) ) ( y x ),

F* = x / (y x (y z)) ( y x ). •

Теорема (принцип двойственности). Если формула F задает булеву функцию f(x1, …, xn), то двойственная ей формула F* задает двойственную функцию f*(x1, …, xn).

Доказательство. По условию теоремы формула F задает булеву функцию f(x1, …, xn). По определению формулы F имеем:

F=f(x1, …, xn) = f0(f1(x1, …, xn), …, fm(x1, …, xn)).

Рассмотрим двойственную ей формулу:

F*= f0*(f1*(x1, …, xn), …, fm*(x1, …, xn))=

[ по определению двойственной функции для fi*(x1, …, xn), i=1, …, m ]

=f0*(f 1(x 1, …, x n), …, f m(x 1, …, x n))=

[ по определению двойственной функции для f0*(y1, …, ym) ]

[ по закону двойного отрицания ]

=f 0(f1(x 1 …, x n), …, fm(x 1, …, x n))= f (x 1, …, x n) =

[ по определению двойственной функции для f(x1, …, xn ]

=f*(x1, …, xn).

Пример. Рассмотрим формулу F = , задающую булеву функцию НЕ-ИЛИ, то есть стрелку Пирса. Двойственная ей формула F* = x y должна задавать функцию, двойственную стрелке Пирса – это штрих Шеффера: в самом деле F* = x y – это функция НЕ-И, то есть штрих Шеффера. •

Следствие из принципа двойственности. Если формулы F1 и F2 равносильны, то двойственные им формулы F*1 и F*2, также равносильны.

Доказательство. Равносильные формулы F1 и F2задают одну и ту же булеву функцию f(x1, …, xn), следовательно, по принципу двойственности, двойственные им формулы F*1 и F*2, задают двойственную f(x1, …, xn) функцию f*(x1, …, xn). •

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

Примеры. Исходя из закона склеивания конъюнкций x y x y = y и используя следствие, получим ( x y ) ( x y ) = y – закон склеивания дизъюнкций. Исходя из одного закона де Моргана = x y и используя следствие, получим другой закон де Моргана x y = x y . •