Интервальное представление булевых функций

Интервальное представление устанавливает более тесную связь между геометрическим представлением логической функции и ее записью в виде логической формулы в булевом базисе. Обозначим – множество всех вершин единичного n –мерного куба. Пусть – множество всех таких вершин куба, на которых функция . Для вышеприведенного примера . Множество является, фактически, отношением на вида .

Сформулированное в разделе 2.1.5 правило получения СДНФ связывает с каждой вершиной n –мерного куба конъюнкцию членов, а со всей областью истинности функции – дизъюнкцию этих конъюнкций. Пусть для некоторой функции . Тогда СДНФ имеет вид . Применив к полученной формуле операцию склеивания по получим . Легко заметить, что исходные вершины соединены ребром. Если связать с этим ребром конъюнкцию , то можно построить цепочку: конъюнкция трех составляющих – вершина куба, конъюнкция двух составляющих – ребро куба и т.д.

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

Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний , где , в которой каждая переменная встречается не более одного раза. Часто, в литературе, переменную или ее отрицание вида называют первичным термом. Число называется рангом конъюнкции. В случае конъюнкция называется пустой и полагается равной 1.

Подмножество называется интервалом r–ого ранга, если оно соответствует элементарной конъюнкции –ого ранга.

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

Пример. В трехмерном кубе, конъюнкции соответствует ребро , являющееся интервалом 2–го ранга (такой интервал часто обозначают (X11)), а конъюнкции – грань , являющаяся интервалом 1–го ранга.

Для некоторой логической функции можно ввести понятие комплекса интервалов –ого ранга. Например, для функции, заданной выше таблицей истинности 2.7 и рисунком 2.2, можно выделить следующие комплексы: