Опр Если каждый конъюнкт содержит все переменные (причём только саму переменную или её отрицание), то ДНФ называется совершенной (СДНФ)

СЛЕДСТВИЕ Из формулы Шеннона следует, что любая булева функция представима в виде СДНФ (причём это представление единственно, с точностью до перестановки конъюнктов).

АЛГОРИТМ приведения к СДНФ с помощью таблицы истинности: 1) заполнить таблицу истинности для функции ;

2) по строкам, в которых функция равна , выписать формулу Шеннона.

Пример Представим формулу в виде СДНФ. Руководствуясь теоремой Шеннона, выписываем дизъюнкцию тех конъюнктов, на которых формула принимает значение . Последние берем из таблицы истинности. Тогда

.

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

Опр Булева функция вида где -дизъюнкт, называется конъюнктивной нормальной формой (КНФ).

Опр Если каждый дизъюнкт содержит все переменные, причём либо саму переменную, либо её отрицание, то КНФ называется совершенной (СКНФ).

СЛЕДСТВИЕ Каждая булева функция единственным образом представима в виде СКНФ с точностью до перестановки дизъюнктов.

ЗАМЕЧАНИЕ По схеме теоремы Шеннона доказывается такая формула представления булевой функции в виде СКНФ .

Пример Ранее мы составили таблицу истинности для формулы . Поэтому в соответствии с алгоритмом имеем такую ее СКНФ .

_____

Опр Замыканием подмножества М булевых функций называется множество булевых функций, которые получаются из с помощью операции суперпозиции (составления сложных функций).

Пример Для имеем .

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

Пример В силу теоремы Шеннона подмножество , называемое базисом Буля, функционально полное.

ЗАМЕЧАНИЕ Известен критерий Поста функциональной полноты произвольного множества .

Опр Функционально полное множество называется базисом (минимальным базисом), если удаление хотя бы одной функции из делает оставшееся множество не функционально полным.

ТЕОРЕМА 5 Следующие подмножества операций являются базисами: .

_____

Опр Импликантой булевой функции называется конъюнкт, который может принимать значение лишь на тех -ках , на которых .

Пример Выпишем таблицу истинности для ранее рассмотренной булевой функции в таком виде

Из приведенных в левом столбце конъюнктов импликантами для нее в соответствии с определением будут только , , , .

Опр Импликанта называется простой, если никакая ее часть не является импликантой. Простая импликанта называется существенной (ядровой), если на некоторой -ке среди всех простых импликант только она принимает значение .

Пример Все импликанты примера не являются простыми. Их максимальными простыми частями будут импликанты , , . Среди них является несущественной, а остальные существенны как видно из таблицы

Опр Тупиковой ДНФ (ТДНФ) булевой функции называется ее ДНФ, составленная из простых импликант, ни одну из которых нельзя удалить. Логическая функция имеет, вообще говоря, несколько ТДНФ.

Определение Минимальной ДНФ (МДНФ) булевой функцииназывается та ее ТДНФ, которая имеет наименьшее число символов переменных.

Пример Образуя из полученных трех простых импликант примера различные ДНФ, получаем на основании таблицы такие ДНФ нашей булевой функции , . Первая из них не является тупиковой. Вторая явлется тупиковойи потому минимальной ДНФ.

Приведем один метод построения МДНФ. Пусть булева функция задана в виде таблицы истинности или СДНФ. Составим карту всевозможных конъюнктов, образованных переменными из первых столбцов. Эта таблица имеет строк.

		.					.			.	…
		.					.			.	…
.	.	.	.	.	.	.	.	.	.	.	.
		.					.			.	…
		.					.			.	…

ЗАМЕЧАНИЕ Если конъюнкт , стоящий в последнем столбце, не входит в СДНФ функции , то любой конъюнкт этой строки не входит ни в одну ДНФ, равносильную . Действительно, если конъюнкт не входит в

СДНФ, то по алгоритму построения СДНФ . Если бы какой-то конъюнкт этой строки таблицы вошел в некоторую ДНФ функции , то, так как этот конъюнкт на ке равен .

На замечании основан метод минимизирующих карт.

АЛГОРИТМ (построения минимальной булевой формы)

1) Вычеркнуть в карте строки, порожденные конъюнктами , которые не входят в СДНФ функции .

2) Вычеркнутые в этих строках конъюнкты вычеркнуть также в остальных строках (на основании замечания).

3) В каждой невычеркнутой строке оставить только конъюнкты с минимальным числом сомножителей (они и являются в силу определения простыми импликантами), а остальные вычеркнуть. Если в строке остается одна импликанта, то она ядровая и должна быть включена во все тупиковые ДНФ.

4) В каждой невычеркнутой строке выбрать по одной импликанте, и составить из них ДНФ.

5) Полученное множество ДНФ содержит все ТДНФ. Из него выбрать минимальные ДНФ.

Пример Построим, следуя алгоритму, минимальную ДНФ логической формулы предыдущего примера. Ее минимизирующая карта имеет вид

После вычеркивания конъюнктов 4-ой, 5-ой, 6-ой, 8-ой строк и

выполнения пунктов 2) и 3) алгоритма, получаем карту

Из четырех строк можно образовать, беря по одному конъюнкту, такие ДНФ , . Минимальной ДНФ будет последняя. Имеем .