Метод кубов

Рассмотрим минимизацию булевых функций с помощью метода кубов.

В качестве предварительной задачи рассмотрим метод кубов для двух переменных. В этом случае куб вырождается в квадрат.

Каждой точке соответствует определенный набор значений переменных и определенный минитерм.

Причем движение по координате x,y … соответствует переменной в прямом виде, отсутствие движения соответствует переменной в инверсном виде (для минитермов).

Каждая точка соответствует двухбуквенному выражению. Двум точкам, лежащим на одном ребре, соответствует одна переменная. Например, верхние точки: , нижние точки: . Слияние происходит по той переменной, направление которой параллельно ребру. Это позволяет упрощать былевые выражения. В отличие от диаграмм Эйлера-Венна каждому минитерму и строке значений переменных соответствует не область, а точка на кубе или квадрате.

Рассмотрим метод кубов для трех переменных. Совокупность минитермов и наборов значений соответствуют 8 точкам, находящихся в вершине куба. Поясним сказанное следующим примером.

Т.1 соответствует набору 000 и минитерму ,

Т. 2 – 001 и ,

…

Т. 7 – 110 и ,

Т. 8 – 111 и .

Каждой точке соответствует трехбуквенное выражение. Каждому ребру (2-м точкам) соответствует двухбуквенное выражение. Например, ребро т. 1 и т. 3 соответствуют (от y не зависит), ребро т. 6 и т. 8 соответствует xy. Каждой грани соответствует одна переменная. Например, т. 5 + т. 6 + т. 7 + т. 8 - это x,

т. 2 + т. 4 + т. 6 + т. 8 – z.

Рассмотри минимизацию функции и представлении ее в виде СДНФ на конкретном примере.

Пусть .

Выясним, можно ли ее упростить. Выражению AC соотв. т.6 и т.8, AB ─ т.7 и т.8, ─ т.3 и т.7.

Функции соответствует объединение всех точек: т.3+т.6+т.7+т.8. Точкам 3 и 7 соответствует , т.6 и т.8 ─ AC. Следовательно, точки 3, 7, 6, 8 соответствует выражению . Нам удалось упростить функцию, исключив ребро (т.7 и т.8), т.к. эти точки входят в другие ребра.

Получим СДНФ; F=т.3+т.6+т.7+т.8 . Остальные задачи (получение СКНФ, переход от табличной к алгебраической форме и т.д.) решаются также как и в диаграммах Эйлера-Венна.

Для 4-х переменных строится гиперкуб.

Внешний куб соответствует (D =0), считается, что движения по D нет. Внутренний куб соответствует D (D=1), движение по оси D есть. Остальные все приемы такие же, как и для случая третьих переменных.

Каждая точка соответствует минитерму ─ четырехбуквенному выражению. Две точки, лежащие на одном ребре, соответствуют трехбуквенному выражению. Можно провести слияние по той переменной, направление которой параллельно ребру. Ребра, совпадающие с направлением D - это ребра, соединяющие вершины внешнего и внутреннего кубов.

Четыре точки, лежащие на одной грани, соответствуют двум переменным. Например, нижняя грань внешнего куба ─ , верхняя грань внутреннего куба ─ DC.

Восемь точек, лежащих на внешнем или внутреннем кубе, усеченных пирамидах (все они называются гиперквадратами в 4-х мерном пространстве) соответствуют одной переменной. Например, нижняя усеченная пирамида соответствует , верхняя ─ С.

Шестнадцать точек образуют гиперкуб и соответствуют F≡1 (для всякого набора значений переменных функция равна единице).

Таким образом, уже для 4-х переменных метод кубов оказывается достаточно громоздким. Поэтому для 4-х и более переменных часто применяют модернизированный метод кубов, в котором развертка куба или гиперкуба изображается на плоскости.

Случай 2-х переменных:

Случай 3-х переменных. Для получения развертки куба зеркально отобразим квадрат относительно вертикальной оси. Пусть левой половине соответствует z=0 (в минитермах ), правой половине z=1 (в минитермах z).

При этом некоторые ребра изображаются изогнутыми линиями.

Случай 4-х переменных. Надо зеркально отразить развертку куба для трех переменных относительно горизонтальной или вертикальной оси. Тогда одна половина будет соответствовать W=0, другая W=1.

Аналогично подстраиваются развертки гиперкубов для 5-ти и более переменных. На рисунке ребра указываются линиями. Однако имеется сложность в определении граней и гиперквадратов.

3. Карты Карно

Карты Карно являются модификацией диаграммы Эйлера-Венна, но в более удобном виде. Эффективны для n ≤ 6. Каждый столбец и каждая строка в картах Карно соответствует определенному значению переменной (единица или ноль). Каждая клетка соответствует определенному набору переменных, т. е. определенной строке таблицы истинности и определенному минитерму. Две соседние клетки отличаются друг от друга значением только одной переменной. Поэтому объединение клеток позволяет исключить ту переменную, которой они отличаются. Например, .

Работа с картами Карно основана на аналогии: дизъюнкция ─ объединение (клеток), конъюнкция ─ пересечение (областей, состоящих из клеток). Таким образом, карты Карно похожи на диаграммы Эйлера-Венна и метод кубов, но в них вместо областей (подмножеств) и углов гиперкубов используются клетки карты.

n=2 n=3

n=4 n=5

Для n=6 надо к таблице для n=5 снизу пририсовать еще такую таблицу. Верхняя часть (4 строки) соответствует (0), нижняя часть ─ F(1).

Внутри каждой клетки минитермы и наборы переменных не пишут (они и так быстро определяются), а ставят 1, если значение функции равно 1, и 0, если значение функции равно нулю. Примеры для n=4:

Переход от таблицы истинности к картам Карно и алгебраическому виду

Каждая клетка соответствует строке таблицы истинности, поэтому в карты Карно переносят 1 и 0 из таблицы истинности. Т.к. каждая клетка соответствует определенному минитерму, то алгебраический вид можно поучить в виде СДНФ, как дизъюнкцию тех минитермов, для которых в карте Карно стоят 1.

Дата добавления: 2015-05-06