Геометрическая интерпретация днф

Рассмотрим специальную интерпретацию соотношений эквивалентности 1 - 3, которая позволяет лучше понять, почему проводимые с помощью этих правил преобразования ДНФ приводят к получению минимальной ДНФ.

В дальнейшем будем рассматривать булевские функции для фиксированного множества обозначений переменных
{x1, . . ., x n}.

Двоичные числовые наборы длины n поставим в соответствие точкам n-мерного евклидова пространства. Тогда все n-элементные двоичные наборы образуют множество вершин единичного n-мерного куба. Для n = 3 такой куб имеет вид, приведенный на рис. 4.4.

геометрическая интерпретация днф - student2.ru x3011 111

001 101

x2

010110

x1

000 100

Рис 4.4

Для произвольной б.ф. f обозначим как Nf - множество вершин единичного n-мерного куба, в которых f принимает значение 1.

Справедливы следующие свойства таких множеств для произвольных функций f1 и f2:

1) геометрическая интерпретация днф - student2.ru ;

2) геометрическая интерпретация днф - student2.ru .

Элементарная конъюнкция K = геометрическая интерпретация днф - student2.ru , имеющая рангr, принимает значение 1на 2 n-r наборах значений переменных x1, . . . , xn.

Поэтому множество NK, состоящее из вершин единичного n-мерного куба, в которых конъюнкция K равна 1, представляет собой(n – r)-мерную грань куба. Вершины такой грани соответствуют всем двоичным наборам, в которых переменные геометрическая интерпретация днф - student2.ru принимают фиксированные значения геометрическая интерпретация днф - student2.ru , а остальные n - r переменных - произвольные значения. Заметим, что такая грань содержит 2 n-r вершин.

Например, для n = 4 и конъюнкции K = геометрическая интерпретация днф - student2.ru множество NK равно{(0001), (0011), (1001), (1011)}.

Для произвольной ДНФ D = геометрическая интерпретация днф - student2.ru справедливо равенство

N D = геометрическая интерпретация днф - student2.ru .

Это означает, что грани, на которых конъюнкции, входящие в ДНФ, равны 1, образуют покрытие множества ND.

Справедливо и обратное утверждение: всякая (n – r)- мерная грань единичного n-мерного куба представляет собой множество точек, на которых обращается в 1 некоторая конъюнкция рангаr .

Действительно, если некоторая грань единичного n-мерного куба состоит из вершин, в которых значения переменных геометрическая интерпретация днф - student2.ru фиксированы и соответственно равны геометрическая интерпретация днф - student2.ru , а остальные переменные принимают произвольные значения, то соответствующая такой грани конъюнкция имеет вид: геометрическая интерпретация днф - student2.ru .

Например, для n = 5 грань N, состоящая из вершин, в которых переменные x1, x2 и x4 принимают фиксированные значения 1, 0 и 0, а значения остальных переменных произвольные, соответствует конъюнкции: K = геометрическая интерпретация днф - student2.ru .

Следовательно, всякая ДНФ представляющая б.ф. f, порождает покрытие множества N f , и наоборот, всякое покрытие множества Nf гранями единичного n-мерного куба порождает ДНФ, представляющую некоторую б.ф. f.

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

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

Если заданы две конъюнкции K1 и K2 так, что запись K1 является частью записи K2, то для граней геометрическая интерпретация днф - student2.ru и геометрическая интерпретация днф - student2.ru справедливо включение геометрическая интерпретация днф - student2.ru Í геометрическая интерпретация днф - student2.ru Справедливо и обратное соотношение: если геометрическая интерпретация днф - student2.ru Í геометрическая интерпретация днф - student2.ru то запись конъюнкцииK1 является частью конъюнкции записи K2.

Нетрудно видеть, что элементарные конъюнкции, входящие в состав минимальной ДНФ для функции f, должны соответствовать таким граням единичного n-мерного куба, которые содержатся в Nf , но не могут быть расширены.

ОПРЕДЕЛЕНИЕ

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

1)NK ÍN f;

2) геометрическая интерпретация днф - student2.ru , где N - произвольная грань единичного n-мерного куба, то N геометрическая интерпретация днф - student2.ru Nf .

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

ТЕОРЕМА 4.3

Если D = K1 геометрическая интерпретация днф - student2.ru . . . геометрическая интерпретация днф - student2.ru Kr - это минимальная ДНФ для f, то всякая конъюнкция Ki является максимальной для f.

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

Предположим противное. Пусть D = K1 геометрическая интерпретация днф - student2.ru . . . геометрическая интерпретация днф - student2.ru Kr является минимальной ДНФ для некоторой б.ф. f, содержащей конъюнкцию Ki, которая не является максимальной для этой функции. Пусть K - это произвольная максимальная конъюнкция для f, такая что геометрическая интерпретация днф - student2.ru Ì геометрическая интерпретация днф - student2.ru .

Рассмотрим ДНФ D* = K1 Ú. . . Ki-1 Ú K Ú Ki+1. . . ÚKr .

Поскольку геометрическая интерпретация днф - student2.ru Ì геометрическая интерпретация днф - student2.ru Í геометрическая интерпретация днф - student2.ru , то D* º D.

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

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

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

Например, для функции f = x1 ® (x2 ® x3) множество Nf состоит из наборов, соответствующих выделенным вершинам куба, изображенного на рис. 4.5.

геометрическая интерпретация днф - student2.ru x3

011 111

001 101

x2

010 110

000 100 x1

Рис. 4.5

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

N1 = {000, 001, 010, 011} K1 = геометрическая интерпретация днф - student2.ru ;

N2 = {000, 001, 100, 101} K2 = геометрическая интерпретация днф - student2.ru ;

N3 = {001, 011, 101, 111} K3 = x3.

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

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

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

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

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

ОПРЕДЕЛЕНИЕ

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

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

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

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

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

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

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

Наши рекомендации