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

 

Для начала дадим основные определения.

Определение. Говорят, что булева функция сохраняет 0, если f (0,0,…,0)=0.

Определение. Говорят, что булева функция сохраняет 1, если .

Определение. Функция, реализуемая формулой , называется двойственной к функции .

Функцию, двойственную к функции , обозначают , т.е. .

Определение. Говорят, что булева функция самодвойственная, если .

Определение. Если для любого  (), то говорят, что вектор предшествует вектору  и пишут .

Например, ; .

Определение. Говорят, что булева функция монотонна, если для любых наборов  и  значений переменных, таких что , выполняется неравенство .

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

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

ПРИМЕР. Является ли система булевых функций  полной?

Чтобы убедиться в функциональной полноте, составим таблицу, столбцы которой соответствуют классам , , , ,. , строки – функциям , а в клетках проставляется «+» или «–» в зависимости от того, принадлежит ли функция соответствующему классу или не принадлежит.

0	+	–	–	+	+
1	–	+	–	+	+
	–	–	+	–	+

 

 

Как видно из таблицы, для каждой пары классов найдется функция, принадлежащая одному классу из пары и не принадлежащая другому

Определение. Система функций B называется базисом, если:

1. B – полна;

2. при удалении из системы B хотя бы одной функции, полнота теряется.

 

ПРИМЕРЫ.

1.  – дизъюнктивный базис Буля.

2. – конъюнктивный базис Буля.

3.  – базис Шеффера.

4.  – базис Пирса.

5. – базис Жегалкина.

 

Минимизация высказываний методом Квайна

 

1. Выражение из произвольной формы приводится к СДНФ.

2. Выполнив в СДНФ все возможные неполные склеивания, а затем все возможные поглощения мы получим Сокращенную ДНФ (СкДНФ). Конъюнкции в СкДНФ называются импликантами.

3. На основании СкДНФ и СДНФ строим импликантную матрицу и путем нахождения минимального покрытия этой матрицы получаем минимальную дизъюнктивную нормальную форму (МДНФ).

ПРИМЕР. Минимизировать функцию

Решение. Воспользуемся алгоритмом метода Квайна.

1. Получить СДНФ.

2. Получить сокращенную ДНФ (СкДНФ), используя следующие равносильности:

– склеивание;

 – неполное склеивание;

 – поглощение.

3. Построить импликантную матрицу, с помощью которой получить МДНФ.

1.  - ДНФ

 - СДНФ

                                                1 2        3  4              5  6

2. Применяя операции склеивания, получаем СкДНФ.

 

1-2:		3-4:
1-5:		4-6:
2-3:		5-6:

3. Составляем импликантную матрицу

	+	+
	+				+
		+	+
			+	+
				+		+
					+	+

 

Выбираем импликанты, которые поглощают все конституенты единицы.