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

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

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

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

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

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

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

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

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

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

Пусть s_i1, s_i2, s_i3,…, s_ir фиксированная система чисел из 0 и 1 такая, что Множество всех вершин куба Е^п таких, что a_i1= s_i1, a_i2 =s_i2, a_i3= s_i3,…, a_ir= s_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