55. Основные эквивалентные соотношения в булевой алгебре. Выражение через дизъюнкцию, конъюнкцию и отрицание других логических бинарных операций. Двойственность.

• ассоциативностей aÚ(bÚc)=(aÚb)Úc, aÙ(bÙc)=(aÙb)Ùc;

• коммутативностей aÚb=bÚa, aÙb=bÙa;

• дистрибутивностей aÙ(bÚc)=aÙbÚaÙc; aÚbÙc=(aÚb)Ù(aÚc);

• идемпотентностей aÚa=a, aÙa=a;

• двойного отрицания ØØa=a;

• законы нуля (лжи) aÚ0=a, aÙ0=0, aØÙa=0;

• законы единицы (истины) aÚ1=1, aÙ1=a, aØÚa=1.

• де-Моргана ØaØÚb=Ø(aÙb), ØaØÙb=Ø(aÚb);

• противоречия aØÙа=0;

• исключенного третьего aØÚа=1

Для упрощения формул наряду с основными соотношениями используют также тождества

поглощения aÚaÙb=a, aÙ(aÚb)=a;

склеивания aÙbÚaØÙb=a, (aÚb)Ù(aØÚb)=a;

обобщенное склеивание aÙcÚbØÙcÚaÙb = =aÙcÚbØÙc;

aØÚaÙb = aÚb

Двойственность

Функция f1(x1,…, xn) называется двойственной к функции f2(x1,…, xn), если .

Отношение двойственности между функциями симметрично. Из определения двойственности ясно, что для любой функции двойственная функция определяется однозначно. В частности, может оказаться, что функция двойственна самой себе. В этом случае она называется самодвойственной.

Примеры:

дизъюнкция двойственна конъюнкции;

константа 1 двойственна 0;

отрицание самодвойственно;

функция самодвойственна.

Принцип двойственности: если в формуле F, представляющей функцию f, все знаки функций заменить соответственно на знаки двойственных функций, то полученная формула F* будет представлять функцию f*, двойственную к f.