Определение

Конъюнкция K называется максимальной для функции f, если:

1) N_K N _f;

2) , где N  произвольная грань единичного n-мерного куба, то N N_f .

Грани единичного куба, соответствующие максимальным конъюнкциям функции f , называются максимальными гранями для f.

ТЕОРЕМА 4.3

Если D = K₁ . . . K_r  это минимальная ДНФ для f, то всякая конъюнкция K_i является максимальной для f.

Доказательство

Предположим противное. Пусть D = K₁ . . . K_r является минимальной ДНФ для некоторой б.ф. f, содержащей конъюнкцию K_i, которая не является максимальной для этой функции. Пусть K  это произвольная максимальная конъюнкция для f, такая что  .

Рассмотрим ДНФ D^* = K₁ . . . K_i-1  K  K_i+1 . . . K_r .

Поскольку   , то D^*  D.

Но конъюнкция K короче конъюнкции K_i. Значит, справедливо неравенство L(D^*)  L(D), что противоречит предположению о минимальности ДНФ D.

Следовательно, все конъюнкции минимальной ДНФ D являются максимальными.

Доказательство окончено.

Например, для функции f = x₁  (x₂  x₃) множество N_f состоит из наборов, соответствующих выделенным вершинам куба, изображенного на рис. 4.5.

x₃

011 111

001 101

x₂

010 110

000 100 x₁

Рис. 4.5

Соответствующие максимальные грани и определяемые ими конъюнкции имеют вид:

N₁ = {000, 001, 010, 011} K₁ = ;

N₂ = {000, 001, 100, 101} K₂ = ;

N₃ = {001, 011, 101, 111} K₃ = x_3.

Поскольку ни одна максимальная грань для f целиком не покрывается другими такими гранями, то минимальная ДНФ для f имеет вид .

Рассмотрим введенные ранее соотношения эквивалентности в правилах поглощения, склеивания и обобщенного склеивания.

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

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

Например, без правила обобщенного склеивания невозможно осуществить преобразование ДНФ в ДНФ .

Определение

ДНФ D называется сокращенной ДНФ функции f, если она состоит из всех максимальных конъюнкций для f.

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

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

Возьмем СДНФ для f и последовательно применим к этой дизъюнктивной форме следующие преобразования:

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

2) к полученной в результате первого преобразования ДНФ применимы правила поглощения и склеивания, пока это возможно.

Упражнение. Сформулировать геометрическую интерпретацию правил поглощения, склеивания и обобщенного склеивания в терминах граней единичного n-мерного куба.