Пример 1

Пусть задана ПФ трех (n=3) переменных в виде совершенной ДНФ (СДНФ)

(1)

Карта Карно для данной ПФ (рис.1) состоит из клеток. Каждая клетка карты описывается тремя (n=3) координатами, причем любые соседние клетки отличаются одной координатой [4, 5].

x2
x2
x3
x3
x3
x1
x1
Для минимизации ПФ по «единицам» при определении минимальной ДНФ на карте Карно ставится «1» в клетке, описываемой набором координат, на котором функция принимает единичное значение (рис.2, а). Затем находится покрытие единиц карты Карно минимальным количеством прямоугольников максимальных размеров со сторонами длиной, кратной степени двойки, т.е. , где i, j - целые числа. Минимальное покрытие единиц для функции f1 (см. рис.2, а) выделено Пример 1 прямоугольниками, содержащими и клеток.

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

x2
x2
x1
x1
x3
x3
б)
a)
Отсюда следует, что каждому полученному прямоугольнику карты ставится в соответствии некоторая конъюнкция, в которой отсутствуют переменные, изменяющие в данном прямоугольнике свои значения.

Дизъюнкция элементарных конъюнкций, описывающих полученные на карте Карно (рис.2, а) прямоугольники, образует минимальную ДНФ Пример 1 функции:

Для построения ПФ в виде минимальной КНФ целесообразно произвести минимизацию обратного значения ПФ по «нулям». Для этого на карте Карно в клетки с координатами, соответствующими наборам переменных, на которых ПФ принимает нулевые значения, ставиться «0». Далее для нулевых клеток находится минимальное покрытие.

Карта Карно для обратного значения ПФ , имеет вид (рис. 2, б), ей соответствует минимальная ДНФ

(2)

Поскольку цена покрытия ( количество букв в r-кубах, покрывающих все «1» или «0» Карно) ( ), представляющего обратное значение ПФ меньше цены покрытия ее прямого значения ( ), то минимальная ДНФ для обратного значения ПФ (2) является более простой.

Используя правила Моргана, из (2) получаем минимальную КНФ ПФ:

Пример 2 Пусть ПФ четырех переменных Пример 1 задана в виде комплекса 0-кубов:

x2 x4
x4
x4
x3
x3
x3
x2
x2
a)
x2
x2
x2
б)
x1 x3

Рис. 3. Минимизация переключательной функции f2 четырех переменных


Данной ПФ соответствует СДНФ

и карта Карно (рис.3, а).

Из рис. 3, а следует, что все единицы заданной ПФ покрываются тремя 2-ку-бами, представляющими прямоугольники из четырех соседних клеток карты Карно. Тогда минимальное покрытие ПФ f2 и минимальная ДНФ примут вид

, (3)

Минимизация обратного значения данной ПФ f2 на карте Карно (рис.3, б)

дает КНФ




documentadsjaer.html
documentadsjhoz.html
documentadsjozh.html
documentadsjwjp.html
documentadskdtx.html
Документ Пример 1