Минимизация логических функций методом карт Вейча

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

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

Каждая клетка карты соответствует некоторому набору значений аргументов. Этот набор аргументов определяется присвоением значе­ния лог. 1 буквам, на пересечении строк и столбцов которых расположе­на клетка. Так, в карте функций четырех аргументов клетки первой строки соответствуют следующим комбинациям значе­ний аргументов:

1-я клетка

2-я клетка

3-я клетка

4-я клетка

Число клеток карты равно числу всех возможных наборов значений аргументов 2" ( п — число аргументов функций ). В каждую из клеток карты записывается значение функции на соответствующем этой клетке наборе значений аргументов. Пусть функция задана таблицей истиннос­ти в форме, которая использовалась ранее (табл. 2). Таблица истин­ности этой функции в форме карты Вейча представлена табл. 3.

Х1	0	0	0	0	1	1	1	1
Х2	0	0	1	1	0	0	1	1
Х3	0	1	0	1	0	1	0	1
F(Х1, Х2 ,Х3)	0	1	0	1	0	0	1	1

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

Сформулируем правила получения МДНФ функций с помощью карт Вейча.

Все клетки, содержащие 1, объединяются в замкнутые области. При этом каждая область должна представлять собой прямоугольник с чис­лом клеток 2^к, где к = 0, 1, 2,... Значит, допустимое число клеток в области 1, 2, 4, 8,... Области могут пересекаться и одни и те же клетки могут входить в разные области. Затем проводится запись выражения МДНФ функции. Каждая из областей в МДНФ представляется членом, число букв в котором на к меньше общего числа аргументов функции n (n-k). Каждый член МДНФ составляется лишь из тех аргу­ментов, которые для клеток соответствующей области имеют одинако­вое значение (без инверсии либо с инверсией).

	1	1	0	0					1		1	0		0
	0	1	1	0					0		1	1		0

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

Рассмотрим минимизацию с помощью карты Вейча функции трех аргументов, представленной табл. 4. Все клетки, содержащие 1, охва­тываются двумя областями. В каждой из областей 2¹ клеток, для них n-k =3-1= 2, и эти области в МДНФ будут представлены членами, содержащими по две буквы. Первой области соответствует член (аргумент х₃ здесь не присутствует, так как для одной клетки этой области он имеет значение без инверсии, для другой — с инверсией); второй области соответствует член . Следовательно, МДНФ функ­ции

Рассмотрим пример минимизации функции четырех аргументов, заданной табл. 1.28. Первая и четвертая области имеют по две клетки, для них n-k= 4 -1 = 3. Эти области в МДНФ будут представлены членами, содержащими по три буквы. Вторая и третья области содер­жат по четыре клетки и в МДНФ выражаются членами, содержащими по две буквы (n-k = 4 -2 = 2). Минимальная ДНФ функции

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

	1	1	1	0								0	1	1		0
	0	1	1	0								0	0	0		0
	0	0	1	1								1	1	0		1
	0	0	1	0								1	1	1		1

В силу допустимости такого сворачивания карты вдоль горизонталь­ной и вертикальной осей, например, клетки, расположенные в четырех углах карты функции четырех переменных, оказываются соседними и могут быть объединены в одну область. Покажем это на примере мини­мизации функции, заданной табл. Минимальная ДНФ функции

	1	0	1	1								1	0	1		1
	0	0	1	1								0	0	0		0
	0	0	1	1								0	1	1		0
	1	0	1	1								0	1	1		0

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