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

Карта Вейча – это определенным образом заполненная таблица истинности логической функции.

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

Фигурные скобки показывают части карты, где аргументы X₁, X_2, X_3, X₄ равны «лог.1» или «лог. 0».

Необходимо учесть, что X₁, X₂, X₃, X₄ = 1, а _. Например: f (1, 1, 1, 1) = 0, f (0, 1, 0, 1) = 1 (рисунок 1.2.10.1)

Рисунок 1.2.10.1

 

Процесс минимизации осуществляется в 3 этапа:

1) Заполнить карту Вейча в соответствии с функцией заданной таблицей. Пусть «0» и «1» в карте Вейча расположились так, как показано на рисунке 1.2.10.2.

 

Рисунок 1.2.10.2.

 

2) Чтобы получить МНДНФ необходимо: единицы объединить в области вдоль строк и вдоль столбцов, так чтобы в область входило 2ⁿ клеток, при этом стремятся, чтобы количество областей было минимальным, а количество клеток, входящих в область было максимальным. Допускается пересечение областей, клетки, находящиеся на краях карты Вейча, можно объединять в области, сворачивая карту в цилиндр.

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

 

Рисунок 1.2.10..3.

 

МДНФ

 

Чтобы получить МКНФ необходимо по такому же правилу в области объединить 0, но при записи аргументов их дополнительно инвертировать (рисунок 1.2.10.4.)

 

Рисунок 1.2.10.4.

 

МКНФ