Представление булевой функции на карте Карно

Допустим, что карта Карно для заданного n, то есть распределение минтермов по клеткам таблицы, заранее вычислена. Тогда можно построить следующее представление любой булевой функции, заданной таблицей истинности. Рассматривается булева матрица того же размера, что и карта Карно. Каждой строке таблицы истинности соответствует некоторый минтерм. Если значение в этой строке равно 1, то записываем 1 в соответствующую ячейку матрицы, в противном случае записываем 0. Фактически, элементы вектора значений таблицы истинности булевой функции раскладываются по ячейкам булевой матрицы, а правило раскладывания задается картой Карно.

Пример Функция g (x, y, z), заданная в примере подраздела 3.4.5. имеет следующее представление на карте Карно.

Рассмотрим некоторые примеры применения карт Карно для решения задач с булевыми функциями. Первый пример связан с минимизацией дизъюнктивных форм (подразделы 3.4.4. и 3.4.6.). Заметим, что так же, как каждая отдельная ячейка с 1 соответствует минтерму, каждая прямоугольная группа смежных ячеек, содержащих 1, соответствует элементарной конъюнкции. Таким образом, задача минимизации дизъюнктивной формы сводится к отысканию покрытия всех ячеек содержащих 1 на карте Карно минимальным количеством прямоугольников.

Пример Для функции g (x, y, z), заданной в примере подраздела 3.4.5, минимальное покрытие на карте Карно содержит два элемента, они выделены штриховкой.

Второй пример связан с построением канонических форм для функций и их комбинаций. Карта Карно для одной заданной функции очевидным образом задает её СДНФ – достаточно выписать минтермы, указанные ячейками с 1, и соединить их знаками дизъюнкции. Столь же просто можно построить СДНФ для отрицания, дизъюнкции и конъюнкции заданных функций. Для получения СДНФ отрицания достаточно просто инвертировать матрицу. Для получения СДНФ конъюнкции или дизъюнкции произвольного числа k булевых функций можно поступить следующим образом. Взять матрицу, заполненною нулями, и добавить в каждую ячейку независимо 0 или 1 для каждой функции. При этом в некоторых ячейках окажется 0, в некоторых 1, а в некоторых какие-то числа вплоть до k. Все ненулевые ячейки образуют СДНФ дизъюнкции, все ячейки, равные k, образуют СДНФ конъюнкции.

Третий пример связан с эффективным вычислением значения булевой функции. Вообще говоря, если булева функция представлена картой Карно и задан набор значений переменных (s ₁,…, s_n), то ответ получается за один шаг: значение функции на заданном наборе содержится в ячейке, соответствующей минтерму (s ₁,…, s_n). Таким образом задача сводится к быстрому отысканию нужной ячейки. Здесь можно применить различные подходы. Один из вариантов приведен в алгоритме 3.4.

[1] Морис Карно, род. 1924