Определение сокращенной ДНФ и геометрический метод ее построения

Грань , содержащаяся в , называется максимальной, если не существует грани такой, что:

1) ;

2) Размерность грани больше размерности грани .

Пример 2. Пусть (см. пример 1). Рассмотрим конъюнкции , , , которым соответствуют грани

,

,

.

Эти грани имеют соответственно ранги , , и являются соответственно одномерной гранью (ребром), одномерной гранью (ребром) и двумерной гранью, которые представлены на рис. 1.

x ₃ °

°

x ₂

°

° ° x ₁

Рис. 1.

Грани и – максимальные, а грань не максимальная для , так как и размерность больше размерности .

Конъюнкция , соответствующая максимальной грани множества , называется простой импликантой функции .

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

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

Теорема. Минимальная ДНФ функции состоит из простых импликант.

ДНФ, являющаяся дизъюнкцией всех простых импликант, называется сокращенной.

Пусть множество всех максимальных граней множества . Тогда

,

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

.

Так как сокращенная ДНФ реализует функцию , то она имеет вид

.

Пример 3. Пусть функция задана таблицей 2:

Таблица 2

Этой функции соответствует множество

.

Имеем две максимальные грани:

,

.

Тогда покрытие для функции имеет вид:

.

Ему соответствует сокращенная ДНФ

.

Рассмотренный пример иллюстрирует геометрический метод построения сокращенной ДНФ Однако желательно иметь также и аналитическое решение.