5.Постановка задачи минимизации в геометрической форме.

Обозначим через Еⁿ множество всех наборов из 0 и 1. Это множество будем рассматривать как множество всех вершин единичного n –мерного куба. Само множество Еⁿ будем называть единичным n – мерным кубом. Количество вершин куба Еⁿ равно 2ⁿ.

0-мерный куб – это одна вершина или точка.

Одномерный куб – Е¹ , множество вершин {(0), (1)}:

Двухмерный куб – Е² , множество вершин {(00), (01), (10), (11)}:

Т рехмерный куб – Е³ , множество вершин {(000), (001), (010), (001), (110), (011), (101), (111)}:

Четырехмерный единичный куб – Е⁴ :

Пятимерный единичный куб – Е⁵ :

Заметим, что наборы , соответствующие соседним вершинам куба, т.е. вершинам, которые соединяются ребром, отличаются значением только какой –либо одной координаты, как соседние ячейки карты Карно.

Далее введем понятие грани куба.

Пусть _i1 , _i2, _i3,…, _ir фиксированная система чисел из 0 и 1 такая, что Множество всех вершин куба Е^п таких, что _i1= _i1 , _i2 =_i2, _i3= _i3,…, _ir= _ir называется (n –r) – мерной гранью.

Введем в рассмотрение множество N_f всех вершин куба таких, что По этому множеству можно однозначно восстановить саму функцию.

Пример: Функции f(x, y, z) соответствует множество N_f = {(000), (100), (101), (110), (111)}.

По данному множеству восстановим булеву функцию:

Графическое представление множества N_f :

Рассмотрим какую –либо элементарную конъюнкцию К из ДНФ функции n –переменных, состоящую из r множителей. Сопоставим ей множество таких наборов, при которых эта конъюнкция равна 1. Обозначим это множество N_k. Полученное таким образом множество называется (n –r) –мерной гранью куба Еⁿ . Количество множителей – r в конъюнкции называется ее рангом . Ранг конъюнкции является и рангом соответствующей грани.

Пример: Дана ДНФ каrой-либо фукнции f(x, y, z) :

Составим для каждой конъюнкции множество N_ki:

N_k1= {(100), (101)} – это 3-2=1 – одномерная грань трехмерного куба, ранг равен 2;

N_k2= {(010), (110), (011), (111)} – это 3-1 = 2 – одномерная грань трехмерного куба, ранг - 1;

N_k3= {(011)} – это 3-3=0 – нольмерная грань трехмерного куба, ранг -3.

Легко заметить, что чем меньше ранг конъюнкции. Тем больше мерность соответствующей грани.

Свойства соответствия между f и N_f:

Если f(x₁, x₂, …, x_n) = g(x₁, x₂, …, x_n)Vh(x₁, x₂, …, x_n), то:

1. N_g  N_f , N_h  N_f;

2. Nf = N_g  N_h .

В частности следует. Что если f – есть ДНФ: f = К₁V К₂ V…VК_s, то из указанных свойств следут, что Nki  Nf, т.е. Nki – это грань расположенная внутри множества N_f и :

N_f = N_k1 N_k2 …N_ks, т.е. множество N_f покрывается гранями N_k1, N_k2 ,…,N_ks .

Если грани N_ki имеют ранги ri (i = 1-s), то ранг всего покрытия равен

Теперь сформулируем задачу минимизации в геометрической форме (задача о покрытии):

Найти для данного множества N_f такое покрытие гранями N_ki, чтобы его ранг был наименьшим.

Пример:

Составим множество N_f ={(000), (100), (101), (110), (100)}

Данное множество имеет точечное покрытие, соответствующее СДНФ, состоящее из 5 нольмерных граней. Используя закон склеивания можно минимизировать СДНФ. Графически эту задачу можно решить так: объединить вершины из множества N_f по возможности в грани большей мерности, а значит меньшего ранга. Покажем это на рисунке:

Вершины нижнего основания можно объединить в одну двухмерную грань {(100), (110), (010), (000)}, которой соответствует конъюнкция ; соседние вершины (100) и (101) соединим в одну одномерную грань {(100), (101)}, которой соответствует конъюнкция

Значит, данное множество имеет еще одно покрытие одной двухмерной и одной одномерной гранями, а СДНФ равносильна ДНФ: v