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

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

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

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

· первая клетка

· вторая клетка

· третья клетка

· четвертая клетка

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

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

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

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

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

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

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

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

Рассмотрим пример минимизации функции четырех аргумен. тов. заданной табл. 3.14.

Первая и четвертая области имеют по две клетки, для них n – k = 4 – 1 = 3. Эти области будут в МДНФ представлены членами, содержащими по три буквы.

Вторая и третья области содержат по четыре клетки и в МДНФ выражаются членами, содержащими по две буквы (n – k = 4 – 2 = 2).

Минимальная ДНФ функции имеет вид

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

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

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

Таблица 3.17

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

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

Таблица истинности здесь состоит из двух карт, каждая из которых представляет собой карту четырех переменных. Одна из них соответствует x₅ = 1, другая – x₅ = 0, Эти карты можно мысленно представить себе расположенными одна над другой (рис. 3.29). При этом области охвата клеток могут быть трехмерными, т. е. одной областью могут охватываться клегки двух карт.

Для приведенной в табл. 3.18 функции МДНФ равна

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