1.4. Принцип и закон двойственности

Алгебра логики обладает замечательным свойством, которое называется принципом двойственности: если имеет место тождество

где то справедливо также тождество

т.е., если в каком-либо тождестве произвести взаимную замену символов 0 и 1 (если они имеются) и операций дизъюнкции и конъюнкции, то в результате также будет получено тождество. Два тождества, связанные между собой таким образом, называются двойственными. Соотношения (1.24) и (1.25) позволяют доказывать только одно из тождеств, второе же непосредственно следует из этих соотношений. Если выражения (1.24) и (1.25) совпадают, то они называются самодвойственными. Истинность самого принципа двойственности не доказывается, так как данный принцип является внутренним свойством алгебры логики (заключен в ее аксиомах).

Законы двойственности (1.13) определяют способ отыскания инверсных функций, представляющих собой дизъюнкцию и конъюнкцию двух переменных. К. Шеннон предложил обобщение этих теорем, позволяющее отыскивать инверсию любой функции где Закон двойственности, установленный К. Шенноном, имеет вид

где инверсию любой функции можно получить взаимной заменой переменных и их инверсий и операций дизъюнкции и конъюнкции.

Докажем теорему (1.26). Пусть задана полностью определенная функция где которая в точках имеет значение а в точках значение общее число точек равно т.е. Так как точки

представляют собой комбинации символов 0 и ( или или 1), то по принципу двойственности

где Очевидно, что

Из последних двух соотношений следует, что

так как равенства выполняются для всех точек

Рассмотрим два примера на применение закона двойственности. Пусть тогда то

Чтобы избежать ошибок при получении инверсной функции, следует учитывать все неявные скобки, положение которых задается иерархией операций конъюнкции и дизъюнкции.

В дальнейшем часто будут использоваться обозначения

На основании закона двойственности легко показать, что

Выражения (1-27) и (1.28) позволяют в компактной форме записывать специальные функции без ограничения числа переменных.