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

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

Оглавление
Введение
1 Нижние и верхние окрестности
1.1 Нижние окрестности и теорема о финитарности
1.2 Предупорядоченные пространства
1.3 Сильно предупорядоченные пространства
1.4 Примеры сильно предупорядоченных пространств
1.5 Соответствия и замыкания Галуа
1.6 Примеры. Соответствия Галуа для функций многозначной логики
1.7 Соответствие Галуа для переключательных функций
1.8 Итоги первой главы
2 Клоны с мажоритарной функцией и их обобщения
2.1 И-описания и лемма Б. А. Ромова о доопределении
2.2 Клоны с мажоритарной функцией
2.3 Клоны с Фподклонами
2.4 (с, й)-Клоны
2.5 Предикатная характеризация (с, Д-клонов
2.6 (с, г)-Разложения (с, Д-клонов
2.7 Итоги второй главы
3 Квазимонотонные функции на полурешётке
3.1 Полурешётки и полурешёточные функции
3.2 Основные клоны полурешёточных функций
3.3 Точечные функции
3.4 Пример. Дважды монотонные функции
3.5 Дизъюнктивные формы троичных функций

3.6 Обобщённые дизъюнктивные формы
3.7 Итоги третьей главы
4 Проблема полноты в слабо центральном клоне
4.1 Предельные предикаты
4.2 Расширенные и-описания и теорема о выделении
4.3 Слабо центральные предикаты и клоны
4.4 Слабо центральные клоны,
определяемые системами множеств
4.5 Теорема о полноте в клоне квазимонотонных функций
4.6 Мощностные оценки
4.7 Итоги четвёртой главы
5 Проблемы полноты
для трёхзначных квазимонотонных функций
5.1 Теорема о выразимости минимальных точечных функций
5.2 Теорема о полноте в классе монотонных функций
5.3 Аналог теоремы Слупецкого для квазимонотонных функций
5.4 Теорема о полноте в классе квазимонотонных функций
5.5 Итоги пятой главы
Заключение
Список использованных источников

Введение
Актуальность проблемы. В диссертации развивается теоретическое направление дискретной математики, изучающее различные пространства дискретных функций с замыканием относительно операций суперпозиции. (Пространством называется множество с замыканием в системе его подмножеств.) Необходимость развития этого направления обусловлена его теоретическими и практическими приложениями к анализу и синтезу дискретных управляющих систем [2, 55] с одной стороны и собственными потребностями дискретной математики с другой. Первые требуют решения в некоторых конкретных функциональных пространствах ряда задач, а вторые требуют обобщённого рассмотрения с единых позиций различных классов пространств и разработки общих методов решения различных проблем (типов задач) в них.
Начало активному изучению дискретных функций и их пространств положено работами Э. Поста, К. Шеннона, С. В. Яблонского, А. В. Кузнецова, О. Б. Лупанова и других исследователей. К настоящему времени теория дискретных функций получила серьёзное развитие, в результате которого были выделены (и продолжают выделяться) для исследования основные классы функциональных пространств (такие, как клоны, наследственные и инвариантные классы и прочие) и сформированы различные направления исследований. В том числе были сформулированы и стали классическими изучаемые в диссертации проблемы полноты и выразимости, проблемы эффективного задания замкнутых классов и их конечной порождаемое, поиска форм представления функций.
Так, проблема полноты (выразимости заданного класса) в пространстве состоит в описании, по-возможности эффективном, всех подмножеств пространства, в чьих замыканиях содержатся все элементы пространства (соответственно заданного класса). Решение этой проблемы в функциональном пространстве даёт условия, при которых задача синтеза управляющих си-

классы функций из Рс,е, замкнутые подстановками функций из клонов Ь и Я [75] (иначе — (Ь,Я)~замкнутые классы [135], возникающие при пустых множествах 17 и О), а также наследственные классы дискретных функций [110] (возникающие при пустых множествах и и О, когда клоны Ь и Я состоят только из селекторов). Это делает 5-замкнутые классы привлекательными для изучения.
Помимо этого ^-замкнутые классы имеют приложения в теории управляющих систем как классы переключательных функций, вычисляемых переключательными схемами с неограниченным числом каскадов [37]. При этом элементы множеств Е и С интерпретируются соответственно как состояния узлов и как проводимости между узлами, возможные в схемах, см. [5]. Функции клонов Ь и Я интерпретируются как допустимые используемой технологией синтеза операции над проводимостями и состояниями. В множестве О находятся функции переключательных (транзисторных) элементов, используемых при синтезе наравне с базисными переключательными (транзисторными) элементами. Наконец, множество 17 состоит из функций узлового соединения [5], каждая из которых определяет состояние произвольного узла схемы набором проводимостей от него до полюсов питания. Обычно, в схемах с г-полюсным источником питания состояние любого узла однозначно определяется набором проводимостей от него до полюсов питания, тогда множество Е совпадает с Сг,& множество II состоит из единственной тождественной функции и^ : Сг —> Е. Естественной также является ситуация, когда в дополнение к сказанному выше множество О содержит все «селекторы» я* : Е —>■ С такие, что зг(х) — хг; где переменная х — (х1,...,хг) принимает значения в множестве Е = Сг, её г-я компонента хг принимает значения в множестве С и 1 ^ г < г. Следует отметить, однако, что в этом последнем случае, при выполнении равенств Е — Сг и Ь = Яе, О — {я1,..., зГ}, Я = 5с, 17 = {Фг)}, изучение 5-замкнутых классов сводится к изучению клонов функций из Ре, чего нельзя гарантировать в других случаях.
Будем обозначать через < предупорядочение в множестве Рс,е относительно подстановки переменных, при котором для функций V и т, зависящих соответственно от п и т переменных, неравенство V < ги означает возможность получить функцию V из функции ю подстановкой переменных так,