Понятие карты Карно

Карта Карно — графический способ минимизации булевых функций, обеспечивающий относительную простоту работы с большими выражениями. Способ представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

Пример карты Карно

Рис. 3.3. Пример карты Карно

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

Принципы минимизации с помощью карт Карно

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами

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

Аналогично для КНФ:

В

озможность поглощения следует из очевидных равенств:

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

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную /V-мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке 3.4 изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2- мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

Таблица истинности для булевой функции двух переменных

Рис. 3.4. Таблица истинности для булевой функции двух переменных

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке 3.5 в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.

Таблица истинности и куб для булевой функции трёх переменных

Рис. 3.5. Таблица истинности и куб для булевой функции трёх переменных

Как видно из рисунка 3.5, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

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

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом, появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Куб для булевой функции трёх переменных

Рис. 3.6. Куб для булевой функции трёх переменных

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N-5 приведены на рисунке 3.7. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4x4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4x4 являются соседними, и соответствующие им термы можно склеивать.

Таблица истинности для булевой функции трёх переменных

Рис. 3.7. Таблица истинности для булевой функции трёх переменных

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути, карта Карно — это таблица истинности, составленная в 2-х мерном виде. Благодаря использованию кода Г рея в ней, верхняя строка является соседней с нижней, а правый столбец — соседним с левым, и вся карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того, как карта заполнена, можно приступать к минимизации.

Если необходимо получить минимальную ДНФ, то в карте рассматриваем только те клетки, которые содержат единицы. Если работа идет с КНФ, то рассматриваются те клетки, которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

  • 1. объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала 2 клеток (п — целое число в диапазоне О...оо). Необходимо помнить про то, что крайние строки и столбцы являются соседними между собой, в области не должно находиться клеток, содержащих нули;
  • 2. область должна располагаться симметрично оси (ей) (оси располагаются через каждые четыре клетки);
  • 3. несмежные области, расположенные симметрично оси (ей), могут объединяться в одну;
  • 4. область должна быть как можно больше, а количество областей как можно меньше;
  • 5. области могут пересекаться;
  • 6. возможно несколько вариантов покрытия.

Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неизменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.

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

  • 1. Чем являются основные элементы булевой алгебры? На какие группы по количеству операндов делятся логические функции?
  • 2. Перечислите основные булевы функции. К каждой функции подберите пример.
  • 3. Перечислите производные булевы функции. К каждой функции подберите пример.
  • 4. Приведите примеры применения булевых функций.
  • 5. Каков приоритет выполнения булевых операций? Приведите примеры вычисления булевых функций с учетом приоритета операций.
  • 6. Назовите переместительный, сочетательный и распределительный законы логики.
  • 7. Перечислите законы де Моргана. Приведите примеры применения.
  • 8. Что такое карты Карно? Приведите пример применения.
  • 9. Назовите основные принципы минимизации. Приведите пример минимизации.
  • 10. Что такое СКНФ? Приведите пример составления СКНФ по таблице истинности.
  • 11. Что такое СДНФ? Приведите пример составления СДНФ по таблице истинности.
  • 12. Опишите правила получения КНФ функции по карте Карно.
  • 13. Составить таблицу истинности для следующего выражения:

14. Составить таблицу истинности для следующего выражения:

15. Составить таблицу истинности для следующего выражения:

16. По таблице истинности восстановите логическое выражение:

X

У

f

0

0

1

0

1

0

1

0

0

1

1

1

17. Упростите следующее логическое выражение:

  • 18. Упростите логические выражения из задания 13.
  • 19. Составьте КНФ по данной карте Карно:

ХЗХ4

00

01

11

10

Х1Х2

00

0

0

1

1

01

0

0

1

1

11

1

1

1

0

10

1

1

0

1

20. Составьте ДНФ по данной карте Карно:

ХЗХ4

00

01

11

10

Х1Х2

00

0

1

1

0

01

0

1

1

0

11

0

0

0

0

10

1

0

0

1

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >