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

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

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

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

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

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

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

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

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

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

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

В ряде работ был предложен и разработан операторный подход к исследованию специальных представлений конечнозначных функций [15, 16, 51, 52, 12], где под оператором на множестве FJ} (конечнозначных функций от п переменных при фиксированном простом к) понимается любое отображение t: Fjl —>

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

Зафиксируем набор х = (х,., хг) и будем рассматривать операторы q^ вида qу)) = h (x fhn{x, z),., hri (x, z) fhim (x, z),., hrm (x, z)^ где h — (г + га)-местная функция, hij — фиксированные функции. При этом если переменная Х{ не встречается среди переменных функции /, то считаем, что — /• Рассматривается класс таких операторов по всем х.

Пусть д является n-местной конечнозначной функцией, ti,., «tri — операторы, тогда операция д на множестве операторов из этого класса определяются следующим образом: д{ ti,., tri)/ = flr (ti/,., tn/).

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

В диссертационной работе рассматриваются три специальных оператора из этого класса: разностный — d.%% подстановки — s%> и сдвига —.

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

Ра^/О^Ь ¦ ¦ ¦ ixii ¦ ¦ ¦ 1 хп) = f{x 1,.. ¦, Xi-l, Xi + йг, Xi+1,. .. , Хп), d? if{xi, ., Xi,., xn) = f (xu ., xi,., xn) + f (xh ., Xi-l, Xi + ah xi+u ., xn),.

Sx'{f (X b • • •) xii • • ¦ > xn) = f (x 1) • ¦ •) ^i-l) ai) Жг+Ь ¦ • ¦ > xn)•.

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

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

Для набора констант, а = (сг^,.,.

В рамках этого подхода можно переформулировать известные результаты: например, возможность представления любой булевой функции суммой произведений остаточных подфункций [17] записывается как представление функции в виде: f&v) = Ч52<�Хёт9Ш> s?/)> ат где х, у — разбиение множества переменных функции / на две части, д — конъюнкция, oifrf Е. {0,1}, а суммирование берется по всевозможным наборам а, т.

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

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

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

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

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

• переменные — ., хп;

• х — вектор-переменная (xi,., хп).

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

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

• а — набор констант ., ап), где сгЕ Е^ б = (0,., 0),. = (к — 1,., к — 1);

• xh Х2, ¦ ¦ ¦, xq — некоторое разбиение множества {х,., хп} переменных функции /- <7i, а" 2,., dq — наборы констант, причем |ai| = xi,., aq = xq.

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

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

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

• операция «—» определяется как обратная к операции «+» ;

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

• булева функция называется нечетной, если вектор функции содержит нечетное число единицфункция Амзначной логики /(ж) при к > 2 называется невырожденной, если выполняется условие.

Е /и * °> дьщ и вырожденной в противном случаефункцию /(ж) будем называть полилинейной, если она линейна по любому своему аргументудля булевых функций будем считать, что ж, если <7 — 1;

X* = I.

I ж, если сг = 0. для функций fc-значной логики при к > 2 будем считать, что х° — 1 и хп = $ ¦. «¦ х, если п^Оп остаточными функциями от функции / по г-му аргументу называются функции, размерности которых на единицу меньше размерности /. Обозначаются и определяются остаточные функции следующим образом:

Г (т1, ¦ • •, T"l) = /(Г1,. .. , Tii, <7*, Tj, ., rni) для любого f ЕБ^-1- Если а{ = 0, то остаточная функция называется нулевой остаточнойесли 0{ = 1, то — единичной остаточной. Индуктивно распространяется понятие остаточной функции на множество аргументов i)., ц по набору а^,., <7ц (I < п):

Jjj ,.,(7^, ytaiii <7j (sZ}aJf для функций полученных из / подстановкой наборов 5″ х,., <хa-j+i,., aq вместо переменных множеств жх,., жж^+х,., xq соответственноозначает, что суммирование берется по всевозможным наборам 0. вп с" Ь ¦ ¦ • «ап)? х-у для fi (x у) = (0001).

X У у для /2(ж у) = (0111).

X -«> у для /з (ж у) = (1101) х^у для /4(ж у) = (1011) х I у для /5(ж У) = (1110).

X ^ у для /6(ж у) = (1000) ж -/> у для f7(x у) = (0010).

X у для f8(x v) = (0100).

• для нечетных бинарных булевых функций конъюнкция) — дизъюнкция) — импликация) — обратная импликация) — штрих Шеффера) — стрелка Пирса) — коимпликация) — (обратная коимпликация);

• для любого натурального п и любого i Е {1,., п} селекторной функцией называется функция e" (a?i,., хп), значения которой совпадают со значениями переменной а^;

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

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

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

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

О" ! СГ2. СГ, и которые часто называются представлением в виде суммы бинарных термов.

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

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

Вторая глава посвящена полиномиальным разложениям булевых функций с использованием оператора подстановки, а именно представлениям вида (1) и вида f (xh., xq) = y^Ol (72 •¦•.

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

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

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

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

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

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

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

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

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

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

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

Предложение 6 Булева функция f (x 1,2)2) представима в виде f{xhx2) = Y^ ь^з) ^ sg/(?hx2)], тогда и только тогда, когда не существует наборов fi,., fm, т = 2r + 1, г > 0 таких, что для любого д выполняется.

Е =.

1<1<т.

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

Для разложений по штриху Шеффера справедливо следующее.

Предложение 8 Булева функция f (x 1,2)2) представима в виде f{xhx2) = [S?J I s%f] ' тогда и только тогда, когда не существует представления константы 1 по функции f и конъюнкции вида.

01,02 в которой выполняется равенство Yh Рага2 = 1 В предложении 9 рассматривается аналогичное разложение для стрелки Пирса.

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

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

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

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

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

1) операторные образы фиксированной функции д (х) по операторам из заданного пучка Т f (x) = Y, ^ е Т, с5 G Ек] аеЕ.

2) операторные образы функций gz (x) из системы функций G по фиксированному оператору t.

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

Пучок операторов Т размерности п называется базисным, если существует такая функция д? что любую функцию / G FJ! можно представить в виде линейной комбинации операторных образов функции д по операторам из Т.

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

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

О при, а = 0- I 0 при t = р и, а ф 0;

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

Матрицей пучка Т = {t°, .tfc1} операторов t5 = t^. t^'g длины n назовем матрицу Mj = (m^) такую, что т~а~г = ЫУ^. (ап~ауЫ • сад^)®-1. где а, те а.

1 при, а — т или т — 0;

0 = /° пРиа=0' оН Л.

I 1 при, а ф 0, I I г[а).

0 в остальных случаях. Справедлива.

Теорема 3 Если Т = {t°,., tk~1} — пучок операторов длины п и g (x) е FJ}, то любую функцию f (x)? можно представить в виде f{x)= czta9{x), где Са? Ek тогда и только тогда, когда выполняются условия:

1) det Mj ф 0,.

2) д (х) — невырожденная функция.

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

Предложение 15 Пучок операторов Т = {t°,. t^-1} является базисным тогда и только тогда, когда для любого оператора и найдутся такие eg, что для любой функции f (x) имеет место следующее разложение и/И — c/f (x) +. + c-^f^fix).

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

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

Pt: f{x) =? cf-Ых), где, а является набором показателей оператора t, а с^ Е Е.

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

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

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

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

LK (f)= min L (Pt (f)) назовём сложностью функции / в классе полиномов К. Сложностью класса функций S в классе полиномов К будем называть число.

LK (S) = m&xLK (f).

Если S = FJ!, то используем обозначения LK{n). Рассматриваются два класса полиномов: К = Kf — линейные комбинации образов функций из базиса G по операторам из Т и К = Щ — линейные комбинации образов невырожденной функции g по пучку из класса пучков Т.

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

Gi — {ж? • • • ¦ • • • •"xi 1' • • •' хп и.

G2 = {vk ¦ ¦ -Ving{x 1,., xn){ih., in).

Среди пучков выделяется пучок О = (с^.-.о^., гп) е Oi? {р, d}), который называется однородным, и его частные случаи.

Р = (vh.vin (n,-, in) 6 Щ) и D = (d.d*|(ii, ., g е Епк).

С1.

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

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

LK^inX,-?" fcnV" -г, к> 3. к (к — 1) Ln (к — 1).

71+1 vv — к{к-1) + Г кп~к2-к + 1У.

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

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

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

LK%2{n) = kn, к> 3.

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

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

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

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

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

Заключение

.

На защиту выносятся следующие результаты.

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

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

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

4. Сложность полиномиальных представлений конечнозначных функ.

Г1 о ций в классах KD К02, К?.

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