Замкнутые классы k-значной логики, содержащие классы монотонных или самодвойственных функций

• Автор: Ларионов, Виталий Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 158 с.

Содержание
Введение
Глава 1. Монотонные классы с бесконечной надструктурой
1.1. Основные понятия
1.2. Семейство классов монотонных функций с бесконечной надструктурой
1.3. Минимальные логики, содержащие классы монотонных функций с бесконечной надструктурой
Глава 2. Свойства надрешетки классов монотонных функций
2.1. Невырожденные предикаты
2.2. Общие свойства надрешеток классов монотонных функций
2.3. Над структура классов монотонных функций, сохраняющих
несвязное ЧУМ
Глава 3. Необходимые и достаточные условия для бесконечной
надструктуры класса монотонных функций
3.1. Достаточные условия для конечной надструктуры класса монотонных функций
3.2. Необходимые и достаточные условия для наличия бесконеч-
ной надструктуры у некоторых семейств классов монотонных функций
3.3. Неограниченность конечной надструктуры классов монотонных функций
Глава 4. Надструктура замкнутых классов самодвойственных
функций

4.1. Семейства классов, содержащих замкнутый класс самодвойственных функций
4.2. Надструктура классов самодвойственных функций
4.3. Структура решетки замкнутых классов над
Литература

Введение
В современной математике и технике теория булевых функций занимает важное положение. Двухзначная логика используется как во многих теоретических областях, так и в прикладных. Всевозможные цифровые устройства, системы искусственного интеллекта, управляющие системы решают сложнейшие задачи, выполняя при этом элементарные двоичные операции и храня данные в виде нулей и единиц.
До сих пор доминирующее положение занимает именно двухзначная логика. Однако сложность решаемых задач, а, следовательно, и технических устройств, постоянно возрастает. Уже подходят к своему пределу многие технологические возможности, такие как увеличение плотности элементов на схемах, повышение рабочей частоты. Применение многозначной логики является одним из путей решения указанных проблем.
Многозначная логика предоставляет более широкие возможности для разработки различных алгоритмов во многих областях. Она позволяет уменьшить как вычислительную сложность, так и размеры, число соединений в различных арифметико-логических устройствах, повысить плотность размещения элементов на схемах, найти альтернативные методы решения задач.
Уже сейчас многозначная логика с успехом применяется при решении многих задач и во множестве технических разработок. Среди них АазЬ-память, различные арифметические устройства, системы искусственного интеллекта и обработки данных, обработка сложных цифровых сигналов и т. Д-
Одной из основных задач в многозначной логике является проблема выразимости функций: заданную /с-значную функцию или класс функций требуется выразить, используя суперпозицию функций некоторого имеющегося множества. Указанную задачу, несколько уменьшив общность постановки,
предикат р над {Л}, в том числе и для F, справедлив следующий факт: в ЧУМ Ьр> существует пара сравнимых элементов, соответствующих свободным переменным.
Переходя к графу, получим, что в графе Gp формулы F существует ориентированный путь между двумя вершинами, соответствующими свободным переменным формулы F. Поскольку граф Gp состоит из компонент связности ,Gfn, то указанный ориентированный путь будет в некоторой
компоненте связности Gpr Отсюда следует, что в ЧУМ Lpt существует пара сравнимых элементов, соответствующих свободным переменным формулыF{. По лемме 13 выполнено Polpi = Pol Л.
Итак, мы нашли требуемый предикат рі Є Р такой, что Рої рг = Рої Л.

Лемма 17. Пусть R — предикат, задающий класс монотонных функций, ЛЬЛ2 С [Л] — некоторые множества предикатов, такие что РоІЛі = Р0ІЛ2. Тогда для любого предиката р Є Лі, задаваемого над системой {Л} формулой из множества F, справедливо р Е [Л2].
Доказательство. По лемме 9 имеем [Pi (J{d}] = [Л2 U{<^}], гДе ^ ~ Двухместная диагональ. Получаем, что произвольный предикат р Е Pi реализуется формулой над системой {ЛгІЛоі}}. Поскольку указанная формула не может быть бесконечной, то существует конечная система предикатов Г = {t,..., tm} такая, что Г С Л2 IJ{d} и р выражается формулой над системой Т. Не ограничивая общности, положим, что tm = d, а все предикаты Пі • ■ ■ і tm-1 Є Pi'
Введем замкнутый класс функций В — Рої Г = Рої ({П, - • •, tm-1, d}) = Pol ({Н, • ■ •, im-i}) (используем лемму 8). Обозначим через t конъюнкцию без отождествления переменных предикатов ti,... ,tm-1. В силу леммы 4 полу-