Дискретная математика

В полученной квадратной таблице каким-либо символом (например, 1 или ) отмечают только вершины, принадлежащие носителю. Чтобы соответствие номеров наборов носителя и элементов карты Карно было взаимно однозначным, вектор значений функции размещают в таблице Карно следующим образом:

Первую четверку значений записывают в первую строку, поменяв местами пару последних значений в четверке. Аналогично поступают со второй четверкой. Это обусловлено переменой мест значений 11 и 10 переменных x3 и x4.

Третью четверку вектора значений функции располагают в четвертой строке, а четвертую- в третьей, не забыв поменять местами 3 и 4 элемент в каждой четверке. Такое расположение координат вектора значений функции связано с тем, что значения 11 и 10 у переменных x1 и x2 в карте Карно поменяли местами.

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

Пример 6.1. Изобразить с помощью карты Карно двоичную функцию fe= (1000 0101 1100 0111).

Решение.

1. В первых двух четверках вектора значений

xy

функции ( 1000 и 0101 ) меняем местами 1000 7→1000

последние две цифры и записываем их в

xy

две первых строки карты Карно (указываем 0101 7→0110 только наборы носителя!):

2. Третью четверку (1100), поменяв местами

xy

третий и четвертый элементы, помещаем 1100 7→1100

в четвертую строку таблицы.

3.В четвертой четверке (0111) меняем местами

xy

два последних значения и записываем её в 0111 7→0111 третью строку карты Карно.

91

4. Получим следующую таблицу.

5.Убедимся, что булева функция изображена верно. Для этого найдем носитель функции.

Nf =

= { (0000), (0101), (0111), (1000), (1001), (1101), (1110), (1111) }.

Рассмотрим первый по порядку набор носителя ( (0000) ). Все четыре переменные входят в этот набор с нулевыми значениями. Это означает, что символ "1\, соответствующий данному набору, находится на пересечении первой строки (эта строка соответствует нулевым значениям первых двух переменных) и первого столбца (нулевые значения переменных x3 и x4).

Элемент карты Карно, соответствующий набору (0101), расположен на пересечении второй строки и второго столбца, так как на этом наборе x1x2 = x3x4 = 01.

Следующему по порядку набору носителя, (0111), соответствует символ "1\, который является пересечением второй строки (x1x2 = 01) и третьего столбца (x3x4 = 11).

Два следующих набора носителя ( (1000) и (1001) ) располагаем в четвертой строке, так как эта строка соответствует единичным значениям переменных x1 и x2, в первом (x3x4 = 00) и втором (x3x4 = 01) столбцах соответственно.

Остальные наборы помещаем в третью строку, так как переменные x1 и x2 на этих наборах входят со значениями, равными 1. Столбцы,на пересечении которых расположены данные элементы таблицы, соответствуют значениям переменных x3 и x4.

92

6.2Алгоритм Карно минимизации булевых функций

Алгоритм Карно рассмотрим на следующем примере.

Пример 6.2. Минимизировать с помощью карты Карно двоичную функцию fe= (1000 0101 1100 0111) из примера 6.1 .

Решение.

1.Изобразим булеву функцию с помощью карты Карно (см. пример 6.1) .

2.Объединим вершины носителя в максимальные интервалы. Максимальными интервалами являются прямоугольные фигуры, покрывающие 2n наборов, стоящих рядом, например:

•24 = 16 вершин, образующих квадрат 4 × 4 (весь булев куб

B4)

•23 = 8 вершин, образующих 2 рядом стоящие строки или 2 столбца (напомним, соседними являются также 1 и 4 строки и столбцы)

93

94