Полиномиальные операторные представления конечнозначных функций Зинченко Анна Сергеевна

Содержание к диссертации

Введение

1 Обзор полиномиальных представлений 19

1.1 Полиномы и конечнозначные функции 20

1.2 Разложения по бинарным термам 24

1.3 Разностный оператор и оператор сдвига в полиномиальных представлениях булевых функций 29

2 Оператор подстановки в полиномиальных представлени ях булевых функций 32

2.1 Разложения, применимые к произвольным булевым функциям 33

2.2 Нечетные, несохраняющие единицу бинарные функции в полиномиальных представлениях 44

3 Разностный оператор и оператор сдвига в полиномиальных представлениях конечнозначных функций 55

3.1 Свойства операторов 56

3.2 Существование полиномиальных операторных представлений 60

3.3 Способы порождения и специальные классы базисных пучков 71

3.4 Некоторые оценки сложности 78

Заключение 87

Список литературы

• Разложения по бинарным термам
• Разностный оператор и оператор сдвига в полиномиальных представлениях булевых функций
• Нечетные, несохраняющие единицу бинарные функции в полиномиальных представлениях
• Существование полиномиальных операторных представлений

Введение к работе

Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике. Математические модели. описанные на языке функций, находят широкое применение в различных областях человеческой деятельности. В последнее время интенсивно развивающейся областью теории функций является класс дискретных функций, так как аппарат таких функций используется при проектировании современных вычислительных устройств [3, 8, 10], кодировании информации [41], передаче данных [И] и др.

В теории дискретных функций значимой частью является теория конечнозначных функций, то есть функций, которые определены на множестве {0,1,...,&—1}и принимают значения из этого же множества. Такие функции возникают как в самой теории функций, так и в многозначной логике (поэтому конечнозначные функции часто называют функциями /с-значной логики), в которой требуется для описания некоторых явлений употреблять высказывания, принимающие более двух значений, в частности для описания широко известной проблемы «будущей случайности». В девятой главе трактата «Об истолковании» Аристотель ставит следующую проблему: верно ли, что относительно единичного и вместе с тем будущего события всякое утверждение или отрицание истинно или ложно? Данная проблема оказалась продуктивной для развития логики: распространенным является мнение, что именно многочисленные попытки логической реконструкции подхода Аристотеля к решению проблемы будущей случайности привели к появлению многозначных логик, которое связывается, прежде всего, с именем Я. Лукасевича [38].

Традиционной для теории функций является задача представления функций суперпозицией других функций. Одним из решений этой задачи является построение полных систем функций. Различные примеры полных относительно суперпозиции систем конечнозначных функций можно найти в работах [75, 76, 67, 69, 70, 42, 43].

Но это достаточно общий ответ на вопрос, так как для произвольной

функции он не указывает какой вид имеет представление через функции данной системы. Поэтому естественной является следующая задача: можно ли построить представления конечнозначиых функций, имеющих заданный вид?

Одним из ответов на этот вопрос является возможность представления таких функций дизъюнктивными и конъюнктивными нормальными формами и их аналогами для произвольного к > 2 [55, 67]. Для к = 2 наиболее общая постановка задачи рассматривалась О. Б. Лупаиовым в работе [39], где отмечается возможность декомпозиции по произвольной функции без фиктивных переменных.

Особый интерес при представлении функций специальными формами вызывают представления, использующие внешнюю операцию «сложение по модулю к», так как они находят широкое применение при синтезе и упрощении схем [5, 7, 55]. Такие представления мы будем называть полиномиальными формами, то есть под полиномиальным представлением понимается представление функций в виде суммы конечного числа определенным образом построенных слагаемых

/ = S\ + ... + S_m.

Среди полиномиальных представлений выделяют два направления: разложения при простых значениях к и при составных. Это деление обусловлено тем. что при простом к множество {0,1,..., к— 1} относительно сложения и умножения по модулю к образует поле. Поэтому при изучении таких конечнозначиых функций можно применять известные результаты теории полей.

Для простых к наиболее изученным является случай к = 2, при котором функции называются булевыми или функциями алгебры логики.

В диссертаций исследуются специальные полиномиальные представления конечнозначиых функций при простых к, для которых рассматриваются вопросы существования и сложности.

Условия, налагаемые на систему функций, по которой существует полиномиальное разложение для любой конечиозначной функции при

фиксированном количестве аргументов, в общем случае известны и состоят, обычно, в требовании невырожденности матрицы, образованной значениями функций некоторой подсистемы. Но вызывает интерес проблема более подробного описания классов функций, удовлетворяю]цих этим условиям. Кроме того, задача проверки невырожденности матрицы является нетривиальной.

Б ряде работ был предложен и разработан операторный подход к исследованию специальных представлений конечнозначных функций [15. 16, 51, 52, 12], где под оператором на множестве Fj? ( конечнозначных функций от п переменных при фиксированном простом к) понимается любое отображение t : F% -^ F%.

В работе [52] выделяется класс операторов, включающий в себя большинство из известных операторов и обладающий свойством замкнутости относительно суперпозиции и применения операции алгебры ко-нечнозначной логики.

Зафиксируем набор х = (х\,... ,х_г) и будем рассматривать операторы q^ вида

где h — (г + т)-местная функция, / — фиксированные функции. При этом если переменная хі не встречается среди переменных функции /, то считаем, что /^ = /. Рассматривается класс таких операторов по всем х.

Пусть д является п-местной конечгюзначной функцией, tj,..., t,₍ — операторы, тогда операция д на множестве операторов из этого класса определяются следующим образом:

#(ti,...,t_n)/= 5(^/,--АЯ-

Произведением операторов и и v называется оператор uov, определяемый и о v — u(v/).

В диссертационной работе рассматриваются три специальных оператора из этого класса: разностный — dj, подстановки — sj и сдвига —

Vx\ (аналогичные или похожие можно найти в работах [11, 24. 51]):

VxJ І'¹'¹; '"і^ж«)--- і^Хп) ⁼ j{^xl, і^жі-1; ^хі + ^аі;^Хі+1> >^:Т'п)і

<г/(.х_ь ...,х_и..., х_п) = /(яі,..., ц,..., х_п) + f{x_u ..., Хі-иХі + сц, х_і+1,..., х_п),

Также в работе используется тождественный оператор е, который определяется естественным образом.

При рассмотрении таких операторов нижний индекс как правило опускается, если это не вызывает недоразумений.

Для набора констант а = (с^,... ,а";_г) и набора переменных х — (xi_v ... ,x_ir) оператор t~ определяется как произведение г операторов й\ 0-.-0. где і є {e,p,d,s}.

В рамках этого подхода можно переформулировать известные результаты: например, возможность представления любой булевой функции суммой произведений остаточных подфункций [17] записывается как представление функции в виде:

где х_}у — разбиение множества переменных функции / на две части, д — конъюнкция, a$f Є {0,1}, а суммирование берется по всевозможным наборам сг, т.

Естественным является вопрос: какие еще функции кроме конъюнкции можно использовать в качестве д для представления функции в таком виде? Основным результатом второй главы диссертации является ответ на этот вопрос.

Многие известные полиномиальные представления булевых функций удалось описать с использованием разностного оператора и оператора сдвига [15, 12, 1]. Полиномиальные представления произвольных конечнозначных функций с использованием этих операторов рассматриваются в [51]. В третьей главе продолжаются исследования таких полиномиальных представлений: в частности, найдены критерии существования двух видов представлений и приведены некоторые оценки сложности.

Полученные результаты имеют теоретическое значение и могут найти применение в исследованиях по теории функциональных систем и по теории сложности функций многозначных логик. Результаты могут быть использованы при проектировании дискретных преобразователей информации.

При доказательстве результатов диссертации используются методы дискретного анализа, в частности комбинаторики, а также методы теории конечнозначных функций, алгебры и линейной алгебры.

Для понимания дальнейшего изложения и формулировки результатов диссертации введем используемые обозначения и определения:

переменные — Жі, ..., х_п\

х - вектор-переменная (жі,.. ,, х_п);

константы -- а, 6, с,..., а, /3,7, , возможно с индексами;

область значений переменных, констант и функций — множество Ek = {0,1,..., к — 1}, где к — простое число, возможно и 2;

а - набор констант (<ті,... ,а_п), где ег,; Є Е^\ б = (0,..., 0),... к^Л = {к - 1,..., к - 1);

Х\, х-2, - -, x_q — некоторое разбиение множества {xi,..., х_п\ переменных фу н к ции /; <7ъ 5"2; -, я? ^{— н} абор ы констант, 11 р и ч е м

jfflj = |ii|,...,|cr_ff| = \x_q\.

множество всех функций fc-значной логики от п переменных обозначим через F;

функция f(x) сохраняет единицу, если /(1) = 1;

операции " + " и "" выполняются но mod к;

операция " —" определяется как обратная к операции " + ";.

операция ^мф" есть сложение по mod 2;

булева функция называется нечетной, если вектор функции содержит нечетное число единиц;

функция &-зиачной логики fix) при к > 2 называется невырожденной, если выполняется условие

_{т * .}

и вырожденной в противном случае;

функцию f(x) будем называть полилинейной, если она линейна по любому своему аргументу;

для булевых функций будем считать, что

х, если а — 1;

І Ж, ЄСЛИ (7 = 0.

для функций /с-значной логики при к > 2 будем считать, что

x^Q = 1 и ⁿ = jc ... х,, если n ^ 0;

остаточными функциями от функции / по г-му аргументу называют
ся функции, размерности которых на единицу меньше размерности
/. Обозначаются и определяются остаточные функции следующим
образом:

для любого f Є ^2^_1' Если (7{ = 0, то остаточная функция называется нулевой остаточной; если 0{ = 1, то — единичной остаточной. Индуктивно распространяется понятие остаточной функции на множество аргументов i\._t..., ц по набору а^,..., <т:,_л (I < п):

Jii,...,ii ~~ \h_u...,k-i >ч

S^Y-'f ДЛЯ фуНКЦИЙ ПОЛучеННЫХ ИЗ / ПОДСТаНОВКОЙ Наборов <7_1; . . . , &і-\.

(j,;₊i,..., a_q вместо переменных множеств х\,..., 5j-i, .Xj+i, ...,(/ соответственно;

^] означает, что суммирование берется по всевозможным наборам

п\...а_п

(<П,...,а_п)є5

'71.

для нечетных бинарных булевых функций

х-у для /і(ж,у) = (0001

х Vy для Л (г, у) = (0111

.х -л у для /₃(г,г/) = (1101

х ^у для/₄(ж_;у) = (1011

ж | у для /₅(ж,г/) = (1110

ж I у для /₆(as,y) = (1000

ж ^ у для f₇{x,y) = (0010

х w- у для /₈(ж₍2/) = (0100

(конъюнкция);

(дизъюнкция); (импликация); (обратная импликация); (штрих Шеффера); (стрелка Пирса); (коимпликация); (обратная коимпликация);

для любого натурального п и любого і Є {1, ...,п} селекторной функцией называется функция е"(яі,..., ж_п), значения которой совпадают со значениями переменной Х{\

булева функция / называется симметричной, если на наборах с одинаковым количеством единиц она принимает одинаковые значения.

Первая глава диссертации посвящена обзору полиномиальных представлений конечнозиачных функций, при этом, как правило, сохраняются авторские обозначения и определения.

В первом параграфе главы приводятся общие результаты по таким представлениям, среди которых можно выделить представления в виде суммы произведений степеней переменных (представление полиномом по mod к), обобщением которых являются так называемые поляризованные полиномы.

Во втором параграфе рассматриваются известные полиномиальные представления с использованием оператора подстановки, многие из которых можно записать как представление функций в виде

f(Xi,.,.,X_g)

_{= Хл}

_{яі(4;/.»0/.---,9,-1(4:::/,4;/)---)), w}

0\Ої~Л_ц

и которые часто называются представлением в виде суммы бинарных термов.

В третьем параграфе рассматриваются полиномиальные представления булевых функций, в которых слагаемые строятся с использованием, так называемых, операторов нормализации и дифференцирования. Эти операторы являются частным случаем операторов сдвига и разностного.

Результаты, полученные диссертантом, изложены во второй и третьей главе.

Вторая глава посвящена полиномиальным разложениям булевых функций с использованием оператора подстановки, а именно представлениям вида (1) и вида

f(xi,...,x_q) =

«(s^/.ft^/.-.S^^/.s^/)...))

(2)

ffid-2-.-a,/

При q — 2. то есть когда множество переменных разбивается на две части, операторные представления (1) и (2) совпадают.

В первом параграфе показывается, что любую булеву функцию можно представить суммой импликаций остаточных подфункций.

Предложение 3 Для любой булевой функции f(x, у) имеет .место представление

Аналогично показывается справедливость этого результата для обратной импликации.

Показано, что кроме этих и известных ранее конъюнкции и дизъюнкции, нет других бинарных булевых функций, разложения по которым существуют для всех булевых функций при разбиении множества переменных на две части, поэтому можно сформулировать

Предложение 5 Разложение (1) при q = 2 имеет место для любой булевой функции т,огда и только тогда, когда д\ Є {V, , ^, —>}.

Эти результаты получены совместно с В. И. Пантелеевым.

В теоремах 1 и 2 рассматриваются разложения вида (1) и (2) при разбиении множества переменных функции на произвольное число компонент.

Теорема 1 Полиномиальные представления вида (1) имеют .место для любой булевой функции f тогда и только тогда, когда q = 2 и

Si {-,V,-,«-}

В теореме 2 формулируется аналогичный результат для представлений вида (2).

Во втором параграфе дается описание класса булевых функций, допускающих полиномиальное представление, в элементарные слагаемые которых входят нечетные, несохраняющие единицу функции, то есть коимпликация. обратная коимпликация, штрих Шеффера и стрелка. Пирса образой самой функции по оператору подстановки.

Предложение 6 Булева функция /(жі,^) представимо, в виде

f(x_ltx₂) = - [^/(^1. <^sg/(i,₂)] ,

тогда и только тогда, когда не существует наборов fi,...,f_m. т = 2г + 1, г > 0 таких,что для любого а\ выполняется

\<1<т

В предложении 7 рассматривается аналогичное разложение для ко-импликации.

Для разложений по штриху Шеффера справедливо следующее Предложение 8 Булева функция f(xi^x₂) представилш в виде

тогда и только тогда, когда не существует представления константы 1 по функции f и конъюнкции вида

в которой выполняется равенство ^ р^₂ = 1.

В предложении 9 рассматривается аналогичное разложение для стрелки Пирса.

Результаты второй главы опубликованы в работах [27, 28, 29. 35].

В третьей главе рассматриваются полиномиальные операторные представления конечиозначных функций по операторам, являющимся произведением оператора сдвига, разностного и тождественного. Длиной такого оператора называется число операторов в произведении.

В первом параграфе рассматриваются основные свойства этих операторов. Вводится понятие пучка операторов.

Пучком операторов называется упорядоченное множество, состоящее из к^п операторов длины п, число п называется размерностью этого пучка.

Во втором параграфе рассматриваются два типа полиномиальных операторных представлений функций &-значной логики, в которых элементарными слагаемыми являются:

1. операторные образы фиксированной функции д(х) по операторам из заданного пучка Т

2. операторные образы функций д^Іх) из системы функций G по фиксированному оператору t

f{x}= ^ cttgt(x)_} gz(x) Є G, с_ъ Є Е_к.

Для рассмотрения вопросов существования полиномиальных представлений первого типа вводится понятие базисного пучка операторов.

Пучок операторов Т размерности п называется базисным, если существует такая функция g Є Fj}. что любую функцию / Є Ff. можно представить в виде линейной комбинации операторных образов функции g по операторам из Т.

При описании базисности определяется матрица, пучка и вводятся специальные характеристики оператора длины 1.

Для каждой компоненты t^a оператора t определим константы а и /3 следующим образом

^{

О при а = 0; 0 при і = р и а Ф 0;

1 при а ф 0, I 1 в остальных случаях.

Матрицей пучка Т - {t, ..., t^fc_1} операторов t^? = t'g ... t^f длины n назовем матрицу Mj = (гп^-А такую, что

где о,т Є j?, а

1. при а = 0; , , I 1 при а = т или г = 0;

2. при а ^ 0, I 0 в остальных случаях.

Справедлива

Теорема 3 Если Т = {t,..., t*"¹} — пучок операторов длины п и д(х) Є F'j}, то любую функцию f(x) Є Fj можно представить в виде

f(x) = ^2 c^t^ag(x), где с_ъ Є E_k

тогда и только тогда, когда выполняются условия:

1. detM-r^O,

2. g[x) — невырожденная функция.

Теорему 3 можно использовать в качестве критерия базисности пучка. Кроме того справедлив следующий результат.

Предложение 15 Пучок операторов Т = {t,... t^fe_1} является базисным тогда и только тогда, когда для любого оператора и найдутся такие Cq, ...,с~, что для любой функции f{x) имеет место следующее разлооїсение

и/(ї) = ^/(5) + ... + 0^^/(.

Критерий существования разложений второго типа представлен в следующей теореме.

Теорема 4 Пусть Т — класс операторов и G = {д$,..., Рггт} — базис пространства всех п-местных функций k-значной логики, к > 2. Тогда для любой функции f(x) и любого t Є Т существует единственное полиномиальное представление

^:/(3)=^^(5-),

Г ^н

где а лвляет,ся набором показателей оператора t, а с~ Є Е^.

Замечание При к — 2 теорема 4 справедлива, если в произведении операторов встречаются только ір и е.

В третьем параграфе предлагаются способы порождения базисных пучков, а также вводятся и исследуются некоторые специальные классы базисных пучков,

В четвертом параграфе приводятся оценки функции Шеннона для рассматриваемых полиномиальных операторных представлений.

Пусть P\(f) — полином, представляющий функцию /. Сложностью L(P_t(fJ) полинома Д(/) будем называть число слагаемых в нём. Число

Щ/)= min L{P_t(f))

назовём сложностью функции f в классе полиномов К. Сложностью класса функций S в классе полиномов К будем называть число

LK(S) = maxLK(f).

Если S = F, то используем обозначения ЬК{п).

Рассматриваются два класса полиномов: К = К — линейные комбинации образов функций из базиса G по операторам из Т и К = Щ линейные комбинации образов невырожденной функции g по пучку из класса пучков Т.

Среди базисов пространства FJ} выделяются два:

G₂ - {v^h . - .pS(si> , г_п)|(гі, - , і_п) Є Щ,

где д — невырожденная функция. Первый базис состоит из произведений степеней переменных, второй из сдвигов функции д.

Среди пучков выделяется пучок О = (о\¹...о¹^\(ц, ....і_п) Є Щ, 0{ Є {р, d}), который называется однородным, и его частные случаи

Р = (р'\..рЧ(п,...,ї„) Є Щ) и D = (d\..(T"|(ti, ...,i„) Є Я).

Верхняя оценка сложности класса полиномов LK_D^l указана в следующем утверждении.

Теорема 5 При любом п > 1

^{"D v'- fc(fc-l) + r fc^^-jfe + l)'}

В теореме 6 приводится нижняя оценка сложности для этого класса полиномов, полученная совместно с В.И. Пантелеевым.

Теорема 6 При любом п > 0 справедливо неравенство

Я(„)>р±1у, k>3. Теорема 7 При любом п>1

Кроме того, в параграфе поставлен вопрос о соотношении сложностей класса всех функций fc-значной логики в полиномиальных представлениях первого типа по различным функциям. Ответ па него дает следующая теорема.

Теорема 8 Для любого класса В базисных пучков операторов значение функции Шеннона ЬК^(п) не зависит, от выбора функции д{х).

Таким образом, при рассмотрении сложностей класса полиномов ЬЩ, состоящих из линейных комбинаций образов невырожденной функции д по пучку из класса пучков Т, можно использовать обозначение LKj

и рассматривать полиномиальные разложения по операторным образам любой невырожденной функции.

Результаты третьей главы опубликованы в работах [30, 31, 32. 33, 34, 36].

Диссертация изложена на 96 страницах машинописного текста: состоит из введения, трех глав, разбитых надевать параграфов, заключения и списка литературы, содержащего 78 наименований, включая работы диссертанта,

В работе используются следующие утверждения: предложения, теоремы, следствия. Нумерация теорем и предложений — сплошная, следствия не нумеруются. В первой и третьей главе формулируются несколько теорем, принадлежащих другим авторам. Такие теоремы нумеруются римскими цифрами. Формула нумеруется только в том случае, если на нее в тексте есть ссылка. Для формул используется двойная нумерация: первым идет номер главы, вторым — номер формулы в главе.

Начало и конец доказательства предложения или следствия будут обозначаться соответственно символами > и <1, теоремы — и <.

Результаты диссертации были представлены на ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета (Иркутск, 2001 г., 2002 г., 2003 г.), Международной конференции «Компьютерные науки и информационные технологии» (Саратов, 2002 г.), второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск. 2003 г.), Международной конференции «Алгебра, логика и кибернетика» (Иркутск, 2004 г.), VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2004 г.). XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), школе-семинаре «Синтаксис и семантика логических систем» (Иркутск, 2006 г.), а также докладывались на семинаре кафедры Математической информатики Иркутского государственного педагогического университета «Дискретная математика и математическая информатика» под руководством проф,_; д.ф.-м.и. Н.А. Перязева.

По теме диссертации опубликовано 10 научных работ, отражающих основное содержание диссертации, в том числе две работы в журналах, рекомендованных ВАК РФ.

1. Зинчеико А. С. Некоторые полиномиальные представления булевых функций / А. С. Зинчеико, В. И. Пантелеев // Вестник Иркутского университета. Специальный выпуск: Материалы ежегодной научно-теоретической конференции молодых ученых. — Иркутск: Иркут. ун-т., 2001. - С. 72-73.

2. Зинченко А. С. Специальные полиномиальные представления булевых функций / А. С. Зинченко, В. И. Пантелеев // Компьютерные науки и информационные технологии: Материалы международной конференции (Саратов, 2002 г.). — Саратов: Изд-во С арат, ун-та, 2002. — С. 28-29.

3. Зинченко А. С, Полиномиальные представления булевых функций с использованием собственных подфункций / А. С. Зинченко // Вестник Иркутского университета. Специальный выпуск: Материалы ежегодной научно-теоретической конференции молодых ученых. — Иркутск: Иркут. ун-т., 2002.- С. 8-9.

4. Зинченко А. С. О базисных пучках операторов булевых функций / А. С. Зинченко // Вестник Иркутского университета. Специальный выпуск: Материалы научно-теоретической конференции молодых ученых, посвященной 85-летию ИГУ. — Иркутск: Иркут. ун-т.. 2003. — С. 76-77.

5. Зинченко А. С. О представлении функций конечнозначиой логики пучками операторов / А. С. Зинчеико, В. И. Пантелеев // Алгебра, логика и кибернетика: Материалы Международной конференции, посвященной 75-летию со дня рождения профессора А. И. Кокорина (Иркутск, 25-28 августа 2004 г.). — Иркутск, Изд-во Иркут.гос.пед.ун-та, 2004. — С. 139-142.

6. Зинченко А. С. Полиномиальные операторные представления
функций fc-значной логики / А. С. Зинченко, В. И. Пантелеев // Дис
кретные модели в теории управляющих систем: Труды VI Международ-

ной конференции, посвященной 80-летию со дня рождения С. В. Яблонского (Москва, 7-11 декабря 2004 г.). — М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2004. - С. 31-32.

7. Зинченко А. С. О нижней оценке сложности операторных полиномиальных форм для функций &-значной логики / А. С. Зинченко, В. И. Пантелеев // Проблемы теоретической кибернетики: Материалы XIV Международной конференции, посвященной 80-летию со дня рождения СВ. Яблонского (Пенза, 23-28 мая 2005 г.) Под редакцией О. Б. Лупа-нова. — М.: Изд-во механико-математического факультета МГУ, 2005. — С. 51.

8. Зинченко А. С. Базисные пучки операторов функций &-значной логики / А. С. Зинченко // Синтаксис и семантика логических систем: Материалы российской школы-семинара, посвященной 100-летию со дня рождения К. Геделя (Иркутск, 23-27 августа). — Иркутск. Изд-во Иркут, гос. пед. ун-та, 2006. — С. 36-39.

9. Зинченко А. С. Полиномиальные представления булевых функций по коимпликации / А. С. Зинченко // Вестник БГУ. Серия 13: Математика и информатика. — 2006. — Вып.З. — С. 23-28.

10. Зинченко А. С. Полиномиальные операторные представления
функций fc-значной логики / А. С. Зинченко, В. И, Пантелеев /./ Дис
кретный анализ и исследование операций. Сер. 1. — 2006. — Т.13, № 3. —
С. 13-26.

Разложения по бинарным термам

Напомним, что под полиномиальным разложением функции / понимается представление / в виде / — Si + ... + Sm, где сложение рассматривается по mod к, a 1 построены некоторым специальным образом.

Достаточно часто слагаемые представляют бинарные термы, в построении которых используются только бинарные функции, символы переменных и остаточные разлагаемой функции.

Дадим строгое определение бинарного терма. Пусть (7i,(72 — константы, Xi,Xj — символы переменных, f\ и /2 — некоторые остаточные функции /, тогда: 1) если д - бинарная функция, то д(х\ xf), g{xai\fl), p(/i,/2) бинарные термы: 2) если д — бинарная функция, В — бинарный терм, то д(х \В)., g{.fi,B) — бинарный терм.

Среди представлений, в которых слагаемые являются бинарными термами, выделим два типа: 1) с использованием символов переменных; 2) без использования символов переменных (то есть слагаемые построены только из остаточных функций).

Наиболее изученными такие представления являются в теории булевых функций. Например, к представлениям первого типа относятся хорошо известные: В большинстве таких разложений в качестве бинарной функции берется конъюнкция. Но использование конъюнкции не является обяза.-тельным. В [4] приводится представление булевых функций в виде суммы по модулю 2 импликаций аргументов.

В [1] показано, что в разложениях такого типа можно использовать любую нечетную функцию.

Теорема III [1] Любая булева функция /(х і,..., хп) умеет полиномиальное разлоэ/сение по переменным х,/а,..., ж;т, т п: f(xb...,xn) = YJ (xh1+TlAl... ( +ТтД7 (Ж1)... , ,...,(7 ,...,) )...)), где для г = 1,..., т 0, если А7; Є {, j, -7-, -), [О, есл,и Ат Є {V,4, —У, -л-}, 1, если Aj Є {V, І, «-, "-}; [1, если Дт Є {-,1, -,+ }.

В этой же работе как следствие из теоремы III приведены разложения по одной функции или разложения без использования отрицания — позитивные разложения.

Нечетность бинарных функций, используемых во всех этих разложениях, является необходимым условием того, что разложение такого вида можио применить ко всем булевым функциям. Это требование можно получить из следующего достаточно очевидного утверждения.

Предложение 1 Булева функция f(xi,..., хп) является нечетной тогда и только тогда, когда степень полипома Жегалтна, представляющего эту функцию равна п. Среди разложений второго типа рассматриваются представления вида где gi{yu 2/г)і - 9q-i ІУь 2ft) - бинарные функции. Интересен вопрос: при каких условиях такие представления возможны для всех конечнозначных функций. Как и для разложений первого типа достаточно очевидным является утверждение Предложение 2 Если разложение (1.2) имеет, .место для любой булевой функции f, то функции gi,..., gq-\ являются нечетными. В работах [17, 13] для разложения (1.2) при к = 2 и q — 2 были рассмотрены случаи, когда бинарной функцией д\ является конъюнкция или дизъюнкция. Теорема IV [17] Любая булева функция /( 1,) имеет, разложение вида /(жі,Е2) = Х]а (Я:х /) Теорема V [13]. Любая булева функция /(а г) имеет разложение вида f(xu ...,!„) = Yla a ll v fit) 28 В работе [53] представление (1.2) было рассмотрено для произвольного к. Теорема VI [53]. Для любой функции к-значной логики /(.ЇЇ, хъ) имеет, место разложение тогда и только тогда, когда к = Рі-р2Рп гдєрі7р2, рг —попарно различные простые числа (г 1).

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

Функции 1, которые допускают разложения для всех булевых функций при q = 2, являются нечетными и, кроме того, для них выполняется условие (?1 (1,1) — 1. Это условие можно получить из (2.1) непосредственно, взяв в качестве функции / константу 1. Но, кроме того, справедлив следующий результат.

Предложение 4 Для любой нечетной булевой функции д\ [у\, у{] такой, что gi(l,l) = 0 существует неконстантная функция, которая не допускает, представления в виде (2.1) при q = 2. Пусть (ft (1,1) = 0. Тогда если вектор функции д\ содержит одну 1, то можно взять, например, соответствующую селекторную функцию, а если три 1. то функцию ху + 1. ОС ЇДРУТЕ;;ЕК:І:-.Л Таким образом, в случае когда множество переменных разбивается на две части, из теорем IV, V и предложений 3, 4 следует окончательный результат.

Предложение 5 Разложение (2.1) при q = 2 имеет, место для любой булевой функции тогда и только тогда, когда Q\ Є {V, -, (—, — }. Оказывается случаем q — 2 описываются все разложения вида (2.1). применимые к любой булевой функции. Теорема 1 Полиномиальные предстлвления вида, (2.1) имеют место для любой булевой функции f тогда и только тогда, когда q = 2 и Si {-,V,- , -}. Возможность таких полиномиальных, представлений при q = 2 показана в предложении 5.

Покажем, что для любого q 2, для любых нечетных бинарных булевых функций gi,...,gq_i существует функция / и разбиение множества переменных на q чкомпопент, при котором не имеет место разложение (2.1).

Такой функцией является, в частности, функция /, обладающая свойствами а) она симметрична, б) ее полином Жегалкина содержит нечетное количество слагаемых, в) каждая переменная входит в нечетное число слагаемых, г) для каждой переменной Х{ в полиноме Жегалкипа есть слагаемое .Xj.

При q — 2m + 1 функцией, обладающей такими свойствами, является линейная функция / = х\-\- х% + %%п+\ 2. При q = 2т таковой является в частности функция, полученная из полинома Жегалкина, у которого свободный член равен нулю, коэффициенты при произведении 2т — 1 переменных тоже равны 0, а коэффициенты при всех остальных возможных произведениях равны 1.

Рассмотрим разложения булевых функций вида (2.2). При q = 2 такие представления совпадают с разложениями вида (2.1). Пусть q 2. Достаточно показать, что в этом случае для любого q найдется функция, которая не допускает разложение. Очевидно, что в качестве gi имеет смысл подставлять только невырожденные бинарные функции. Доказательство разобьем па две части. (а) Рассмотрим представления вида (2.2), в которых Q\ — ... = gq \ и Pi Є bV,-», -, ,4, , -}.

Множество переменных {#i,..., хп] разобьём на п компонент \х\\U ... U {х„}, то есть q = n. Рассмотрим разложение Аналогичным образом можно рассмотреть функцию ху.. . жґ/+1 для разложений, когда ft Є {і-, ], } и функцию xq для разложений

Тогда, если то в качестве контрпримера приводим функцию. Если существуют берем любую из вышеприведенных функций. 2.2 Нечетные, несохраняющие единицу бинарные функции в полиномиальных представлениях

Если рассматривать разложения (2.1) при q 2 с использованием в качестве д\ других нечетных бинарных функций, то не все булевы функции допускают такие представления. Существует восемь нечетных бинарных булевых функций, разложения по четырем из них (конъюнкции, дизъюнкции, импликации и обратной импликации) описаны в предыдущем параграфе. Оставшиеся четыре функции являются функциями, несохраняющими единицу, то есть на наборе (1,1) принимают значение

Опишем класс функций, допускающих полиномиальные разложения нида (2.1), в элементарные слагаемые которых входят нечетные, несохраняющие единицу функции, то есть коимпликация. обратная коимшшка-ция. штрих Шеффера и стрелка Пирса образов самой функции по оператору подстановки.

Нечетные, несохраняющие единицу бинарные функции в полиномиальных представлениях

В этой главе рассматриваются полиномиальные операторные представления конечнозначных функций по операторам, являющимся произведением операторов сдвига, разностного и тождественного.

В первом параграфе даются определения и рассматриваются основные свойства введенных операторов. Определяется пучок операторов.

Во втором параграфе исследуются два типа полиномиальных операторных представлений функций fc-значной логики, в которых элементарными слагаемыми являются: операторные образы фиксированной функции д(х) по операторам из заданного пучка Т и операторные образы функций д$(х) из системы функций G по фиксированному оператору t. Рассматриваются вопросы существования таких представлений. Вводится понятие базисного пучка операторов. В третьем параграфе предлагаются способы порождения базисных лучков, а также вводятся и исследуются некоторые специальные классы базисных пучков. В четвертом параграфе приводятся оценки функции Шеннона для рассматриваемых полиномиальных операторных представлений.

Свойства операторов В этой главе под оператором, действующим на функцию f(x) Є F будем понимать последовательность символов i"1 2 - -О таку JO, ЧТО U Є {е,р, d}, щ Є Ej при г Є {1,2,... ,п}, и которую будем обозначать через t, ее члены называть компонентами оператора, U — основанием компоненты оператора, щ — ее показателем, а число п — длиной оператора. Оператор определяется индуктивно следующим образом.

Пустая последовательность задает единственный оператор длины 0. Обозначим его 0. Оператор длины п задает отображение из F в F" по правилу lf(x) — /п(ж), где fn(x) определяется по индукции следующим образом: /о(а?) — /(ж),

При п = 1 оператор єа будем называть тождественным, pa — оператором сдвига, а d — разностным оператором.

Напомним, что операции сложения +, вычитания —, умножения выполняются по модулю к. Операция 0 есть сложение по модулю 2. Также будем считать, что Х = 1 если п 0. ТІ Пример 5 Пусть к — 3 w n = 3. рассмотрим действие оператора X = e2p2d1 на функцию f(x) = 21 2 3 + а жз + жі + 2. tf (ж) - е2р2 (жіж2(2ж3 + 1) + ж2(2ж3 + 1) + 2жі + 1) - є2 {Xl{x2 + 2)(2ж3 + 1) + (12 + 2)(2 + 1) + 2хг + 1) = - хі{х2 + 2)(2ж3 + 1) + {х2 + 2)(2ж3 + 1) + 2жі + 1. Пусть задан оператор t — 12. - .". Весом этого оператора u (t) будет называться натуральное число: 11, если ti ф г и ц ф О, w{t) = l aU гДе ai = j=l I 0, если ti — е или щ = 0. Следующее предложение показывает линейность введенных операторов. Предложение 10 Для любых; функций fix) и д(х), для любого оператора t выполняется: t(f(x)+g(x))=tf(x) + tg(x). О Доказательство будем проводить индукцией по весу оператора I = (t). Базис индукции. Пусть I 0. Тогда оператор t имеет вид t = ... , то есть является тождественным. По определению тождественного оператора выполняется равенство е ... є/(ж) — /(ж), откуда следует выполнение условия предложения. Шаг индукции. Пусть I 0 и в операторе t tm ф е и ат т О-Рассмотрим оператор h. = / 1 ... Л 1, где Л,; — .;, 6; = ( при і ф гпи hm = е или 6m = 0. Тогда оператор t может быть представлен в следующем виде tf(x) = e...e e...e(h ..fh m). Откуда по предположению индукции следует цепочка тождеств t (/() + g(x)) = е ... etfte ...e(hh (f(x) + 5())) = Обозначим ta(ia{..Aa{f{x))...)) = {ta)lf(x). і Предложение 11 ДЛЯ любой функции f{x) справедливы следующие равенства (pa)kf(x) = f(x), (&a)kf(x) = 2f(x). О Действительно, для оператора сдвига (pa)kf(x) = (pf- a + а) = (рв) "2/(я + 2а) = ... ... - (Va)f(x + (к- 1)а) = /(я + ка) = /(я). Для разностного оператора i=0 -1

Следующее предложение готовит о сохранении свойства быть вырожденной функцией в операторном образе вырожденной функции.

Предложение 12 Если функция fix) вырооюденная, то для любого оператора t функция tf(x) также является выроо/сденной. Оператор сдвига переменных не меняет вырожденность функции. Рассмотрим разностный оператор d = dai ... da".

Очевидно, что конечнозначная функция f(x) является невырожденной тогда и только тогда, когда полином, представляющий эту функцию имеет степень (к — 1). Тогда при к 2 разностный оператор d не увеличивает степень полинома, представляющего функцию f{x), следовательно операторный образ &f(x) также является вырожденным.

Свойство операторов, сформулированное в предложении 13, дает возможность разбивать в некотором смысле сложные операторы на более простые.

Предложение 13 Пусть f(x) = g(y) h{z), где набор х разбит па непересекающиеся наборы у = у\.. .уп и z = z\... zm. Тогда для любого оператора t = і"1 ... t , выполняется равенство: tf(x)=ug{y)-vh(z где t — ul1... u\iivLi ... v%?, u-ul1,.. vfc, v = vf .., v%? Рассмотрим действие оператора t на функцию f(x). Пусть w(t) = 1 и щ ф е,Ьі ф 0. Тогда v - eC:L... еСп и для оператора t имеет место цепочка тождеств; t/(s) = «?Ь.. (/() =«? кзМй)- (ВД) иЬ1 ЗМ$) -g. (h(z))=ug{y)-vh(z). т Пусть w(t) = г и щ ф є, bi ф 0. Тогда по определению оператора: tf(x) = ub/(t f(x)), где w(t ) = г — 1, (і ) г = еи (t )i = ij для і ф I, ufb — оператор, совпади,-ющий сина всех ПОЗИЦИЯХ І при і ф I и u tl = е. По индукции имеем uf(t!№) = (vll g{y) -vh(z)) =иЪ(и! д{у)) -vh( z) = щ(у) -vh(z). Случай ь і ф єні ф 0; очевидно, полностью аналогичен рассмотрен ному. 1

Упорядоченное множество, состоящее из кп операторов длины п называется пучком операторов и обозначается Т, число п называется размерностью этого пучка. Пучки операторов будем также называть операторными пучками или яросто пучками. Для упорядочения операторов в пучке будем использовать наборы 0 = (0,0,..., 0),... :к — 1 = (к — 1,к 1}. ..,к — I), например, произвольный пучок обозначается следующим образом Т — {t,... ,tfc-1}.

Существование полиномиальных операторных представлений

По индуктивному предположению для функции A(xi,..7xn) существует оператор tn = d4 .., (Г" такой, что L(Pt(A)) LK (n - 1).

Пусть Ptn(A)І Ptn(B) — полиномы, представляющие функции А и В соответственно. Каждое слагаемое в этих полиномах является произведение монома на некоторый коэффициент atVl...ttjl Є Ek Множество всех мономов из Ptn{A) разделим на к частей. Для удобства части занумеруем как 0,1,..., к — 1.

В нулевую часть занесем мономы, которые не встречаются среди слагаемых в Pt{B), в первую — такие мономы, отношение коэффициентов перед которыми в Pt{B) и Pt(A) равно (к —1)2-1. во вторую — такие мономы, отношение коэффициентов перед которыми в Pt(B) и Pt{A) равно (к — 2)2-1 и так далее, в (к — 1)-ю — такие мономы, отношение коэффициентов перед которыми в Pt(B) и Р\{А) равно 2-1.

Очевидно, что из всех к частей можно выбрать к — 1 частей таких, что общее число мономов не превосходит Y-LKDl(n — 1). Пусть і — номер отсутствующей части. В ней содержится не менее у,ЬК 1{п) мономов.

Возьмем оператор tn+1 — сР1... d d\ Пусть Тогда Л = PJA), Д - 2-1 ) + Ptn{B)) и сумма длин Аг и ВІ не превосходит Ыф{п - 1) + (Р - \lK {n -1)). С учетом того, что длина оставшейся части в P\n+1{f) не превосходит (к — 2)fcn, получаем нужный результат. М В следующей теореме содержится нижняя оценка этого же класса полиномов. Теорема 6 При любом п 0 справедливо неравенство Рассмотрим функцию f(x) = х -\-х 3-f.. . + аг + 1 и покажем, что её сложность равна . Пусть для разностного оператора сР разложение (3.2) имеет вид d0:/W = 5]ci0,dV (3.5) ГҐП тттлсг жпоп1ІПІГІ„а 2 При a = 0 среди коэффициентов разложения содержится ненулевых элементов, так как І(/(ж)) = /(ж). Покажем, что в остальных разложениях число ненулевых коэффициентов не меньше Y".

Таким образом, показано, что в остальных разложениях число ненулевых коэффициентов не меньше - . Поэтому LK-Q1 ) -у. Для получения функции от п переменных сложности ( Р)п достаточно рассмотреть функцию д(х) — f{%i)f(x2)---f{xn), где f[x) — функция, построенная при доказательстве теоремы в случае п — 1. 4 В следующей теореме приводится точная оценка функции Шеннона для полиномиальных форм (3.2) по оператору из класса О и системе G .

Так как в j-й строке матрицы Ма в позициях j и j + а находятся единицы, то в j-м столбце матрицы М 1 в позициях j и j + а находится элемент -к. Все остальные строки матрицы Ма при умножении на j-й столбец матрицы М"1 должны давать 0, то есть при г ф j в г-й и (г + а)-й позициях находятся ИЕІ«. Таким образом, в каждом столбце матрицы М"1 имеется и вхождений элемента и и и вхождений элемента v. Тогда

Интересно заметить, что не всегда LK (f) = 1. На это есть две причины: во-первых, разложения существуют только по нечетным функциям; во-вторых, среди образов функций по пучку операторов может не оказаться самой функции.

В связи с изложенными замечаниями интересен вопрос о соотношении сложностей класса всех функций fc-значной логики в полиномах по разным функциям. Ответ на него дает следующая теорема.

Теорема 8 Для любого класса В базисных пучков операторов значение функции Шеннона LK (n) не зависит, от выбора функции д(х).

Рассмотрим базисный пучок Т операторов и две невырожденные функции gi(xi,..., хп) и (/2(жі) хп). Операторные образы этих функций ( {tpi( ),...,t -I3i(x)} и {Хд2{х),. ..,Хк 1д2(х)}) являются базисами линейного пространства всех функций fc-значной логики от п переменных. Поэтому найдется такое единственное линейное преобразование (р, переводящее один базис в другой, что p(tagi) = Xа д2 По предложению 14 существуют CQ, ..., с-г-г Є Ek такие, что имеет место разложение аЄЕЦ Тогда V( lW) = Р Е СЛ (Ж) = E (СЛі(ж)) = Рассмотрим произвольную функцию f(x). Для любого пучка Т Є В имеем (/()) = Л Е 1 = Е ) - Е 5ЙЙ Поэтому сложность полиномов, порожденных пучком по функции д\{х) для f(x] и этим же пучком по функции 32( ) Для (./ (& )) совпадают, то есть

Так как преобразование невырожденное, то f(F ) = i 1. Следо вательно LK${n) = LKl{n). Таким образом, при рассмотрении сложностей класса полиномов ЬЩ, состоящих из линейных комбинаций образов невырожденной функции д по пучку из класса пучков Т, можно использовать обозначение LKj.

Похожие диссертации на Полиномиальные операторные представления конечнозначных функций

Операторы в полиномиальных представлениях булевых функцийВинокуров Сергей Федорович

Методы представления дискретных функций в задачах подсчёта, тестирования и распознавания свойствВороненко Андрей Анатольевич