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

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

	Сохрание 0,	Сохрание 1,	Самодвойственность, S	Монотонность, M	Линейность, L
			+		+
	+	+		+
	+				+

В таблице знаком «+» обозначено принадлежность функции к данному классу.

Для того чтобы функции составляли базис, по теореме Поста необходимо, чтобы хотя бы одна функция не сохраняла 0, хотя бы одна функция не сохраняла 1, хотя бы одна функция не была самодвойственной, хотя бы одна функция не была монотонной и хотя бы одна функция не была линейной. Из вышеприведенной таблицы видно, что данный набор функций составляет базис. Причем для базиса достаточно первых двух функций, то есть отрицания и дизъюнкции.

Проверим возможность получения из заданной булевой функции f путем суперпозиции некоторой булевой функции . Для этого проверимf на принадлежность классам Поста.

По таблице истинности , следовательно.

, следовательно .

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

	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
f	1	1	1	1	0	1	1	0	1	1	1	1	1	1	1	1
	0	0	0	0	0	0	0	0	1	0	0	1	0	0	0	0

Исходя из таблицы истинности , следовательно.

Рассмотрим два набора и. Согласно лексикографического порядка, но. Поэтому.

Степень полинома Жегалкина для заданной функции f равняется 3, поэтому .

Заданная функция f принадлежит к функционально полному в слабом значении классу, так как она немонотонная и нелинейная. Поэтому добавление констант 0 и 1 в класс позволит получить изf путем суперпозиции любую булеву функцию .

4. Схемная реализация функций методом каскадов

Полином Жегалкина для функции

.

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

Для определения веса производных построим таблицы истинности.

0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0	0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0	0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1

Таким образом, , то есть дизъюнктивное разложения на этапах метода каскадов можно проводить по любым переменным. Выберем, например, что на первом этапе проведем разложение по переменной, на втором – по переменной, на третьем – по переменной.

Проведем дизъюнктивное разложение функции по переменной.

Проведем дизъюнктивное разложение функций іпо переменной.

Построим контактную схему (см. рис. 1).

Рисунок 1 – Схемная реализация булевой функции методом каскадов

Таким образом, сложность контактной схемы равна количеству контактов в ней и составляет .