О пересечениях и объединениях предполных классов многозначной логики

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

Содержание
Введение
1 Некоторые свойства предполных классов многозначной логики
1.1 Основные понятия
1.2 Вспомогательные утверждения
1.3 Утверждения о пересечениях и объединениях предполных классов
1.4 Свойства пересечений предполных классов монотонных функций
1.5 Полурешетка пересечений предполных классов
1.6 Системы аксиом вложения
2 Построение решетки основных замкнутых классов
в трехзначной логике
2.1 Свойства предполных классов двузначной логики
2.2 Полурешетка пересечений предполных классов в Рз
2.3 Распределение трехзначных функций по предполным классам
2.4 Множество всех тупиковых аксиом вложения в Рз
3 Некоторые свойства предполных классов четырехзначной логики
3.1 Следствия из универсальных свойств
3.2 Фрагменты решетки Ь для классов монотонных функций
3.3 Фрагменты решетки Ь для классов функций, сохраняющих
разбиения
3.4 О количестве неприводимых тривиальных пересечений
Заключение
Приложение А. Решетка основных замкнутых классов алгебры
логики

Приложение В. Элементы полурешетки пересечений В Рз
Приложение С. Примеры функций для строк множества Е(3)
Приложение Ю. Аксиомы вложения в трехзначной логике
Приложение Е. Фрагменты решетки основных замкнутых классов в Р4
Список литературы

Введение
Актуальность проблемы. Функции многозначной логики — один из основных модельных объектов дискретной математики, широко используемых для описания разнообразных дискретных систем. Интерес к функциям многозначной логики обусловлен как достаточно широкими выразительными возможностями данных функций, так и возможностью применять к функциям комбинаторно-логические приемы и методы различного рода. В частности, эти методы позволяют получать многочисленные разложения и представления функций через „элементарные“ функции.
Современная проблематика теории функций многозначной логики весьма разнообразна. Здесь ставятся и решаются задачи метрического, перечислительного, композиционного, сложностного, классификационного и ряда других типов. Особое место в этом ряду занимают задачи классификационного характера. В самом деле, прежде чем проводить систематическое исследование множества функций многозначной логики, необходимо провести хотя бы приблизительное структурирование (классифицирование) этого множества, разбить его на подмножества (классы), которые отвечали бы свойствам, характерным для выбранного направления исследований.
Среди различных подходов к классифицированию множества функций многозначной логики исторически первым явился подход, основанный на термальной (формульной) выразимости функций. Этот подход содержался в пионерских работах Э. Поста [36, 37], в которых была построена полная классификация множества булевых функций. Сейчас этот подход связывают с операторами замыкания на множестве функций многозначной логики (у Поста — оператор суперпозиции) и классификациями, состоящими из замкнутых (относительно выбранного оператора замыкания) классов.
Классификации множеств функций /с-значной логики, основанные на операторе суперпозиции, являются самыми известными и самыми изучен-

ШИМ элементом В Ц И = {«1, «2, . . - , с*;}.
Лемма 1.5. Пусть к ^ 3, 1 ^ К А’-2 « / е Если /(0) ^ 0 « функция / монотонна относительно порядка /л типа 0 <— {«1, «2,..., аД, то существует г Е {1,2,... ,1} такое, что 1т(/) С .
Доказательство. Как и в доказательстве предыдущей леммы, индекс у здесь будем опускать.
По условию леммы С1 = {«х, «2,..., аД. Применяя лемму 1.4 при а = 0, получим и Са, = С0 {0} = Ек {0}.

Обозначим а = /(0). Т.к. а ф 0, то а Е Ек {0} и в силу вышеизложенного найдется г Е {1,2,...,/} такое, что а Е СД, значит, а; ^ а, откуда по лемме 1.2 имеем С?а С ДД.
Далее, согласно следствию 1.2, выполнено 1т(/) С С30.
В итоге 1т(/) СДС . Лемма доказана.
Замечание 1.1. Свойства, аналогичные свойствам множеств выполняются и для множеств Ьа<1Х.
Лемма 1.6. Пусть у Е 0 /Дс Ек и существует 5 Е Д такое, что Д С Ьд,ц (т.е., Д имеет наибольший элемент 5). И пусть найдется а Е ДД П 1т{/, Д). Тогда /т(/, Д^Д С /т(/, ДД) С Д0;,г С ДД.
Доказательство. И здесь индекс ц будем опускать.
Так как а € /ш(/, Д), существует набор 5' = (£[, <5^,..., 5'п) Е Д" такой, что ф(д') = а. Рассмотрим произвольный набор (3 = {(3, /?2, • • ■, АД € Сд-Имеем: /(Д) = /(/?Х,/?2: • ■ • , Аг) Д /(5, Ф ■ ■ ■ ,6) Д /№, ДД =»■ В силу
произвольности набора /3 е получаем /т(/, ДД С Да.
Далее, из а е получим 5 -< а, поэтому, вследствие леммы 1.2, имеем Да С Д^- Наконец, из последнего вложения немедленно вытекает /т(/, Да) С /т(/, ДД. Лемма доказана.