12.4. Простые импликанты.

Пусть K(f) - комплекс кубов функции f. Куб uÎK(f) называется простым импликантом, если K(f) не содержит куба, покрывающего куб u. Простые импликанты обозначаются Z(f). В данном примере Z(f)=(10*, **1).

Теорема. Если С - минимальное покрытие, то С состоит только из простых импликантов, т.е. С_min£Z(f).

Действительно, если uÎ С_min и не является простым импликантом, т.е. покрывается кубом vÚK(f), то заменив u на v, получим покрытие меньшего веса, что противоречит минимальности С.

12.5. Экстремали и отмеченные вершины.

Можно ли утверждать, что все простые импликанты входят в минимальное покрытие? Какие из них нужно включить в него обязательно? Ответ на этот вопрос даст следующая теорема .

Назовём вершину отмеченной, если она покрывается только одним простым импликантом, а сам этот импликант назовём экстремалью, и множество всех экстремалей обозначим Е.

Теорема. Каждая экстремаль принадлежит минимальному покрытию E£C_min£Z(f).

Если Е=Z(f), то Е= C_min. Так будет в нашем примере. Вершина 100 является отмеченной для куба (10*), а вершина 001(а также (011)и (111)) для куба (**1). Поэтому Z(f)=(10*, **1)=Е=С_min и f_min=x_1`x_2Úx₃.

Существуют алгоритмы, позволяющие строить множество простых импликантов и экстремалей для функции, зависящей от любого числа переменных. При этом не обязательно экстремали образуют покрытие. В этом случае используются специальные методы извлечения минимального покрытия из множества простых импликантов. Мы же ограничимся разбором различных ситуаций для функции, зависящей от трёх переменных, используя геометрическую интерпретацию.

Заметим, что если f(x₁, x₂, x₃) не является тождественно истинной, то грань, принадлежащая комплексу K(f), а также ребро комплекса, не покрываемое гранью из K(f), является простыми импликантами. Функция f может задаваться как множеством вершин, так и ДНФ, ей равносильной. В последнем случае, используя геометрическую интерпретацию, можно построить комплекс кубов, не находя СДНФ.

Пример 1. Для функции f=x_{1`</sub>x<sub>2Ú`}x₁x_2Úx₃ найти минимальную ДНФ.

Р

x3

x1

x2

ешение. Слагаемому x₃ соответствует грань **1, уравнением которой является х₃=1. Конъюнкции x<sub>1`</sub>x<sub>2</sub> соответствует ребро (10*), являющееся пересечением граней x<sub>1</sub>=1 и х<sub>2</sub>=0. Аналогично конъюнкции `х₁х₂ - ребро, являющееся пересечением граней х₁=0 и х₂=1. Изобразим их на кубе размерности 3.

D

F

A

B

C

E

F

C

E

D

Комплекс кубов содержит простые импликанты - грань BCDE и рёбра AB и DF. Они же являются экстремалями. Для грани отмеченными вершинами будут С и Е, для рёбер А и F соответственно, а потому данная ДНФ является минимальной.

Пример 2. Найти минимальную ДНФ, для функции заданной вершинами А, В, С, D, E, F.

Р

A

B

ешение. Здесь простыми импликантами будут две грани ABCD и AFED. Они же являются экстремалями для отмеченных вершин В и С для ABCD и F и Е для AFED . Уравнениями этих граней будет х₁=1 и х₃=0. Им соответствует f_min=x_1Ú`x₃.

Пример 3. Для функции f=(00111101) построить минимальную ДНФ

Решение. Функция f принимает значение 1 для наборов 010, 011, 100, 101, 111. Изобразим эти вершины на кубе размерности 3. Каждое из рёбер является простым импликантом, т.к. нет граней.

011

A

B

C

E

D

100

101

111

01010

При этом рёбра АВ и DE - экстремали для отмеченных вершин А и Е соответственно, но они не образуют покрытия. Из оставшихся рёбер ВС и CD можно взять любое. Они покрывают оставшуюся вершину С и имеют одинаковую цену. Значит, С_min=(AB, DC, DE). Им соответствует

f_min= x_{1`</sub>x<sub>2Ú</sub>x<sub>1</sub>x<sub>3`}x₁x₂.

Пример 4. Найти минимальную ДНФ для функции, заданной вершинами.

Р

A

B

C

E

D

F

ешение. Здесь все рёбра являются простыми импликантами, но нет экстремалей. Для решения задачи применяется метод "ветвления". Сначала строим минимальное покрытие, содержащее какое-нибудь ребро, например АВ. Это будут рёбра АВ, CD и FE и находим его цену. А затем ищем минимальное покрытие, не содержащее АВ. Это будут рёбра BC, DE, AF. Оба эти покрытия имеют одинаковую цену, и можно взять любое. Тогда ребру ВС соответствует (1*1), ребру DE (01*), и ребру АF -

(*00). f_min=xzÚ`xyÚ`y`z.