Совершенная дизъюнктивно нормальная формы

Если ДНФ функции f1(x₁,x₂,…,x_n) от n переменных в каждой своей конъюнкции содержит все n переменных либо их отрицания, то это совершенная дизъюнктивная нормальная форма (СДНФ). Для перехода от ДНФ к СДНФ необходимо в каждый из членов, в которых представлены не все аргументы, ввести выражение вида , где x_i - отсутствующий в члене аргумент. Так как , такая операция не может изменить значений функции [12].

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

Для n переменных составляют q=2ⁿ минтермов: m₀, m₁,... , m_q-1.

Алгебраическое выражение логической функции в форме СДНФ представляют в форме суммы:

, (2.2)

где f_i, m_i - значение функции (0 или 1) и минтерм, соответствующий i- ому набору переменных.

Для перехода от табличного представления функции к алгебраическому в виде совершенной конъюнктивно нормальной формы (СКНФ) каждому i-ому набору переменных ставится в соответствие макстерм (M_i) - дизъюнкция переменных, которые входят либо в прямом виде, если значение данной переменной равно 0, либо в инверсном виде, если значение переменной равно 1.

Алгебраическое выражение логической функции в форме СКНФ представляют в виде произведения

, (2.3.)

где f_i, M_i - значение функции и макстерм, соответствующий i-ому набору переменных [13-15].

Пример 2.3. Дана функция _. Показать переход от ДНФ к СДНФ.

Решение. Добавление в члены выражений в виде приведет к функции

На основании свойств операций конъюнкций и дизъюнкций

.

Отсюда после приведения подобных членов имеем СДНФ

.

Пусть исходная функция задана в виде таблицы истинности:

Для этой функции СДНФ имеет вид

Каждый член в этой таблице соответствует некоторому набору значений аргументов, при котором f(x1,x2,x3) равна 1. Каждый из наборов аргументов, при которых f(x1,x2,x3) равна 1, обращает в единицу соответствующий член полученной СДНФ, вследствие чего и вся функция оказывается равной единице.

Пример 2.4. По заданной таблице истинности построить логическое выражение и упростить его.

Решение. 1.Выбираем строки, в которых F=1, и строим для них минтермы.

1 строка

2 строка

3 строка

1. Объединяем минтермы:

3. Упрощаем логическое выражение:

Пример 2.5. Упростить совершенную ДНФ для импликации.

Решение. Импликация может быть определена по формуле

( ) ( ) ( ).

Упростим правую часть равенства. Применяя тождества 3б, 1а, 4а, 1б, 4 г, получим

( ) ( ) ( ( )) (

)) ( ( ) (

(

Пример 2.6. Пусть функция Y задана таблицей:

Х1	X2	X3	Y	Минтерм	Макстерм	ЗначениеYi
						Y1=0
						Y2=0
						Y3=0
						Y4=0
						Y5=0
						Y6=1
						Y7=1
						Y8=1

Алгебраическая форма записи данной функции:

.

Число слагаемых при использовании СДНФ равно количеству строк таблицы истинности, в которых Y_i=1.

С использованием СКНФ выражение функции Y будет:

Число сомножителей в СКНФ равно числу строк, в которых Y_i=0.

Если число строк в таблице истинности, содержащих Y_i=1, меньше числа строк, содержащих Y_i=0, то целесообразно использовать СДНФ, если наоборот, то СКНФ.

Пример 2.7. Логическая функция равнозначность (эквивалентность) для двух переменных представлена таблицей. Представить эту функцию в алгебраической форме в виде СДНФ и СКНФ.

Решение.1. Для n=2 переменных составляют q = 2ⁿ = 4 минтерма и макстерма, которые вписаны соответственно в 3-ю и 4-ю графы таблицы 2.2.

Таблица 2.2.

x1	x2	mi	Mi	f

2. Алгебраическое представление логической функции в СДНФ

3. Алгебраическое представление логической функции в СКНФ

Пример 2.8. Представить в СДНФ логическую функцию пяти аргументов f(x₁,x₂,x₃,x₄,x₅), равную единице на следующих четырех наборах

Решение. 1. Запишем четыре произведения аргументов, связанных знаком дизъюнкции, и под каждым из них - один из перечисленных наборов

2. Расставляя отрицания над аргументами, равными нулю, получим СДНФ логической функции:

Ú Ú Ú

Пример 2.9. Представить в СКНФ переключательную функцию четырех аргументов f(x₁,x₂,x₃,x₄) , равную нулю на наборах

Решение.1. Запишем четыре произведения дизъюнкций всех аргументов и под каждым из них один из перечисленных наборов:

2. Расставляя знаки отрицания над аргументами, равными единице, получим СКНФ логической функции:

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