Метод минимизирующих карт

(Карты Карно)

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

Карты Карно для:

2-х переменных 3-х переменных 4-переменных.

Если Метод минимизирующих карт требуется получить карту Карно для какой-либо функции, то поначалу записывают эту функцию в НДФ. Каждый член, который возникает в этой форме, задается на карте Карно при помощи 1 в соответственной клеточке. Потом группируют единицы в соответственных полях, очерчивая их замкнутыми линиями. При исследовании карты с очерченными полями Метод минимизирующих карт оказывается, что если две примыкающие клеточки содержат 1, то из их всегда можно удалить одну переменную, а конкретно ту переменную, для которой ее инверсия размещается в последующей примыкающей клеточке. Разглядим примеры для функций 2-х, 3-х и 4-х переменных.

1. .

Имеем последующую карту Карно:

Тогда и в малой форме функцию можно представить как Метод минимизирующих карт:

.

2.

Для этой функции карта Карно будет иметь вид:

После минимизации получаем:

.

3. .

Получаем:

4.

Полностью разумеется, что логическую функцию в последнем примере можно представить в малой форме и другими вариациями, объединяя ”1” по иному.

Карты Карно для числа переменных n>4 составляются из схожих (в смысле обозначения сторон первичными термами) карт для 4 переменных Метод минимизирующих карт.

Две карты Карно для 4 переменных будем именовать примыкающими, если они имеют общую грань. Клеточки, расположенные в схожих местах примыкающих карт для 4 переменных, являются примыкающими, т.к. им соответствуют примыкающие минтермы.

К примеру, для n=5

Примыкающими клеточками тут являются: 0 и 16, 1 и 17, 7 и 23, 14 и 30, 8 и 24 и т.п.

При n=6 имеем Метод минимизирующих карт:

Тут примыкающими являются клеточки: 0 и 32, 0 и 16, 5 и 37, 5 и 21, 14 и 30, 14 и 46 и т.п. Но 0 и 48, 18 и 34, 15 и 63 и т.п. не являются примыкающими.

Пример. Минимизировать ФАЛ:

В согласовании с вышеизложенным получаем карту Карно, вид которой представлен на рис. 2.4.

И в итоге минимизации получим:

=

= .

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

Рис. 2.4.

Пример. Минимизировать ФАЛ:

Заполняя карту Карно для n=6 получаем:

Итог минимизации будет представлен в этом случае как:

.

Карты Карно употребляют и для получения малых КНФ. Это вытекает из принципа Метод минимизирующих карт двойственности и законов двойственности. Покажем это на примере.

Пусть имеем ФАЛ .

Минимизируя при помощи карты Карно (рис.2.5) получаем:

.

Тогда имеет место в этом случае последующее соотношение:

,

откуда на основании двойственности получаем:

.

Рис. 2.5.


metod-pryamogo-osredneniya-sglazhivaniya.html
metod-pryamoj-mozgovoj-ataki.html
metod-raboti-s-informaciej.html