Тупиковая ДНФ. Метод Блейка-Порецкого

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

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

Пример
Пусть ДНФ функции имеет вид:
Тогда ее единичное множество может быть представлено в виде:
Построим таблицу покрытия.

Пример:
Из таблицы видно, что вторая строчка – лишняя, то есть если ее убрать, все элементы единичного множества останутся покрыты.

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

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

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

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

Метод Блейка-Порецкого –
метод получения сокращенной ДНФ, содержащей все простые импликанты.
Пусть дана СДНФ функции.
1. Перенумеруем элементарные конъюнкции.
2. Осуществим попарно склеивание каждой конъюнкции с каждой, если это возможно. Под полученными конъюнкциями будем фиксировать номера.

Метод Блейка-Порецкого
3. Допишем к списку полученных конъюнкций те, которые не участвовали в склеивании (их номера не фиксировались).
4. Вернемся к п.1.
В результате получим сокращенную ДНФ, содержащую все простые импликанты.

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

Метод Блейка-Порецкого
П. 1.
;
П. 2, 3. ;
П.4 .

Так как больше склеивания произвести нельзя, сокращенная ДНФ имеет вид:
Метод Блейка-Порецкого
Построим таблицу покрытия:

Таблица покрытия

Таблица покрытия

Таблица покрытия

Таблица покрытия

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

Метод Блейка-Порецкого
П. 1.
П. 2, 3.
П.4.

Так как больше склеивания произвести нельзя, сокращенная ДНФ имеет вид:
Метод Блейка-Порецкого
Построим таблицу покрытия:

Таблица покрытия

Таблица покрытия

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

Метод Блейка-Порецкого
П. 1.
П. 2, 3.
П.4. l

Метод Блейка-Порецкого
П. 1.
П. 2, 3.
П.4. l

Так как больше склеивания произвести нельзя, сокращенная ДНФ имеет вид:
Метод Блейка-Порецкого
Построим таблицу покрытия:

Таблица покрытия