автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Применение алгебраических методов в исследовании одного класса формул второго порядка

г I О и Л

' 9 С-Н ^гн

" " ' НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК РА И

ЕРЕВАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ

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

ДАВИДОВ СЕРГЕЙ СТЕПАНОВИЧ

ПРИМЕНЕНИЕ АЛГЕБРАИЧЕСКИХ МЕТОДОВ В ИССЛЕДОВАНИИ ОДНОГО КЛАССА ФОРМУЛ ВТОРОГО ПОРЯДКА

05.13.16-Г1рименемие вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФГРЛГ

диссертации на соискание ученой степени кандидат«! фитию математически« наук

Работа выполнена на кафедре высшей алгебры и геометрии Ереванского государственного универсжета

Научный руководитель - доктор физико-математических наук, профессор МОВСИСЯН Ю.М.

Официальные оппоненты: доктор физико-математических наук, ' профессор ЗАСЛАВСКИЙ И.Д. кандидат физико-математических наук, доцент ШИРВАНЯН В.Л.

Ведущая организация - Армянский государственный педагогический институт им. Х.Абовяна

Защита состоится а&уа* 1994г. в Л "часов на заседании специализированного совета К005.21. 01 по присуждению ученной степени . кандидата наук в' Институте проблэм информатики и автоматизации Национальной АН РА и ЕГУ по адресу: 375044 г.Ереван,ул. П.Севака 1.

С диссертацией можно ознакомиться в библиотеке ИГЖА РА и ЕГУ.

Автореферат разослан "4" и/о/гл 1954.

Ученный секретарь специалчзированного совета К005,2 1.01., к.э.н..с.н.с.

МЕЛКОНЯН А.Е.

ОБЩАЯ ХАРКТЕРИСТЙКА РАБОТЫ Актуальность темы. В последнее время сверхтождества представляют один из наиболее- интенсивно исследуемых классов формул второго порядка в теории моделей. Актуальность этого научного направления обусловлена широким применением тождеств с переменными операциями, с характеризацией многообразия многообразий, с описанием примальных алгебр, с разработкой теории моделей логики второго порядка и др.

В явней форме сверхтождества в бинарных обратимы; алгебрах впервые расматривал В.Д.Белоусов (1965). Из работ этого периода отметим также работы Р. Шауфлгра (связанные с некоторыми вопросами теории кодирования), Сада, Чупона и Стейна. Из исследований других формул языка второго порядка отметим работы А.Н.Мальцева, и Черча. Систематическое исследование сверхтождеста начато в работах Ю.М.Мовсисяна [1,2].

Толчком к исследованию сверхтождеста послужила и теА-'.я мальцевских многообразий, развитая в работах У. Тейлора, Д.М.Смирнова, Г. Гретцера и др. и берущая начало с классической работы А.И Мальцева [3]. Именно в связи с мальцеескимм классами многообразий и возникло понятие многообразия многообразий , а в связи с описанием таких

1. Мовсигян Ю.М. Сверхтождества и сверхмногообразия в алгебрах. -Ереван, Изд ЕГУ, 1990.

2. Мовсисян Ю.М. Введение в теорию алгебр со сверхтождествами. -Ереван, Изд ЕГУ, 1986.

3. Мальцев А.И. К общей теории алгебраических сисгем.-Мат.сб. 1954, т.35. N1. с.3-20.

многообразий и началось изучение сверхтождеств полиноминальных (термальных) алгебр в работах У.Тейлора, Дж.Бергмана, Р.Падманабхана и П.Пениера.

Одним из основных вопросов сверхтождеств (тождеств) класса «лгебр является вопрос об эквивалентности этой системы сверхтождеств (тождеств) ее конечной подсистеме (так называемая "проблема конечной базируемое™"). Свойство конечной базируемости класса алгебр К существенно, например, при алгоритмическом решении вопроса о принадлежности данной алгебры классу К, поскольку этот вопрос сводится к проверке выполнимости конечного набора сверхтождеств (тождеств).

В последнее врем» опубликован ряд работ, посвященных вопросу ' конечной базируемости сверхтождеств многообразий алгебр. Ю.М.Мовсмсяном доказано, что многообразие булевых алгебр имеет конечный базис сверхтождеств, а класс полиноминальных алгебр булевых алгебр не обладает конечным базисом сверхтождеств. Дж.оергман показал, что множество сверхтождеств полиноминальных

алгебр (всех) групп не является конечно- базируемым. Аналогичный результат получен и для сверхтождеств лслиноминальных алгебр решеток и полурешето«. Однако соответствующие вопросы, для отдельно взятых алгебр, остаются открытыми.

Цель работы изучение свойства конечной базируемости

сэержтождес та решеток, абелевых и триабелевых алгебр, конгрузнц-дисфмбутмвных сверхмногообоа)ий и их конечных алгебр

Не годы исследования FJ работе применены аппарат и методы современной алгебры (• частости теирми <■&<!>>» pyrin и ч-ирии реш'мог). математической логик» и теории моделей. ультра произведений арифметически однотм t не тем и теоремы компактности Мальцева.

Кзгчпая пофяжа и теоретическая ценное!» В диссертации Мр**>*р«|]л<»*гя с*ер>тс>1кде< тм конечных решеток. коитружц

дистрибутивных сверхмногообразий и их конечных алгебр. Найдены достаточные условия, при которых конгрузнц-дистрибутмвиое сверхмногообразие имеет конечный базис сверхтождеств. На основе характеризачии псевдосверхмногообргзий доказана формула Йонссона для сверхтождеств ( сверхмногообразий ). Приводится описание триабелевых обратимых алгебр с помощью сверхтождеств. Для нахождения конечного базиса применяется понятие примитивной выполнимости.

Все результаты,приведенные в диссертации являются новыми. Работа носит теоретический характер. Ее результаты могут найти применение в научных исследованиях, проводимых алгебраическими методами, а также при алгебраических исследованиях теории второго порядка и баз данных.

Апробация работы. Результаты работы докладывались на семинаре по алгебре и математической логики Института математики с ВЦ АН Молдовы, на семинаре "Алгебра и геометрия" кафедры высшей алгебры и геометрии Ереванского государственного университета, на отчетных научных конференциях профессорско-преподавательского состава Ереванского госуниверситета, на конференциях молодые ученных Армении, на семинаре по теории квазигрупп и комбинаторного анализа ИМ с ВЦ АН Молдовы.

Публикации. Основное содержание диссертационной работ изложено в трех статьях.

Структура и объем работы. Диссертация изложена на 90 страницах машинописного текста, состоит из введения и трех глав. Библиография содержит 46 наименований.

СОДЕРЖАНИЕ РАБОТЫ Во введении сделан краткий обзор литературы, расматривается структура н содержание диссертации и определяется понятие сверхтождества.

Сзерхтождество- это формула 2-го порядка го специализированными кванторами

УХ,..........*Х,„ гх,..........Ух„(УУ,=\Л/,,)

где X,.........,Хк - все функциональные переменные, а х,.........,х„- все

предметнее переменные в термах Однако сверхто^кдества для

простоты записываются без квснторной приставки, понимая его выполнимость (в алгебре <0;2>) как вылопнимосто соответствующей

формулы 2-го порядка со специализированными кванторами X),.......Хк.

Специализация здесь заключайся в том. что каждая функциональная переменная X, принимает любое значение из 1 соответствующей арности.

Формула 2-го порядка вида

..........Эд„. УХ,..........УХ„ (V*

где X,..........Хк - все функциональные переменные, а Х|..........х„- все

предметны* переменные в к-рмах W1. называется котождеством.

В первой главе определяются алгебраические системы арифметического типа, дается испилыуемая в диссертации интерпретация • >.х*а 2 го порядка. а ахкг определяется у/'ырапроизведение ар*«Хж**(ичес*и однотипных ал1е6раичес»и* сноем

Под арифметическим типом ал^браичеоои системы А»<0:П»;Пр> пстмаетс* упорядочение* пара < > (юд»»>№л«гч« нл'ур.шьнои чис «•«.

( п«^) для МГ»ОГО|*>» "Псрации / ¡(11

(тек / т-(Р^ дл« ие.от^к-п г>ргд««4П

где 1Р-1 (соотвегсвенио Р^О-арность операции (предиката |Р^|). Если !2р=.'. то А называется алгеброй арифметического типа Т|ияи Т<-алгеброй.

Пусть задан некоторый язык К 2-го порядка. Мы будем говорить, что некоторое множество формул (термов) этого языка имеет арифметический тип <Т1Д2> П"1>. где Т,,Т2^М или являются множеством <Т|,Т2>-фо^мул (Т)-термов), если множество арностей »се* функциональных символов, входящих в эти формулы (термы), содржатся в Т1( а множество арностей

всех предикатных символов, участвующих в этих формулах, содержатся в

■^.Интерпретация Т^-териов и <Т1,Т2>-фзрмул языка К задается! на

алгебраической системе А=<0;Пр;Пр> арифметического типа <Т1Д2> *

следующим образом: кванторы по предикатным и функциональным переменным предполагаются специализированными в том смысле,что выражения V Р', ЗР' означают-"Для каждого предиката из Пр соответствующей арности", "в С^ существует операция П такая, что";

значения свободных предикатных и функциональных переменных также берутся из Пр и Пр соответственно. Другими словами областью значений

свободных и связанных предикатных и функциональных переменных являются множества Пр и Пр.

Пусть А)=<0|;Пр,;Яв,> и А2=<02;41?:2;С1р2> две арифметически однотипные алгебраические системы. Тройка отображений (<р,>л7),где

о.О] -+02

«Пр'^Ор*

и отображения у,х сохраняют арность, называется гомоморфизмом А) •, систему А2,если для любой п-арной операции РеПр'.т-арного предиката

Р-Пр' и элементов х|.....О»,выполняются /слоаия

^(Р(х,....ля))=[уР)(гэх1.....«рх»)

Р(х,,^хп)=И=>(хРН<?х,.....•41Хт)=И.

Алгебраические системы арифметического типа *С Т^,Т^ ^ , и их гомоморфизмы (<л~',х) (в качестве морфиэмов) образуют категорию. В дальнейшем понятия подалгебры, прямого произведения, ультралроиэведеиия и др. понимаются в смысле зтой категории (см. [1], [21).

Сверхгождесгво называется Т-сверхтождеством, если

являются элементами алгебры слов с арифметическим типом Т. Класс Т-алгебр М называется саерхмногообразием (Т-алгебр), если существует такая совокупность Т-сверхтождеств С, что М - класс всех Т-алгебр, в которых выполняются все сверхтождества из I.

В §2 определяется понятие фильтруемости <Т|.Т_, >-формул и для

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

В $3 применительно к арифметически однотипным алгебрам доказывается следующее

ПРЕДЛОЖЕНИЕ 3.1. Пусть 1_о.....I п 1 конечные Т-^лгебры с конечным

множеством операций и (Ь, 11 с-1) непустое семейство Т-алгебр, каждая ил которых есть одна из алгебр (.ф.). Если О ультрафильтр над I. то существует число |, 0$|<п такое, что

В {4 расматриваются аксиоматизируемые и универсально аксиоматизируемые на языке 2-го порядка классы алгебраических систем, а так »о вложения 2-го порядка алгебраических систем с соответствующими мрмтермспаками В конце (4 приводятся характеристические свойства К»вдос»*1>аммо<оо6р*зий. -т.е. к лассо« Т-»т«Ър. мдаьаемыл псмдосмрхгождес таамн (дизъюнктными сдерхюмдестыми) Абсолютно Ымкмутм формул« 2 го пормм вида

Л. V«,....«. (♦,<*,.....О-Ч^-Д,".»«. ...«т|У

.....*„.«»... .«„О (5)

где .....1|„ д|......д|- термы арифметического типа Т, называется Т-

псевдосверхтождеством (дизъюнктным сверхтождеством арифметического типа Т).

ТЕОРЕМА 4.8. Класс К алгебр арифметического типа Т тогда и только тогда являлся псевдосверхмногообразием, когда он

(I) наследственен:

(и) замкнут относительно гоморфизмов;

(ш) : айкнут относительно ультрапроизведений.

Вторая глава - "О базисе сверхтождеств" состоит из трех параграфов.

В §5 доказывается формула Йонссона для конгруэнц-дистрибутивных сверхмногообразий. Сверхмногообразие Т-алгебр М называется конгруэнц-дистрибугивным, если для любой алгебры Д. М решетка ее (главных) конгруэнций Соп°.\- дистрибутивна. Для зтой цели вводится понятие примитивной выполнимости.

ОПРЕДЕЛЕНИЕ 5.1. Т-алгебра А=<0;1> удовлетворяет псевдосверхтождеству в арифметического типа Т примитивно (в записи А<=РЗ). если А удовлетворяет условию: для любых А^Е.а^О

0(1](А,а) д](А.а)) ....... 0(1,(А.а).д,(А.а))=0

где 0(а,ь)-наименыиая конгруэнция, содержащая пару (а.Ь).

Через Неди К обозначим сверхмногообразие, порожденная классом Т-алгебр К.

ТЕОРЕМА 5.3. Пучь ( >ин|ру.)н4 дистрибутивное сверхмногообразие Т-4лге6р и множество псевдосверхтождеств арифметического типа Т. £сли К юной! из всех членор í. коюрые удовлетворяют П. тогда Нецц К состоит из тех алгебр Е. киторыг удовлетворяют Ц примитивно

Если дм произвольного Класса К Т алгебр обозначим чер«| М([Х(,5(К).Ри|К) И Р$<Х) соответггвеинг,. кл<сс есед гоиоморф»щ оОраю».

подалгебр, ультралроизведений и подпрямых произведений алгебр из класс К, то из теоремы следует, что

Hequ K=PsHSPu(K)

§6 посвящен доказательству конечной базируемости сверхтождеств из конгруэнц-дистрибутивного сверхмногообразия. 6 этом' параграфе предполагается, что арифметический тип Т конечен. Алгебра A=<Q;I> называется конечно подпрямо неразложимой, если 0 = 4 или любые ее две ненулевые (главные) конгруэнции обладают ненулевым пересечением. Через Kpsi обозначим класс алгебр, состоящий из конечно подпрямо

неразложимых алгебр класса К,-Тогда имеет место

ТЕОРЕМА 6.2. Если и конгруэнц-дистрибугивное сверхмногообразие и Aifsi конечно аксиоматизируемо на языке 2-го порядка, то м конечно базируемое сверхмногообразие'.

Основным результатом §6 является

ТЕОРЕМА 6.3. Любая конечная алгебра из конгруэнц-дистрнбутивного сверхмногообразия Т-алгебр конечного арифметического типа Т имеет конечный базис сверхтождеств.

В качестве примеров из этой теоремы получаем, что конечная булева алгебра, конечная битернарная алгебра Мальцева, а также конечные Т-произведения конечных булевых алгебр имеют конечный базис сверхтождеств.

В §7 исследуются сверхтождества кончйой решетки. Пусть А=<0;£> Т-алгебра и a.nsN. Систему всех ее сверхтождеств, имеющих ранг ^п (и длину ьа), обозначим через Н"(А)(соответственно НП„(А)).

Алгебру А назовем слойно-конечной, если каждый n-арный слой клона С(А)-конечен.

ПРЕДЛОЖЕНИЕ 7.1. Для любой слойно-конечной алгебры А с конечным множеством операций i и для любых (Натуральных чисел и,п система сверхтождеств Нп11(А) конечно-базируем4. /

С использованием этого результата получаем

СЛЕДСТВИЕ 7.1. Система сверхтождеств Н"(1-) конечной решетки I. имеет конечный базис.

В третей главе "Абелевые обратимте алгебры" изучаются сверхтождества триабзлевых и абелевых обратимых алгебр. Бинарная алгебра <ОД> называется обратимой, если для всех а О,А- 1 отображения а:х >Х(а,х); >Х(х,а). называемые соответственно,

левой и правой трансляциями-биекции. Бинарная алгебра называется абелевой, если в ней выполняется сверхтождество

Х[У(х.у).У(г,и)]=У[Х(х,г)1Х(у,и)]

В §8, носящем вспомогательный характер, исследуется связь обратимых алгебр, удовлетворяющих сверхтождествам Муфанг Х[У(х,х),У(у,х)]=У[Х(х,у),Х(х.г)] Х[У(у.г)Л(х.х)]=У[Х(у,х),Х(г.х)] и некоторым котождествам с коммутативными лупами Муфанг. Доказывается, что каждая операция А, в таких алгебрах представляется в

виде

А,(Х,7)=(..>|Х-'.',У)-!1

где (^-операция коммутативной лупы Муфанг, а Ф, и ^ ее автоморфизмы.

В §9 рассматриваются триабелевые обратимые алгебры. Бинарная алгебра называется триабелевой, если каждая ее подалгебра, порожденная любыми се тремя 1лементами-абелева. Основным результатом этого параграфа явлне(сл

СЛГДС.IВИ1- Пусть М класс всех обратимы« алгебр. Тогда

Ш)Д»ЛИ1С |СМ |рил1)|-л«-м.|* и;1"М1Ю1еМ1НЫХЛ>р-»ТИМЫХ ,|ЛП-0|) |)11|)..Д. /11.-|( Я внутри М следующими двумя «.верхюждсчвами

Х(Д.Д| '

=Х1,{Х9{Х2[Х1(а,Ь),Х1(а,с)],Х41Хз(х.2),Хз(У.г)]).Х,о!Х6[Х5(и,«).Х5(у,и), Х8[Х7(г,5),Х7(Г,0]}).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Доказательство конечной базируемое™ сверхтождеств с конечныг. (<п) числом функциональных переменны* конечной решетки.

2. Найдены достаточнее условия при которых конруэнц дистрибутивное сверхмногообразие имеет конечный базис сверхтождеств.

3. Доказательство конечной базируемое™ сверхтождеств конечное алгебры из конгрузнц-дчетрибутивного сверхмногообразия.

4. Дано описание триабелевых и идемпотентных обратимых алгебр двумя сверхтождествами.

Пп теме диссертации опубликованы следующие работы:

1. Давидов С.С. Триабелевые обратимыа алгебры с котождествами -Меж.вуз.с6.науч.тр. Математика, Ереван, 1988, N6, с.118-131.

2. Давидов С.С. О базисе сверхтождеств конечных Т-алгебр-Меж.вуз.сб.науч.тр. Математика, Ереван, 1988, N6, с.243-247.

3. Давидов С.С. Коммутативные дистрибутивные алгебры с одной делимой операцией.- Меж.вуз.сб.науч.тр. Математика, Ереван, 1992, N7.

ШФПФШ-и

^ubpinujghujjmú huíGpu)hui24u»l)Uiü ùbpnrçObpml ЬЬшшрпшфиЗ t ipl)finpr\ Цшрсф puiGuiàlibp|i újt rvtLiu, npnüe Цп^фий bü qhpQniiOnipjmGQhp

ipinbri X). .. Xk-ü Wi=W2 ршпЬр|1 $niüljg[inGiui фпфп^шцшйОЬрО bü. fiulf

!......x„ -p rjpuiûg шпшрЦиуиЦшй фпфп|иш1)и!ййЬрй Ьй:

IbpünijünipjniüObpü huiÚLunnin Û2uiGujl|tJrui5 Ьй W,=W2 àbnij:

QbpürujGrupjniüGbpnLl прп21|ш0 huiúpuihuJ2fiilübp|i г)шиО '.jnjiJniú t .bppiuqùiuûbnip,niû:

QbpGniiOnipjniOObpti (ûnijlinipjniûûbpt») nwiiiCkuutipnipjuiG hiiÛLuL|mCi ЬшрдЬр^д úbl|G rçpujQç Ишйшр iJbpjujilnp pujr^fiufi qr.jnipjujQ шрдй t. ai)u|ifipü г)ршйд huidiupdb^ntpjujü huipgO t ЦЬрршЦпр р^пЦ bpOntjûnipjntûbbpli (GmjünipjruGGbph) puiqúrupjujÚQ, npQ LpijpUnp t GujL LUÚoiLimpqbph unqnp|iir.úujj|iG pCntjp тЬЬдпг) fuCr)fipCibpti iiiiüúujü hojúujp: и2[ишшшйр)1 h[iúüiijl|UJÜ LupttjniCpCibpü Ьй.

1 4bpgiu4np ^luilujpfi i)bpfwi}np piln4 ('n) $niúl)g|inüuii пфп[ишЦшйОЬр niübgnri qbpCint)QnipjmüObpp niQbü ^bpçoi^np pmqfiu;

2 LmGqpmtGg-pu^hJU^ujü o.bppujqùujûliniBjmû ЦЬрдш^гр puiqtiu

0ЬС|Ш[П1 ршфиршп u-¡iujúuj(jGbfi¡i илцш<,шдгшЗ(!

\

3 LinGqpnitGg-puJ2fuwl)'ujû qb|.pujqùijiûLmpjniGûbp|i ЦЬррш^пр ийршИшгЩйЬро niübCi qbpûnijGnipjruGûbph ЦЬрршЦпр piuqfiu;

4 QbpGnijürupjruüübpft oqünipjuj Jp uuiiugi(bi t ЬрЬршрЬишй иЦшцшр0Ь1Ь hujCipLuhiL^fiijühph GljiupoiqunipjntCiii

' X, Xk. X,.....x„ (W,=W2)