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

Зинченко, Анна Сергеевна

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

Зинченко, Анна Сергеевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Иркутск МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

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

Зинченко Анна Сергеевна

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

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Красноярск — 2006

Работа выполнена на кафедре математической информатики Иркутской! государствен [Ю1'о педагогического университета

Научный руководитель:

кандидат физико-математических наук, доцент Пантелеев Владимир Иннокентьевич

Официальные оппоненты:

доктор физико-математических наук, профессор Нужин Яков Нифантъевич; кандидат физико-математических наук, доцент Кириченко Константин Дмитриевич

Ведущая организация:

Новосибирский государственный технический университет

Защита состоится 21 декабря 2006 г. в 15 часов на заседании диссертационного совета К 212.098.03 в Красноярском государственном техническом университете по адресу: 660074, г. Красноярск, ул. Ки-ренского, 20.

С диссертацией можно ознакомиться в библиотеке Красноярского государственного технического университета (г, Красноярск, ул. Ки-ренского, 26).

Автореферат разослан 20 ноября 2006 г.

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

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

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

В теории дискретных функций значимой частью является теория конечнозначных функций, то есть функций, которые определены на множестве {0,1,— 1} и принимают значения го этого же множества. Такие функции возникают как в самой теории функций, так и в многозначной логике (поэтому конечнозначньге функции часто называют функциями А-значной логики), в которой требуется для описания некоторых явлений употреблять высказывания, принимающие более двух значений.

Традиционной для теории функций является задача представления функций суперпозицией других функций. Одним из решений этой задачи является построение полных систем функций. Различные примеры полных относительно суперпозиции систем конечнозначных функций можно найти в работах [13, 14, 12, 5, 6].

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

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

Особый интерес при представлении функций специальными формами вызывают представления, использующие внешнюю операцию «сложение по модулю Л», так как они находят широкое применение при синтезе и упрощении схем.Такие представления мы будем на-

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

/ = 5, + ... +

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

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

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

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

В работах [3, 2) был предложен и разработан операторный подход к исследованию специальных представлений конечнозначных функций, где под оператором на множестве Рк (всех конечнозначных функций при фиксированном простом к) понимается любое отображение 1. : ^ —> Р*..

В работе [8] выделяется класс операторов, включающий в себя большинство из известных операторов и обладающий свойством замкнутости относительно суперпозиции и применения операции алгебры конечнозначной логики. В диссертационной работе рассматриваются три специальных оператора из этого класса; разностный — ¿£1, подстановки — и сдвига —

/(11,... .. ,.гп) + /(х),,. + а^.а^+ь ... ,х„),

■ ■ ■ > ■ ■ ' ~ /С*1-! I • ■ ■ >^4-1 > Ь . ■ • 1 Ж«)-

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

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

Цели работы:

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

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

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

Основные результаты и научная новизна. Основные научные результаты диссертации следующие:

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

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

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

Основные результаты диссертации являются новыми.

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

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

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

(Пенза, 2005 г.), школе-семинаре «Синтаксис и семантика логических систем» (Иркутск, 2006 г.), а также докладывались на семинаре кафедры Математической информатики Иркутского государственного педагогического университета «Дискретная математика и математическая информатика» под руководством проф., д.ф.-м.н. H.A. Перязева.

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

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

Содержание работы

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

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

• переменные — Жь... ,х„, х ~ вектор-переменная (xi,.. .,in);

• множество Ek = {0,1,...,А: — 1}, где к — простое число, возможно и 2;

• д - набор констант (сть... , <7„), где аi € Ек', 0 — (0,... ,0), ..., к — 1 = (fc — 1,..., fe — 1);

• ii,X2, • •. ,х<, — некоторое разбиение множества {ii,...,in} переменных функции /; Ol,<72,... ,<Tq — наборы констант, причем

1 = 1^11.....=

• константы — а, Ь, с,... ,a,j3,7,... € Ek, возможно с индексами;

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

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

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

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

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

♦ функция /с-значпой логики /(.т) при к > 2 называется невы-

рожденной, если выполняется условие /(?) / 0;

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

= 1 и I™ = у •... • х, если пф 0;

* «Й7 для Функций полученных из / подстановкой наборов $1,... <it+i 1 - • ■ вместо переменных множеств xj,... ... ,xq соответственно;

* 2 означает, что суммирование берется по всевозможным наборам (<7i,...€

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

х ■ у для fi(x, у) = (0001) (конъюнкция); х V у для /г (х, у) = (0111) (дизъюнкция); х —► у для /3(х,у) = (1101) (импликация); х у для /4(1, у) = (1011) (обратная импликация); х | у для у) = (1110) (штрих Шеффера); х | у для /е(х, у) = (1000) (стрелка Пирса); х У для fr(x, у) = (0010) (коимпликация); х **- у для /а(х, у) = (0100) (обратная коимпликация).

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

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

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

f(x =

= .....(d

5 iSj-.í,

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

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

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

}{х !,...,£„) =

.....•■))]. (2)

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

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

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

та) = J2 aw» Рт,у) -> sfv(*.í».

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

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

Предложение 5 Разложение (1) при д = 2 имеет место для любой булевой (функции тогда и только тогда, когда </1 € {V, ■,«—

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

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

Теорема 1 Полиномиальные представления вида (1) имеют место для любой булевой функции } тогда и только тогда, когда <¡ — 2 € {-.V,

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

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

Предложение 6 Булева функция /(£ьхг) предстазима в виде

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

X 1.

1 <{<т

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

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

Предложение 8 Булева функция /(хьхг) представима в виде

£ [8*ЛФ'Ь

01,0-2

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

1= [»*;/• «й/Ь

в котором выполняется равенство £ ~ 1*

5 ¡Л

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

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

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

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

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

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

Я2) = Ц сА(х), € Т, СЭ е Ек-,

2} операторные образы функций из системы функций С по фиксированному оператору 1

/(х) = с$гдэ(х), дэ(х) € С, сз € Ек■

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

Пучок операторов Т размерности п называется базисным, если существует такая функция д е что любую функцию / е

.можно представить в виде линейпоП комбинации операторных обра-;юл функции у по операторам на Т.

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

Для каждой компоненты оператора I определим константы а и Р следующим образом

[О приа = 0; |0 п

1 1 при а ф 0, 1 1 в

при I — р и а ф 0; остальных случаях.

Матрицей пучка Т = ..г*-1} операторов X." = ... длины п назовем матрицу Л/у = (т^?) такую, что

= <а15)^> -... • (ап5Г<^ • ОМ^*»

- ■ • • (Ад)40®1 ■ (к - а!5)Ы ..... (Л - а^Ч

где а, т € а

¿(о)=/° ПРИ а = 0; амЛ1

[1 при а ф 0, |0

при а = т или т = 0; в остальных случаях.

Справедлива

Теорема 3 Если Т = {1°,.— пучок операторов длимы п и д{х) € то любую функцию /{х) € .Г" можно представить в виде

Я*) = £ где сг € Ек

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

1) ¿еЬМт фО,

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

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

Предложение 15 Пучок операторов Т = {^..Л*-1} является базисным тогда и только тогда, когда для любого оператора и найдутся такие сд,..., ер^, что для любой функции /{х) имеет место следующее разложение

и/(х) = сц^т +... + с^Х^Пх).

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

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

Л : /<*) - 45)tдэ{х),

3 €Е£

где а является набором показателей оператора t, а е £ft.

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

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

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

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

LK(f)= min ¿(Л(Я) МЯек

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

U<{$) = raaxLtf (/).

Если S — то используем обозначения LK(n).

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

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

С, ...-ас®.....atf"1-...-**"1} и

<?2 - {Vй - • - pS(*1 , • ■ . ,®n)|(il,..., t«) 6 },

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

Среди пучков выделяется пучок О = (o'j1 ...oj;-1(¿]_____ in) 6

о» € {p, d}), который называется однородным, и его частные случаи

Р = (р*'..У"|(г1,...,г„) € ££) и D = (df'...di-|(i,.....in) е Е£).

Разложения по операторам из класса Р и базису G\ позволяют получить представления, называемые поляризованными полиномами. Н. А. Перязев в работе |9] нашел точное значение функции Шеннона для класса булевых функций и класса симметрических функций в поляризованных полиномах Жегалкина (форм Рида-Маллера):

а С. Н. Селезнева в работах ] 10, 11] получила оценки сложности функции Шеннона для поляризованных полиномов при к > 3, которые имеют вид

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

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

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

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

В теореме 7 приводятся точная оценка функции Шеннона для лса полиномов ЬК^*. Теорема 7 При любом п > 1

1.Л'£а(л} = А", к > 3.

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

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

Ф)-

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

Библиографический список

(1| Избранные вопросы теории булевых функций: Монография / А. С. Валюк, С. Ф. Вииокуров, А. И. Гайдуков и др.; Под ред. С. Ф. Винокурова, Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.

|2] Винокуров С. Ф. Полиномиальные операторные разложения и канонические формы булевых функций / С. Ф. Винокуров. — Иркутск: Из-во Иркутского ун-та. — 1992. — 26 с.

[3] Винокуров С. Ф. Полиномиальные разложения булевых функций / С. Ф. Винокуров, Н. А. Перязев // Кибернетика н системный анализ. - 1993. — № 6. — С. 34-47.

[4| Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципы локального кодирования / О. Б. Лупапов // Проблемы кибернетики. — 1965. — № 4. — С. 31-110.

[5] Марченков С. С. Замкнутые классы булевых функций / С. С. Марченков. — М.г Физматлит, 2000. — 128 с.

(6) Марченков С. С. классификация функций трехзначной логики / С. С. Марченков. — М.: Физматлит, 2001. — 80 с.

|7] Пантелеев В. И. Полиномиальные разложения fc-значпых функций по операторам дифференцирования и нормализации / В. И.

Пантелеев // Известия вузов. Математика. -- 1998. — № 1,— с. 17-21.

(8| Пантелеев В. И. 06 операторах булевых функций ,' В. И. Пантелеев, Н. А. Перязев // Синтез и сложность управляющих систем: Материалы XI Межгосударственной школы-семипара (Нижний Новгород, 20-25 ноября 2000 г.). — М.: Изд-во Центра прикладных исследований МГУ, 2001. — Часть 2. — С. 141-14G.

|91 Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм / Н. А. Перязев // Алгебра и логика. - 1995. - Т.34, №. 3. - С. 323*326.

|10] Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами / С. Н. Селезнева // Дискретная математика. — 2002. — ТЛ4, № 2. — С. 48-53.

[11] Селезнева С. Н. О сложности поляризованных полиномов функций многозначных логик, зависящих от одной переменной / С. Н. Селезнева // Дискретная математика. — 2004. — Т.16, № 2. — С. 117-120.

[12] Яблонский С. В. Функциональные построения в &-значной логике / С. В. Яблонский // Труды матем. ин-та им. В. А. Стек-лова. - 1958. —Т.51. - С. 2-142.

[13J Post Е. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer J. Math. —1921. — V. 43, N. 4. — P. 163-185.

[14] Post E. L. Two-valued iterative systems of mathematical logic / E. L. Post // Annals of Math. Studies. Princeton Univ. Press. — 1941. — V; 5.

Работы автора по теме диссертации

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

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

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

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

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

[20] Зинченко А. С. Полиномиальные операторные представления функций £-значной логики / А. С. Зинченко, В. И. Пантелеев // Дискретные модели в теории управляющих систем: Труды VI Международной конференции, посвященной 80-летию со дня рождения С. В. Яблонского (Москва, 7-11 декабря 2004 г.). — М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2004. - С. 31-32.

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

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

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

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

Редакциоино-издательский отдел Иркутского государственного университета 664000, Иркутск, бульвар Гагарина, 36

Формат бумаги 60x84 1/16. Объем 1,0 п.л. Тираж 100 экз.

Отпечатано в ОКИС ЦНИТ ИГУ 664003, Иркутск, б, Гагарина, 20

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Зинченко, Анна Сергеевна

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Одним из ответов на этот вопрос является возможность представления таких функций дизъюнктивными и конъюнктивными нормальными формами и их аналогами для произвольного к > 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)•

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

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

Для набора констант а = (сг^,., <jir) и набора переменных х = (xiv ., Х{г) оператор t~ определяется как произведение г операторов

В рамках этого подхода можно переформулировать известные результаты: например, возможность представления любой булевой функции суммой произведений остаточных подфункций [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, к), обобщением которых являются так называемые поляризованные полиномы.

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

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

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

При 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) д(х) — невырожденная функция.

Предложение 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) <E Щ}, где g — невырожденная функция. Первый базис состоит из произведений степеней переменных, второй из сдвигов функции д.

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

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

С1

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

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

LK^inX,;?" fcn- V" -г, к> 3. к(к - 1) Ln (к - 1)

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

Теорема 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, К?.

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Зинченко, Анна Сергеевна, Иркутск

1. Избранные вопросы теории булевых функций: Монография / А. С. Балюк, С. Ф. Винокуров, А, И. Гайдуков и др.; Под ред. С. Ф. Винокурова, Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.

2. Авгуль Л. Б. Обобщенные полиномиальные разложения симметрических булевых функций / Л. Б. Авгуль, В. П. Супрун // Кибернетика. 1991. - № 1. - С. 122-125.

3. Артюхов В. Л. Настраиваемые модули для управляющих логических устройств / В. Л. Артюхов, В. Л. Копейкин, А. А. Шалыто. — Ленинград: Энергоиздат, 1981. — 166 с.

4. Авсаркисян Г. С. Представление булевых функций суммой по модулю 2 импликацией аргументов / Г. С. Авсаркисян // Автоматика и вычислительная техника. — 1977. — № 1. — С. 8-11.

5. Авсаркисян Г. С. Обобщенные полиномиальные формы булевых функций и синтез многовыходных логических схем / Г. С. Авсаркисян //Автоматика и Телемеханика. — 1983.— № 11. — С. 111-119.

6. Авсаркисян Г. С. Полиномиальные формы частичных функций к-значной логики / Г. С. Авсаркисян // Кибернетика. — 1985. — № 4. — С. 32-36.

7. Авсаркисян Г. С. Квазиполиномиальные формы функций fc-значной логики / Г. С. Авсаркисян // Кибернетика. — 1988. — № 3. — С. 104— 105.

8. Ачасова С. М. Алгоритмы синтеза автоматов на программируемых матрицах / С. М. Ачасова. — М.: Радио и связь, 1987. — 135 с.

9. Балюк А. С. Функция Шеннона для некоторых классов операторных полиномиальных форм / А. С. Балюк, С. Ф. Винокуров // Оптимизация, управление, интеллект. — 2000. — Вып 5. — С. 167-180.

10. Баранова С. И. Цифровые устройства на программируемых СБИС с матричной структурой / С. И. Баранова, В. А. Скляров. — М.: Радио и связь, 1986. — 270 с.

11. Бохманн Д. Двоичные динамические системы / Д. Бохманн, X. По-стхоф. — М.: Энергоатомиздат, 1986. — 401 с.

12. Винокуров С. Ф. Смешанные операторы в булевых функциях и их свойства / С. Ф. Винокуров // Иркутский Университет. Серия: Дискретная математика и информатика. — Иркутск, 2000. — Вып. 12. — 36 с.

13. Винокуров С. Ф. Полиномиальное представление булевых функций с использованием только остаточных функций / С. Ф. Винокуров, В. И. Пантелеев // Труды XII Байкальской международной конференции. Иркутск, 2001 .- Т.5. - С. 27-31.

14. Винокуров С. Ф. Полиномиальные разложения булевых функций по невырожденным функциям / С. Ф. Винокуров, Н. А. Перязев // Алгебра и логика. 1991. - Т.ЗО, № 6. - С. 631-637.

15. Винокуров С. Ф. Полиномиальные операторные разложения и канонические формы булевых функций / С. Ф. Винокуров. — Иркутск: Из-во Иркутского ун-та. — 1992. — 26 с.

16. Винокуров С. Ф. Представление булевых функций полиномиальными формами / С. Ф. Винокуров, Н. А. Перязев // Кибернетика и системный анализ. 1992. - № 3. - С. 175-179.

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

18. Винокуров С. Ф. Полиномиальные разложения булевых функций / С. Ф. Винокуров, Н. А. Перязев // Кибернетика и системный анализ. 1993. - № 6. - С. 34-47.

19. Винокуров С. Ф. Полиномиальная декомпозиция булевых функций / С. Ф. Винокуров, Н. А. Перязев // Математические заметки. —-1993. Т.52, № 2. - С. 25-29.

20. Винокуров С. Ф. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций / С. Ф. Винокуров, Н. А. Перязев // Изв. вузов. Матем. — 1996. — № 1. С. 17-21.

21. Винокуров С. Ф. Полиномиальные разложения булевых функций по образам неоднородных операторов / С. Ф. Винокуров, Н. А. Перязев // Кибернетика и системный анализ. — 2000. — № 4. — С. 40-55.

22. Винокуров С. Ф. Разложения булевых функций по собственным операторным образам и термам над бинарными функциями / С. Ф. Винокуров // Оптимизация, управление, интеллект. — 2000. — Вып.4. — С. 167-180.

23. Гельфонд А. О. Исчисление конечных разностей // А. О. Гель-фонд. — М: Физматлит, 1959. — 400 с.

24. Жегалкин И. И. Арифметизация символической логики / И. И. Жегалкин // Мат. сборник. 1928. - Т.35. - С. 311-373.

25. Жегалкин И. И. Арифметизация символической логики / И. И. Жегалкин // Мат. сборник. 1929. - Т.36. - С. 305-338.

26. Зинченко А. С. О нижней оценке сложности операторных полиномиальных форм для функций &-значной логики / А. С. Зинченко,

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

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

29. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К. Д. Кириченко // Дискретная математика. 2005. - Т.17, № 3. - С. 80-88.

30. Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики / Лукасевич Я. — Биробиджан: ИП «ТРИВИУМ», 2000. 312 с.

31. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципы локального кодирования / О. Б. Лупанов // Проблемы кибернетики. 1965. - № 4. - С. 31-110.

32. Лупанов О. Б. Асимптотические оценки сложности управляющих систем / О. Б. Лупанов. — М.: Изд-во Моск. ун-та, 1984. — 137 с.

33. Мак-Вильямс Ф.Дж. Теория кодов, исправляющих ошибки / Ф. Дж. Мак-Вильямс, Н. Дж. А Слоэн. — М.: Связь, 1979. 477 с.

34. Марченков С. С. Замкнутые классы булевых функций / С. С. Мар-ченков. — М.: Физматлит, 2000. — 128 с.

35. Марченков С. С. б'-классификация функций трехзначной логики / С. С. Марченков. — М.: Физматлит, 2001. 80 с.

36. Мещанинов Д. Г. Некоторые условия представления функций из Pk полиномами по модулю к / Д. Г. Мещанинов // ДАН СССР. — 1988. Т.299, №1. - С. 50-53.

37. Мещанинов Д. Г. Перестановочные представления функций к-значной логики / Д. Г. Мещанинов // Вестн. МГУ / Вычисл. мат. и киберн. 1988. - № 3. - С. 61-66.

38. Мещанинов Д. Г. О вторых р-разностях функций ра-значной логики / Д. Г. Мещанинов // Дискретная математика. — 1992. — Т.4, № 4. С. 131-140.

39. Мещанинов Д. Г. Метод построение полиномов для функций к-значной логики / Д. Г. Мещанинов // Дискретная математика. — 1995. Т.7, № 3. - С. 48-60.

40. Мещанинов Д. Г. О замкнутых классах &-значных функций, сохраняющих первые d-разности / Д. Г. Мещанинов // Математические вопросы кибернетики. Вып. 8. — М.: Наука, 1999. — С. 219-229.

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

42. Пантелеев В. И. Полиномиальные разложения конечнозначных функций.: Дисс.канд. физ.-мат. наук: 01.01.06 / В. И. Пантелеев; Иркут. гос. университет. — Омск, 1994. — 85 с.

43. Пантелеев В. И. Полиномиальные разложения fc-значных функций по операторам дифференцирования и нормализации / В. И. Пантелеев // Известия Высших Учебных Заведений. Математика. — 1998. № 1- с. 17-21.

44. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм / Н. А. Перязев // Алгебра и логика. — 1995. Т.34, Ж 3. - С. 323-326.

45. Поспелов Д. А. Логические методы анализа и синтеза схем / Д. А. Поспелов. М.: Энергия, 1974. - 368 с.

46. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами / С. Н. Селезнева // Дискретная математика. 2002. - Т. 14, № 2. - С. 48-53.

47. Селезнева С. Н. О сложности поляризованных полиномов функций многозначных логик, зависящих от одной переменной / С. Н. Селезнева // Дискретная математика. — 2004. — Т.16, № 2. — С. 117-120.

48. Супрун В. П. Преобразования булевых функций на основе симметрической разности / В. П. Супрун // Изв. АН СССР. Техническая кибернетика. 1983. - № 5. - С. 199-202.

49. Супрун В. П. Табличный метод полиномиального разложения булевых функций / В. П. Супрун // Кибернетика. — 1987. № 1. -С. 116-117.

50. Супрун В. П. Декомпозиция булевых функций на основе полиномиального разложения / В. П. Супрун // Известия АН СССР. Техническая кибернетика. 1989. - № 3. - С. 187-191.

51. Супрун В. П. Об одном методе полиномиального разложения булевых функций / В. П. Супрун // Кибернетика. — 1989.- № 5. — С. 122-124.

52. Тошич Ж. Полиномиальные представления в одном классе трехзначных логик / Ж. Тошич // Известия АН СССР. Техническая кибернетика. — 1967. — №. 2.

53. Тошич Ж. Полиномиальные представления булевых функций и их минимизация / Ж. Тошич // Известия АН СССР. Техническая кибернетика. 1967. - №. 3. - С. 141-143.

54. Черепов А. Н. Описание структуры замкнутых классов в содержащих класс полиномов / А. Н. Черепов // Проблемы кибернетики. 1983. - № 40. - С. 5-18.

55. Черепов А. Н. О надструктуре класса полиномов / А. Н. Черепов // Труды семинара по дискретной математике и ее приложениям. — М.: Изд-во Моск. ун-та, 1989. С. 117-120.

56. Шеннон К. Э. Работы по теории информации и кибернетике / К. Э. Шеннон. М: ИЛ., 1963. - 829 с.

57. Яблонский С. В. Функциональные построения в fc-значной логике / С. В. Яблонский // Труды матем. ин-та им. В. А. Стеклова. — 1958. —Т.51. С. 2-142.

58. Яблонский С. В. О суперпозициях функций алгебры логики / С. В. Яблонский // Мат. сборник. 1952. - Т.ЗО, № 2. - С. 329-345.

59. Яблонский С. В. О суперпозициях функций в / С. В. Яблонский // Проблемы кибернетики. — 1963. — № 9. — С. 337-340.

60. Яблонский С. В. Предполные классы в многозначных логиках / С. В. Яблонский, Г. П. Гаврилов, А. А. Набебин. М: Из-во МЭИ, 1997. - 144 с.

61. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов. / под ред. В. А. Садовничего / С. В. Яблонский. — 3-е изд., стер. — М.: Высш. шк., 2001. — 384 с.

62. Balyuk A. Classes of Operator Forms / A. Balyuk, S. Vinokurov // 5th International Workshop on Boolean Problems. — Freiberg, Germany, 2002. — P. 217-224.

63. Gaidukov A. I. Operator polynomial expansions of Boolean functions / A. I. Gaidukov, S. F. Vinokurov // 4th International Workshop on Boolean Problems. — Freiberg, Germany, 2000. — P. 63-68.

64. Muller D. E. Application of Boolean algebra to switching circuit design and error detection / D. E. Muller // IRE Trans. Electron. Com-put. — 1954. — V.3, N. 3. — P. 6-12.

65. Post E. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer J. Math. — 1921. — V. 43, N. 4. — P. 163-185.

66. Post E. L. Two-valued iterative systems of mathematical logic / E. L. Post // Annals of Math. Studies. Princeton Univ. Press. — 1941. — V. 5.

67. Reed I. S. A class of multiply-error-correcting codes and decoding scheme / I. S. Reed // IRE Trans. Inform. Theory. — 1954. — V. 4, N. 9. — P. 38-49.

68. Logic synthesis and optimization / ed. T. Sasao. — Kluwer Academic Publishers, 1993. — 320 p.