Исследование групповой эквивалентности замкнутых классов К-значной логики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК БЕЛОРУССКОЙ ССР ИНСТИТУТ МАТЕМАТИКИ

На правах рукопиои

НГУЕН ВАН 10А

УД 512.725

ИССЛЕДОВАНИЕ ГРУППОВОЙ ЭКВИВАЛЕНТНОСТИ ЗАЫКНУШ КЛАССОВ К - ВНАЧНОЙ ЛОГИКИ

01.01«09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

МИНСК 1987

работа выполнена на кафедре высшей алгебры Белорусского ордена Трудового Красного Знамени государетвенного университета имели Б.И. Ленина.

Научный руководитель - кандидат фиаико-матекатических наук,

доцент

Горлов Валерий Васильевич.

Официальные оппонента: I. Доктор физико-математических наук, профессор

Анисимов Анатолий Васильевич ?.. Кандидат технических наук

Бибило Петр Николаевич

Ведущее учреждение - НИИ ПМК при Горьковском государственном университете ии. Н.И.Лобачевского

Защита состоится " 3>0 " МиЛ___ 1988 года в

часов на заседании специалчзироианого совета 'К 006.019.01 в Институте математики АЛ БССР по адресу: 220604, г.Минск, ул. Сурганова II, Институт математики.

С диссертацией можно ознакомиться в библиотеке Института математики /Л БССР

Автореферат разослан "иЦ,"___1988 года.

Учений секретарь специализированного совета, кандидат физико-матемаги -ческих наук

Л.Н. МЕТЕЛЬСКИЙ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Одной из важнейших в теории функционалъ- . них систем является задача о полноте. Эта задача наиболее глубоко изучена Э. Постом для Ръ . Им била , по существу, решена задача о полноте для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции. C.B. Яблонским была решена задача о полноте для f^ , при этом предполныэ классы были явно описаны. В дальнейшем, А.И. Мальцев в 1964 году решил задачу о полноте для f^ • C.B. Яблонским, В.А« Кузнецовым, Ло Чжу-каеы, И. Розенбергом и др. били последовательно построены в явном виде все предполные классы для к-значнцх логик. Завершающее построение при этом провел в 1970 году последний из них.

Проблема полноты для произвольных к-значных логик с операциями суперпозиции ( т.е. замкнутых классов из f^ ) не имеет окончательного решения. Причиной этого, по видимому, является принципиальная невозможность получения описания решетки замкнутых классов из F|< , аналогичного полученному Э. Постом для двузначной ло^ гики. Поэтому представляет определенный интерес исследование более "грубых" структур замкнутых классов из F^ , получающиеоя отождествлением замкнутых классов, имеющих одинаковый список стабилизаторов ( всего три типа стабилизаторов ), функций, принадлежащих отождествляемым замкнутым классам.

Цель работы. Каждой функции к-значной логики поставим в соответствие стабилизатор одного из трех типов ( G- » G- , L -стабилизатор ). Два замкнутых класса называютоя (г-эквива-лентныаи ( G- , I— -эквивалентными) если множества Сг, ( Gr, L ) - стабилизаторов функций из этих замкнутых классов совпадают.

Целью работы являются исследование и построение структур клас-

сов О, , -эквивалентностей для Рк , к

Метод исследования. Основными методами, используемыми в диссертации являются методы теории функциональных систем и теории групп,

Основные результаты и научная новизна. В случае к= Ь , используя диаграмму замкнутых классов Э. Поста получено в явном виде описание всех структур классов

& , Сг , 1_ -эквивалентностей. Структуры классов -эквива-

лентности и 1_ -эквивалентности оказываются проще по сравнению со структурой замкнутых классов Поста. Структура классов О"-эквивалентности содержит б элементов.

Доказано, что мощность структур классов О- ( Сг , и ) -эквивалентности континуальна при .

При получены почерпающие результаты о строении верх-

ней части структуры классов I--эквивалентности. Это, в частности, позволило получить критерий 1_-эквивалентности произвольного замкнутого класса всей ^

Построена бесконечная убивающая цепочка замкнутых классов, & -полных в Р* ( т.е. Сг -эквивалентных всей ),

при этом при к^-н длина цепочки континуальна.

Естественно вводится понятие Сг -границы, содержательно означающее "границу" между Сг -полными и не. О-полными замкнутыми классами в решетке замкнутых классов из . Дока-

зано, что Сг -граница не менее чем счетна при и кон-

тинуальна при "Н .

Апробация работы. Основные результаты работы докладывались на семинаре "Алгебра и логика" в институте математики СО АН СССР и на семинарах кафедры высшей алгебры БГУ.

Публикации. Основные результаты диссертации опубликованы в

? печатных работах.

Объем работы. Диссертация состоит из введения и трех глав, списка литературы, включающего 24 наименования. Содержит 124 с. машинописного текста, 3 рисунка, 2 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

В введении дается обоснование проблематики дисеертации а также краткое изложение результатов.

В главе I введены основные понятия и доказаны некоторые вспома-гательные результаты, которые представляют самостоятельные интересы.

В §1.1 определены понятия G , G- , L -эквивалентностой.

Для каждой jiictlх^,..., х^,) из F^ пусть

есть симметрическая группа степени *ъ }

Множество Glj-1 является подгруппой группы S^ .

Две системы функций к-значной логики 1. и называ-

ются (г -эквивалентными, если для любой функции из Í2J ( ) существует функция ус^) из

( ) такая, что Gl^

Пусть £ € и % действует на наборе переменных Íxm-ixivI • Доопределим S до преобразования £ , которое действует на счетном множестве переменных ( Ч1Ч1-Л111 х^+ц;,... ] следующим образом: S действует на { ..., х^Д как t , а на остальной части [ »^«ч-г»" I как тоздес-

твенное преобразование. Тем самым каждой группе

сопоставлена От 1 j) . Нетрудно показать, что G является подг-

руппой симметрической группы SN , где N -множество

натуральных чисел. ^

Аналогично О -эквивалентности определяется О" -эквивалентность.

Пусть 1_к = , где -группа всех подстановок на множестве > а «V-декартова степень

с ^

группы Ь с • Элементы группы ик будем писатв в виде

<<г,тгм...,-тги> .где £ * .а ^ .....ТГ^^« Ь Е •

Тогда ^

И = I ^,ТГП> € \Г*К: ^ - ^ V*,.V..,хО,

где Х^ ( = ) - результат действия подстановки

^ на значение переменной XI > ]

и -эквивалентность систем функций к-значной логики определяется аналогично (т -эквивалентности.

Система функций к-значной логики 2.- 1 ^¡ у - 1 называется полной относительно з.к. '"УТЬ ( в з.к. ,

если ~2. С ОТЬ ), если для любой функции ^х^,... из ОТЬ существует функция ^ {■х.^х^) из 12.1 такая, что 011 - & \ .

Аналогично От -полноте определяются Сг * -полноты систем функций к-значной логики относительно некоторого з.к. ( в некотором з.к. ).

Факторизуя по О" (Сг , и ) -эквивалентности множество з.к. из и учитывая, что Сг ( О* I I— )

-эквивалентность согласована с отношением включения на множестве з.к. получим частично-упорядоченное по включению множество различных классов Сг ( Сг , 1_ ) -эквивалентности, которое будем называть Сг ( О , ^— ) - структурой з Р^ и

обозначим через

В §1.2 проводилось подробное изучение О" -стабилизаторов функции к-зпачной логики.

Доказана следующая теорема

Теорема 1.2.1. В к-значной логике Р^ , К} г, , для любой функции ^1*,.,..., х^) ^ существует функция ,

такая, что - О-(^) .

Отсюда вытекает следующее

Следствие 1.2.1. В ^ , к^ г , для любых еЫ и

для любой функции -х^) можно построить функцию

-х^р^) такую, что - О ^ .

В главе 2 исследованы структуры

.(гьр,. л^ .

л/

В §2.1 сформулирован критерий & -полноты систем б.ф. в ^

Теорема 2.1.1. Для того, чтобы система б.ф, 5.= | Кг\ьг" I

была (г -полна в ^ необходимо и достаточно, чтобы она не содержалась ни в одном из з.к. ,

Получено полное описание структуры .

Теорема 2.1.2. З.к. Поста С^ , 1_|. , , , , образуют трансворсаль О• -эквивалентности.

В §2.2 Сформулирован критерий 0"-полноты систем б.ф. в В

ь

Теорема 2.2.1. Для того, чтобы система б.ф. /Л -была Сг -полной в , необходимо и достаточно, чтобы она

но содержалась ни в одном из следующих з.к. Кз,, , ^ , ^ ,

Полнено полное описание структуры

Теорема 2.2.2. З.к. Поста , ^ , , , Р£ ,

образуют трансверсаль От -эквивалентности.

В §2.3 сформулирован критерий -полноты систем б.ф, в Р^

Теорема 2.3.1. Для того, чтобы система б.ф. 2 = Ц».»^--- ]

была и -полной в необходимо и достаточно, чтобы 2.

не содержалась ни в одном из з.к. Сч 4 , , ^х р^* , Получено полное описание структуры

Теорема 2.3.2. З.к. Поста С^ , С^ , , , ,1-5 , (

^ .ПГ.Р^ Рн . , . ^ ,

«Ц . ^ , 04 , , О,

образуют трансверсаль -эквивалентности»

В главе 3 изучены свойства структур классов групповых акви-валентностей для ^ , К^З

В §3.1 доказано, что мощность всех структур , ОгЬРК1

континуальна.

В §3.2 при К-Ъ получены исчерпающие результаты о строении

верхней части структуры классов 1_ -эквивалентности. Это в

частности позволило получить критерий I—эквивалентности

произвольного з.к. всей .

Теорема 3.2.1. Для того, чтобы система функций 2.= из была и -полна в необходимо и достаточно,

чтобы она не содержалась ни в одном из следующих з.к.

иста инл^

л Уем ,имл и^ .Х/щлУил.ита .171^1)

Шго1\ ТТ(ооюг\ т гг 11110% тиххоьг\ Т Т(оо1.оя1г\ ы.о) , I «инои > ^Чоги) I ^ Ьюгои),

т Г( и.о4.гог\ т/{гго и ^ со^гч». I I V/\гог1.го4.|

В § 3.3 исследован вопрос Сг -полноты замкнутых классов в Рч , к^Ъ.

Е>у\,

^иьЦс-. «Xj.it ] I 1 где 1:« Еч . Тогда

Е: - \_1

где а | ~ € . *х<д\ а ^ , г - в,к-1 1

Множество называется клеткой шюжества Е^ . Пусть .Клетку Е^'^''"' будем называть невырожденной, если каждый ее набор содержит все к различных

чисел из .В противном случае эту клетку назовем вырожден-

ка

ной. Объединение всех невырожденных клеток обозначим через пк , а вырожденных - через О,^ . Клетку, содержащую набор ы. обоз-

Пусть А,,- ^ и = при , а

начим через Едз?)

Г п. «« 'К ~ "

А - , где иЗ^ и-^к-г,...,*-^ и * Е « N

При о <. -п. к.

Для множества 2!» функций из ^ , полмножества множества Ек , через 2. /¡\ обозначим множество ограничений всех уь -местных функций из "51» на 14

Пусть есть множество всех симметрических функции из

. Справедлива

Теорема 3.3.1. Пусть для з.к. ЭТЪ из , к^Ъ

следующие условия

1/ т/х^ * Р^/х 2/ т*

выполняются для любого л\, , лг= . Тогда ООЪ

О -полон в .

Пользуясь теоремой 3.3.1 ыокно доказать следующую теореыу Теорема 3.3.2. В , К^Ъ , сущеотвуев счетная убыва-

ющая цепочка & -полных з.к.. Для существует конти-

нуальная убивающая цепочка Сг -полных з.к».

Пусть Н$* есть некоторая максимальная цепь з.к. из Р^ , ^МЪ* ес2Ь мнолЕвоио всех не О -полных з.к. из . От-

носительно порядка "включения множеств" справедлива Леша 3.3.12. Ъил^«* ^мь* 31 С и ТЬ^ ]

Для произвольной максимальной цепи Н514 будем называть

(г-граничным классом в ^ , а множество всех Сг -граничных классов - 0 -границей в ^ . Обозначим О -границу в Рк через ОВ^ . Теорема 3.3.3. Множество &С>^ , по крайней мере, счетно. Теорема 3.3.Множество 06^, к^ , континуально. Автор выражав! искренним благодарность Валерию Васильевичу Горлову за постоянное внимание, помощь и поддержку в работе.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

I. Нгуен Ван Хоа . О G -полных системах булевых функций // В кн. "Седьмая.Всесоюзная конференция по математической логике", Новосибирск, 1984. С,119.

2« Нгуен Ван Хоа . Об одном типе групповой полноты систем функций из Р //В кн. "Всесоюзная конференция по прикладной логпка", Новосибирск, 1985. C.I54-I56.

3. Нгуоп Ван Хоа. О мощности G-решетки// В кн. "Седкая Всесоюзная конференция проблемы теоретической кибернетики ". Иркутск, 1285. С.149. _

4. Нгуен Ван Хоа . О высоте и глубине G -првдполных классов в Р^ //В кн. "Воская Всесоюзная конференция по нат<зматнчеокой

логике", Москва, 1986. С.132.

5. Нгуен Ван Хоа. О' групповой полноте в ¡"^ // Мвявузопский оборник "Комбинаторно-алгебраический методы в прикладной математике". Горький: Изд-во ГГУ. Г986. C.II4-I38.

6. Нгуен Ван Хоа. О групповой эквивалентности в Fj^ // Взсгняк БГУ . Сер. I , Фаз., Маг. и Мех. 1986. С. 38-41.

7. Нгуен Вая Хоа . Об L-эквивалентности сястеи функций в многозначных логиках// Алгебра ж логика. 1988. Т.2?, Я. С.37-47.