Правила минимизации с использованием диаграмм Вейча (карт Карно)

 

В диаграммах Вейча (картах Карно) таблица истинности булевой функции представляется в виде координатной карты состояний, которая содержит 2ⁿ клеток (по числу входных наборов булевой функции n переменных). Переменные функции разбиваются на две группы так, что одна группа определяет координаты столбца карты, а другая – координаты строки.

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

При минимизации булевых функций с помощью диаграмм Вейча (карт Карно) используют следующие правила.

1 В карте Карно группы единиц (для получения ДНФ) и группы нулей (для получения КНФ) необходимо обвести четырехугольными контурами. Внутри контура должны находиться только одноименные значения функции. Этот процесс соответствует операции склеивания или нахождения импликант данной функции.

2 Количество клеток внутри контура должно быть целой степенью двойки (1, 2, 4, 8, 16...).

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

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

5 Все единицы (нули) в карте (даже одиночные) должны быть охвачены контурами. Любая единица (нуль) может входить в контуры произвольное количество раз.

6 Множество контуров, покрывающих все 1 (0) функции, образуют тупиковую ДНФ (КНФ). Целью минимизации является нахождение минимальной из множества тупиковых форм.

7 В элементарной конъюнкции (дизъюнкции), которая соответствует одному контуру, остаются только те переменные, значение которых не изменяется внутри обведенного контура. Переменные булевой функции входят в элементарную конъюнкцию (для значений функции 1) без инверсии, если их значение на соответствующих координатах равно 1, и с инверсией – если 0. Для значений булевой функции, равных 0, записываются элементарные дизъюнкции, куда переменные входят без инверсии, если их значение на соответствующих координатах равно 0, и с инверсией – если 1.

Пример – Пусть функция f(x, y, z) = 1 на наборах 0, 1, 2, 3, 6, 7, 8, 15. Диаграмма Вейча для заданной функции представлена на рисунке 3.

 

 

Рисунок 3 – Минимальная ДНФ на диаграмме Вейча

 

Единицы функции, стоящие в соседних клетках, отличаются значением только одной переменной, следовательно, они склеиваются по этой переменной и образуют импликанту. В этом случае говорят, что импликанта покрывает соответствующие единицы булевой функции. Например, две единицы на наборах 7 и 15 покрываются импликантой yzt.Четыре единицы на наборах 2, 3, 7, 6 – импликантой . При этом соседними считаются также клетки, стоящие вдоль левого и правого края диаграммы (отличаются значением у)и вдоль верхнего и нижнего края (отличаются значением x).

При минимизации булевой функции на диаграмме Вейча сначала находят покрытия, содержащие максимальное число единиц (8, 4, 2), а затем покрытия, накрывающие оставшиеся единицы таким образом, чтобы они также были максимальны по величине и при удалении этого покрытия хотя бы одна единица функции осталась непокрытой. При этом некоторые единицы могут быть покрыты неоднократно.

Для функции, представленной на рисунке 3, минимальная ДНФ

 

.

 

Минимальная КНФ строится двойственно по диаграмме Вейча, заполненной нулями в пустых клетках. Для данной функции минимальная КНФ

 

.

 

⇐ Предыдущая123Следующая ⇒

Поделиться: