2015-05-13
616
Опишем процедуру построения комплекса кубов данной функции f. Она соответствует операции построения всевозможных элементарных конъюнкций, которые могут входить в равносильную ей ДНФ.
Пусть функция f представлена вершинами k-мерного куба. Множество всех этих вершин, называемых 0-кубами, обозначим K0.. Для рассматриваемой в примере функции K(f)0={101, 100, 111, 011, 001}. Каждой такой вершине соответствует элементарная конъюнкция веса 3 и наоборот. Так, вершине 001 соответствует`x1`x2x3.
Будем говорить, что две вершины (0-кубы) образуют ребро (1-куб), если они отличаются только одной координатой, например, i-ой. Тогда ребро имеет те же самые общие координаты (они называются связанными) и свободную i-ую координату, которая может принимать 2 значения 0 и 1 и обозначается символом "*". При этом говорят, что ребро покрывает эти вершины. Например, вершины 011 и 001 образуют ребро 0*1. Этой процедуре соответствует операция `x1x2x3Ú`x1`x2x3º`x1x3.
Множество всех рёбер обозначим K(f)1. В данном случае K(f)1={10*, *01, 0*1, *11, 1*1} и ребро 0*1 покрывает вершины 001 и 011. Любому ребру соответствует элементарная конъюнкция веса K-1 и наоборот.
|
|
|
Два ребра образуют грань (2-куб), если у них одинаковая свободная координата, а связанные отличаются только в одном месте. Например, Рёбра *01 и *11 образуют грань **1. Грань покрывает уже 4 вершины. Аналогично определяются кубы любой размерности. Так две грани **011 и **001 образуют 3-куб **0*1, покрывающий уже 8 вершин и т.д.
Заметим, что если K=3 и f не тождественно истинна, то нет кубов размерности 3 и больше. Объединение всех таких кубов и составляет комплекс кубов функции f. Он обозначается K(f).
Покрытие. Минимальное покрытие.
Пусть f - булева функция, K(f) - её комплекс кубов и C£K(f) - некоторое подмножество кубов. С называется покрытием комплекса K(f), если для любой вершины из K0 существует куб сÎС, покрывающий эту вершину.
Из определения вытекает, что покрытию С комплекса K(f) соответствует ДНФ, равносильная данной функции f. Весом куба назовём число его связанных компонент, т.е. вес соответствующей ему конъюнкции, а весом покрытия - сумму весов всех входящих в него кубов. Следовательно, вес покрытия - это вес, соответствующей ему ДНФ. Минимальным покрытием называется покрытие минимального веса, и ему соответствует минимальная ДНФ. В данном примере можно построить 3 покрытия. С1=(100, **1), С2=(*01, *11, 10*) и С3=(10*, **1). Их веса |C1|=3+1=4, |C2|=2+2+2=6, |C3|=2+1=3. Отметим, что покрытию С1 соответствует ДНФ x1`x2`x3Úx3 веса 4, покрытию С2 - `x2x3Úx2x3Úx1`x2 веса 6 и покрытию С3 x1`x2Úx3 веса 3, и все эти ДНФ равносильны данной функции. Мы увидим дальше, что С3 - минимальное покрытие, а x1`x2Úx3 - минимальное ДНФ.
