§ 15. Тупиковые и минимальные д.н.ф.

Начнем с рассмотрения примера. Пусть задана функция, представленная в с.д.н.ф.:

$f(x,y,z)=x\&y\&z∨x\&y\&¬ z∨¬ x\&y\&¬ z∨¬ x\&¬ y\&¬ z$

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

$f(x,y,z) ∼ x\&y∨y\&¬ z∨¬ x\&¬ z.$

В полученной сокращенной д.н.ф. импликанту y&¬z можно исключить. Действительно, умножив y&¬z на x∨¬x (что не изменяет значений y&¬z) и применив операцию поглощения, получим

$f(x,y,z) ∼ x\&y∨ x\&y\&¬ z∨¬ x\&y\&¬ z ∨ ¬ x\&¬ z ∼ x\&y∨¬ x\&¬ z$

В результате получили дизъюнкцию некоторых простых импликант исходной функции. Ясно, что при отбрасывании любой из двух импликант, входящих в (3.24), получим функцию, не равносильную исходной.

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

Некоторые булевы функции имеют несколько тупиковых форм, например, функция $f(x,y,z)=¬ x\&y∨x\&¬ y∨x\&z∨y\&z$ имеет две тупиковых д.н.ф.:

$¬ x\&y∨x\&¬ y∨x\&z и ¬ x\&y∨x\&¬ y∨y\&z$

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

Отметим, что в определении идет речь о минимальном числе вхождений переменных (с отрицанием или без отрицания), а не различных переменных. Например, д.н.ф. x&y∨¬ x&¬ z содержит четыре вхождений переменных, но три различные переменные (x,y,z).

Теорема 3.19. Всякая минимальная д.н.ф. булевой функции f является её тупиковой д.н.ф.

Доказательство. Пусть минимальная д.н.ф. некоторой функции имеет вид:

$f = C_1∨ C_2∨...∨ C_n $

где каждое Ci (1≤ i≤ n) - элементарное произведение. Покажем, что каждое Ci является простой импликантой заданной функции.

Если f обращается в 0 при некоторых значениях своих аргументов, то, очевидно, и каждое Ci (1≤ i≤ n) принимает значение 0, следовательно, каждое Ci является импликантой функции. Далее покажем, что эта импликанта простая, т.е. никакая собственная часть Ci (1≤ i ≤ n) уже не является импликантой.

Допустим, что, например, $C_k (1≤ k≤ r)$ не является простой импликантой. Каждое $C_i (1≤ i≤ n)$, в том числе и $C_k$, по доказанному, является импликантой функции f. Так как по допущению $C_k$ не является простой импликантой (но импликанта для f), то некоторая ее часть будет простой импликантой для f, т.е. $C_k$ может быть представлена в виде $C_k = C_k’\&C_k*$, где $C_k*$ - простая импликанта. Заменим правую часть (3.25) на равносильную:

$C_1∨ C_2∨...∨ C_n∨ C_k*$

В выражении (3.25) в качестве дизъюнктивного члена содержатся все простые импликанты, тогда при некотором $i: C_i=C_k*$, но тогда $C_k$ должна поглощаться членом $C_i$:

$C_i∨C_k = C_i ∨C_k’\&C_k* ~ C_i$

В результате получим, что

$f = C_1∨ C_2∨...∨ C_{k-1}∨ C_{k+1}∨...∨ C_n.$

Получили д.н.ф., которая содержит меньше вхождений переменных, чем в (3.25), что противоречит минимальности (3.25). Это противоречие и доказывает, что все слагаемые минимальной д.н.ф. являются простыми импликантами.

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

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

Для отыскания тупиковых, следовательно, и минимальных д.н.ф. существует несколько методов.