Полиномиальные разложения конечнозначных функций тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО НАРОДНОМУ ОБРАЗОВАНИЮ НАУКЕ И ТЕХНИЧЕСКОЙ ПОЛИТИКЕ ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Пантелеев Владимир Иннокентьевич

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

01.01.08 - математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата фиоико-математических наук

Омск — 1091

Работа выполнена на кафедре алгебры, логики и кибернетики Иркутского государственного университета

Научный руководитель - кандидат фиои&о-математических

наук, доцент H.A. Перяаев.

Официальные оппоненты- доктор физико-математических

наук, профессор A.C. Морозов; кандидат фноико-математических наук, доцент В.Я. Беляев.

Ведущая организация - Московский государственных!

университет им. М.В. Ломоносова.

Защита состоится "11." 199.\г, в ".и." часов на ааседа-

нни специализированного Совета К 064.36.02. при Омском государственном университете но адресу: 644077 г. Омск., пр.Мира 55-А.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета.

Автореферат разослан г.

Ученый секретарь специализированного совет

доктор фиа-гмат. /В А. Рошщькои.

в

Общая характеристика работы.

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

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

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

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

При к — 2 наиболее общая постановка задачи разложения функций рассматривалась О.Б. Лунановым 2).

При синтезе и упрощении схем нашло широкое применение полиномиальное представление функции в виде суммы конечного числа определенным образом Построенных слагаемых. •

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

'Яблоиский О.В Фупкцнональные построения н к-гэнлчной легнке// Труди матсм. ин-та им. В.А. Ст1-*лопа-1958-т.51.-с.2-М2.

гЛуи-лиев О С. Об одном подхода к пттспу )1трлнляющих схем - пришиты локального кодирования // Проблемы кибернетики.-1905.-N-1. г.ЗЫЮ

линомпальные формы, рассматриваемые, например в 3) . В случае простого к любую функцию можно представить в виде полинома (mod к).

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

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

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

- нахождение различных базисов в атнх классах,

- получение формул вычисления коэффициентов полиномиальных форм.

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

3М. Perkovski, M.Xetwell.P.VVu. Minimization of multiple- valued input u.ullionput mixed radix exclusive funis of products for incompletely specified Boolean funetions//J9th líií.Symp.Muitiple Valued Log., Guagihou,1989:Proc.-Wa6hiiigton(D.C),lä89.-c.256-263

4Винокуров С.Ф., Перяиеь H.A. Полиномиальные разложений булевых функций(обэор)// Кибернетика и системный аиы1и.1.-1993.^6.- С.1-11.

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

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

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

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

Методика исследований. В диссертации использованы методы линейной алгебры, теории чисел, теории функций ¿-значноп логики.

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

Апробация. Отдельные результаты диссертации докладывались на школе-семинаре по дискретной математике и ее приложениям (Москва., 1993), X Международной конференции по проблемам теоретической кибернетики (Саратов, 1993), Международной конференции по алгебре памяти М.П. Каргаполова (Красноярск, 1993), конференции, посвященной 75-летпю ИГУ, семинарах кафедры "Алгебры, логики и кибернетики" Иркутского университета.

Публикации. По теме диссертации опубликовано 4 работы.

Структура работы. Диссертация состоит пз введения, трех глав, разбитых на 8 параграфов и изложена на 85 страницах. Список литературы содержит 29 наименований.

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

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

Операции суммирования и умножения выполняются по mod к. Операция " - " определяется как обратная к операции " + ". Для сокращения записи, в тех случаях, когда это не может вызвать недоразумений, указание (mod к) будем опускать. Конечнознач-ную функцию /(х 1,... ,хп) при простом к будем называть функция f(xu...,xn).

В работе применяются следующие обозначения: х = (х-ь...,£п), у = (yi,...tyi), а = (аи...,ар) - наборы, размерность которых определяется по контексту. Выражение аД") означает к - 1 - х + n(modk). Если а = (crj,...,ар), г — (xj,. ■• ,тр), то ffW = (a[ri),...,4T^).

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

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

В §1 получено описание специального класса функций, исполь-оуемых в дальнейшем. Назовем функцию f(x) невырожденной, если

Е/И* о-

а

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

Теорема 1 . Функция f(xi,...,xn) является невырожденной тогда и только тогда, когда полином, представляющий эту функцию имеет степень равную (к -1) ■ п.

'Винокуров С.ф.,11еряэев H.A. Полиномиальные разложения булевых функций по невырожденным ф)'нкциям//Ллгебра и логика.-Ш1,-30,б.-с.631-637.

В §2 вводятся операторы дифференцирования, нормализации п смешанные п рассматриваются разложения, использующие эти операторы. ' -

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

Индуктивно определим операторы (I (дифференцирования), р (нормализации), t (смешанные):

}41/(хи.,.,х1,...,х„} = }(хи...1х^),...,х„1 0 </?<* - 1;

dx,0f{xu...,xi,...,xn) = /(х,,...,1„);

х*.) = f(x^,■■■,xi<...,xrl) + /^¡,...,1 ¡-0,.,.,хп), 1<Р<к-1.

Зафиксируем набор (<!,...,<„), где е {р,(¿¡. Однородно смешанный по ¡1 и </ оператор Ь определяется по данному наберу следующим образом:

■ ^...^...^Л .....*.....еслйГ*

если

и в общем случае:

• ■ ■ .*») = К\ ■ ■ ■ ,х«)),

где И е {р, <1, <}, т <п.

Теорема 2. Произвольная функция {(х\,-■ ■ ,хп) пмерт раало-женне вида

/(хи...,х„)= £ ап.....г„К\;::\9{х\, • ■ •,

где к с {р,с?, £}, тогда и только тогда, когда д(х1хп) невырожденная функция,

В случае, если к = р, матрица коэффициентов разложения А вычисляется по формуле

Л = £ д(ти...,тп))-\

где

в

9(01°),..., К0»)

¡(и,..., о) \ /(о,..,1)

г =

\ /(к-1,...,к~1) )

Пусть «М — к-1-х-т.

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

/(*!,«•, х„) = _ Е «П.....

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

Приводится формула вычисления коэффициентов.

В §3 этой главы рассматриваются полиномиальные представления функций, использующие собственные подфункции. Предложения 3.1 и 3.2 используют понятие невырожденности.

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

Назовем п местную функцию /(х1,...,х)1,,..,х^,...,хп) хорально наследственно невырожденной, если существует набор коистацт (а1,...,а,п), (т < п) такой, что функция, получившаяся й ре-аультате замены переменных а-,, .'•••) х1,г| этими константами, будет невырожденная и наследственно невырожденной, если все ее собственные подфункции невЫрожденЫ.

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

Если п местная функция ¡(х\,...,х„) представима в полиномиальной форме, описанной в предложении 3.1, где х = (х1,...,хт), т < п, то будем говорить, что у нее отделены переменные Х\,.,., хт.

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

Предложение 3.2. Для любой функции существует разложение вида:

ап- векторы гонстанты,

/ /(0,... ,0,Xj+],... ,хп)

F{x

i+Ь • •

, Х„) =

!l(x)' - одноместная невырожденная функция, <з - кронекерово произведение.

Предложение 3.3.Любая функция f(x,y) имеет разложение вида:

ах

где аат € {0,... ,k - 1}.

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

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

Функция f(x) называется полилинейной, если она линейна по любому своему аргументу.

'Винокуров С.ф.,Перяоев H.A. Разложение булевых функций на сумму проиоведевий подфункции //Дискретная математика -1993.-Т.5 вып.3.-е.102-104

Интерес к изучению полилинейных функций связан и с тем, что многие процессы имеют линейный характер и с тем, что эти функции являются непосредственным обобщением класса булевых функций. Многие результаты можно применять к булевым функциям, с другой стороны переход к полилинейным функциям позволяет уточнить различные утверждения о булевых функциях с точки зрения к- оначных (к > 3) функций.

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

Теорема 4. Если полилинейная функция от п переменных д(у) имеет степень п, то любую полилинейную функцию от п переменных /(х) можно представить в виде:

Г1,...,Г„

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

/(*!,.. ., Х„) = £ 4' • •' х°™ /(СТЬ • • •, 0т, Л'т4 1, ■ • • , *п).

Пусть - произвольная функция,

через Ь(д(х1,..., т^,. ..,г1к,...хп)) обозначим линейную комбинацию остаточных функций ^

д(хи...,0,...,0,...,хп),...,д(хи...,к-1,...,к-1,...,хп), 1 < ¿1 < «'* < п.

Теорема 5. Для любой полилинейной функции }(х\, ...,хт,..., х„) существует полиномиальное разложение вида:

/Оь .•■, Жгтп •■•, ^п) — а'1 .....тт(/(?"1, ..., Тт, а:т+(, ..., Хп))-

П.....Тт

Это разложение можно записать в матричном виде:

(

<°> . . т(0) \

= (ДО,■...,О,...,/(1,...,1, !„+,,'...,1»))-Л/-

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

В §6 рассматривается наиболее общее разложение полилинейных функций. "

Для функции 3(11,... ,х„,у) определим матрицу С следующим образом: £? = (9т,<т), где дг,а = и И(х1,...,хп) = (к - 1) ■

+ е {0,1}.

Теорема 6. Любая полилинейная функция }{х\,.. .,х„) имеет разложение вида: •

/(XI,..., хп) = £ ат,ад(х\т'\..., х\пт\(с-/(сть ..., от,хт+1,..., хп))Ы)

Т,<Т

по яояяяняеяноп функции д(х У), (г/г < я) тогда и только

тогда когда функция д{х[,..., х,„у) имеет степень равную т + 1. Матрица коэффициентов А есть С-1, с = к-1, 7 = гп + 1,где т = 1Т.ап.....г„ст_,-б{0,1}

.• _ ( 1, если набор (г\,...,тт) содержит четное число 1; п,-,тт ч /,• - 1, в противном случае,

константа I зависит от выбора функции д(х1,...,х„,у).

Теоремы 4, о и теорема 6 позволяют получить следующее разложение:

Предложение 6.1. Пусть {дт(х,у)/т е Р'г"} - система полилинейных функций такая, что матрица [пат] ~ невырожденная (Пат = Тогда любая полилинейная функция

}{х, г) нредставима в виде

= £ /(от, 2)) + (* - 1) . 9т(х, 0)1,

<т т

где [/?„] = [а^]-1.

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

Здесь используется обычное понятие степени:

х' = х •... • х,,

я

причем = 1 для всех х. Тогда представление пнд;.:

/(*ь.....т„)= £ «г,.....

является представлением в виде полинома по модулю к.

Будем рассматривать обобщенный представления следующего вида:

/\хи...,тп) = Ял.-.г^К1,.--,^"),

где д(х 1,...,хп) конечнозначная функция. В §7 рассматривается поле /V

Для п местной функции /(*!,..., хп) индуктивно определим" систему функций {/"■'•■■,">(*т+!,...,хп)}, т < п, е {1,2,3} следующим образом:

р{х2,...,хп) = /(1.х2,...,г„); /2(а:2,...,1п) = /(0,1-2,...,а:,1)-/(1,Х2,...,а.-п); /3(х2,-,*>>) = /(2,х2,....х„)-/(1,х2,...,хп).

Если функция /,1,»--'™(хт+),...,хп) уже определена, то:

При т = п, получаем систему из 3" элементов поля Р¡¡.

Справедлива следующая теорема о возможности представления функций обобщенными полиномами в /3:

Теорема 7. Любую 3-оннчную фушцпю /(х1,...,х„) можно представить в виде.

/(а:ь...,гп) =

тогда и .только тогда, когда в системе {//"'",/ Ъ' б {1,2,3}} всо элементы отличны от нуля.

Число функций ¡(х\,...,хп) для которых система {/"•'",/ е 11,2,3}} не-содержит нулевых элементов равно 23".

В §8 рассматривается поле Р5.

Для п местной функции ...,£„) индуктивно определим систему функций {/'»''•■•,'"(:гт-и,...,*„) / т < н, ij е {1,2,3,4}}

следующим образом:

у.^.ЬЛ^у,;;, ..<„(1, х-,,);

'™3 = /,'1,'1-(-(4,г,„«, ...,*„) - /м>~Ч1.*т+а,-,*..); /¡„V. .™-! = yi.ii. <-(3,гт+а,...,хв) - /•'«•■>-«-(2,1то+а,...,!„).

При т = п, получаем систему из 4" элементов поля Р5.

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

Теорема 8. Любую 5-ацачную функцию /(хь..., хп) можно представить в виде:

I

■ ■/(*!,= ЕаГ1.....Гяд(х?>-'хп)

тогда и только тогда, когда в системе {д'1- '", ¡г, е {1,2,3,4}} все элементы отличны от нуля. '

Число функций ¡(х\,...,хп) для которых система {/''" К/ 1] б {1,2,3,4}} не содержит нулевых элементов равно 44" - б5"-4".

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

«

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

Публикации автора по теме диссертации.

1.. Пантелеев В.И.. Полиномиальные разложения к знатных функций по невырожденным функциям // Математические заметки. -1994, -т.55,вып.1. -с.144-149.

2. Пантелеев В.И. Полиномиальные разложения полилинейных функций £-значпой логики. -Иркутск. -1994. -23с. -( Препринт / Из-во Иркутского ГУ).

3. Пантелеев В.И. Полиномиальные канонические формы

к- оначных функций. -Методы и системы технической диагностики / Материалы 10 Международной конференции по проблемам теоретической кибернетики. -Саратов. -1993. -с.134.

4. Пантелеев В.И. Обобщенные полиномы в конечных полях. -III Международная конференция по алгебре. -Красноярск. -1993. -с.255.