Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

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

Минимизация по картам Карно

Хотя табл. 1.12 более громоздка, чем табл. 1.11, метод сочетания индексов не считается более сложным, чем метод Куайна, если помнить, что до составления таблиц Куайна необходимо произвести многочисленные склейки конституент и импликант. Реализация на компьютере алгоритма метода сочетания индексов оказывается сравнительно простой. И напротив, внешняя простота и наглядность третьего метода минимизации логических функций с помощью карт Карно оборачивается сложной программой при реализации алгоритма на компьютере.

Карта Карно для четырех переменных представлена табл. 1.13. Каждая клетка карты соответствует конституенте. Заполненная карта представлена табл. 1.14 (функция взята та же, что и в первых двух методах). Согласно закону склеивания, две смежные конституенты с единичными значениями всегда можно объединить для получения соответствующей импликанты. Причем смежными считаются и те, которые лежат на границах карты. Какие именно единицы требуется объединить для получения подходящей импликанты, легко определить визуально. Следует также помнить, что в соответствии с законом идемпотентности одна и та же единица табл. 1.14 может склеиваться с двумя или тремя смежными единицами.

Таблица 1.13

Таблица 1.14