научная статья по теме КРАТЧАЙШИЕ И МИНИМАЛЬНЫЕ ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ ПОЛНЫХ ФУНКЦИЙ Математика

Текст научной статьи на тему «КРАТЧАЙШИЕ И МИНИМАЛЬНЫЕ ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ ПОЛНЫХ ФУНКЦИЙ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 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 рублей.

Показать целиком