Рассмотрим классы логических функций. Данная классификация не является бессмысленным украшением, а необходима для теоремы Поста, которая будет рассмотрена в следующей главе.
Классы логических функций
Это - такая логическая функция, значение которой равно 0,
если все аргументы равны 0:
Примером функции, сохраняющей 0, является функция
.
Это - такая логическая функция, значение которой равно 1,
если все аргументы равны 1:
Примером функции, сохраняющей 1, является функция &.
Это - такая логическая функция, которую можно выразить
через & и .
Монотонную функцию можно распознать по ее таблице истинности. Для этого нужно взять все пары строк в таблице, которые отличаются всего в одном столбце (не считая крайнего правого). Например: 0,0,0,0 и 0,0,0,1; 1,0,0,1 и 1,1,0,1. Пусть в одной строке в некотором столбце стоит "0", а в другой строке в этом же столбце стоит "1". Нельзя, чтобы в крайнем правом столбце, где записано значение функции было наоборот: "1", а потом "0". Если такая ситуация нигде не встречается, то функция монотонная, и ее можно выразить через
и &. Пример монотонной функции: .
Это - такая логическая функция, которую можно выразить
через 
, 0 и 1.
Чтобы узнать, линейна ли функция, надо выразить ее через полином Жегалкина и посмотреть, не встречается ли там операция &. Если нет, то функция линейна. Для функций от 1 и 2 переменных мы уже приводили формулы, выражающие их через &,
и константы.
Логические функции f и g называются двойственными, если
Кратко это будем обозначать так:
"" * "
"
"
"
"
Это - логическая функция, которая двойственна самой себе: