Дизъюнктивные формы представления ЛФ

Конъюнкция любого числа двоичных переменных х₁, х₂,..., х_п называется элементарной, если сомножителями в ней являются либо одиночные аргументы, либо отри­цания одиночных аргументов.

Например, конъюнкции х₂ и х₁ х₃ являются элементарными,

а конъюнкции х₁ и х₃ ими не являются.

Очевидно, что символ любой переменной в элементарной конъюнкции может встречать­ся только один раз, так как произведение переменной на себя равно этой же переменной (по правилу повторе­ния), а произведение переменной на свое отрицание равно нулю.

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

Напри­мер, ЛФ F = х₂ + х₂ + х₄ записана в ДНФ, так как она представляет собой логическую сумму элементарных конъюнкций.

Число переменных, входящих в элементарную конъюнкцию, определяет ранг этой конъюнкции.

Напри­мер, - х₂ — конъюнкции 1-го ранга;

- х₂, х₃ -конъюнкции 2-го ранга и т. д.

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

Полученные произведения, которые носят названия конституанты единиц, или минтермов, суммируют.

Пример 3.4 Найти ДНФ для логической функции 3-х переменных, которая равна единице в случае, если хотя бы две из входных переменных равны 1.

№	х2	х1	х0	f

· Запишем эту функцию в виде таблицы истинности:

· В последнем столбце отмечаем «1» те строки, которые удовлетворяют условию задания.

· Для написания ДНФ ЛЭ используем строки, логическая функция которых равна «1».

· Это строки: 3, 5, 6, и 7 таблицы.

· ДНФ для данной логической функции имеет вид:

F (х₂, х₁, х₀) = ₂х₁х₀ + х_{2 1}х₀ + х₂х_{1 0} + х₂х₁х₀

ДНФ, полученная суммированием конституанта единицы, называют совершенной СДНФ.

Совершенной ДНФ (СДНФ) логической функцией, имеющей п аргу­ментов, называется такая форма, в которой все конъюнк­ции имеют ранг п.

Или совершенной (СДНФ) логической функции имеющей n аргументов (х₁, х₂,..., х_п) называется такая форма в которой все конъюнкции содержат n аргументов.

Например, ЛФ f₁ = + х₂ - ДНФ, т.к. каждая конъюнкция содержит не все переменные (или их отрицания) входящих в логическую функцию по одному разу,

а ЛФ - f₂ = + х₂ - СДНФ, т.к. каждая конъюнкция содержит все переменные (или их отрицания) входящих в логическую функцию причем по одному разу.