О полноте и A-полноте S-множеств детерминированных функций

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

Содержание
1 Основные понятия и результаты
2 Отношения; тупиковые и приведенные отношения
3 Понятие 7г-множества. Д-рефлексивные отношения
4 Семейства отношений Сп(&,т), Мх(к,т), У(к,т), Ь(к,т).,
<2о(к,т), (к,т), Я2(к,т)
5 Б-тупиковые отношения. Б-критериальность Б-тупиковых
отношений
6 Критерий полноты в 1. Б-критериальные системы в Рк- ■
7 Семейства отношений (к, 1), 1з(к, 1),
Р(к, 1), Ь{к,1), Щк,1)}
8 Б-предполнота Б-множеств, принадлежащих классам сохра-
нения отношений из объединения семейств 2[к, 1), N{k, 1), Р(к, 1), Ь(к, 1) и 1(к, 1)
9 Семейства отношений Z{k, т), И(&, т), АТ(к, т), 1(к, т), Ь(к, т)
и V(к, т). Доказательство теорем 1.4 - 1.
10 О числе Б-предполных классов в функциональной системе

11 О полноте вДи А-полноте Б-множеств детерминирован-
ных функций, содержащих все одноместные детерминированные Б-функции
12 Об алгоритмической разрешимости задачи об А-полноте
для систем ограниченно-детерминированных функций, содержащих все одноместные Б-о.-д функции

Введение
Одной из важных проблем, рассматриваемых в дискретной математике и математической кибернетике, является проблема полноты для разных функциональных систем. Функциональная система представляет собой множество функций и множество операций над этими функциями. Проблема полноты для функциональных систем состоит в описании всех таких подмножеств функций, используя которые с помощью операций функциональной системы можно выразить все принадлежащие функциональной системе функции.
С точки зрения алгебры функциональные системы могут рассматриваться как вариант универсальных алгебр [1]. Существенной особенностью функциональных систем, выделяющей их из общего класса универсальных алгебр, является содержательная связь функциональных систем с реальными кибернетическими моделями управляющих систем и отражение важнейших характеристик таких моделей: функционирования, правил построения более сложных систем из заданных, описания функционирования более сложных систем по функционированию его компонент.
Центральное место среди функциональных систем принадлежит итеративным функциональным системам, представляющим собой множество дискретных функций с операциями итерации — суперпозиции, обратной связи, а также их модификациями [2,3]. Развитие теории итеративных функциональных систем шло по пути изучения конкретных моделей функциональных систем. В 1921 году Е.Постом была полностью описана структура замкнутых классов в двузначной логике — это описание, изложенное в монографии в 1941 году, по существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции [4,5,6]. Интерес к изучению итеративных функциональных систем особенно возрос в начале 50-х годов прошлого века в связи с появлением ЭВМ и необходимостью синтеза сложных кибернетических устройств. В 1954 году С.В.Яблонским [7] была решена проблема полноты в трехзначной логике. После появления работы [7] усилия многих авторов были сосредоточены на решении проблемы полноты в произвольных А>значных логиках. Начиная с 60-х годов прошлого века наряду с й-значными логиками стали интенсивно изучаться итеративные функциональные системы, элементами которых являются автоматные отображения [8,9], функции счетнозначных логик [11,12]. Позже появились работы, связанные с изучением итеративных функциональных систем, содержащих в качестве элементов вычислимые функции [12,15], программы и схемы программ [13,16].

Изучение конкретных и важных с точки зрения приложений моделей итеративных функциональных систем позволило накопить опыт в их исследованиях, отточить и разнообразить проблематику. Возник ряд задач, примыкающих к задаче о полноте, таких как существование и оценка сложности алгоритмов распознавания полноты конечных систем, исследование базисов, гомоморфизмов и конгруэнций, сравнения операций в функциональных системах и т.п. [17,18,19,20].
Как показано в [2] итеративные функциональные системы могут быть разделены на два типа: истинностные функциональные системы и последовательностные функциональные системы. В первом случае функции, принадлежащие функциональной системе, вычисляются без использования, а во втором — с использованием ’’памяти”.
Среди всех истинностных функциональных систем центральное место занимает функциональная система Р&, состоящая из функций Дознанной логики и операций суперпозиции над ними. Это объясняется прежде всего тем, что, во-первых, в большинстве реальных моделей истинностных функциональных систем функции, как правило, конечнозиач-ны и, во-вторых, любая функция в каждой истинностной функциональной системе аппроксимируется функциями /с-значных логик путем увеличения числа к. Критерии полноты в Р& могут быть сформулированы с использованием понятия критериальной системы. Система замкнутых подмножеств множества Р/,. образует критериальную систему в Р*,, если из непринадлежности произвольного множества функций 7-зпачной логики к каждому из подмножеств данной системы следует его полнота. Тривиальным примером критериальной в Р/,. системы является множество всех собственных замкнутых подмножеств множества Р&. Однако мощность этой критериальной системы континуальна и с ее помощью нельзя получить эффективный критерий ПОЛНОТЫ В Рк [21]. Вместе с тем, в функциональной системе Р* существуют конечные полные системы, и любое замкнутое подмножество множества Р/. расширяется до предполного в Рк класса (максимальной подалгебры), причем для любого к > 2 число предполных в Р/; классов конечно. Нетрудно видеть, что всякий предполный класс принадлежит любой критериальной системе, а множество всех предполных классов образует минимальную критериальную систему в Р*.. Таким образом, из явного описания множества всех предполных классов следует эффективный и наилучший в определенном смысле алгоритм для распознавания полноты произвольных конечных систем функций 7-значной логики. В уже упоминавшихся работах Е.Поста и С.В.Яблонского [4,7] решение задач о полноте в двузначной и трехзначной логиках как раз и было достигнуто путем явного описания множества предполных классов; при этом оказалось, что в Р2 пять, а в Р3 восемнадцать таких классов. Проблема явного

{1,... Ji}. Так как R тупиковое отношение, то в существует эле-
мент Л, не принадлежащий Л. Предположим, что R является также и S-тупиковым. Пусть Лш и Лш - w-фундаменты элементов А и А соответственно. Тогда в силу леммы 5.3 и теоремы 5.2. для некоторого n (n > 1) в замыкании множества S(U(R)) существует д.функция /(х,..., хп) такая, что f(Au,..., Аш)п = Аш, а функция fc-значной логики F^a^ap,...,
Ч" •v'*
хп), где 21 = (Лы,..., А,А не выпускает ни одного значения из множе-

ства Ек. Пусть А = (oi, ■■■,%, aJl+v ah),Ä = (äb ..., ä;~, ä~h+1, ...,äh). Для функции fc-значной логики -Р[/діШ] (ж і, введем обозначение
F(xі,..., xn). Пусть наборы (ск*,..., a"),..., (ah ..., a?) чисел из Ek таковы, что F(a,..., a") = ä(ii),..., F(a~,..., ck~) = сф(Д). Рассмотрим совокупность Лі = (Д,..., аі, о;і+1,.. .,ал),..., Ап = (а?,..., а?, aÄ+1,..., a/j) элементов из ДМ таких, что w-фундаменты Лі,...,Лп совпадают ефи для любого s (1 < а < К) имеют место равенства a(ti) = a;J,..., a”(П) = a". Нетрудно видеть, что /(Лі,..., Л„) = А. Однако по условию леммы Лі Є R,..., Ап Є R, но А ф R. Возникает противоречие, из которого следует справедливость утверждения доказываемой леммы.
Лемма 5.5. Пусть к > 2, Т = (ііДгДг/ где t < t2 < г. Пусть Д С Fj, причем 7гд(1,2) = яд(1,3) = яд(2,3) = 1 (рис Зв)). Пусть R С Д, і? - тупиковое, Д-рефлексивное отношение. Тогда отношение R не является S- тупиковым.
Доказательство Предположим противное. Пусть отношение R является S-тупиковым. Очевидно, множество {1,2,3} разбивается на два класса Д-эквивалентности: wi = {1} и w2 = {2, 3}. Нетрудно видеть, что при к = 2 отношение R в силу леммы 5.3. не может быть S-тупиковым. Поэтому будем считать, что к > 3. Пусть А — (cp, а2, аз) - произвольный элемент из Д^/аДП) = a, 02(H) = «з(П) = ß- Ясно, что а ф ß. Пусть Д (ар, ар, Х2, ар,..., ар, хк) - функция Аьзначной логики такая, что
F1(ß,...,ß) = ß
и для всякого 5 Є Ек
El (ар, Жр . . -, ж<р ж^, а: ар+і, х^^-2: ^6+2? ■ • ■; ар, Ж/^) гг $
Ei(®i, • • •) ^5j ар, ж^^-і, <т, ж^ц_2) ai^+2j • • ■ э ^
Очевидно, функция Д (ар, äp,..., ар, жі-) не выпускает ни одного значения из множества Ек.