Карты Карно

Карты Карно — позволяют упростить булево выражение с помощью графического представления данного выражения.

К примеру, у нас есть функция которая возвращает громоздкое выражение, упрощать которое достаточно утомительная задача:

return (a && b && c && !d) || (!a && c) || (!b && c) || (c && d);

Используя карту Карно, мы можем относительно легко решить данную задачу.

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

Составляется данная карта по следующему принципу — заполняемая клетка в карте должна являться пересечением каждого подвыражения.

На рисунке выделены области истинности для каждого отдельного оператора a, b, c и d (выделены малиновым цветом), и области отрицания каждого оператора — строки и столбцы не помеченные малиновым. К примеру, для оператора а — второй и третий столбец являются истинными, а первый и четвертый отрицанием, для оператора d — вторая и третья строчка истинны, первая и четвертая — отрицание, и т.д.

В итоге получаем для выражения (a && b && c && !d) — красная звездочка, для (!a && c) — желтые, для (!b && c) — синие, и для (c && d) — зеленые звездочки соответственно.

Карта Карно составлена, теперь нам нужно интерпретировать полученный результат.

Необходимо выделить звездочки в максимально возможный объект, причем количество звездочек должно быть четным. Нужно помнить, что первый столбец является соседним для четвертого, первая строка — соседняя для четвертой. Своеобразный цилиндр. Объект может быть в виде линии, или столбца (**, ****), или квадрата, как в нашем примере.

В данном примере выделяем две области — синюю и красную.

Начинаем упрощать. Рассмотрим синюю область. В синюю область входит оператор а и , это равно единице, b и b — пишем b, с и с — пишем с, d и !d — единица. В итоге синяя область получилась равна bc. Рассуждая аналогично получаем, что красная область равна !bc.

В итоге имеем:

return (b && c) || (!b && c);

Выносим с за скобки: с(b && !b) = с (выражение (b && !b)=1).

С помощью карты Карно мы упростили исходное выражение, и выяснили, что оно эквивалентно:

return c;