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

• Автор: Зинченко, Анна Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Иркутск
• Количество страниц: 96 с.

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]. Такие представления мы будем называть полиномиальными формами, то есть под полиномиальным представлением понимается представление функций в виде суммы конечного числа определенным образом построенных слагаемых
/ = + . . . + ДпСреди полиномиальных представлений выделяют два направления: разложения при простых значениях к и при составных. Это деление обусловлено тем, что при простом к множество {0,1 к—1} относительно сложения и умножения по модулю к образует поле. Поэтому при изучении таких конечнозначных функций можно применять известные результаты теории полей.
Для простых к наиболее изученным является случай к — 2, при котором функции называются булевыми или функциями алгебры логики.
В диссертации исследуются специальные полиномиальные представления конечнозначных функций при простых к, для которых рассматриваются вопросы существования и сложности.
Условия, налагаемые на систему функций, по которой существует полиномиальное разложение для любой конечнозначной функции при

тогда
1 = 1_К^_±1.

т-(2г+2)+1
При нечетном т получим противоречие 1 = 0, следовательно то не является нечетным. Таким образом, предположение о том, что то > 2г + 1, ложно.
(б) при то = 2г + 1, имеем ад = 1, і Є {1 то}, тогда
/Отії) + • • • + /(АіІт) = 1, £ Є {1, . . • , то}
ТО ЄСТЬ
ф(ц,ф) = 1 для любого столбца ц.
1 <1<т
Таким образом, функция / не представима в виде (2.10) тогда и только тогда, когда существует набор ті гт, то = 2г + 1, г > 0 такой, что для любого од выполняется
У] їі^ьП) = 1.
1 <1<т
Аналогичный результат можно сформулировать для коимпликации. Предложение 7 Булева функция /'(ащжг) представима в виде ф{х 1,х2) = У] а^2 [8%/(х1}Х2) &а£!{х1,хъ) ,
а 1Д2
тогда и только тогда, когда не существует наборов т тт, то = 2г + 1, г > 0 т,аких,что для любого 62 выполняется
у^ /(тьа2) = 1.
1<1<т
Пример 2 Рассмотрим функцию трех аргументов / = (0010 1100) и разбиение множества переменных {х, Х2, £3} = {ац} и {жг
(д) Функция / представима по коимпликации, так как не существует набора т£Е2 такого, что /(т, а) = 1 скя любого а Є Е%-