Карно-Вейча

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

Каждая клетка карты соответствует определенному набору значений аргументов. Этот набор аргументов определяется присвоением значения логической 1 буквам, на пересечении строк и столбцов которых расположена клетка (х₁ = 1, = 0).

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

Пусть функция для трех аргументов задана выражением (2.14) при условии, что её значение при различных комбинациях аргументов равно 1.

F (x_1, x₂, x₃) = x₁× x₂× Ú x₁× x₂× x₃ Ú × x₂× x₃ Ú × x₂× . (2.14)

Составим карту Карно-Вейча для выражения (2.14) в соответствии со следующей методикой. В клетках карты, соответствующих комбинациям аргументов выражения (2.14) ставится 1 { F (x_1, x₂, x₃) = 1}, в остальных клетках 0 { F (x_1, x₂, x₃) = 0}.

 

 

Рисунок 9 Рисунок 10

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

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

Все клетки, содержащие 1, объединяются в замкнутые области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2^h, где h = 1, 2,.... Таким образом, допустимое число клеток в области равно - 2, 4, 8,.... Области могут пересекаться и одни и те же клетки могут входить в разные области.

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

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

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

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

 

F (x_1, x₂, x₃) = x₁× x₂Ú × x₃ . (2.15)

 

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

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

Так, для функции, при­веденной выражением (2.14), МКНФ будет иметь вид

 

F (x_1, x₂, x₃) = (x₁Ú x₃ ) × ( Ú x₂). (2.16)

 

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