4.4.1. Дизъюнктивные нормальные формы

Переменные х₁, х₂, … , х_п и их инверсии назовем литералами и введем обозначение а^, где а^ = а, если  = 1, и а^ =а, если  = 0. Элементарной конъюнкцией K_i является многоместная конъюнкция попарно различных литералов, т. е. K_i = . К элементарным конъюнкциям относятся также одиночные литералы и константа 1 – конъюнкция, состоящая из пустого множества литералов. Число литераловr элементарной конъюнкции называется ее рангом. Элементарная конъюнкция называется полной относительно переменных x₁, x₂, …, x_n, если она содержит символы всех переменных (со знаком отрицания или без него). Ранг таких конъюнкций равен n.

Дизъюнктивная нормальная форма (ДНФ) – это выражение вида K_i, т. е. дизъюнкция элементарных конъюнкций. Примером дизъюнктивной нормальной формы является выражение х₁х₂  х₂ х₃ х₄ х₁ х₃, где две конъюнкции имеют ранг 2 и одна конъюнкция – ранг 3. Одна элементарная конъюнкция также может считаться ДНФ.

Любая булева функция f(x₁, x₂, … , x_n) может быть представлена в следующем виде:

f(x₁, x₂, … , x_n) =f(₁, ₂, … , _n). (4.1)

Последнее выражение является представлением булевой функции f(x₁, x₂, … , x_n) в совершенной дизъюнктивной нормальной форме (СДНФ). Здесь f(₁, ₂, … , _n) является значением функции на наборе значений аргументов (₁, ₂, … , _n), т. е. константой 0 или 1.

Легко построить СДНФ, представляющую произвольную булеву функцию, заданную в табличной форме. Для этого достаточно выделить наборы (₁, ₂, … , _n), на которых функция принимает значение 1, и для каждого из них ввести в СДНФ полную элементарную конъюнкцию, где любая переменная x_i присутствует с отрицанием, если _i = 0, и без отрицания, если _i = 1.

Очевидно, для любой булевой функции f(x₁, x₂, …, x_n), кроме константы 0, существует единственная СДНФ (с точностью до порядка литералов и конъюнкций). Поэтому данная форма представления булевой функции является канонической. Например, СДНФ для функции от трех аргументов, заданной табл. 4.5, имеет следующий вид:

f(x₁, x₂, x₃)  = x₁ х₂х₃    x₁х₂х₃  x₁х₂ х₃ .

Таблица 4.5

Задание функции f (x, y, z)

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