Алгоритм карт Карно

Эквивалентность геометрического и алгебраического языков реализована в алгоритме карт Карно. Этот алгоритм является непосредственным, визуальным способом выделения максимального покрытия. Он является, по-видимому, самым наглядным, но реально применим к булевым функциям с малым числом переменных – 3 и 4. Он основан еще на одном геометрическом представлении булева куба – в виде карт Карно. Карта Карно – это таблица, в строках и столбцах которой записаны в определенном порядке значения аргументов, а на пересечении строк – значения функции (0 обычно опускается). Суть метода – именно в определенном порядке записи переменных. Карта устроена так, что грань куба на ней изображается соседними клетками – двойкой, четверкой, восьмеркой, причем соседними считаются клетки и с разных концов таблицы. Другими словами, карта Карно представляет из себя двумерный тор. Поэтому максимальное покрытие на карте видно сразу: следует выделить группы клеток, в которых записаны единицы. При этом ядровым импликантам соответствуют единицы, покрытые однократно, а остальным соответствуют тупиковые ДНФ, которые нужно выбирать простым перебором.

Пример.