Метод карт Вейча

Метод Квайна определяет порядок и правила выполнения отдельных операций по получению минимальной формы функции, поэтому его можно использовать при минимизации функции любой сложности (с любым числом переменных). Однако он требует проведения многочисленных попарных сравнений членов исходной функции для определения возможности их склеивания и поглощения.

Более прост и нагляден метод Вейча, использующий специальные карты, называемые картами Вейча. Но метод Вейча ограничен сложностью минимизируемой функции (не более пяти аргументов).

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

Карта Вейча для функции двух переменных состоит из четырех клеток (таблица 1.14). Внутри каждой клетки вписаны ее координаты. Для трех аргументов функция содержит 8 различных состояний, что отражается и в карте Вейча (таблица 1.15).

Таблица 1.14 Таблица 1.15

Карта для четырех аргументов представлена в таблице 1.16 и содержит 16 клеток.

На сторонах карты указаны аргументы, присвоенные отдельным строкам или столбцам, причем они размещены таким образом, что образуют все возможные сочетания входных переменных. Если в наборе аргумент равен 1, то в координатах карты он указывается как прямое значение, если 0, то инверсное.

Т аблица 1.16

Для функции пяти аргументов надо использовать две карты для четырех аргументов, расположив их друг над другом и присвоив одной из них прямое, а другой – инверсное значение пятого аргумента (карта для пяти аргументов объемная). Это наибольшая сложность функции при использовании метода карт Вейча.

Для заполнения карты надо для каждого набора входных переменных определить соответствующую ему клетку карты (минтерм, принимающий единичное значение на наборе) и поставить в ней значение функции для этого набора аргументов. Для функции, заданной таблицей 1.17, карта Вейча приведена в таблице 1.18.

Т аблица 1.17 Таблица 1.18

X1 X2 X3	0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
Y	0 1 0 0 0 1 1 1

Для получения минимальной дизъюнктивной нормальной формы (МДНФ) надо выделить прямоугольные области из одной, двух, четырех, восьми или шестнадцати смежных клеток, в которых записана 1, и рассмотреть изменение в них переменных. Если при перемещении из одной клетки выделенной прямоугольной области в другую переменная меняется (переходит из прямого значения в инверсное), то при выполнении операций склеивания членов СДНФ, находящихся в пределах этой области, она поглощается. Тогда в результирующей конъюнкции остаются только те переменные, которые во всех клетках выделенной области имеют одинаковое значение (прямое или инверсное).

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

Чем больше клеток входит в одну область, тем проще результирующая конъюнкция. Чем меньшим числом областей можно объединить клетки с

единичным значением функции, тем проще окажется МДНФ. Карту можно сворачивать в цилиндр в любом направлении, также объединять в одну область клетки углов карты (карта представляет собой замкнутую область).

Таблица 1.19 Таблица 1.20

В карте Вейча функции четырех переменных (таблица 1.19) выделены три пересекающиеся прямоугольные области. В пределах первой области только аргумент Х₃ переходит из прямого в инверсное значение, в результате при склеивании он поглотится и результирующая конъюнкция этой области будет содержать три переменные (Х₁, Х₂, ).

Во второй области поглотятся переменные Х₂ и Х₄ (останутся X₁ и X₃), в третьей – Х₁ и Х₄ (останутся и X₃). Результирующая МДНФ имеет вид:

Y = + X₁X₃ + .

В карте таблицы 1.20 для получения наибольших областей ее надо свернуть по горизонтали, при этом выделяется область 1 из четырех клеток, и соединить таблицу углами с выделением области 2 также из четырех клеток. Результирующая МДНФ:

Y = +

Для получения МКНФ в прямоугольные области объединяются клетки с нулевыми значениями функции, в дальнейшем минимизация проводится аналогично. Исключение составляет лишь то, что оставшиеся (не поглощенные) члены в дизъюнкциях при записи результата инвертируются.

Для получения МКНФ таблицы 1.20 выделены две области, в каждой клетке которой записан нуль: одна (обозначенная номером 3) из восьми клеток, в пределах которой не инвертируется только переменная Х₃, другая (обозначенная номером 4) из четырех клеток, где не инвертируются переменные Х₂ и Х₄. В результате при записи МКНФ Х₃ окажется с инверсией (в пределах области Х₃ была без инверсии).

Во второй же области окажется проинвертирована Х₄ (в ней Х₄ была без инверсии), а Х₂ будет представлена прямым значением (двойная инверсия в результате даст прямое значение аргумента):

Y = = .