с использованием карт Карно

Для минимизации логических функций при небольшом числе переменных целесообразно использовать карты Карно, в которых все возможные комбинации переменных представляются в виде таблиц, по существу, являющихся видоизменением таблиц состояния. Такие таблицы, называемые картами Карно, для двух, трех и четырех переменных приведены на рис. 7.10. Каждая комбинация переменных заносится в таблицу карты таким образом, чтобы комбинации в соседних клетках отличались только одной переменой, на что указывают символы на краях таблиц рис. 7.10. Как и в таблицах состояний, символ «1», заносимый в клетку, соответствует прямому значению переменного, символ «0» - обратному значению. Соседними считаются также крайние клетки каждого столбца и каждой строки (например, клетки с комбинациями переменных и на рис. 7.10.в).

Основой принципа метода минимизации с использованием карт Карно является распределительный закон и тождества (7.1) и (7.4), вследствие которых сумма комбинаций переменных двух соседних клеток может быть заменена одним произведением, содержащим на одно переменное меньше. Если соседними являются четыре комбинации переменных, то их сумма может быть заменена одним произведением, содержащим уже на две переменные меньше.

Первым этапом минимизации логических функций с использованием карт Карно является ее заполнение. Если уже составлена таблица состояний, то ее данные переносятся в соответствующие клетки карты. Если составлена формула логической функции, то в ней должны быть раскрыты скобки и исключены знаки инверсии над суммами переменных. Последнее проводится с использованием формул де Моргана. В окончательном виде формулы должны представлять собой сумму слагаемых, в каждом из которых должно быть одинаковое число переменных. Для обеспечения последнего требования можно использовать тождества 7.2 и 7.8. Например, если в формуле имеется слагаемое с тремя переменными, то оно может быть заменено двумя слагаемыми, являющимися комбинациями четырех переменных:

.

Рисунок 7.10. Карты Карно функций для двух (а),

трех (б) и четырех (в) переменных в комбинации

Каждое слагаемое формулы логической функции вносится в соответствующую клетку карты Карно, как показано на рис. 7.10. Вместо самой комбинации каждого слагаемого формулы в соответствующую клетку вносится заменяющий ее символ «1». В оставшиеся незаполненные клетки карты вносятся символы «0». На рис. 7.11 приведена карта Карно, отражающая формулу (7.13), полученную при решении задачи в предыдущем разделе.

Рисунок 7.11. Карта Карно, отражающая формулу (7.13)

После заполнения карты Карно проводится объединение соседних клеток, содержащих одинаковые символы, в группы с числом клеток, равным 2 ⁿ. Такие группы клеток должны располагаться либо в одной строке, либо в одном столбце. При этом клетки на противоположных границах карты также считаются принадлежащими к одной строке или к одному столбцу соответственно. Например, клетки с комбинациями переменных и на рис. 7.10.в принадлежат одному столбцу. Целесообразно иметь минимальное число групп с наибольшим количеством клеток. На рис. 7.11 сплошными контурами отмечены группы с символами «1», а пунктиром – группы с символами «0».

Последним этапом процесса минимизации логической функции является представление ее формулы на базе выделенных групп наибольшей карты Карно. Эта формула может быть получена двояким образом. Она представляется в виде суммы слагаемых, являющихся комбинациями логических переменных, входящих либо в группы с символами «1», либо в группы с символами «0». В последнем случае получается формула для инверсного значения искомой функции.

Выделенные на карте Карно рис. 7.11 две группы с символами «1», позволяют записать формулу:

которая совпадает с формулой (7.14). Выделение на этой карте двух групп с символами «0» дает:

Как видно, окончательный вид формулы логической функции не зависит от того, на базе какой совокупности групп она получена.

Следует отметить, что не всегда минимизация логической функции с использованием групп с символами «1» и «0» дает одинаковые формулы, хотя они являются равнозначными. Техническая их реализация также будет различной. Полученные различными способами формулы с использованием алгебры логики могут быть преобразованы к одному виду, что не всегда можно просто осуществить.