Закон двойственности
Теорема. Любая булева формула, не содержащая отрицаний, представляет монотонную функцию, отличную от 0 и 1, и наоборот, для любой монотонной функции, отличной от 0 и 1, найдется представляющая ее булева формула, не содержащая отрицаний.
Пример. Проверить на монотонность следующие функции:
x
y,
x & y, x & ( y z ).
Согласно приведенной теореме, данные функции будут монотонными, т.к. в представляющих их формулах нет отрицаний.
M- класс всех монотонных логических функций. Можно показать, что класс M является замкнутым классом.
Определение. Логическая функция n переменных называется линейной, если полином Жегалкина, представляющий данную функцию, содержит только линейные слагаемые, т.е.
f( x1, …, xn ) =
a0 
a1 x1 a2 x … an xn
, (1.14)
где ai 
{0,1}.
Легко видеть, что константы 0, 1 и функции x, 
, x y
являются линейными функциями. Функциzя x y не
является линейной, т.к. она представляется следующим полиномом Жегалкина: