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

Рассмотрим произвольные булевы ф-ции 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 ₁, он является допустимым (это передняя боковая грань).

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

Дата добавления: 2017-01-13