Метод минимизирующих карт Карно
Карты Карно – это графическое представление таблиц истинности логических функций. Они содержат по 2n ячеек, где n—число логических переменных. Например, карта Карно для функции трёх переменных содержит Карта размечается системой координат, соответствующих значениям входных переменных. Обратим особое внимание на то, что координаты столбцов (а также и строк, если n >3), следуют не в естественном порядке возрастания двоичных кодов, а так: 00 01 11 10. Это делается для того, чтобы соседние наборы (в том числе и столбцов 1 и 4) отличались лишь одной цифрой в каком либо разряде. Процесс минимизации заключается в формировании правильных прямоугольников, содержащих по 2к ячеек, где к—целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям (т. е. отличаются только в одном разряде). Несмотря на то, что карты Карно изображаются на плоскости, соседство квадратов устанавливается на поверхности тора. Верхняя и нижняя границы карты как бы склеиваются, образуя поверхность цилиндра. При склеивании боковых границ получается поверхность тора. Пример: Минимизировать функцию трёх переменных, заданную таблицей истинности (таблица 6). Таблица 6 Таблица истинности функции трёх переменных
СДНФ функции: Составляем карту Карно и производим разметку её сторон: Рисунок 8 Карта Карно функции 3-х переменных.
На карте Карно формируем два прямоугольника. Первый из них объединяет (как бы заключает в скобки) два первых минтерма (слагаемых), а второй – первое и третье слагаемые СДНФ минимизируемой функции, приведённой выше. Минтермы, объединённые в прямоугольники, отличаются только в одном разряде. Их неизменяемая часть, которая при минимизации расчётным методом выносится за скобки, и является минимизированным значением функции:
Таким образом, карта Карно позволяет поместить рядом, то есть в соседних ячейках, соседние элементарные произведения, отличающиеся только одним сомножителем.
Последовательность действий при минимизации: 1 Изображается карта Карно и производится разметка её сторон. 2 Ячейки карты Карно, соответствующие наборам переменных, обращающих функцию в «1», заполняются единицами, остальные – нулями. 3 Выбирается наилучшее покрытие карты прямоугольниками. Наилучшим считается покрытие, образованное минимальным числом прямоугольников, а если таких вариантов несколько, то выбирается тот, который даёт максимальную площадь прямоугольников. Пример: Минимизировать функцию четырёх переменных, представленную картой Карно: (Рисунок 9)
Рисунок 9 Карта Карно функции 4-х переменных
Из карты Карно записываем минимизированное значение функции:
Читайте также: Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|