Суперпозиции функций k-значной логики и их обобщений

• Автор: Пантелеев, Владимир Иннокентьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Иркутск
• Количество страниц: 215 с.

Оглавление
Введение

1 Основные понятия и результаты

§ 1.1 Истинностные значения и многозначные логики

§ 1.2 Функции Ахзначной логики и их обобщения

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

2 Логика с обобщенной интерпретацией переменных

§ 2.1 Обобщенная интерпретация переменных и частичная ги-

перзначная семантика

§ 2.2 Обобщенная интерпретация переменных и 4-х значная логика

§ 2.3 2-значная логика и обобщенная интерпертация переменных

3 Гипер- и ультрафункции
§ 3.1 Частичные гиперфункции на двухэлементом множестве
3.1.1 Примеры полных множеств
3.1.2 Замкнутые классы
3.1.3 Вспомогательные леммы
3.1.4 Критерий полноты
§ 3.2 Ультрафункции на двухэлементном множестве
3.2.1 Замкнутые классы
3.2.2 Вспомогательные результаты
3.2.3 Критерий полноты

§ 3.3 Полные множества частичных гипер- и ультрафункций на
произвольном множестве
4 Операторные представления функций /с-значной логики
§ 4.1 Об операторах функций Ахзначной логики
4.1.1 Основные понятия и определения
4.1.2 Операторы булевых функций
4.1.3 Некоторые операторы функций /с-значной логики
§ 4.2 Разностный оператор и оператор сдвига в полиномиальных
представлениях функций А;-значной логики
4.2.1 Существование полиномиальных представлений
4.2.2 Некоторые оценки сложности
§ 4.3 Оператор подстановки в полиномиальных представлениях
4.3.1 Разложения, применимые к произвольным булевым
функциям
4.3.2 Разложения функций А;-значной логики
4.3.3 Разложения с оператором сдвига
§ 4.4 Операторы подстановки и сдвига в разложениях полилинейных функций
Список литературы

Введение
Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике. Математические модели, описанные на языке функций, находят широкое применение в различных областях человеческой деятельности. В последнее время интенсивно развивающейся областью теории функций является класс дискретных функций, так как аппарат таких функций используется при проектировании вычислительных устройств [4, 12, 14], кодировании информации [53], передаче данных [17], в диагностике и контроле схем, в теории конечных автоматов, в теории игр, в языках программирования, при математическом моделировании природных процессов и др.
В рамках дискретных функций одним из важнейших понятий является понятие функциональной системы — пары (Р, Q), где Р — множество функций, Q — множество операторов, заданных на Р. Изучение функциональных систем связано с именами целого ряда выдающихся математиков. Среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, К. Шеннон, И.И. Жегалкин, А.И. Мальцев,
В.М. Глушков, A.B. Кузнецов, С.В. Яблонский, О.Б. Лупанов.
Одной из распространенных функциональных систем является система, в которой рассматриваются функции, определенные на множестве {0,1

§ 1.3 Полиномиальные представления функций А>значной логики
Традиционной для теории функций является задача представления функций суперпозицией других функций. Одним из решений этой задачи является построение полных систем функций. Различные примеры полных относительно суперпозиции систем конечнозначных функций можно найти в работах [131, 132, 95, 96, 98, 55, 56].
Но это достаточно общий ответ на вопрос, так как для произвольной функции он не указывает, какой вид имеет представление через функции данной системы. Поэтому естественной является следующая задача: можно ли построить представления конечнозначных функций, имеющих заданный вид?
Одним из ответов на этот вопрос является возможность представления таких функций дизъюнктивными и конъюнктивными нормальными формами и их аналогами для произвольного к > 2 [73, 95]. Для к = 2 наиболее общая постановка задачи рассматривалась О. Б. Лупановым в работе [46], где отмечается возможность декомпозиции по произвольной функции без фиктивных переменных.
Особый интерес при представлении функций специальными формами вызывают представления, использующие внешнюю операцию «сложение по модулю к», так как они находят широкое применение при синтезе и упрощении схем [6, 8, 73]. Такие представления мы будем называть полиномиальными формами, то есть под полиномиальным представлением понимается представление функций в виде суммы конечного числа определенным образом построенных слагаемых
/ = £>1 + ... + 5т.
Среди полиномиальных представлений выделяют два направления: разложения при простых значениях к и при составных. Это деление обусловлено тем, что при простом к множество {0,1