Карты Карно

1. Что такое карта Карно

Карта Карно - это таблица истинности, перерисованная в виде сетки. Морис Карно предложил её в Bell Labs в 1953 году как способ упрощать переключательные схемы на глаз, и до сих пор это самый быстрый способ минимизировать небольшую булеву функцию вручную: никакой алгебры, никаких законов, которые надо помнить, - только прямоугольники.

Каждая клетка карты содержит одну строку таблицы истинности. Больше, чем перестановкой, карту делает порядок, в котором эти строки расположены: соседние клетки различаются ровно одной переменной.

Это единственное свойство и делает всю работу. Если две соседние клетки истинны, то переменная, которая между ними меняется, не может быть причиной истинности выражения: она выпадает, и один член покрывает обе клетки. Упрощение превращается в рисование самых больших прямоугольников, какие получится провести.

2. Почему столбцы идут не по порядку

Столбцы карты Карно нумеруются не 00, 01, 10, 11, а 00, 01, 11, 10 - это отражённый код Грея, порядок, в котором каждое значение отличается от следующего одним битом. При обычном двоичном счёте 01 оказалось бы рядом с 10, а они различаются двумя битами, и соседние клетки ничего бы не говорили.

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

3. Объединяем единицы

Чтобы прочитать с карты минимальную сумму произведений, покройте каждую клетку с единицей прямоугольными группами, соблюдая четыре правила:

• Группа - это прямоугольник из 1, 2, 4, 8 … клеток: степень двойки по каждой стороне.
• Группа может заворачиваться за края карты - по горизонтали, по вертикали или сразу в обе стороны.
• Группы могут перекрываться. Дважды покрытая клетка ничего не стоит, а непокрытая меняет функцию.
• Делайте каждую группу настолько большой, насколько она может быть, а затем берите как можно меньше групп, чтобы покрыть все единицы.

Каждая группа даёт один член. Читают его так: смотрят, какие переменные остаются одинаковыми по всей группе - они и входят в член (без отрицания там, где равны 1, и с отрицанием там, где равны 0), - а все меняющиеся переменные выпадают. Группа из двух клеток теряет одну переменную, из четырёх - две, из восьми - три. Минимальное выражение есть дизъюнкция этих членов.

4. Разобранный пример

Возьмём (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Карта имеет четыре переменные: A и B по строкам, C и D по столбцам.

Две группы покрывают все единицы. Первая - блок из четырёх клеток на пересечении двух строк, где A = 0, и двух столбцов, где C = 1: внутри него меняются и B, и D, поэтому они выпадают, и член равен ¬A ∧ C. Вторая - целая строка, где A и B равны 1, по всем четырём столбцам: вдоль неё меняются C и D, остаётся A ∧ B.

Значит, минимальная форма - (¬A ∧ C) ∨ (A ∧ B). Третий член исходного выражения, B ∧ C ∧ D, исчез: каждая покрытая им клетка уже была покрыта одной из двух групп. Вот как выглядит поглощение, когда его можно увидеть.

5. Простые и существенные импликанты

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

Если какую-то клетку покрывает лишь одна простая импликанта, она существенная: ни одна минимальная форма не может без неё обойтись, потому что эту клетку больше ничто не покрывает. Сначала возьмите существенные импликанты, а оставшееся покройте как можно меньшим числом прочих групп.

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

6. Объединяем нули

Всё сказанное выше так же работает и с нулями. Покройте их теми же прямоугольниками, прочитайте каждую группу с отрицанием литералов - переменная, равная 1 по всей группе, входит с отрицанием, равная 0 - без него, - и соедините группы знаком ∧ вместо ∨.

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

7. Карты побольше и безразличные наборы

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

Проектирование аппаратуры добавляет ещё одну идею. Некоторые наборы входов не встречаются никогда - двоично-десятичная цифра не бывает 1010, - и разработчику всё равно, что схема с ними сделает. Такие клетки помечают знаком X и читают как любое значение - то, при котором группы получаются больше. Карты в этом калькуляторе строятся по формуле, а она задаёт значение для каждого набора, так что безразличных клеток здесь не бывает.

8. Попробуйте сами

Введите в калькулятор выражение с двумя-четырьмя переменными, и его карта появится под таблицей истинности: каждая группа обведена своим цветом, а минимальная форма выписана внизу. Переключите на произведение сумм, чтобы увидеть, как объединяются нули.