ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 7, с. 1266-1280
УДК 519.7
КРАТЧАЙШИЕ И МИНИМАЛЬНЫЕ ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ ПОЛНЫХ ФУНКЦИЙ^
© 2015 г. Ю. В. Максимов
(127051 Москва, Большой Каретный переулок, 19, стр. 1, ИППИРАН и МФТИ) e-mail: yury.maximov@phystech.edu Поступила в редакцию 17.06.2014 г.
Почти всем булевым функциям от n переменных, число нулей к которых не превышает log2n - log2log2n + 1, может быть сопоставлена некоторая булева функция от 2к-1 - 1 переменой с к нулями (полная функция) так, что сложность реализации исходной функции в классе дизъюнктивных нормальных форм определяется исключительно сложностью реализации полной функции. В работе установлена асимптотически точная граница для минимального возможного числа литералов, содержащихся в дизъюнктивных нормальных формах полной функции. Библ. 14. Фиг. 1.
Ключевые слова: булева функция, дизъюнктивная нормальная форма, сложность реализации булевых функций дизъюнктивными нормальными формами.
DOI: 10.7868/S0044466915070108
1. ВВЕДЕНИЕ
К задаче построения простых дизъюнктивных нормальных форм (ДНФ) булевых функций приводит большое число практических задач из различных областей дискретной оптимизации, таких как построение эффективных ¿йТ-солверов, вычисление характеристических функций классов в задачах машинного обучения, синтез управляющих схем и многие другие (см., например, [1]-[4]).
В работе исследуются булевы функции, заданные в конъюнктивной нормальной форме (КНФ) произведениями вида
к 1 2 n
f(xh..., Xn) = A (V V x2 V ... V Xn '), (1)
где {а'{}{, = у- = 1} — фиксированные булевы переменные.
Трудоемкость прямого построения сокращенной ДНФ путем перемножения скобок (КНФ) и последующего ее упрощения до минимальной ДНФ послужила толчком для разработки эффективных методов аппроксимации оптимальных по сложности ДНФ. Как правило, при исследовании сложности результирующей ДНФ оцениваются две основные меры сложности: длина, равная числу входящих в нее конъюнкций, ранг, равный суммарному числу входящих в нее литералов. Дизъюнктивная нормальная форма с наименьшим значением ранга называется минимальной, а ДНФ с минимальным числом конъюнкций — кратчайшей. Под линейной мерой сложности ДНФ мы будем понимать произвольную выпуклую комбинацию длины и ранга. Впервые указанная мера была определена в [5]. Рассмотрение линейных мер сложности мотивировано неэквивалентностью понятий минимальной и кратчайшей ДНФ, установленной Ю.И. Журавлевым в [6].
В [1], [2], [7], [8] и других работах было показано, что при достаточно малом числе скобок в произведении (1) возможны эффективные методы построения ДНФ, близких к минимальным и кратчайшим. В [1] было показано, что если число сомножителей в (1) не превосходит к = 1о§2 п — 1о§2 1о§2 п + 1, то построение искомой ДНФ сводится к построению ДНФ некоторой функции от су-
1) В части разделов 1—5 работа выполнена в МФТИ при финансовой поддержке РФФИ (код проекта 14-07-31277 мол_а) и Лаборатории структурных методов анализа данных в предсказательном моделировании ФУПМ МФТИ, грант правительства РФ дог. 11.G34.31.0073; в части раздела 6 исследование выполнено в ИППИ РАН за счет гранта Российского научного фонда (проект № 14-50-00150).
щественно меньшего числа переменных и при этом сложность сведения невелика. Более того, почти все исходные функции с указанным числом нулей и переменных сводимы к одной и той же булевой функции, названной в работе [1] полной.
Основным результатом настоящей работы является подход, позволяющий строить асимптотически минимальные ДНФ по всем линейным мерам сложности для широкого класса булевых функций. В частности, предложенные в работе алгоритмы позволяют строить и асимптотически минимальную и асимптотически кратчайшую ДНФ для полной функции.
2. ТЕРМИНОЛОГИЯ
В настоящей работе использован ряд стандартных терминов теории булевых функций, определенных в [7], [9]. Кратко напомним основные из них.
Матрицей нулей М^булевой функции/(х1, х2, ..., хп) является матрица, по строкам которой последовательно выписаны все различные нули функции /. Обозначим через М' ' подматрицу матрицы М, находящуюся на пересечении строк /ь ..., ¡,со столбцами..., Матрица, не содержащая одинаковых строк, называется тестом.
Пусть Вк — множество всех булевых векторов размерности к; В°к и в\ — множество булевых векторов, первая координата которых равна 0 или 1 соответственно; пусть [к, п] = {к, к + 1, к + 2, ..., п} — целочисленный отрезок от к до п включительно; обозначим через [п] отрезок [1, п], а х : Вк —- [2к — 1] — (взаимно-однозначное) отображение, заданное правилом
х((а 1, )) = ах2к-1 + ъ{1к-2 + ак2к.
Значение х(х) назовем номером, а минимум из числа единиц и числа нулей назовем весом вектора х, х е Вк.
Литералом будем называть булеву переменную или ее отрицание. Литерал х, ассоциируем со столбцом к], а литерал Х1 с покоординатным отрицанием столбца Мщ , 1 < - < п. Далее под термином литерал х'' будет часто подразумеваться ассоциированный с ним булев вектор. Дизъюнкции (конъюнкции) литералов сопоставим дизъюнкцию (конъюнкцию) ассоциированных с ними булевых векторов.
Отображение х индуцирует линейный порядок на векторах из Вк в соответствии с естественным порядком на прообразах. Обозначим его через < . Обозначим через < стандартный частичный порядок на Вк.
Скажем, что литерал имеет порядок х'' < X/ (х'' < X/) для функции/, если соответствующие им столбцы матрицы (или их отрицания) связаны таким же соотношением относительно частичного порядка < (соответственно <х). Под весом и номером литерала будем понимать вес и номер соответствующих ему векторов матрицы нулей.
Определение 1. Ненулевой вектор а е Вк назовем разложимым по векторам а1, ..., а„ если выполнены следующие равенства:
а = а1 V а2 V ... V а,, (а, а 1> = (а, а2) = ... = (а, а,) = к, где под символом (а, р> понимается скалярное произведение векторов а и р.
Определение 2. Ненулевой вектор а е Вк назовем ортогонально разложимым по векторам а1, ., а„ если выполнены следующие равенства:
а = а1 © а2 © ... © а,, а = а1 V а2 V ... V а,.
Обозначим через Пк вектор размерности к, состоящий только из единиц. В случае а — ак в условиях предыдущего определения назовем вектор (аг}'■ = 1 ортогональным разложением единицы. Заметим, что если вектор а разложим по векторам {а,-},- е 1, то х(а) > х(а,), - е I.
В теории сложности ДНФ традиционно рассматриваются такие характеристики, как число литералов и конъюнкций входящих ДНФ. Число литералов ДНФ Б обычно обозначается через гапк(Б), число конъюнкций Б обозначается через |Б|. В [5] рассматривались произвольные вы-
пуклые комбинации числа литералов и числа конъюнкций ДНФ, для которых в работе будет использовано обозначение еопуа, р(Д) = а ■ гапк(Д) + р ■ \Б\, а > 0, р > 0, а + р = 1. (В оригинальной работе [5] такие меры сложности назывались линейными мерами.) В настоящей работе будут рассматриваться только описанные выше меры сложности.
Пусть пп — класс (инвариантных) преобразований Шеннона—Поварова булевых функций от п переменных таких, что всякое преобразование п е пп сопоставляет упорядоченному набору пе-
п
а,
ременных (х1, х2, ..., хп) набор {у1, у2, ..., уп) = (1, х^2, ..., х1 п), где (г1, ..., гп) — произвольная перестановка отрезка [1, п], ст; е {0, 1} при г е [1, п]. Отметим, что булева функция и ее образ при преобразовании Шеннона—Поварова имеют одинаковую сложность при представлении их дизъюнктивными нормальными формами.
Цепью называется монотонная (в смысле отображения х) упорядоченная последовательность точек из Вк без повторений, в которой каждая следующая точка отличается от предыдущей только в одной координате. Для последовательности точек а1, а2, а3, входящей в цепь С, назовем точку а дополнительной, если а1, а, а3 есть цепь и, кроме того, а2 Ф а. Цепь назовем симметричной, если ее первый и последний элементы имеют одинаковый вес.
Обозначим через Zf — множество нулей функции /, а через Щ — множество ее единиц. Определим векторы {ек }к = 1 равенствами ек+1 = х-1(2'), 0 < г < к.
Конъюнкция К называется импликантой функции /(хь х2, ..., хп), если ЩК с Щ. Импликанта К называется простой, если из К не может быть вычеркнут ни один литерал так, чтобы полученная конъюнкция была импликантой/(х1, х2, ..., хп). Термины простая импликанта/и несократимая конъюнкция, входящая в сокращенную ДНФ функции /, употребляются в работе как синонимы.
Обозначим через р класс булевых функций от п переменных, имеющих в точности к различных нулей. Произвольной функции/е р сопоставим функцию g е Рк таким образом, что верны следующие условия:
1) в матрице Ш& отсутствуют нулевой и единичный столбцы. Всякий столбец матрицы М^или его покомпонентное отрицание присутствует в М^,
2) одинаковые столбцы в М1, расположены последовательно;
3) для любой пары столбцов матрицы М, один из которых является отрицанием другого, в матрице М1, присутствует не более одного.
Заметим, что инвариантными преобразованиями Шеннона—Поварова всякая булева функция, не имеющая столбцов веса 0, может быть записана в представленном виде (с сохранением сложности в классе ДНФ). Булева функция g называется правильной, если ее матрица нулей удовлетворяет условиям 1)—3). Если, кроме того, матрица нулей g не содержит одинаковых столбцов, то g называется приведенной.
^к _ 1 _ 1
Приведенную функцию, принадлежащую классу р , назовем полной. Обозначим через Рк класс всех полных функций, имеющих ровно к нулей. Полную булеву функцию класса ¥к, столбцы матрицы нулей которой упорядочены по возрастанию в соответствии с отображением х, назовем канонической (полной) функцией и обозначим ее через Fk.
Пусть тё — функция, сопоставляющая всякому бинарному вектору число его ненулевых компонент. Далее нам понадобится еще одна полная функция Ск такая, что столбец матрицы нулей Gk совпадает с соответствующим столбцом матрицы нулей Fk, если число единиц в последнем не больше, чем к/2, и дополнителен к столбцу матрицы нулей Fk в противном случае.
Согласно результату, полученному в [1], [2], всякая правильная булева функция ф предста-
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.