Сокращенная ДНФ

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

Очевидно, что каждый интервал содержится в некотором максимальном интервале . Поэтому совокупность всех максимальных для интервалов определяет покрытие подмножества .

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

Пример. Из рисунка 2.3. следует, что область истинности включает четыре интервала 2–го ранга, которые образуют покрытие области истинности . Интервалов 1–го ранга здесь нет. Таким образом, полученная ДНФ является сокращенной ДНФ функции .

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

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

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