Минимизация ДНФ. Тупикова ДНФ

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

Пример. Пусть сокращенная ДНФ функции имеет вид:

.

Тогда ее единичное множество может быть представлено в виде:

.

Заметим, что наборы, входящие в последнее подмножество, находятся так же в первом и во втором. Так (говорят, набор 101 покрывается множеством ), а . Значит, если убрать из объединения составляющую , объединение от этого не изменится. Говорят, что множество покрывается объединением и . Следовательно, импликант xz – лишний.

Сокращенная ДНФ, из которой удалены все лишние импликанты, называется тупиковой.

Отношение покрытия между единичными наборами и импликантами ДНФ наглядно задается таблицей покрытия.

Строки таблицы соответствуют конъюнкциям ДНФ, столбцы – элементам единичного множества. На пересечении строки и столбца ставится пометка, если данная конъюнкция обращается в единицу данным набором значений аргументов (иначе говоря, данный набор покрывается единичным множеством конъюнкции).

Пример. Пусть ДНФ функции имеет вид:

.

Тогда ее единичное множество может быть представлено в виде:

.

.

Построим таблицу покрытия.

y

Из таблицы видно, что вторая строчка – лишняя, то есть если ее убрать, все элементы единичного множества останутся покрыты. Значит, импликант – лишний. Таким образом, ДНФ можно упростить, убрав лишний импликант. Она приобретает вид , и в данном случае является тупиковой, так как оставшийся импликант – простой.

Так бывает не всегда.

Замечание.1 Чтобы с помощью таблицы покрытия получить тупиковую ДНФ, необходимо сначала получить сокращенную ДНФ и именно ее простые импликанты помещать в таблицу покрытия.

Замечание.2 У функции может быть несколько тупиковых ДНФ. Чтобы найти их необходимо построить сокращенную ДНФ, содержащую все простые импликанты данной функции.

Метод Блейка-Порецкого – метод получения сокращенной ДНФ, содержащей все простые импликанты.

Пусть дана СДНФ функции.

1. Перенумеруем элементарные конъюнкции.

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

3. Допишем к списку полученных конъюнкций те, которые не участвовали в склеивании (их номера не фиксировались).

4. Вернемся к п.1.

В результате получим сокращенную ДНФ, содержащую все простые импликанты.

Пример. Дана СДНФ вида:

.

Получить с помощью метода Блейка-Порецкого сокращенную ДНФ, содержащую все простые импликанты.

П. 1. ;

П. 2, 3. ;

П.4. .

Так как больше склеивания произвести нельзя, сокращенная ДНФ имеет вид: .

Построим таблицу покрытия:

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

Таким образом, дана функция имеет 2 тупиковые ДНФ:

;

.

Пример 2.

П. 1. ;

П. 2, 3. ;

П.4. ;

Так как больше склеивания произвести нельзя, сокращенная ДНФ имеет вид: .

Построим таблицу покрытия:

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