Логические и арифметические основы и принципы работы ЭВМ


Понятие покрытия


Определение. Если на каком-либо наборе f принимает значение а1, а

– значение а2, то говорят, что f своим значением а1 покрывает значение а2 функции
.

При минимизации ФАЛ стремятся получить форму, в которой будет меньше букв, чем в исходной. По отношению к ДНФ эта форма называется сокращенной (Сок. ДНФ).

Смысл построения Сок. ДНФ заключается в том, что в нее входят такие элементарные произведения, которые своими единицами покрывают не одну единицу исходной функции, а несколько.

Так, каждое элементарное произведение, входящее в СДНФ, покрывает только одну единицу функции.

Например:

f(Х1, Х2)= Х1Х2

Х1Х2
Х1Х2

1 1 1

Эти единицы функции могут быть накрыты более короткими произведениями: Х1 накрывает две единицы: Х1Х2 и Х1Х2 и Х2

, которое накрывает также две единицы: Х1Х2 и Х1Х2

, т.е.

f(Х1, Х2)= Х1

Х2

ТЕОРЕМА (без док-ва):

Любая ФАЛ может быть представлена единственным образом в Сок. ДНФ, т.е. записана в виде дизъюнкции простых импликант.

Сокращенная форма не означает, что это форма является минимальной. Однако для практической реализации эта форма более удобна, чем совершенная.

Рассмотрим метод получения Сок. ДНФ, предложенный Квайном. Этот метод, и, в частности, теорема Квайна в явном и неявном виде входит практически во все методы минимизации.

Исходная форма функции – совершенная ДНФ.

ТЕОРЕМА Квайна:

Если в СДНФ в начале произвести все операции неполного склеивания, а затем все операции поглощения, то в результате получится сокращенная ДНФ.

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

X)=1.

Пусть Х1Х2 – простая импликанта некоторой f(Х1, Х2, Х3) трех переменных. Тогда:

Х1Х2 (Х3

Х3)=Х1 Х2 Х3
Х1 Х2 Х3

получатся после многократного применения этой операции дизъюнкции конституент единицы исходной функции, т.е. ее СДНФ.

В эту форму, вообще говоря, могут входить несколько одинаковых членов, т.к.


- Начало -  - Назад -  - Вперед -