Простейшие замкнутые классы булевых функций.

Напомним, что булева функция принимает значение из множества . Заметим, что для булевой функции всегда можно добавить фиктивные переменные. Пусть, например, рассматривается булева функция , тогда она может рассматриваться как функция от переменных в соответствии с равенством . Тогда легко понять, что суперпозиция булевых функций снова будет являться булевой функцией. .

Для некоторого набора булевых функций с помощью операции суперпозиции получается некоторое множество булевых функций , которое определяется по индукции:

1) ;

2) если уже определен класс , то следующий подкласс конечных суперпозиций определяется следующим образом:

;

3) .

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

Класс всех булевых функций был обозначен буквой Ф. Рассмотрим некоторое подмножество совокупности всех булевых функций.

Определение 5. Подкласс класса булевых функций называется замкнутым, если суперпозиция функций из подкласса снова лежит в этом подклассе.

Определение 6. Подкласс

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

Определение 7. Подкласс

булевых функций, сохраняющих 1.

ТЕОРЕМА 10. Подклассы являются замкнутыми классами.

Доказательство. Рассмотрим функцию

, где .

Тогда имеем

.

А значит , что и доказывает замкнутость класса .

Замкнутость класса доказывается аналогично.

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

Определение 8. Булева функция называется линейной, если соответствующий ей многочлен Жегалкина является линейным.

- линейная , где .

Введем класс всех линейных функций

.

ТЕОРЕМА 11. Класс является замкнутым.

Утверждение очевидно. Суперпозиция линейных функций снова является линейной функцией, т.к. это соответствует суперпозиции линейных полиномов Жегалкина.

ТЕОРЕМА 12. (Свойство нелинейной функции) Если функция нелинейная, то подстановкой вместо переменных 0, 1, а также используя отрицание из этой функции можно получить конъюнкцию и дизъюнкцию.

Доказательство. Для функции рассмотрим соответствующий полином Жегалкина .Так как этот многочлен нелинейный, то в нем содержатся слагаемые, содержащие произведения переменных. Рассмотрим тот из них, который имеет минимальную длину , где . Проведем замену переменных в этом многочлене , для всех . Тогда полином примет вид: , где .

Отметим, что через данный полином достаточно выразить одну из указанных операций либо дизъюнкцию, либо конъюнкцию, т.к. вторая операция получается из другой из них по законам де-Моргана. Приведем выражения этих операция из полинома при различных значениях , сведя все в таблицу.

f					Эквивалентная формула	Искомая суперпозиция
	0	0	0
	0	0	1
	0	1	0
	0	1	1
	1	0	0
	1	0	1
	1	1	0
	1	1	1