Классы Функций
[предыдущая глава]  [оглавление]  [следующая глава]

Рассмотрим классы логических функций. Данная классификация не является бессмысленным украшением, а необходима для теоремы Поста, которая будет рассмотрена в следующей главе.

Классы логических функций

Функция, "сохраняющая 0".

Это - такая логическая функция, значение которой равно 0, если все аргументы равны 0: f(0,0,...,0) = 0.


Примером функции, сохраняющей 0, является функция .

Функция, "сохраняющая 1".

Это - такая логическая функция, значение которой равно 1, если все аргументы равны 1: f(1,1,...,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 называются двойственными, если

f(~x1, ~x2,...,~xN) = ~g(x1, x2,..., xN).


Кратко это будем обозначать так: "f" * "g". Двойственные функции легко обнаружить с помощью простого приема. Надо заменить в таблице истинности все "0" на "1", а все "1" на "0". Полученная таблица истинности и будет таблицей двойственной функции. Ниже приведен список двойственных функций для всех унарных и бинарных операций.
"0" * "1"
"x" * "x"
"~" * "~"
"&" * ""
"" * ""
"|" * ""
"<" * ""
">" * ""

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

Это - логическая функция, которая двойственна самой себе:

f(~x1, ~x2,...,~xN) = ~f(x1, x2,..., xN).