Геометрическая интерпретация конъюнкций и дизъюнкций

Рассмотрим произвольные булевы ф-ции f₁ и f₂ , которым соответсвуют множества единиц N_f1 и N_f2, тогда конъюнкции ф-ций f₁, f₂ будет соответствовать пересечение соответствующих множеств: f₁ Ù f₂ « N_f1 Ç N_f2 .

Действительно, единицы конъюнкции есть в точности те наборы, на которых обе ф-ции f₁ и f₂ равны 1. А это есть пересечение множеств N_f1 и N_f2 , т.е. те наборы, которые принадлежат и N_f1 , и N_f2 .

Дизъюнкция f₁Ú f₂ « N_f1 È N_f2 (объединение).

Действительно, единицы дизъюнкции есть наборы, на которых или f₁= 1 или f₂= 1. Это и есть объединение множеств N_f1 и N_f2.

Определение:Интервалом называют множество единиц некоторой элементарной конъюнкции.

Например: Интервал N (x₁ ) - есть те вершины булева куба, на которых данная конъюнкция равна 1, т. е. x₁ = 1,
x₂ = 0, т. е. для трехмерного булева куба это вершины 101 и 100 (ребро).

Интервал, соответствующий конъюнкции x₁, есть наборы, в которых x₁ = 1

111 — это есть квадрат

Утверждение: Если удалить множитель из элементарной конъюнкции, то полученной конъюнкции будет соответствовать интервал, который содержит начальный.

Действительно:

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

Определение:Рангом интервала называют ранг соответствующей конъюнкции.

Определение:Размерностью интервала называют число

(n - rang), т.е. число переменных,которые не вошли в данную конъюнкцию.

Пример: размерность x₁ в трехмерном кубе равна 1. Размерность интервала x₁ в трехмерном кубе равна 2.

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

Пример: Рассмотрим функцию от трех переменных (рисунок справа), тогда интервал x₁ является допустимым для данной функции, т.к. он состоит целиком из единиц функции f. Интервал x₃ допустимым не является, т.к. он содержит 0 функции f, а именно набор 001, на этом наборе значение функции равно 0, а конъюнкция равна 1. Для данной функции 11 допустимых интервалов.

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

Максимальным интервалом является x₂ x₃ , данный интервал является допустимым, он состоит целиком из 1. Любой интервал, который получается из данного удалением некоторого множителя, будет недопустимым. Интервал x₁ максимальным не является, удалим множитель x₂ и получим интервал x₁, он является допустимым (это передняя боковая грань).

Эквивалентные определения:Допустимый интервал называется максимальным, если он не содержится ни в каком другом допустимом интервале.

Д/з.

Д/з.

Определение:Тупиковым покрытием называют покрытие, при удалении любого интервала из которого, оно перестает быть покрытием.

Пример: Рассмотренное в предыдущем примере покрытие является тупиковым. Действительно, если удалим интервал x₂ x₃ , то вершина 011 не будет принадлежать ни одному из оставшихся интервалов. Если удалим x₁ x₃, то тогда не будет покрыта вершина 101, если удалим x₁ , то не будет покрыта вершина 100, если удалим x₁ x₂ , то не будет покрыта вершина 110. Добавим к рассмотренномупокрытию x₁ x₂, тогда имеем не тупиковое покрытие. Действительно, можно удалить интервал x₁ x₂ и все равно получим покрытие.