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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им.М.В.ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 519.716.3-519.716.5

АРУТШЯН Лаура Артаваздовна

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

(01.01.09 - математическая кибернетика)

АВТОРЕФЕРАТ

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

Москва - 1993

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета Московского государственного университета имени М.В.Ломоносова.

НАУЧНЫЙ РУКОВОДИТЕЛЬ - академик АТН РФ, профессор

В.Б.КУДРЯВЦЕВ

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ - доктор физико-математических наук,

профессор В.М.МАКСИМОВ, - кандидат физико-математических наук К.В.КОЛЯДА

Ведущая организация - Московский энергетический институт

Защита диссертации состоится _июня 1993 г.

в 16 час.05 мин. на заседании специализированного совета Д.053.05.05 при Московском государственном университете имени М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (14 этаж).

Автореферат разослан " " мая 1993 года

Ученый секретарь специализированного совета Д.053.05.05 при МГУ,профессор

В.Н.Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы, функциональные системы (ф.с.) являются одним из главных объектов математической кибернетики,- Под ф.о. понимается пара< J^j ,S\> » ЭД0 М - некоторое множество фикций, - некоторое множество операций над ними со значениями из М .

Простейшим примером такой системы является класс Рд функций алгебры логики, т.е. функций вида -[0/f}^—»- ' с операциями суперпозиции.

В 1921 г. Э.Постом [I] была решена задача описания всех замкнутых классов в РЛ . Таких классов оказалось счетное множество и все они явно указаны им.

Щи переходе к Р^ , при к.>3 » т.е. к рассмотрению классов функций вида j: ^Д...,«-!}""— » Ю.И.Яновым и А.А.Мучником[2J было установлено, что решетка замкнутых классов в этом случае континуальна. Тем самым было установлено принципиальное отличие f-j, от Рк при (С . Позже для более общего объекта, который образован классом F^. неоднородных функций

ввда ¿{ШЧ-.'Ш*}- Bj . J6

где множества Л: L , t е { -J,..., S J ,и j конечны и фиксированы, а 22 = {i^,.JVS] , , Bt}}- с операци-

ями суперпозиции, в работе [ 3] также установлена континуальность множества замкнутых классов для всех Р^ , кроме Р^ .

Выяснению црироды этого континуума посвящено большое число работ [4-15'] . Их объединяет общая тенденция, состоящая в ра-смотрении подклассов функций в Rt и изучении решеток в них. Принципами выборов подклассов являлись либо особая их значимость, типа предполнота в , либо удобная аналитическая описуемость, типа линейности, полиномиальной характеризуемости и др.

В этой работе изучается континуальная решетка замкнутых классов в ф.с. Р , являющейся ф.с. типа Р^. и "ближайшим" образом обобщая ' . При этом строение решетки Ра является инструментальным средством для описания свойств решетки Р .

Цель работы. Исследовать строение решетки замкнутых классов неоднородных функций класса Р , являпцегося одним из "ближайших" обобщений типа р^ для класса .

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

Научная новизна. В диссертации решена задача описания характеров семейств классов заданной глубины. Классификация семейств в Р ведется с помощью их "следов", т.е. булевских футщций, лежащих в них. След.таким образом,является классом Поста. Глубина семейства классов из Р с заданным следом определяется глубиной следа в Рл . Под характером семейств классов из Р заданной глубины £ понимается набор значений всех мощностей семейств, имеющих заданные следы указанной глубины £ . Таким образом, характер глубины очень быстро обретает универсальность.

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

Апробация. Результаты диссертации докладывались на международной конференции по интеллектуальным система (Москва, 1991, 1992), на конференции "Дискретная математика" (Москва, 1991, 1993), на семинарах по теории автоматов на механико-математическом факультете МГУ под руководством академика АТН РФ В.Б.Кудрявцева.

Публикации. По теме диссертации автором опубликовано 5 работ, список которых приводится в конце автореферата.

Структура и объем диссертант. Диссертация состоит из введения, шести глав, заключейия и списка литературы 19 наименований, содержит 7 рисунков. Общий объем диссертации 120 страниц.

П. ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

Диссертация состоит из введения, шести глав и заключения.

Во введении дана общая характеристика работы и приведены основные результаты.

В первой главе вводятся основные понятия, даются функциональные определения замкнутых классов со следами з , С i , 1= Ц и аналитические представления для замкнутых клас-

сов со следами А 4,, L+ и А3 , формулируются основные результаты.

Пусть Л = [о,4], &>={о,3} , N- UЛ,Л . Пусть \J- {и^и-л,,... 1 и ЧА, ] - алфавиты переменных,

где и.i и 1Q ее значениями из оД и соответственно,

l,j & /Д/ • Д®1 упрощения обозначений переменных из О и V" будем обозначать через cc¿ и <¡jj соответственно. Назовем переменные £tr¿ типа .X , а переменные - типа У . Пусть X^ и У = векторы разных переменных.

Обозначим через Р - класс всех функций со

значениями из Qj\ . Эти функции назовем неоднородными. В [ 3 ] этот класс обозначен через •

В р* введем операции , н-суперпозиции. Они образованы операциями переименования переменных типа • X или У на переменные тех же типов соответственно, а также подстановкой неоднородных функций вместо переменных типа в неоднородную функцию и возможной подстановкой константы О вместо переменного типа

У .

Заметим, что для булевских функций (б.ф.), класс которых обозначен в [16 ] через » наши операции н- оуперпо-

' зиции совпадают с обычно рассматриваемыми для оппрациями

суперпозицга.

Пусть М-Р , обозначим через [МЗН множество всех неоднородных функций, получающихся ив М с помощью операций • н-суперпозиции. Множество называем н-замшсанием ^ ;

называем н-замкнутым, если М = ГМ1ц ' Ясио» что > если Щ ^ С^ »то множество совпадает с классом '

всех функций из С^ , получающихся из о помощью опе-

раций суперпозиций.

Пусть М ^ Р и 2 £ {Х,У,ХУ]| , обозначим череа ( "В - след класса ) следущее множество: всех

функций из Р , не зависящих существенно от переменных типа :"У при .X ; зависящих существенно только от переменных

типа "У при 5? - У ; зависящих существенно от переменных типов ЗГ и У при 2 = ХУ соответственно. Ясно, что имеет место однозначное разложение |\/| = МЧО М*У

на попарно непересекающиеся слагаемые.

Пусть г"р С^ и Т = ЕТЗц . Множество всех классов с заданным .X -следом Т обозначим через |Т\ . Мощность множества |Т\ обозначим через ЦТЦ •

Пусть М <0. , Р . Говорят, что М н-предполон

в (обозначение: М^К ), если М и /С н-эамк-

■ нуты, М* 1С , но £М 0 Н33н = К дай всякой § из

к\м .

Изобразим решетку по включению всех замкнутых классов М из | Т | о помощью графа » вершинами которого являются

эти классы, а ребра ( М^Мд*) означают, что предполон

а Таким образом, граф ^^ можно считать классифика-

цией замкнутых классов функций из Р , рассматриваемых с точностью до фиксированного -следа Т .

Введем некоторые технические обозначения. Пусть оС^ — . = .....=

= (л*,..., х: . где о= у

У: . тае и .

где СО 6 {^»еЛ^&есЯ • причем = со и сд° ^ 75 .

Назовем функцию • > %т?) и3 Р четной, если '.

- Цм) • ^сть V - класс всех четных

функций. Обозначим через V«, I где сь € оЯ , класс всех четных функций £ таких, что £?,..., 0} = СЬ.

Функции

и назовем соот-

ветственно Щ- и - двойственными к .

Пусть ^ р и — • Обозначим через М ^ , {, ] » класс всех функций, 1г - двойственных к функциям из класса М . Ясно, что [ М^ 3 и — М^.

Следуя [16] , называем б.ф. ^(а^..., монотонной,

ко1да цс всегда, если й-: ^ С^ нри

всех {4,..., п.}.

Обозначим через множество всех функций /(¿с"",

иг Р таких, что Ъ"1)— О » чеР03 6?0 -множе-

ство функций таких, что ^^ {/'*') — О » а через -класс всех б.ф. таких, что ^ (0,..., О) — О.

В[3] установлено, что является предполным в Р.

Нетрудно видеть, что классы 0о замкнуты,

Теорема I. Графы и ^Р имеют ввд.приведен-

сэ

ный на рис.1.а и рис.1 б.

сл.

ог

С.

Рис.1

Рис.2

Рио.З

Опишем некоторые замкнутые классы : С^- 7п)~ -/; Л'};

/ о'-) = /Г^^; А.лбЛ']; 1 и

УЫ."- (/(ос* -$»>■) еУ) ; н.гъеМ];

/

; А/] .

на рис.2. Пусть

Теорема 2. Граф имеет вид, приведенный

'-л

{ т : О, /О, ^

/Сz^F")- ¿(^I"") ;

■ í ЗСб^д^Ко^Л^о-, ffrjr-y

/(*,., 1H 5 ^ey] ;

= /¿Л*")»*; t.^eVh

б?чо = fо-, jLV-tJr)=i\

Q« = /(0я; о^Кд^Ус-,/СП^Н^-МЬ

0а = -U^ í"): ¡(in'jdnè)=.

= ¿ (î^^b 7*3 С/(J*

{/(^Г):

к, м. е N ] ;

{И^Т) ' ¡(^,0^0 , О")-*;

н,т € N ] . С учетом двойственности имеем замкнутые классы ^ Q*i

о;«, ОЙ, (Й-, с: яг. <й'

Замечание I. При ¿£, и I * 46 в разложении О^бЛ'ЙиОГ имеет место и =

Теорема 3. Граф имеет вид, приведенный на

н

рис.3.

Пусть й = и Е =

Дудем использовать 01_ вместо , если »и

О и вместо £ .если и е^о5 соответствен-

но.. Рассмотрим ^ — р' Г; » гДе Р] = дВ' В' .Пре-

^ = (7 о ^

образуем ^ с помощью операций «,•«. = си . <г УЛ-= си

(приведение подобных) и си V ^ = си «если си € = <(

(поглощение). называем к-формой, если приведение подобных

и? поглощение не меняют . Процесс перевода 'ФС- к к-фор-

ме называем канонизацией.

Выделим следующие классы К_1 к-форм, 1= 4.

= V (^ОЦО; Ч, иАуЪУч^ЩЪ^',^**А/],

ю.

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

класс всех функций из Р , реализуемых к-формами из К-1 .

Цуоть Ал - множество всех монотонных б.ф. и

((*"-> О"1-) ; К,те А/].

В [з] установлено, что Ф5 предполон в р . Теорема 4. Граф ^ имеет вид, приведенный на

Рис.4 Рис.5.

Опишем некоторые замкнутые классы :

К-. , :}(, > 0=

= /О*,у«.) ; л., >*. е/1/3 ;

ж«.,у,,...,;

В [3] установлено, что предполон в Р .

Теорема 5. Граф имеет вид, приведенный .

"з

на рис. 5. .

. пусть Нач+амН >

Выделим класс . ,

В [з] показано, что этот класс предполон в Р . Рассмотрим функции (ж), (¡с), ¿Vи такие, что

х , еа(х)= х, е<(°)=о и

__ 12-

е<(у) • Выражение ввда ^ . ^ , ^ при € ф г' ъ

¿4 6 { 0,4} , ¿е {■/,... > назовем элементарными произведениями (а.п.) степени

С

Рассмотрим выражение вида £ (¡1-014+.<Ж* > тае 0,4] и при -Ьф-Ь'.

Назовем его квазиполиномом (к.п.) и обозначим через б? . В случае, когда С( не содержит переменных из У , он, очевидно, является полиномом Хегалкина. Степенью О назовем £(($) — щах £ ($.{). Имеет место утвервдение, обобщающее известную теорему Хегалкина [17] .

Предложение I. Для всякой функции

существует и

единственный (с точностью до порядков умножения и сложения) квазиполином, равный этой функции.

Пусть б?^ - к.п., равный ^ , разобьем на три слагав-мых = + . тае (?*= у.

У /V ХУ

Следствие. Представление + определяется

однозначно.

Степенью фушсщи / назовем число пуск, и

при • £ =1,3. Ясно, что = /УП°Ч • и /у%0 0

Обозначим при 1=4,3 через /¿к -множество всех функций ^ , таких, что и

Пусть ^ = ¿Г ^ ' .

; Теорема 6. Граф ¿7 ■ имеет вид, приведенный на рис.6.

Теорема 7. Граф

на рис.7.

Ш4

4

имеет вид, приведенный

$0 ^АШс^ £

к;»

I I

а.

К. (с

А

й!

Рио.6.

Рис.7.

Напомним определения некоторых классов Поста: Пусть { Р,,Р3> Р<г, Р(г].

Теорема 8. Если Т£ »то мощность

11Т11

равна континууму.

'Пусть ^сР. Число Т(<??1) » равное мощности минималь-

у

ной неуплотняемой цепи замкнутых классов б.ф. от следа к классу С/) всех б.ф., называется глубиной класса /УП .

Вектор Х(е)= (0<,0А) 03) , где 01 е {+ , 1= , называем характером множества всех классов

/уЦ глубины 2 , в котором ОI = +- точно тогда, когда

существует след глубины £ , тип которого конечен при 1=Л ,

счетен при 1 = 0, и континуален при 1= 3 .

i

Моди$икавдя понятия характера , называемая к-характером

, получается заменой рассмотрения "глубины в "на "глубину не более , чем £ "и 0¿ на 0¿ соответственно.

Теорема (основная). Имеют место соотношения:

1. X (о) =Х'(0) = (+,-,-> ,

2. х О) = XV) = (+.+ -> ,

3. X О) = X'U) = ,

4. X' (в) = (+, + »"0 для любого ¿^л .

• Во второй главе описываются семейства замкнутых классов со следами C¿ , . Устанавливается конечность

этих семейств. Показывается, что указанные замкнутые классы являются конечно-порожденными и доказываются теоремы, дающие описания решеток по их включению.

В третьей главе описывается семейство классов со следом А<. Таких классов оказалось 9. Наряду с заданным в первой главе аналитическим представлением всех классов со следом А^ , здесь даются и функциональные определения этих замкнутых классов для применения критерия полноты в терминах предполного класса. Доказывается теорема, дающая описание решетки по включению этих классов.

В четвертой главе описывается семейство классов со следом

% . Таких классов 10, из которых три класса являются предполны-

• *

ми в рассматриваемой функциональной системе. Доказывается теорема, давдая описание решетки по включение этих классов.

В пятой главе описываются семейства классов со следами La и ¿3 и доказываются теоремы, устанавливавдие счетность этих семейств.

В шестой главе описывается множество со следом , î.= -/,3,5", б . Доказывается теорема, устанавливанцая континуальность этого множества.

В заключении из теорем 1-8 выводится доказательство основной теоремы.

Автор искренне благодарен своему научному руководителю академику АТН РФ, профессору В.Б.Кудрявцеву за постановку задачи, постоянное внимание к работе и поддержку.

ЦИТИРОВАННАЯ ЛИТЕРАТУРА ■

1. Ё. Turo-trcuEtitd i-ie/icvtltrc ¿ytiz+tii таЛАе.-yncvÎLocd iofyic, . Pxinc&ion. , 4944,

2. Янов Ю.И., Мучник A.A. О существовании к-значных замкнутых классов, не имеющих конечного базиса.- ДАН СССР.- 1959

т.127, JK I, с.144-146.

3. Кудрявцев В.Б. функциональные системы. М.: Изд-во МГУ, 1982, 159 с.

4. Мальцев А.И. Итеративные алгебры и многообразия Поста. -•В кн.: Алгебра и логика, семинар, т.5, вып.2, Новосибирск: Изд-во СО АН СССР, 1966.

5. £>аЛтлл J. On, Ыи keitfvU af c&ued -idi af of&wtion lu- flniie, (dcjduu.- Лип. dead. Sc<W. FewUcae, 49GS, Set. A. L V1563, ¡>. 4-U.

6. Бурле Г.А. Классы к-значных функций, содержащие все функции одной переменной/Дискретный анализ,- 1967 - й 10 -с.3-7.

A. On- cJottcL- it^i ÍLtve-ап. ç>fwicviicn-&

OWt £lnibt 4&U af ¿лиалл. ~ftti c.cubci¿каЛс-ЬиЦE&c -bvon.. JnfoXM. VeMH. und K¿éwt.-<f9U-VH, h/í H-fí 541-55$.

8. Марченков С.Сi 0 замкнутых классах самодвойственных функций многозначной логики.- В кн.:Проблемы кибернетики,вып.36,М.: Наука, 1979, с.5-22.

9. J., На*лЛ& L. On- ~Ьке. cabc¿Ln¿Ui¿ij af

JUud doítd ' с£алШ lu k-voAcú Kcz£. - M TA

Auiotn(vi. КиЛаЛо •¿УпЖ. ЬиЛаМЫ'к } Лд, №9 , р. Ч-К.

Ю.Марченков С.С., Деметрович Я., Ханнак Л. О замкнутых классах самодвойственных функций в Р3 // Дискретный анализ,- 1980, » 34, - 0.38-73.

II.Черепов А.Н. Описание замкнутых классов в Pr. .содержащих класс полиномов. - В кн.: Проблемы кибернетики,вып.40, М.: Наука, 1983, о.261-267.

12. Глухо в М.М. Об ©(.-замкнутых классах и oí-полных системах функций к-значной лотки// Дискретная математика. - 1989 -т.1, вып.1 - с.16-21.

13.Ремизов А.Б. О надструктуре замкнутых, классов полиномов по. модулю "к. // Дискретная математика,- 1989 - т.1, .вып.1 -с.3-15.

14.Мещанинов Д.Г. Некоторые условия представимости функций из • Рк. полиномами по модулю 4 //Докл.АН СССР,- 1988 - т.299, Л I, с.50-53.

15.Нгуен Ван Хао. О структуре самодвойственных замкнутых кяас-сов//Дискретная математика.- 1992 - т.4, с.82-95. .

16.Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста.- М.: Наука, 1966, 150 с.

17. Яблонский C.B. Введение в дискретную математику. М.: Наука, 1979, 272 с.

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

1. Арутюнян Л.А. О некоторых классах неоднородных функций// Ме-

ч

тоды и системы технической диагностики, изд-во Саратовского университета, 1992 г. - 4 стр.

2. Арутюнян Л.А. Классификация замкнутых классов неоднородных функций со следом //Методы и системы технической диагностики, изд-во Саратовского университета, 1992 г.- 25 с.

3. Арутюнян Л.А. Замкнутые классы неоднородных функций со следами и 1а3 //Методы и системы технической диагностик®, изд-во Саратовского университета, 1992 г.- II с.

4. Арутюнян Л.А. О решетке замкнутых классов неоднородных функций со следами типа С//Дискретная математика, - 1993- т.5, вып.I - с.130-145.

5. Арутюнян Л.А. О мощности следов классов неоднородных функций// Дискретная математика - 1993 - т.5, вып.2 -.с.149-153.

Подписано в печать 27.04.1993 г. зак.63 тир.100 объем 1,1 п.л. Ротапринтная Института экономики РАН