Построение тупиковых ДНФ на основе геометрических представлений

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

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

Алгоритм построения тупиковых ДНФ. Будем исходить из покрытия множества системой всех его максимальных граней .

Пусть . Составим таблицу 3, в которой

Таблица 3

		…		…
		…		…
…	…	…	…	…
		…		…
…	…	…		…
		…		…

Очевидно, что в каждом столбце содержится хотя бы одна единица. Для каждого найдем множество всех номеров строк, в которых столбец содержит 1. Пусть

.

Составим конъюнкцию, рассматривая номера строк как булевы переменные:

.

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

Пример 5. Рассмотрим функцию . Для нее множество состоит из 6 вершин, которые занумеруем числами I, II, …, VI. Максимальными гранями являются ребра, которые занумеруем арабскими цифрами (рис. 2).

III 3 °IV

2

II° 4

1 °V

5

6 °

I VI

Рис. 2.

Составим таблицу для множеств ( ) (табл. 4). Имеем

Таблица 4

Тогда

Получили пять неприводимых покрытий или пять тупиковых ДНФ:

,

,

,

,

,

из которых и являются минимальными.