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

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

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

Введение

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].

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

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

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

Для набора констант а = (сг^,., <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, к), обобщением которых являются так называемые поляризованные полиномы.

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

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

Теорему 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) <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 приводится нижняя оценка сложности для этого класса полиномов, полученная совместно с В.И. Пантелеевым.

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

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

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

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.