Закон двойственности
Докажем, что класс Sзамкнут. Поскольку класс S содержит тождественную функцию, достаточно показать, что функция Ф = f( f1, …, fm ) является само-двойственной, если f1, …, fm - самодвойственные.
Последнее устанавливается непосредственно:
Ф* = f*( f1*, …, fm* ) = f( f1, …, fm ) = Ф.
Определение. Для двух наборов значений переменных a = ( a1, … , an ) и b = ( b1, … , bn ) выполнено отношение предшествования a d b,
если
a1 d
b1, … , an d bn, где
ai, bi 
{ 0,1 }.
Например, для a = ( 0,1,0,1 ) и b = ( 1,1,0,1 ) выполнено отношение a d b.
Очевидно что если ad b и bd c, то a d c. Следует отметить, что не любые пары наборов значений переменных находятся в отношении предшествования, например, наборы ( 0,1 ) и ( 1,0 ) в таком отношении не находятся.
Определение. Функция f( x1, …, xn ) называется монотонной, если для любых двух наборов значений переменных a и b таких, что a d b, имеет место неравенство:
f( a ) d f( b ). (1.13)
Нетрудно заметить, что функция, равная монотонной функции, так же является
монотонной. Легко проверить, что монотонными функциями будут следующие функции: 0,
1, x, x &
y, x 
y.
Функция 
не является монотонной.
Пример. Проверить на монотонность функции f1 и f2, заданные следующей таблицей:
предыдущаяследующая