ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2013, том 53, № 9, с. 1569-1588
УДК 519.7
РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ С ОГРАНИЧЕННЫМ ЧИСЛОМ НУЛЕЙ В КЛАССЕ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ1)
© 2013 г. Ю. В. Максимов
(117303 Москва, ул. Керченская 1а, кор. 1, МФТИ (ГУ) и НИУ ВШЭ) e-mail: yury.maximov@phystech.edu Поступила в редакцию 16.02.2012 г. Переработанный вариант 31.03.2013 г.
Рассматривается задача построения простых дизъюнктивных нормальных форм (ДНФ) булевых функций с малым числом нулей. Указанная задача интересна как в контексте исследования сложности булевых функций, так и с точки зрения ее приложений в задачах анализа данных. Метод, используемый в работе, является развитием редукционного подхода к построению ДНФ булевых функций. Ключевой идеей редукционного метода является представление булевой функции в виде дизъюнкции булевых функций с меньшим числом нулей. В ряде практически важных случаев предлагаемая техника позволяет значительно снизить сложность ДНФ реализации булевых функций. Библ. 41.
Ключевые слова: булева функция, дизъюнктивная нормальная форма, сложность булевой функции, вероятностно почти корректное обучение, алгебраические методы классификации.
БОТ: 10.7868/80044466913090093
1. ВВЕДЕНИЕ
К задаче построения простых дизъюнктивных нормальных форм (ДНФ) булевых функций с малым числом нулей приводят многие задачи машинного обучения, в частности, построение характеристических функций в задачах распознавания образов (см. [1], [2]), и некоторые задачи вероятностно почти корректного обучения (РАС-1еагшп§, см. [3]—[7]).
Задача построения минимальной ДНФ произвольной булевой функции, равно как и задача распознавания свойства минимальности, является в общем случае сложной, переборной задачей (см. [8]—[10]).
При этом качество аппроксимации задачи построения минимальной ДНФ эффективными алгоритмами также невысоко, даже в наиболее простом случае, когда булева функция задана своей таблицей истинности (см. [9], [10]). Наилучший известный приближенный алгоритм построения минимальной дизъюнктивной нормальной формы, основан на сведении задачи минимизации ДНФ к задаче о покрытии множеств, дает решение размера 0(п • ОРТ), где п — число переменных булевой функции, а ОРТ — размер минимальной ДНФ. В [10] показано, что ^Р-трудно получить приближенное решение задачи с точностью хотя бы п1 для некоторого у > 0.
Однако, как это было указано впервые С.В. Яблонским, построение минимальных (или близких к ним) дизъюнктивных нормальных форм булевых функций с малым числом нулей в ряде случаев может быть выполнено достаточно эффективно.
В частности, С.В. Яблонским было показано, что всякая булева функция, имеющая не более, чем 2 различных нуля, может быть реализована с использованием не более, чем п + 1 конъюнкций.
Существенный прорыв в теории сложности булевых функций с малым числом нулей связан с работами [4], [5]. Следуя [4], обозначаем через Р"к класс булевых функций от п переменных, имеющих ровно к нулевых точек.
1) Работа выполнена при финансовой поддержке Лаборатории структурных методов анализа данных в предсказательном моделировании, ФУПМ МФТИ, грант правительства РФ дог. 11.G34.31.0073.
1569
Скажем, что "почти все" функции класса P"k(п) обладают свойством А, если доля функций класса, для которых это свойство не выполнено, стремится к 0 при n —► да.
В [6] были разработаны методы построения простых ДНФ булевых функций. Предложенный метод позволяет строить, для почти всех функций из класса Pi, дизъюнктивные нормальные формы, число конъюнкций которых не превосходит величины
4 п k k( log 2k - log 2I og 2П )
log2n log2n
Несмотря на ряд недавних публикаций по минимизации булевых функций с малым числом нулей (см., например, [7], [11]—[18]), указанный результат во многих случаях оставался наилучшим из известных к настоящему времени.
2. ОСНОВНОЙ РЕЗУЛЬТАТ РАБОТЫ
В настоящей статье предложены алгоритмы построения ДНФ для булевых функций от п переменных, имеющих в точности к различных нулей (функций класса Р"к) при к > ^2п/2.
Предлагаемые в работе методы позволяют для почти всех функций класса Рк снизить оценки минимального числа конъюнкций, содержащихся в их ДНФ реализации, до величины, асимптотически равной
ьш пк
п . 2 а ^ 2-^(1 + о(1)),
при п —► + да, ка = ^2п — (^2п)05 + а, а — произвольная положительная постоянная, определяющая скорость сходимости к указанному значению.
Более того, если число нулей булевой функции ограничено полиномом от размерности, то полученные дизъюнктивные нормальные формы для почти всех функций
класса Рк содержат число литералов, не превосходящее
МВ[
п • 2 2 +
log 2^ 1 k
(1 + o( 1)) ^ 2 nk ( 3 + log 2k - log2log2n)(1 + o (1)).
log2n
Оценка, полученная в настоящей работе, улучшает ряд известных оценок минимального числа литералов и конъюнкций, достаточных для реализации типичных булевых функций класса Рк дизъюнктивными нормальными формами.
Во многих практически важных случаях полученная оценка длины ДНФ является асимптотически наилучшей из известных к настоящему моменту. В частности, это имеет место при числе нулей булевой функции, ограниченном снизу логарифмом и ограниченном сверху произвольным полиномом от размерности пространства переменных с положительными коэффициентами.
В сочетании с нижними оценками сложности, полученными в [6], указанные результаты позволяют эффективно строить существенно более точные ДНФ, чем это возможно в случае произвольных функций (см. [10]).
3. ОБОЗНАЧЕНИЯ
Обозначим через logx натуральный алгоритм числа x, log(1)x = logx, log(k + 1)x = log(log(k)x) при всех k > 1.
Напомним используемые в работе стандартные асимптотические записи. Записьf(n) = O(g(n)) означает, что существует константа C > 0 такая, что Vn f(n) < C ■ g(n). Запись g(n) = Q(f(n)) эквивалентна записиf(n) = O(g(n)). Записьf(n) = o(g(n)) означает, что Vs > 0 3Ne Vn > Ne :f(n) < s ■ g(n). Запись g(n) = ю( f(n)) эквивалентна записи f(n) = o(g(n)).
Стандартные асимптотические записи 0(-), о(-), О(-) и ю(-) всегда, кроме специально оговоренных случаев, применяются при п —- + да. Выражения/<< g и/>> g, применяемые в неравенствах и формулировках утверждений, равносильны равенствам/ = о(g) и/ = ю(g) соответственно.
Матрицей нулей М[/] функции/ назовем булеву матрицу, по строкам которой расположены
нули функции/ Обозначим через [к] множество {1, 2, ..., к}, через М[/]^\^ — подматрицу матрицы М[/], образованную пересечением строк ¡1, /2, ..., I,со столбцамиу2, ..., jr.
4. ОПРЕДЕЛЕНИЯ И ОБЗОР ИЗВЕСТНЫХ РЕЗУЛЬТАТОВ
В данном разделе, для удобства читателя, будут введены основные понятия теории сложности дизъюнктивных нормальных форм.
Проективным весом булева вектора называется минимум из числа его нулей и единиц.
Логической суммой (дизъюнкцией) функций/1 и/2 называется такая функция/1, которая равна единице в точке х только в случае, если хотя бы одна из функций /1 или/2 равна единице в точке х.
Логическим произведением (конъюнкцией) функций/1 и/2 называется такая функция/2, которая равна единице в точке х только в случае, когда обе функции /1 и /2 равны единице в точке х.
Логической импликацией функций/1 и/2 называется такая функция/3 = /1 —»-/2, которая равна 0 в точке х только в случае, если функция /1 принимает значение 1, а /2 принимает значение 0 в точке х.
Литералом называется булева переменная или ее отрицание.
Логическое произведение литералов, отвечающих различным булевым переменным, называется элементарной конъюнкцией. Конъюнкция Ж называется логической импликантой для функции/(х1, х2, ..., хп), если импликация Ж —-/ истинна при всех значениях переменных х1,
х2, "•, хп.
Конъюнкция Ж называется несократимой (для функции/), если Ж является логической им-пликантой /, однако при вычеркивании из Ж любого из литералов, входящих в ее запись, полученная конъюнкция перестает быть логической импликантой /. Несократимые конъюнкции часто называются простыми логическими импликантами.
Дизъюнкция Б/логических импликант функции/называется дизъюнктивной нормальной формой функции /, если функции Б/ и / принимают одинаковые значения во всех точках булева куба.
Дизъюнктивная нормальная форма Б булевой функции/называется кратчайшей (минимальной), если в записи Б содержится наименьшее число конъюнкций (литералов) среди всех ДНФ, реализующих функцию/ Число конъюнкций, входящих в запись Б, называется длиной ДНФ Б. Число литералов, входящих в запись Б, называется рангом ДНФ Б. (В ряде работ, в частности в [6], вместо термина ранг используется термин сложность. Однако, по мнению автора, термин ранг распространен существенно шире.)
Следует отметить, что множества минимальных и кратчайших ДНФ могут не пересекаться. Впервые это было показано в [19]. Более того, число литералов в кратчайших ДНФ может существенно превышать число литералов в минимальных ДНФ; аналогично, число конъюнкций, содержащихся в минимальных ДНФ, может существенно превышать число конъюнкций, содержащихся в кратчайших ДНФ. Однако в случае, если число переменных булевой функции не превосходит 4, множества минимальных и кратчайших ДНФ любой функции имеют не пустое пересечение; при п > 5 множества минимальных и кратчайших ДНФ могут не пересекаться (см. [20]).
В [20] подробно исследовались меры сложности ДНФ, представляющие собой произвольные выпуклые комбинации длины и ранга. Интересный обзор результатов по минимизации ДНФ по указанным мерам сложности можно найти в [20]—[22].
В [23] было показано, что длина почти всех булевых функций имеет один порядок. Обозначим
указанную величину через I (п), следуя [24].
В [25] для указанной величины была получена оценка
п) ^-Ч-Т^ 1 + 1))
2^2« 1о§2 п
при п —»- + да.
В [26] улучшена эта оценка и доказана
Теорема 1 (см. [26]). При п —»- да справедлива оценка
(
I (п)
1о§2П . 10ё22>П
1 + О
л (3) ^ 10ё2 п П
Ч (2 ) 11
пУУ
Эта оценка в настоящий момент является наилучшей из известных автору.
Из работ, посвященных верхним оценкам сложности ДНФ, следует особо отметить работы [24], [27]—[30]. Верхняя оценка сложности дизъюнктивных нормальных форм почти всех булевы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.