Геометрическое представление булевых функций

В геометрическом представлении ФАЛ значения входных переменных n - местного набора интерпретируются как координаты в n - мерной декартовой системе координат. Координатная система, в которой располагается геометрическая модель ФАЛ, является n - мерным кубом с единичными рёбрами. Кодам наборов входных переменных соответствуют вершины n - мерного куба. Значения кодов входных наборов переменных, на которых заданная ФАЛ равна единице (при использовании СДНФ для представления ФАЛ) помечаются нечисловыми символами и такой n - мерный куб с помеченными некоторыми вершинами и является геометрической моделью заданной ФАЛ. На рис.6 представлен пример геометрической модели функции двух переменных

Рис.6. Геометрическая модель функции двух переменных

На рис.7 представлена геометрическая модель ФАЛ трёх переменных

(23)

Рис.7. Геометрическая модель функции трёх переменных

На рис.7а) изображена модель функции трёх переменных в трёхмерном пространстве, а на рис.7б) - в двумерном пространстве на развёртке единичного куба на плоскость. Отметим чрезвычайно важное для практики свойство геометрической модели ФАЛ, на которой видно, что наборы переменных, отличающиеся по одной переменной принадлежат одному ребру единичного куба. Такие наборы переменных называются соседними. На развёртке соседними являются наборы, расположенные на противоположных краях.

Сопоставляя геометрические модели ФАЛ двух переменных и ФАЛ трёх переменных, сформулируем правило построения развёрток на плоскость n - мерных единичных кубов (карт Карно) по имеющимся развёрткам n-1 - мерных единичных кубов (карт Карно меньшей размерности).

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

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

В картах наборы переменных, на которых функция принимает единичные значения, помечаются нечисловыми символами. Карта с нанесёнными на ней значениями ФАЛ называется диаграммой.

Карты, на которых коды наборов изображаются в восьмеричной системе счисления, называются картами Вейча.

На рис.8 приведены примеры построения карт Карно и Вейча для четырёх- и пятиместных наборов переменных. На картах Вейча на рис.8б) и рис.8в) дана аналитическая разметка, указывающая области нулевых значений переменных в наборах. На картах в соседних клетках размещены коды наборов переменных, являющихся соседними, т.е. отличающимися по какой-то одной переменной знаком инверсии. На рис.9 приведена геометрическая модель частично определённой ФАЛ пяти переменных в виде диаграммы Вейча. Те восьмиричные коды наборов переменных, на которых ФАЛ имеет единичное значение, отмечены кружком. Те восьмиричные коды наборов переменных, на которых ФАЛ не определена отмечены круглыми скобками. В большинстве технических применений функции алгебры логики являются частично определёнными, так как не существует технической возможности появления некоторых наборов переменных, называемых в этом случае запрещёнными. На рис.9 отмечены поля из соседних пар наборов переменных, на которых ФАЛ не определена или имеет единичные значения.

Рис.8. Пример построения карт Карно и Вейча для четырёх- и пятиместных наборов переменных

F= 0Ú2Ú4Ú6Ú12Ú14Ú(16)Ú(20)Ú22Ú24Ú26Ú32Ú34 ;

Коды наборов восьмиричные. На (*) наборах функция не определена.

Рис.9. Диаграмма Вейча ФАЛ пяти переменных

Соседними являются и наборы, лежащие на границах карты, например: 3-7, 3-13, 3-23, 7-17, 1-11, 5-15, 27-37, 25-35, 21-31, 23-33, 2-22, 12-32.

Для карт с количеством переменных больше четырёх соседними являются наборы, расположенные симметрично относительно соединительной линии (на рис.9 указанной стрелкой) карт меньшего на единицу количества переменных. Например: 1-21, 4-24, 0-20, 14-34, 10-30, 11-31, 15-35.

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

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