О порождении монотонных функций из некоторых классов многозначной логики

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

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

1 Основные определения и вспомогательные утверждения

1.1 Системы функций

1.2 Частично упорядоченные множества

2 Свойства семейства Тр

2.1 Определения и вспомогательные утверждения

2.2 Отсутствие конечного базиса у всех замкнутых классов, принадлежащих отрезку [9ЯС; М]

2.3 Цепь и антицепь континуальной мощности в множестве Т .

3 Порождение одноместных функций из множества М<

3.1 Определения и вспомогательные утверждения

3.2 Необходимое условие з-полноты в множестве Г
3.3 Достаточное условие з-полноты в множестве Г
3.4 Описание всех полных систем в множестве Г
3.5 Описание всех полных систем в множестве Г
3.6 Описание всех 5-полных систем в множестве Г
4 Критерий порождения множества Ше(2)
4.1 Определения и вспомогательные утверждения
4.2 Критерий полноты в множестве Р
4.3 Принцип двойственности
4.4 Критерий полноты в множестве Г< относительно композиции
и операции Ф

5 Критерий порождения всех одноместных функций из множества Мр
5.1 Определения и вспомогательные утверждения
5.2 Принцип двойственности
5.3 Необходимое условие полноты в множестве М( 1)
5.4 Достаточное условие полноты в множестве М( 1)
Список литературы

Введение
Диссертация относится к теории функциональных систем — одному из основных разделов дискретной математики и математической кибернетики. В ней рассматривается задача о порождении монотонных функций многозначной логики.
Одной из основных задач в теории функциональных систем является задача о полноте. В общем случае она может быть сформулирована следующим образом. Рассматривается функциональная система (Р; ф), состоящая из некоторого множества Р и некоторого отображения 1р : В{Р) —У В(Р), где В(Р) — множество всех подмножеств множества Р, а В теории функциональных систем важное место занимает исследование множества Рд (к > 2) всех функций /с-значной логики с операцией суперпозиции. В частности, особый интерес представляет описание различных классов из решетки £д (семейства замкнутых классов функций из Рд, упорядоченных но включению). Случай к = 2 описан в работах Э. По-
1 Отображение (р : В(Р) —У В{Р) называется оператором замыкания, если для каждых 21, © е В{Р) выполнены следующие свойства: 1) 21 С <р(21), 2) если 21 С ЯЗ, то ¥>(21) С ¥>(©), 3) ¥>(¥>(21)) = ¥>(21) (см. [2,9]).

Лемма 3.1.5 (о несравнимых значениях). Пусть /1./2 £ Д / = /2 ° /ь Пусть на элементах ср,, Д из мноэюества <3 функция / принимает, несравнимые значения, 1 < к < п. Тогда значения Д (а*) и /1(6;.) несравнимы.
Доказательство. Предположим противное. Пусть /Дсц) сравнимо с Д(ДД Пусть, например, /Да*) < Д(Д) (случай Д(6Д < /Да/,:) разбирается аналогично). Тогда, в силу монотонности функции /2, выполнено неравенство /Д/ДаД) < /2(Д(Д-))- Поэтому верна цепочка соотношений
/Ы = ЯЛЫ) < Я/ДД) = яд).
Таким образом, значения /(ад.) и /Да-) сравнимы, что приводит нас к противоречию.
Лемма 3.1.6. Пусть Д, /2 6 Д / = Д о/2. Тогда если /'(Да) = Да- ъ гс/е 2<к< п, то /2(Да) = Да или /2(Да) = Да
Лемма 3.1.7 (свойство дистрибутивности). Пусть д2,д,к произвольные функции из И. Тогда справедливо следующее равенство:
(#2 V Д о (51 у /г) = (52 о .91) V Ь.
Доказательство. Положим 5 — 92091, 5 — 9 V Д 51 = 51V Д 52 — 52 V Д В новых обозначениях доказываемое равенство принимает вид:
5г о 51 =
Пусть (5 произвольный элемент из множества <5.
Пусть /г(5) = 0. Из неравенства д(5) < 6 и монотонности функции /г следует, что /г(5Д5)) < /г(5) = 0. Таким образом, из определения операции свертки следуют соотношения:
5(5) = (5 V Д(5) = 9(5),
ДД5) = (91 У/г)(5) = 9Д5),
92(9Д5)) = (92 V Л)(9Д£)) = 92(9Д5)),
(9г о 91) (5) = 92(9Д5)) = 92(9Д5)) = 92(9Д5)) = 9(5) = 9(5).