ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДНФ

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

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

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

x₃011 111

001 101

x₂

010110

x₁

000 100

Рис 4.4

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

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

1) ;

2) .

Элементарная конъюнкция K = , имеющая рангr, принимает значение 1на 2 ^n-r наборах значений переменных x₁, . . . , x_n.

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

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

Для произвольной ДНФ D = справедливо равенство

N _D = .

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

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

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

Например, для n = 5 грань N, состоящая из вершин, в которых переменные x₁, x₂ и x₄ принимают фиксированные значения 1, 0 и 0, а значения остальных переменных произвольные, соответствует конъюнкции: K = .

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

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

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

Если заданы две конъюнкции K₁ и K₂ так, что запись K₁ является частью записи K₂, то для граней и справедливо включение Í Справедливо и обратное соотношение: если Í то запись конъюнкцииK₁ является частью конъюнкции записи K₂.

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

Дата добавления: 2014-11-15; просмотров: 462; Нарушение авторских прав

Мы поможем в написании ваших работ!