Карты Карно, таблицы истинности и логические выражения[1]
Кто разработал карту Карно?
Морис Ка́рно (инженер по телекоммуникациям) разработал карты Ка́рно в «Bell Labs» в 1953 году при проектировании схем телефонной коммутации на основе цифровой логики.
Использование карты Карно
Теперь, когда мы умеем создавать карты Карно на основе диаграмм Венна, давайте применим наши знания. Карты Карно сокращают логические функции быстрее и проще по сравнению с методами булевой алгебры. Под сокращением мы подразумеваем упрощение, уменьшающее количество вентилей и входов.
Всегда приятно упростить логику до наименьших затрат, ибо это сокращает расходы за счёт исключения избыточных компонентов. Меньшая стоимость определяется меньшим количеством вентилей с меньшим числом входов на каждый вентиль.
Если есть выбор, то большинство студентов, имеющие на вооружении этот инструмент, предпочитают выполнять логическое упрощение с помощью именно карт Карно, а не методами булевой алгебры.
Рис. 1. Пять разных изображений (включая формулу внизу) про одно и то же.
На рисунке 1 выше показано пять отдельных изображений, которые представляют собой просто разные способы представления одного и того же: произвольной функции цифровой логики с двумя входами. Сначала это релейная логика, затем логические вентили, таблица истинности, карта Карно и, в самом внизу, логическое уравнение.
Дело в том, что все они эквивалентны. Два входа A и B могут принимать значения 1 или 0, высокое или низкое, замыкание или размыкание, «Истина» или «Ложь», в зависимости от обстоятельств. Есть 22 = 4 комбинации входов, дающих выход. Это применимо ко всем пяти примерам.
Эти четыре выхода можно наблюдать на индикаторе в релейной логике, на логическом выводе на вентильной схеме. Эти результаты могут быть записаны в таблицу истинности или карту Карно. Всегда воспринимайте карту Карно как разновидность таблицы истинности.
Выходные данные булевого уравнения могут быть вычислены по законам булевой алгебры и перенесены в таблицу истинности или карту Карно.
Какое из этих пяти эквивалентных логических описаний до́лжно использовать? То, которое наиболее уместно для выполнения поставленной задачи.
Рис. 2. Таблица истинности и изоморфная ей карта Карно.
Выходные данные таблицы истинности взаимно однозначно соответствуют записям карты Карно. Начиная с верхней строки таблицы истинности, где входные данные A = 0, B = 0 дают выход α.
Обратите внимание, что этот же выход α находится в карте Карно по адресу ячейки A = 0, B = 0, в верхнем левом углу K-карты, где пересекаются строка A = 0 и столбец B = 0. Другие строки таблицы истинности с выходами β, χ, δ из входов AB = 01, 10, 11, находятся в соответствующих местоположениях K-карты.
Ниже показаны смежные области по две ячейками в K-карте с двумя переменными. Он сопоставлены с предыдущей прямоугольной диаграммой Венна, как булевы области.
Рис. 3. Смежные ячейки (в количестве 2n) на картах Карно и их соответствующие булевы области на диаграммах Венна.
Клетки α и χ смежны на K-карте, их объединение представлено в виде эллипса в крайнем левом K-отображении в нижнем ряду на рисунке 3. Если взглянуть на предыдущую таблицу истинности, то увидим, что в ней «смежные» α и χ рядом не находятся – между ними есть ещё одна запись в таблице истинности (β). Это подводит нас к сути организации K-карты в виде матрицы – ячейки с любыми общими логическими переменными должны быть близко друг к другу, чтобы наглядно продемонстрировать этот шаблон.
Ячейки α и χ «смежные» не случайно – они имеют общую булеву переменную B'. Мы достоверно знаем это, потому что B = 0 (то же самое, что B') для столбца над ячейками α и χ. Сравните это с прямоугольной диаграммой Венна на рисунке 3, изображённой над K-картой.
Аналогичное рассуждение показывает, что β и δ имеют общее логическое значение B (B = 1). Тогда α и β имеют общее логическое значение A' (A = 0). Наконец, χ и δ имеют общее логическое значение A (A = 1). Сравните две последние карты со средней прямоугольной диаграммой Венна на рисунке 3.
Подводя промежуточный итог, отметим, что нам требуется находить группы ячеек, имеющие общие логические переменные. Карта Карно организована таким образом, чтобы эта общность достаточно очевидна. Разберём несколько примеров.
Примеры
Рис. 4. Некая таблица истинности, которую нужно перенести в заготовку карты Карно.
Пример 1: Перенесём содержимое таблицы истинности на карту Карно на рисунке 4 выше.
Рис. 5. В принципе, достаточно перенести, например, только единицы, а оставшиеся пустые клетки в карте Карно можно впоследствии заполнить нулями.
Решение: (приведено полностью на рисунке 5 выше)
Таблица истинности содержит две единицы среди выходов. Их обе нужно перенести в K-карту. Находим первую единицу во 2-м ряду приведённой выше таблицы истинности.
Обращаем внимание на адрес таблицы истинности: AB.
Находим ячейку на K-карте с таким же адресом.
Помещаем 1 в эту ячейку.
Повторяем процесс и для оставшейся единицы в последней строке таблицы истинности.
Пример 2: Для карты Карно в указанной выше задаче напишите логическое выражение. Решение ниже.
Рис. 6. Чтобы было более очевидно группирование единиц, нули в карту Карно не перенесены.
Решение: (приведено полностью на рисунке 6 выше)
Ищем смежные (то есть, расположенные по соседству выше/ниже или сбоку) ячейки. Диагональные ячейки смежными никогда не являются. Карты Карно устроены так, что соседние ячейки будут иметь одну или несколько общих логических переменных.
Группируем (обводим овалом) две единицы в колонке
Определяем для группы какая переменная (по вертикали или горизонтали) является общей, запишите это как логический результат. В данном случае это B.
Переменные, не совпадающие для группы ячеек, игнорируем. В нашем случае A для ячеек из группы равно и 1 и 0, поэтому логическое значение A игнорируется.
Игнорируем любые переменные, не связанные с ячейками, содержащими единицы. Под B' единиц нет. Игнорируем B'.
Выход = B.
Возможно, будет более очевидно, если сравнить с диаграммами Венна. В частности, обратите внимание на правый столбец B и сравните как расположены единицы в карте Карно (в столбце 1, означающий B).
Пример 3: Напишите логическое выражение для карты Карно ниже.
Рис. 7. Карта Карно (без нулей, чтобы более наглядно работать с единицами) и диаграммы Венна (где расположения логических переменных соответствуют строкам и столбцам в карте Карно).
Решение: (приведено полностью на рисунке 7 выше)
Сгруппируем (обводим овалом) две единицы, идущие подряд.
Находим переменные, общие для группы единиц. Выход = A'.
Пример 4: Для таблицы истинности на рисунке 8 ниже перенесём выходные данные в карту Карно, затем напишем логическое выражение в качестве результата.
Рис. 8. Переносим данные из таблицы истинности в карту Карно и выводим соответствующее логическое выражение.
Решение: (приведено в двух вариантах на рисунке 8 выше)
Переносим единицы из их местоположений в таблице истинности в соответствующие места на K-карте.
Группируем (обводим овалом) две единицы в столбце под B = 1.
Группируем (обводим овалом) две единицы в строке справа от A = 1.
Пишем член произведения для первой группы = B (произведение состоит из одного множителя).
Пишем член произведения для второй группы = A (произведение состоит из одного множителя).
Записываем Сумму-Произведений двух указанных выше членов: Выход = A + B.
На рисунке 8 выше приведено два решения. То которое на средней K-карте является самым простым (а значит, самым оптимальным и наиболее дешёвым). Менее оптимальное решение находится на правой K-карте. Там после группировки двух единиц мы формируя группу из одной клетки. Формально так тоже можно, но это нехорошо. Причина, по которой это нежелательно, заключается в том, что:
У единичной ячейки произведение содержит не один множитель, а два: AB' (из-за того, что группа ячеек состоит из одной клетки, общие переменные берутся и из строки, и из столбца).
Решение в данном случае: Выход = AB' + B.
Это, очевидно, не самое простое решение.
Есть другой способ подобрать эту одинарную 1 в нижнем левом углу карты Карно: можно сформировать группу из двух единиц (кроме этой единицы взять ту, что справа неё в нижнем правом углу карты Карно), как показано в нижней строке средней K-карты на рисунке 8 выше, невзирая на то, что эта 1 уже была включена в другую группу по столбцу B. Это разрешено – повторно использовать ячейки для формирования больших групп. Фактически, это не только можно, но и нужно, потому что приводит к более простому результату.
Следует отметить, что оба выхода, как «оптимальный» так и «неоптимальный», является логически правильными. Обе схемы дают одинаковый выходной сигнал. Просто «оптимальная» схема является самым дешёвым решением.
Пример 5: Заполним карту Карно для логического выражения ниже и запишем логическое выражение для результата.
Рис. 9. Для логического выражения составляем карту Карно, на основе которой упрощаем первоначальное логическое выражение.
Решение: (приведено полностью на рисунке 9 выше)
В логическом выражении есть три произведения. На каждое из них приходится единица. Хотя, как правило, количество единиц в соответствии с числом произведений зависит от общего количества переменных в произведениях по сравнению с размером самой K-карты.
Член с произведением – это адрес ячейки, в которую вносим цифру 1. Первый член с произведением, A'B, соответствует ячейке 01 на карте. В эту ячейку вводим 1. Аналогично поступаем и с двумя другими члена с произведениями, введя в общей сложности три единицы.
Затем переходим к группированию и извлечению упрощённого результата, действуем как в предыдущей задаче 4 с таблицей истинности.
Пример 6: Упростим приведённую на рисунке 10 ниже логическую схему.
Рис. 10. Логическая схема, которую упростим с помощью карты Карно.
Решение: (приведено полностью на рисунке 11 ниже)
Напишем логическое выражение для исходной логической схемы, как показано на рисунке 11 ниже.
Переносим члены с произведениями в виде единиц в соответствующие ячейки карты Карно.
Формируем группы ячеек, как в предыдущих примерах.
Напишем логическое выражение для групп, как в предыдущих примерах.
Рисуем упрощённую логическую схему.
Рис. 11. Для логической схемы составляем логическое выражение, которое переносим на карту Карно, из которой составляем упрощённое логическое выражение, на основе которого рисуем упрощённую логическую схему.
Пример 7: Упростим приведённую на рисунке 12 ниже логическую схему.
Рис. 12. Логическая схема, которую упростим с помощью карты Карно.
Решение: (приведено полностью на рисунке 12 выше)
Пишем логическое выражение для исходной логической схемы, показанной на рисунке 12 выше.
Переносим члены с произведениями в виде единиц в соответствующие ячейки карты Карно.
Видим, что сгруппировать единицы не представляется возможным.
Упрощение невозможно; оставляем как есть.
Для приведённой выше схемы невозможно логическое упрощение. Бывает и такое. Ни методы карт Карно, ни булева алгебра не в силах упростить эту логику.
Кстати, тут показано схемное обозначение «Исключающее ИЛИ» на рисунке 12 выше; однако это не логическое упрощение. Это всего-навсего делает диаграмму более читабельной.
Поскольку невозможно упростить логику исключающего ИЛИ и при этом она широко используется, она предоставляется производителями как базовая интегральная схема (модель 7486).
