ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 4, с. 730-736
УДК 519.7
О МУЛЬТИПЛИКАТИВНОЙ СЛОЖНОСТИ НЕКОТОРЫХ ФУНКЦИЙ
АЛГЕБРЫ ЛОГИКИ1
© 2015 г. С. Н. Селезнева
(119992 Москва, Ленинские горы, МГУ, ВМК) e-mail: selezn@cs.msu.su Поступила в редакцию 05.03.2014 г.
Изучается мультипликативная сложность некоторых функций алгебры логики. Рассматриваются функции алгебры логики, которые представимы в виде xi, x2...x„ Ф q(xi, ..., xn), где q(xi, ..., xn) — квадратичная функция. Доказывается, что мультипликативная сложность каждой такой функции равна (n — 1) и что мультипликативная сложность функций алгебры логики, представимых в виде xi ... xn Ф r(xb ..., xn), где r(xb ..., xn) — мультиаффинная функция, в некоторых случаях равна (n — 1). Библ. 12. Фиг. 2.
Ключевые слова: функция алгебры логики (булева функция), схема из функциональных элементов, сложность, мультипликативная сложность, верхняя оценка.
DOI: 10.7868/S0044466915040122
ВВЕДЕНИЕ
В данной статье изучается мультипликативная сложность некоторых функций алгебры логики. Мультипликативной (или конъюнктивной) сложностью функции алгебры логики f называется минимальное число элементов конъюнкции в схемах из функциональных элементов в базисе {x & y, x © y, 1}, каждая из которых реализует функцию f Мультипликативную сложность функции f будем обозначать через ц(/).
Мультипликативная сложность "самых сложных" функций алгебры логики рассматривалась
в [1], [2]. В [1] получено, что ц(п) = (1 + о(1)) • 2n/2 для ^(n) = max^f) , где индексf пробегает по
f
всем функциям алгебры логики, зависящим от n переменных. Мультипликативная сложность явно заданных функций алгебры логики изучалась в [2]—[7]. В [2] рассматривался важный класс симметрических функций алгебры логики и было доказано, что мультипликативная сложность
каждой симметрической функции, зависящей от n переменных, не превосходит n + Q{Jn). В [3] доказано, что ц(/) > n — 1 для каждой функции алгебры логики степени n, например, для функции x1 ... xn. Это — наилучшая доказанная нижняя оценка мультипликативной сложности для явно заданных функций, зависящих от n переменных (существование функции, зависящей от n переменных, с мультипликативной сложностью (1 + o(1))2n/2 в [1], [2] доказано мощностными рассуждениями). В [3] показано, что мультипликативная сложность каждой мультиаффинной функции алгебры логики, зависящей от n переменных, не превосходит (n — 1). В [3], [4] изучались квадратичные функции. Было показано, что мультипликативная сложность каждой квадратичной функции алгебры логики, зависящей от n переменных, не превосходит |_n/2_|, где LaJ обозначает наибольшее целое число, не превосходящее число a. Кроме того, были описаны квадратичные функцииf, зависящие от n переменных, для которых верно ц(/) = _n/2_. Мультипликативная сложность пороговой функции алгебры логики, зависящей от n переменных, с порогом 2 была получена в [7]. В [5], [6] получены также значения мультипликативной сложности для некоторых других функций алгебры логики.
В [8] изучалась связь между мультипликативной сложностью и сложностью схем из функциональных элементов для функций алгебры логики. Было показано, как получить нижнюю оценку сложности схем из функциональных элементов в базисе из всех функций, зависящих от двух
1) Работа выполнена при финансовой поддержке РФФИ (коды проектов 13-01-00684-а, 13-01-00958-а).
переменных, для некоторых функций, если известна мультипликативная сложность этих функций. В этой же работе была получена нижняя оценка (7/3)п для сложности схем из функциональных элементов некоторых функций, мультипликативная сложность которых равна (п — 1). В [9] показана связь между мультипликативной и аддитивной сложностями функций алгебры логики.
В настоящей статье рассматриваются функции алгебры логики, которые представимы в виде х1х2 ... хп © q(x1, ..., хп), где #(хь ..., хп) — квадратичная функция. Мы исследуем мультипликативную сложность таких функций. Известно, что найдутся такие квадратичные функции алгебры логики, зависящие от п переменных, квадратичная сложность которых равна |_п/2_|. Мы изучаем, как меняется мультипликативная сложность таких функций при добавлении к ним слагаемого х1 ... • хп и доказываем, что мультипликативная сложность каждой такой функции, зависящей от п переменных, равна (п — 1). Затем рассматриваются функции алгебры логики, которые представимы как сумма по модулю 2 двух мультиаффинных функций. Доказывается, что мультипликативная сложность функций алгебры логики, которые представимы в виде х1 ... хп © г(х1, ., хп), где г(х1, ..., хп) — мультиаффинная функция, в некоторых случаях равна (п — 1). Для получения оценок применяется один и тот же подход.
Работа устроена следующим образом. В разд. 1 вводятся основные определения и обозначения. В разд. 2 рассматриваются некоторые свойства квадратичных функций алгебры логики и доказываются оценки мультипликативной сложности функций, представимых как произведение всех переменных и некоторой квадратичной функции. В разд. 3 рассматриваются мультипликативные функции и их свойства и доказываются оценки мультипликативной сложности для некоторых функций, представимых как сумма по модулю 2 двух мультиаффинных функций.
1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ
Функции алгебры логики и их полиномиальные представления. Пусть В = {0, 1}. Если а = = (аь ..., ап) е Вп и р = (Ьь ..., Ьп) е Вп, то а < р при а1 < Ь1, ..., ап < Ьп (п > 1). Весом |а| набора а =
ХП
а1 (здесь рассматривается сумма целых чисел). Если
I = 1
а = (а1, ..., ап) е Вп, то моном та = П х1 соответствует набору а. Мы полагаем, что т,0 ..., 0) = 1.
X ±а1 = 1
Функцией алгебры логики/, зависящей от п переменных, называется отображение/: Вп —»- В, п = 0, 1, ... . Каждая функция алгебры логики/(х1, ..., хп) представима в виде
© «а,
а е В : сДа) = 1
где /а) = ©/(р) е В — коэффициенты, а е Вп, и © обозначает сложение по модулю 2. Это пред-
в < а
ставление функций алгебры логики называется полиномом Жегалкина. Известно, что каждая функция алгебры логики однозначно представляется полиномом Жегалкина (см. [11]). Степенью ёе§(/) функции алгебры логики/(х1, ..., хп) называется величина тах |а| .
а е ВП : сДа) = 1
Схемы из функциональных элементов и мультипликативная сложность. Схемой из функциональных элементов в базисе {х & у, х © у, 1} называется ориентированный граф без ориентированных циклов, полустепень захода каждой вершины в котором равна или 0, или 2. Вершины со полустепенью захода 0 помечаются или переменными из множества {х1, ... , хп}, или константой 1. Такие вершины называются входными. Вершины с полустепенью захода 2 помечаются или функциональным элементом конъюнкции (&), или функциональным элементом сложения по модулю 2(©). Такие вершины называются внутренними. Некоторая вершина помечается как выходная. В каждой вершине V схемы из функциональных элементов реализуется некоторая функция алгебры логики. Если V — входная вершина с приписанной ей переменной х^ (соответственно, константой 1), то в этой вершине реализуется функция, тождественно равная переменной х^ (соответственно, константе 1). Если дуги из вершин v1 и v2 ведут в вершину V, а в вершинах v1 и v2 реализуются функции алгебры логики/1 и/2 соответственно, и вершина V помечена элементом конъюнкции (соответственно, элементом сложения по модулю 2), то в вершине V реализуется функция/1 & /2 (соответственно, функция /1 © /2). Говорят, что схема из функциональных элементов С реализует функцию/, если в схеме С найдется вершина V, в которой реализуется функция/
Мультипликативной (или конъюнктивной) сложностью функции алгебры логики/(хь • ••, хп) называется минимальное число элементов конъюнкции в схемах из функциональных элементов в базисе {х & у, х © у, 1}, каждая из которых реализует функцию/.
2. МУЛЬТИПЛИКАТИВНАЯ СЛОЖНОСТЬ НЕКОТОРЫХ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ
Функция алгебры логики / называется квадратичной, если ёе§(/) = 2. В [4] доказано, что ц(/) < _п/2_ для произвольной квадратичной функции алгебры логики, зависящей от п переменных, а также описаны квадратичные функции/, зависящие от п переменных, для которых верно ц(/) = _п/2_|. Нам нужна структура минимальных схем из функциональных элементов, реализующих квадратичные функции алгебры логики. Поэтому здесь мы сформулируем некоторые результаты (лемму 2.1) из [4]. Заметим, что наша формулировка несколько иная, чем в [4], но она нам больше подходит.
Функция алгебры логики/ называется аффинной, если ёе§(/) < 1. Обозначим множество всех аффинных функций, зависящих от переменных х1, „., хп, черезАффинная функция/называется линейной, если с/(0, •.., 0) = 0. Обозначим множество всех линейных функций, зависящих от переменных х1, „., хп, через Ьп. Линейные функции g1, „., gm называются линейно независимыми, если из того, что
ех gl ©...© = 0,
где с1, „., ст е В, следует, что с1 = „. = ст = 0. В противном случае, линейные функции g1, „., gm называются линейно зависимыми. Известно, что множество Ьп является линейным пространством размерности п (см. [12]).
Выражение вида
I
г © © g¡ • ^,
г=1
где g1, „., g¡, Н1, „., Н1 е Ьп, а Н е называется квадратичной псевдополиномиальной формой (сокращенно, КПП формой) с длиной ¡. Несложно увидеть, что каждая квадратичная функция может быть представлена какой-то КПП формой, например, своим полиномом Желалкина. Длиной ¡2(/) квадратичной функции алгебры логики / в классе КПП форм называется минимальная длина среди всех КПП форм, реализующих функцию /. Понятно, что для произвольной квадратичной функции/, зависящей от п переменных, верно неравенство ¡2(/) < п(п — 1)/2. Но справедливо более сильное утверждение, а именно, что для произвольной квадратичной функции /, зависящей от п переменных, верно неравенство ¡2(/) < _п/2_.
Если КПП форма Р реализует функцию /, и длина Р равна ¡2(/), то будем говорить, что Р — минимальная КПП форма для функции /.
Лемма 2.1 (см. [3], [4]). Если Р — минимальная КПП форма квадратичной функции алгебры логи-
1—Г1
ки /(х1, „., хп), и Р имеет вид ? © 11 & • Н, где g1, „., g¡, Н1, „. , Н1 е Ьп, ?
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.