Введение к работе
Актуальность темы. Возникновение многооначной логики было связано, во-первых, с развитием самой математической ло-гпьи, в которой требовалось для описания некоторых явлений употреблять высказывания, принимающие более двух значений. А во- вторых, с развитием техники: в различных системах телемеханики, связи и вычислительной техники нашли применение к- злачные автоматы.
Но построение логического аппарата, который мог быть использован при логическом анализе и синтезе схем, использующих функции fc-значяой логики (конечноэначные функции) вызывает затруднение в связи с целым рядом трудностей теоретического п практического характера.
Среди работ, посвященных этим функциям необходимо отметить работу СВ. Яблонского '). В ней ппервые было дано систематическое изложение функциональных построений, относящихся к многозначной логике.
Изучение конечнозначных функции естественно поставило задачу о представлении функций различными формами, нахождение функциональных базпеоп п канонических форм в этих базисах.
При к = 2 наиболее общая постановка задачи разложения функций рассматривалась О.Б. Луиановым 2).
При синтезе и упрощении схем нашло широкое применение полиномиальное представление функций в виде суммы конечного числа определенным образом Построенных слагаемых.
Из таких представлений можно отметить разложение функций в Е —П ФРмУі которое может быть.применено у. произвольной к- онрчной функции, и является обобщением соответствующих нормальных форм булевых функций. Аналогичными являются по-
'Яблонский СМ Функциональные построения н к-гэнлчной легнк'*// І^рудіа матсм. ин-та им. В.А. Сті-іслопа-1958-т.5І.-с.2-М2.
2Лупздов О.Б. Об одном подходе к пінтепу іпрлнляющих схем - принципы локального кодирования // Проблеми кибернетики.-H)65.-N-1. г.ЗЫЮ
линомиальные формы, рассматриваемые, например в 3) . В случае простого к любую функцию можно представить в виде полинома (mod к).
Диссертация посвящена исследованию новых полиномиальных разложений и канонических форм по различным системам функций А;-аначной логики при простом к.
Условия, налагаемые на систему функций, по которой существует полиномиальное разложение ддя любой конечцоаначной функции при фиксированном п, в общем случае известны и состоят в требовании невырожденности матрицы, образованной значениями функции некоторой подсистемы.
Но вызывает интерес проблема выделения классов функций, удовлетворяющих этим условиям. До недавнего времени такие исследования мало проводились даже для булевых функций. Различные виды полиномиальных разложений для булевых фу акций можно найти в 4). Кроме того, для рааличных классов функций с подклассами, удовлетворяющими данным условиям, интересными являются следующие задачи:
нахождение различных базисов в отнх классах,
получение формул вычисления коэффициентов полиномиальных форм.
В диссертации, при рассмотрении полиномиальных разложений, эти задачп рассматриваются вместе. Исходя из этого, некоторые результаты, которые в общем виде можно получить, ас польауя классические результаты теории линейных алгебр, теории чисел, теории конечных разностей, имеют независимое доказательство. При этом, или получаем формулы вычисления коэффициентов разложения, или упрощаем процесс построения полиномиального разложения и получаем возможность использовать вычислительную технику.
3М. Perkovski, M.Xetwetl.P.Wu. Minimization of multiple- valued input u.ullionput mixed radix exclusive funis of products for incompletely specified Boolean funetiorja//J9th lrjt.Symp.MuUiple Valued Log., Guagihou,19Sg:Proc.-Wa6hiiigton(D.C),1389.-c.256-263
4В«нокуров С.Ф., Перяиеь H.A. Полиномиальные разложений булевых функций(обоор)// Квбернеї та и системный аиыш.1.-1993.-1Ч6.- С.1-11.
Цель работы. Получить и исследовать новые виды разложений конечноуннчных функций, использующих внешнюю операцию " сложение но модулю fc", где к - простое число, Конкретно:
ввести полиномиальные разложения специальных видов п выделить классы функций по которым возможны такие разложения;
применить операторный подход при построении систем функций для введенных полиномиальных разложений;
получпть формулы вычисления коэффициентов для этих разложений.
Методика исследований. В диссертации использованы методы линейной алгебры, теории чисел, теории функций &-значноп логики.
Научная новизна и практическая ценность. Результаты диссертации являются новыми. Они могут быть использованы прп изучении функций -оначной логики, в теории коне-чных полей. Результаты диссертации могут найти применение прп проектировании дискретных преобразователей информации.
Апробация. Отдельные результаты диссертации докладывались на школе-семинаре по дискретной математике и ее приложениям (Москва, 1993), X Международной конференции по проблемам теоретической кибернетики (Саратов, 1993), Междупародноп конференции по алгебре памяти М.П. Каргаполова (Красноярск, 1993), конференции, посвященной 75-летпю ИГУ, семинарах кафедры "Алгебры, логики и кибернетики" Иркутского университета.
Публикации. По теме диссертации опубликовано 4 работы.
Структура работы. Диссертация состоит пз введения, трех глав, разбитых на 8 параграфов и изложена на 85 страницах. Список литературы содержит 29 наименований.
г.