Электроника:Цифровая электроника/Карты Карно/Преобразование диаграмм Венна в карты Карно

Содержание

Теория

Практика

Проверка знаний

Рецепты

Эксперименты

Резерв

Резерв

Резерв

Резерв

Перевод: Макаров В. (valemak)

Проверка/Оформление/Редактирование: Мякишев Е.А.

Преобразование диаграмм Венна в карты Карно

Начнём с круга множества A, остальное пространство внутри прямоугольного универсального множества – это A' на рисунке 1.a. Трансформируем данную диаграмму Венна (почти) в карту Карно.

Рис. 1. Лёгким движением гомеоморфного преобразования диаграмма Венна превращается… в карту Карно!

В этом небольшом «комиксе» на кадрах 1.б и 1.в окружность расширяется, пока она примерно по размерам и форме не станет соответствовать оставшейся области A' в прямоугольнике универсального множества (кадр 1.г) и затем окончательно A приобретает вид прямоугольника (кадр 1.д). Всё, что за пределами A, является A'. Отобразим A' тоже в виде прямоугольника (кадр 1.е). Кроме того, в этом превращении в карту Карно мы не используем штриховку. То, что мы получили, напоминает карту Карно с одной переменной, но от нее мало проку. Нужно больше переменных.

Рис. 2. В том же универсальном множестве производим похожие преобразования для B и накладываем на результат из рисунка 1.

Рисунок 2.а выше аналогичен предыдущей диаграмме Венна, показывающей A и A', разве что метки A и A' мы расположили над диаграммой, а не внутри соответствующих областей. Представьте, что мы повторили процесс, аналогичный показанному на кадрах 1.а-е, получив таким образом «прямоугольную диаграмму Венна» для B и B', как показано на среднем рисунке 2.б.

Теперь друг на друга наложим диаграммы на рисунках 1.а и 1.б, получив результат 1.в, точно так же, как мы делали это для диаграмм Венна в поисках пересечений множеств. Мы всё это сделали потому, что это наглядно показывает общее для двух перекрывающихся областей, скажем, где A перекрывается с B. Нижняя правая ячейка на рисунке 2.в соответствует AB, то есть это область пересечения A c B.

Рис. 3. Вроде и не скажешь, но эта таблица – по-другому представленная диаграмма Венна с двумя множествами A и B, частично перекрывающих друг друга.

Что ж, не будем снова тратить время на рисование карты Карно, как на рисунке 2.в выше, вместо этого сразу нарисуем упрощённую версию, как показано в левой части рисунка 3 выше. К столбцам с заголовками A и A' относятся ячейки под заголовками. Строки, озаглавленные B и B' связаны с ячейками справа от заголовков.

Для простоты мы не очерчиваем различные области в таком выраженном виде, как на диаграммах Венна.

Правая часть рисунка 3 – альтернативная форма карты Карно, используемая в большинстве текстов. Имена переменных указаны рядом с диагональной линией. Буква A над диагональю указывает, что столбцам присвоена переменная A (и A'). 0 является заменой А', и 1 заменяет A. Буква B под диагональю связана со строками: 0 для B' и 1 для B.

Пример 1: Отметим ячейку, соответствующую логическому выражению AB на карте Карно выше, проставив в ней 1.

Рис. 4. Укажем с помощью единицы какая ячейка соответствует логическому выражению AB.

Решение: Изобразим «тень» (область в виде круга), соответствующую A (оранжевый цвет). Затем, покажем аналогичную «тень» для B (синий цвет). Перекрытие двух областей – это и есть AB. Поставим 1 в эту ячейку. Мы не обязательно огораживаем области A и B, как показано в левой/средней части рисунка 4 выше.

K-карта для 3-х переменных

Рис. 5. Топологическое преобразование диаграммы Венна от трёх переменных в карту Карно. C' делится на две части, чтобы удобнее показать пересечения и с A и с B.

Разрабатываем карту Карно с тремя переменными (рисунок 5 выше). Начнём с областей, подобных диаграмме Венна. Универсальное множество (внутри чёрного прямоугольника) разделяем на две узкие прямоугольные области для А' и А. Переменные B' и B аналогичным образом делят универсальное множество на два прямоугольника. Для C выделена квадратная область в центре прямоугольника универсального множества, а вот C' разделено на два вертикальных прямоугольника по обе стороны от квадрата для C (так тоже можно сделать).

На последнем рисунке мы совмещаем все три переменные, чётко обозначая различные области. Где какая область – менее очевидно если не помечать разными цветами, более очевидно по сравнению с предыдущими рисунками.

Эта K-карта (т.е. карта Карно) с 3-мя переменными имеет 2³ = 8 ячеек в виде маленьких квадратов. Каждая отдельная ячейка однозначно идентифицируется тремя логическими переменными (A, B, C). Например, ABC' однозначно указывает на самую нижнюю правую ячейку (помечено *), A'B'C' – это самая верхняя левая ячейка (помечено ×).

Рис. 6. Каждая ячейка имеет уникальных идентификатор, составленный с помощью переменных A, B, C или их дополнений.

Обычно карты Карно не маркируются именно таким образом, как показано в левой части рисунка 6. Хотя этот рисунок наглядно демонстрирует покрытие карты отдельными логическими переменными в 4-ячеечных областях.

Карты Карно обычно помечаются так, как показано в правой части рисунка 6. Каждая ячейка по-прежнему имеет уникальный идентификатор посредством произведения трёх переменных, т.е. с помощью логического выражения ИЛИ. Возьмём, например, ABC' – нужно следовать вправо вдоль строки A и вниз вдоль столбца BC', точка пересечения окажется в нижней правой ячейке ABC'. Это та ячейка, что помечена как * на рисунке 6 выше.

Рис. 7. Альтернативный вид карты Карно, вместо A/A', B/B' и C/C' отмечаем единицы и нули.

Две разные карты Карно с тремя переменными на рисунке 7 выше эквивалентны и являются окончательными формами. Версия справа немного проще в использовании, так как нам не нужно записывать так много логических буквенных заголовков и чёрточек дополнения над ними, только единицы и нули. Рекомендую использовать форму карты справа, хотя в некоторых текстах вы обнаружите ту, что слева. Заголовки столбцов в форме слева B'C', B'C, BC, BC' эквивалентны 00, 01, 11, 10 формы справа. Заголовки строк A, A' эквивалентны 0, 1 на правой карте.