Дизъюнктивно-Нормальная Форма аналитической записи логической функции (ДНФ)

Нормальными обычно называют формы записи, приведенные путем тождественных преобразований к определенному виду, называемому нормализованным или иногда каноническим (от греческого слова kanon [канон] ‑ правило). Дизъюнктивно-нормальная форма ‑ это дизъюнкция нескольких конъюнкций.

Запись ДНФ функции вида F(abc)=ab+bc+ac можно составить только из тех слагаемых, которые дают согласно нашей Таблице Истинности значение функции, равное "1". Ведь по тождеству X+0=X, и, следовательно, мы можем игнорировать такие слагаемые.

Найдем в Таблице Истинности все наборы, которые дают нам значение функции "1" и отметим их. По свойствам операции "конъюнкция" для трех аргументов результат будет равен "1" только тогда, когда все три аргумента принимают значения, равное "1". Но в нашей таблице истинности это выполняется только для последней строки! В других отмеченных строках есть один, два, а в первой строке даже три нуля! Значит, записывая каждое слагаемое нашей ДНФ, нужно превращать искусственно эти нули в единички при помощи операции отрицания (инверсии). То есть, будем записывать аргументы, имеющие в данном наборе значение "1" в прямом (без значка инверсии), а аргументы, имеющие в данном наборе значение "0" в инверсном виде.

Тогда для нашей Таблице Истинности получается:

a	b	c	F(abc)

Теперь сложим логически (выполним операцию дизъюнкции) полученные варианты записи функции:

Такую ДНФ называют совершенной (СДНФ).

Однако выполненный по такой функции автомат будет насчитывать три элемента НЕ, 10 элементов И и 4 элемента ИЛИ! Это при том, что во всем мире инженеры борются за уменьшение габаритов и энергопотребления проектируемых приборов. Действительно, кому нужен МРЗ-плеер, который не лезет в карман или к которому прилагается два чемодана батареек? Посмотрим, нельзя ли упростить запись нашей ДНФ, выполнив некоторые тождественные преобразования.

Наилучшим образом для преобразования ДНФ подходят тождества склейки и поглощения. При проведении попарных склеек будем учитывать возможность многократной склейки одного и того же члена нашей ДНФ с другими членами согласно тождеству идемпотентности.

Полученную СДНФ функции больше не удается сократить и можно ее назвать Сокращенной Дизъюнктивно-Нормальной Формой - Сокр.ДНФ. Именно к ней мы и должны стремиться как к функции, обеспечивающей Цифровой Автомат из наименьшего числа элементов (см. рис. ниже).

Для проведения сокращения СДНФ имеется удобный и простой алгоритм для выполнения таких склеек, называемый методом карт (диаграмм) Карно-Вейча.

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

Жирной чертой условно выделен столбец или строка карты, в которую указанный аргумент входит в прямом виде, отсутствие такого выделения говорит об инверсном вхождении аргумента в набор. Для функции трех аргументов карта Карно-Вейча с наборами "abc" имеет такой вид:

Разместим на карте Карно-Вейча на месте наборов аргументов соответствующее им значение логической функции из нашей Таблицы Истинности:

Обведем контуром все "единицы" так, чтобы в один контур попало 2ⁿ соседних единиц. Причем соседними считаются и ячейки на крайних противоположных концах карты. При этом объединение по диагонали не допускается! Получим:

	a=1	a=0
b=1	0	1		0
b=0
	c=0	c=1	c=0

Для каждого контура составим член ДНФ для ячеек, "охваченных" нашими контурами. Причем будем указывать только те аргументы из "координат" ячеек, которые входят в контур либо только в прямом, либо только в инверсном виде. Так для верхнего контура аргументы b и c входят в "координаты" охватываемых контуром двух ячеек в прямом виде, а аргумент а - и в прямом, и в инверсном. Он "склеивается", поэтому член ДНФ для первого контура равен только bc.

Аналогично получаем для контура 2, в который аргумент а входит в прямом, а аргумент b - в инверсном виде. Аргумент с склеивается. Получаем член ДНФ .

Аналогично для контура 3, в котором склеивается аргумент а, получаем .

В итоге, не производя аналитических выкладок, мы получили тот же результат:

Помните: чтобы получить Сокращенную ДНФ надо охватить все "единицы" минимальным числом контуров!