Днф, интервалы и покрытия.

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

Введём следующее обозначение: обозначим через множество всех единичных наборов функции . Тогда набор (вектор) из множества принадлежит тогда и только тогда, когда . Множество называется единичным множеством функции , а функция называется характеристической функцией множества . Легко показать, что соответствие между функциями и их единичными множествами является изоморфизмом.

Если функция представляется элементарной конъюнкцией всех переменных, то множество содержит ровно один элемент множества . Если же функция – элементарная конъюнкция переменных , то содержит двоичных наборов. Это объясняется тем, что в таком случае переменных, не входящих в эту конъюнкцию несущественны для функции . Тогда они принимают значений, не изменяя значения . Множество такой функции называется интервалом.

Пример 3. Рассмотрим функцию и найдём её интервал.

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

Далее, очевидно, что только при значениях . При этом переменные могут принимать любые значения. Теперь перечислим все единичные наборы для данной функции: . Итак, .

В рассматриваемом случае говорят, что конъюнкция (или, точнее, интервал ) покрывает множество и все его подмножества.

Представление некоторой функции в виде ДНФ соответствует представлению её единичного множества в виде объединения интервалов; в совокупности все конъюнкции ДНФ покрывают всё единичное множество функции . Обратное также верно: если все элементы некоторого интервала принадлежат , то существует ДНФ данной функции, содержащая конъюнкцию .