Метод карт Карно

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

Например, карта Карно одной переменной (рис. 1.14): п = 1, число наборов N = 2″ = 2.

Рис. 1.14. Карта Карно одной переменной.

Карта Карно двух переменных (рис. 1.15): п = 2, число наборов N=2² — 4.

Рис. 1.15. Карта Карно двух переменных.

Крайние клетки, соответствующие комбинациям 00 и 10, являются соседними и отличаются одной переменной а.

Переменные в карте могут располагаться произвольно, но любые соседние по вертикали ши по горизонтали клетки могут отличаться не более чем одной переменной.

Карта Карно трех переменных (рис. 1.16): п = 3, число наборов Л^г = 2³ = 8.

Рис. 1.16. Карта Карно трех переменных.

Если имеется функция трех переменных, заданная таблицей истинности, представленной ниже, то соответствующая ей карта Карно выглядит так, как показано на рис. 1.17.

Рис. 1.17. Карта Карно функции

Обычно нули в карту не пишут, а заносят только единицы. Карта Карно четырех переменных (рис. 1.18): я = 4, JV = 16.

Рис. 1.18. Карта Карно функции четырех переменных.

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

Карта Карно пяти переменных (рис. 1.19): п = 5, N=32. Это две 16-клеточные карты, отличающиеся только одной (пятой) переменной.

Рис. 1.19. Карта Карно функции пяти переменных

Карта Карно шести переменных (рис. 1.20): п = 6, N = 64. Это четыре 16-клеточные карты.

Рис. 1.20. Карта Карно функции шести переменных

Здесь любые клетки соседние, если они отличаются только одной переменной.

После заполнения карты единицами из таблицы истинности приступают к минимизации. Суть минимизации: охватить все единицы карты Карно наименьшим числом кубов наиболее высокого ранга. Из каждого куба выписывают минтерм общих переменных. Минтермы объединяют дизъюнктивно.

Куб — это прямоугольный или квадратный контур, содержащий клетки только с единицами:

• • одна единица — куб «0"-го ранга, так как 2°= 1;
• • две единицы — куб «1"-го ранга, так как 2¹ = 2;
• • четыре единицы — куб «2"-го ранга, так как 2² = 4;
• • восемь единиц — куб «3"-го ранга, так как 2³= 8;
• • 16 единиц — куб «4"-го ранга, так как 2⁴ = 16, и т. д.

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

Пример 1.1.

Требуется найти МДНФ такой функции: F (a, b, с) = v (l, 3, 6, 7). Составим ее таблицу истинности:

Заполняем карту Карно (рис. 1.21).

Рис. 1.21. Карга Карно функции.

Здесь следует провести два куба первого ранга и составить МДНФ:

Запишем СДНФ исходной функции и преобразуем ее по законам алгебры логики / = abc + abc + abc + abc = ас + ab. Получим тот же результат. Представим карту Карно этой же функции по-другому (рис. 1.22).

Рис. 1.22. Карта Карно функции (другой вариант).

Очевидно, что результат такой же:

Пример 1.2

Требуется минимизировать функцию трех переменных: F (а, b, с) = = л (0, 4, 5).

Начинаем с составления таблицы истинности:

Рис. 1.23. Карта Карно функции.

Карта Карно будет такой, как показано на рис. 1.23.

Соответствующая минимальная форма F_min = b + ас. Здесь первый куб содержит четыре единицы (ранг куба равен г =2). Число переменных в минтерме равно (п — г), где п = 3, п-г=3−2 = — количество переменных из первого куба.

Из второго куба пг= 3−1=2.

Составим СДНФ и выполним склеивание минтермов (конституент единицы) каждого с каждым:

первый склеиваем со вторым, затем с третьим, с четвертым и т. д. Далее второй склеиваем с третьим, с четвертым и т. д. Все минтермы пройдут через склеивание. После первого склеивания выполняется второе и т. д., пока оно возможно. Напомним, что минтермы для склеивания могут отличаться только одной переменной.

Пример 1.3.

Задача — минимизировать функцию двух переменных:

Используя законы алгебры логики, приведем логическую формулу к нормальному виду (СДНФ):

Составим карту Карно (рис. 1.24), по которой получаем /_min = Х_х + Х₂. Этот же результат можно получить склеиванием минтермов.

Рис. 1.24. Карта Карно функции.

Пример 1.4.

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

Рис. 1.25. Карта Карно исходной функции.

Проводим два контура второго ранга и получаем Цена схемы равна Ц = 4 + 2 = б.

Можно в карте Карно объединить нули, но при этом получаем инверсную функцию: /_min = Х₄ + Х₂ • Х₃. Здесь проведены два куба — третьего и второго ранга. Цена схемы получается меньше: Ц = 2 + 2 = 4. Ее реализация на произвольных элементах имеет вид, показанный на рис. 1.26.

Рис. 1.26. Схемная реализация функции.

Отрицание можно перенести в правую часть, что не отражается на цене:

Чем меньше цена, тем лучше. Поэтому минимизировать по карте Карно следует и по единицам, и по пулям. К реализации принимают формулу с наименьшей ценой.

Пример 1.5.

Имеем функцию пяти переменных, заданную картой Карно (рис. 1.27).

Рис. 1.27. Карта Карно исходной функции.

Здесь проводим три куба: 1 — куб второго ранга, 2 — куб третьего ранга, 3 — куб второго ранга. Записываем минимальную форму:

/_mjl, + ₊

Находим цену Ц = 8 + 3 = 11. Желающие могут найти цену схемы после объединения нулей.

Минимизация не полностью определенных функций

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

Пусть, например, исходная функция трех переменных задана такой таблицей истинности:

Здесь символом «*» обозначены запрещенные комбинации входных переменных. Требуется найти минимальную форму.

Если не использовать запрещенные наборы, то карта Карно и минимальная форма будут такими, как показано на рис. 1.28.

Рис. 1.28. Карга Карно исходной функции

Цена схемы равна Ц = 7 + 3 = 10. Если на запрещенных наборах функцию дополнить единицами, то карта Карно принимает вид, как показано на рис. 1.29.

Рис. 1.29. Карта Карно исходной функции, дополненная единицами

Минимальная форма . Цена Ц = 2. Схемная реализация получается значительно проще.