Алгоритм расшифровки монотонных булевых функций, порождаемых неориентированными графами

Существует достаточно прикладных задач, в которых одним из инструментов моделирования служат булевы функции, среди которых важную роль играют монотонные булевы функции. Например, монотонные булевы функции являются удобным средством для описания структуры совместных подсистем несовместных систем условий, поскольку совместность является монотонным свойством.
В работе рассматриваются монотонные булевы функции, порождаемые неориентированными графами, в которых нули функции определяются как такие двоичные наборы, для которых соответствующий подграф исходного неориентированного графа пуст, или не содержит ребер. Для такого класса монотонных булевых функций даются постановки задач, связанных с выделением верхних нулей и максимальных верхних нулей функции. Вводятся понятия k-вершины и (k, m)-вершины в неориентированном графе. Показано, что для любой k-вершины исходного графа существует максимальный верхний нуль порожденной монотонной булевой функции, в котором компонента x_i, соответствующая этой k-вершине, принимает значение 1.
На основе этого утверждения построен алгоритм выделения максимального верхнего нуля для рассматриваемого класса монотонных булевых функций, который гарантирует, при определенных условиях, нахождение точного решения задачи поиска максимального верхнего нуля, либо приводит к снижению размерности исходной задачи. Предложенный алгоритм обобщается для случая использования (k, m)-вершин. Построенный алгоритм выделяет верхний нуль монотонной булевой функции и дает оценку его отклонения от максимального верхнего нуля по числу единиц в этих наборах. Алгоритм имеет сложность O(n^2p), где n - число вершин и p - число ребер исходного графа.

Ключевые слова

монотонная булева функция; верхний нуль монотонной булевой функции; неориентированный граф; алгоритм поиска максимальных верхних нулей монотонной булевой функции.

Литература

1. Гайнанов, Д.Н. Комбинаторная геометрия и графы в анализе несовместных систем и распознавании образов / Д.Н. Гайнанов. - М.: Наука, 2014.
2. Гайнанов, Д.Н. Об одном критерии оптимальности алгоритма расшифровки монотонных булевых функций / Д.Н. Гайнанов // Журнал вычислительной математики и математической физики. - 1984. - Т. 24, № 8. - С. 1250-1257.
3. Коршунов, А.Д. Монотонные булевы функции / А.Д. Коршунов // Успехи математических наук. - 2003. - Т. 58, № 5 (535). - С. 89-162.
4. Сапоженко, А.А. Проблема Дедекинда и метод граничных функционалов / А.А. Сапоженко. - М.: Физматлит, 2009.
5. Bioch, J.C. Minimum Self-Dualdecompositions of Positive Dual-Minor Boolean Functions / J.C. Bioch, T. Ibaraki, K. Makino // Discrete Applied Mathematics. - 1999. - V. 96-97. - P. 307-326.
6. Boros, E. Polynomial Time Ecognition of 2-monotonic Positive Boolean Functions Given by an Oracle / E. Boros, P. Hammer, T. Ibaraki, K. Kawakami // SIAM Journal on Computing. - 1997. - № 26. - P. 93-109.
7. Domingo, C. Efficient Read-restricted Monotone CNF/DNF Dualization by Learning with Membership Queries / C. Domingo, N. Mishra, L. Pitt // Machine Learning. - 1999. - № 37 (1). - P. 89-110.
8. Makino, K. A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions / K. Makino, T. Ibaraki // Journal of Algorithms. - 1998. - № 26 (2). - P. 291-305.
9. Makino, K. The Maximum Latency and Identification of Positive Boolean Functions / K. Makino, T. Ibaraki // SIAM Journal on Computing. - 1997. - № 26. - P. 1363-1383.
10. Torvik, V.I. Guided Inference of Nested Monotone Boolean Functions / V.I. Torvik, E. Triantaphyllou // Information Sciences. - 2003. - № 151 (SUPPL). - P. 171-200.
11. Triantaphyllou, E. Data Mining and Knowleadge Discovery Via Logic-Based Methods. Theory, Algorithms and Applications / E. Triantaphyllou. - N.Y.: Springer, 2010.
12. Valiant, L. A Theory of the Learnable / L. Valiant // Communications of the ACM. - 1984. - № 27 (11). - P. 1134-1142.
13. Torvik, V.I. Triantaphyllou E. Inference of Monotone Boolean Functions / Torvik, V.I. - Encyclopedia of Optimization. - N.Y.: Springer, 2009. - P. 1591-1598.