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

Егамбердиев, Бахтияр АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Ташкент МЕСТО ЗАЩИТЫ
1994 ГОД ЗАЩИТЫ
   
01.01.06 КОД ВАК РФ
Автореферат по математике на тему «Устойчиво простые и устойчиво полупростые базисы логик малой значности»
 
Автореферат диссертации на тему "Устойчиво простые и устойчиво полупростые базисы логик малой значности"

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

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

(01.01.06 — математическая логика, алгебра и

.' v 1 (

■■г: од

1 о м

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

ЕГАМБЕРДИЕВ БАХТИЯР

теория чисел)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Ташкент — 1994

Работа выполнена в Ташкентском Ордена" трудового Красного знамени Института инженеров железнодорожного транспорта

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

наук Р. А. Байрамов

Официальные оппоненты: доктор физико-математических наук А. И. Омаров

кандидат физико-математических наук Р. Гулямов

Ведущая организация: Институт математики СО РАН

I. Новосибирск

Защита диссертации состоится « 3 % 1<ЭД4 г

в часов на заседании специализированного ученого

совета Д 067.02.21 в Ташкентском государственном университете по адресу: 700095, г. Ташкент, ВУЗгородок, ТашГУ, механико-математический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Ташкентского государственного университета.

п

Автореферат разослан ^ 1994 г.

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

С. УМА РОВ

- I - .

ОБЩАЯ ZAPAKTSPIiCim РАБОТЫ

^ктуахьаость_тег.и. Вопросы, связанные с полнотой систем йунк-U яадаются одними из наиболее вааных при изучении К -значных ■ик Рк (2¿ к < ио) . Особый интерес представляют яч базисы шшшальные по включению (равносильно: независимые) полные в системы. Семейство б (Р.) всех базисов логики Р бесконеч-

г\

¿елее того, даже одноэлементных базисов в гк бесконечна !Го — для каждого П У, 2 в Р^ существует П. -арнач Неверова еция. Стремясь выделить в 5 ÍPJ конечное и хорзпш обозримое [семейство, к членам которого предписанным способсм сводились произвольные базисы, Я.С.Новиков ввел свыше 30 лет назад пс-■ие простого базиса логики ' Рк - такого её базиса В , для •орого замена любой J- £ В ее наследственной системой A (J-) it неполную в Рк систему (В\ UA^/); произвольный до В . сводится к простому с помощью ^замены некоторой J-&B подходязуз часть Д (V) . Хотя семейство Лб(Р«) всех прозе базисов"з Рк яонечно при лззбсмк(А.Садомаа-^ ,С.В.Яблсз-а2^), надеетз на его обозримость оправдалась лишь при К -2 : ..Зестапал"^ показала, что в P¿ всего 44 простых базиса-з

Saloma A» On ths uunber of sinple bases of the se-fc of füao— ticna ovar a finite dcitain // Ann» Univ. ТигЗсаевзхз (ser» AX), 1962. Ко 32, ?.247-252.

Яблонский С.З. О суперпозициях функций в Рк // Проблемы кибернетика. 1Э63. Выл.9. С.337-340.

Пестопал Г.А. О числе простых, базисов булевых функций // доклады АН СССР. 1961. 140. :Ь 2. С.314-31?.

. явно выписала их, однако В.Б.Алексеев4'5) через несколько леи.' после этого получил |Лб(Рз)|2 2/755 уже при К = 3 и асимптотику /0^|Лб(Рк)|~ К""'.

В связи с тем, что при сведении произвольного базиса к'простому часто происходит йекелательаое {для многих ситуаций) увеличение мощности базиса, В. Б. Алексеев®^ ввёл понятие пооуярос-того базиса логики. Рк -такого ее базиса В , для которого полнота утрачивается даже при замене любой /б В любым представителем из А/'/) ; очевидно,?сяклй простой базис иолупрост,

т.е. П5(РК) ^.ППб(Рк) ,-где ПГ!5(РК) - семейство всех

полупростых В6 Б(Рц) . Оно еще более несбозрамо, чем (]{)(%}■ как доказано.В.Б.Алексеевш^» .при достаточно больших К выполняется '■ - .

'•;'"•■ - 2К '•:'• . - '

(ППб(Рк))>2кК ;

и упомянутое выше включение является строгим ара любом ; -,.. превращаясь в равенство, лишь- при К - 2. (отметим,-что строгость -.'включения установлена там косвенным образом -.без построения коа-

■ кретного-разделяющего примера -). . '•'.. ' • *

Естествен вопрос: можно яз так усилить свойства простота и полупростоты базисов, (причем .с сохранением присущей исходные свойством содержательности), чтобы семейство всех обладающее усиленной простотой (соотв.,полупростотой) базисоз оказалось

■ 4), Алексеев В.Б. .0 простых базисах ■ К -значной логики//-Матек«

заметки, ЗЭ6Э. 5. Л 4. С.471-482, .

5) Алексеев В.Б. О числе простых базисов з К ' -злачной логике//' Дискретный анализ (Новосибирск). 1971. Вып. 19.. ^С.3-10.

6) Алексеев Б.Б." О пслупрсс-тых .¿азисах К -значной логика//' -:.1атем. заметет. 1960.■ 28. 3 3. -С.407-422. . .

обозримым и при ■ К>/< ? Для■ поиска таких усилений естественно привлекать ослабленные понятия полноты систем функций: если W -полнота (здесь W соответствует W-елк. } слаб ее обычной полноты. потребовав потерю . W -полноты при замене любой функции базиса ей наследственной, системой (соотв. .произвольным представителем атой системы) ,'■ получим понятие W -устойчиво простого (соотв., w -устойчиво полупростого) базиса; очевидно, оно сильнее понятия простого (соотв..полупростого) базиса и будет содержательным при надлежащем выборе "параметра" Наибольший интерес исследование W -устойчивой простота И- U/ —устойчивой полупростоты базисов представляет для тех изучавшихся в литературе понятий W .-полноты,которые получаются из обычной полноты заменой оператора [ J суперпозиционнсго замыкания на композицию у '<>[.]. или" на композицию [ ,где у ■ 2Рк_- некоторый зкстенсивкй и монотонный, но,вообще говоря, неидемпотентный оператор (такой: у часто называют оператором гипозамшгашя, е образ у (А) системы А £= Рк -её у - оболочкой)w -Система А £ Рк - полна (соотв.,Y -полна) в Р^ , если у'([А])=РК (соотв., еслиТу*(А)]=

здесь стрелка вйраво соответствует лоолесуперпсзи-_ иконному действию оператора у ., а стрелка влево - досуперао-зищснному. Простой, базис В логики' . естественно назвать У -устойчиво простым,, если для любой J ¿.В .выполняется

Рк- ■ ' Однако при. формирование понятия ([ ]°Т) -устойчивой простоты возыоявыдва варианта, досуаерпозиционнсго действия ^• :а) ой действует только на наследственную систеглу заменяемой,функции .(это - малая.У -Деформация. базиса); б.) f действует на.все: возникаищее.в резуль-татё замены мнонество функций (Ьто -большая f -деформация

базиса). Сообразно атому, простой базис.В логики Рк естественно назвать: У -устойчиво простым, если дай любой выполняется ""[(ВЧ^^ГСШ))] Ф Рк и^ -устойчиво простым, если -Здесь малая стрелка . соответствует малой ^ -деформации базиса, а большая стрелка- <—> - больной. Аналогично ссуцест вдается переход от понятия полупростого базиса к понятию -устойчиво (соотв. -устойчиво, У —устойчиво и У -сзерх-устойчиво) полупростоте базиса В , где сверх устойчзгтгь соответствует замене / 6 В на у .-оболочку произвольной фувк ции £ € Д (/) ,а обычная устойчивость - выбору произвольного • представителя из /'(д(^)) в качестве заменяющей функции. Актуальность введённых разновидностей' устойчиво простых и устойчиво полупростых базисов определяется как актуальность! (уке обоснованной в литературе) понятий простого базиса и полу простого базиса, так и актуальностью используемых ослабленных вариантов полноты (в частности, содергательвостью используемых для ослабления операторов У ■)•

1}е£ь_ра5отц. Изучить введённые выше с участием параметра У разновидности устойчиво простых и устойчиво полупростых■ба згссз е Р^ .ив В, для следующих реализаций У : оператора! $> , & л £ , задаваемых в терминах групп симметрии функций в введенных Нгуен Вав Хог7-9'1 под влиянием идей- Г.Е.Пова-

7) Егуев Ван 1аг. О групповой эквивалентности в ?к // Вестник Белорусского гос. уеив.(серия I). 1966.& 3.'С.38-41.

8) Егуев Бан Хоа. Об X .-эквивалентности систем функций в мзсгозначнкх логиках// Алгебра и логика (Новосибирск).1986,

27.'» I. С.37-47. .

9) Кгуен Ван Хоа.Исследование групповой эквивалентности замкнутых классов ■К -значной логики// Канд.дисс.МиЕскЛ38Э.

рова10^ и известной гарвардской классификации булевых функций; введённого Р.А.Байрамовым11^' (под влиянием идей В.И.Еуравлёва) . оператора б" образования пермутацаонвсй оболочки; операторов

0Oyi в D, t , обобщающих на многозначный случай одноименные операторы образования £ -оболочка систем булевых функций по мере близости J5 ь, соответственно, мере близости , которые при К-2 были введены Р.М.Дкааадозкм"^ под руководством В.Е.Кудрявцева (здесь £ - число из единичного сегмента вещественной прямой а сужения на каждый арностный

слой pj"^ совпадают с отношением dn/Kn , где ctn -метрика Хэмминга на Рк ).

Ограниченно исследований, в основном, рамками Рг и Р^ (с редкими "выходами" в логику произвольной значности К ) вызвано чрезвычайной трудностью реализации программы в обща* . случав.

йсполззуштйа развитая Э.Постом, : С.Я.ЯблоискимД.В .Кузнецовым,И.Розенбергом ж др. авторами техника функциональных построений в вонечнозначных логиках и от— ■ дельные элементы близкой к ней техники итеративных алгебр Поста-Мальцева .(в частности, клонов), а также основные сведения о группах перестановок я полугруппах преобразований.

10) Поваров Г.Н. О групповой инвариантности булевых функций// В кн."Применение логики в науке и технике"' (М.:Изд.АН СССР. I960). С.263-340. ■. ^

П) Байрамов Р.А. Пермутацаовно порождающие множества алгебр.

Поста// Вестник МГУ. 1374. * б. С.ЗЗЗ. . 12) ¿дазадав P.M. Об £ -полноте множеств функций алгебры логики //. Доклады АН СССР. ЗЭ81. 256. Я 5.. C.I042-IC45. ;

... - о -

ЙДГЩая Довязе^.. Полностью описаны б -тише замкнутые классы трёхзначной логики и с помощью этого описания даны различные критерии (э -устойчивой простоты и б^. -устойчивой полупростоты базисов в Р^ .Описаны -устойчиво простые и б^ -устойчиво полулростые базисы логика Рк , К ^ ^ .Дострое вы; <о . -сверхустойчиво полупростой базис в Р ,ве являющзй-ся -устойчиво простым; jS. -устойчиво пслуг~остдй базис в ,не являющийся б" • -сверхустойчиво псяудростым; другие х________- . Опвсааы а^ -устойчиво престав и -устойчиво 'полупростые базисы в' .Вычислена .хзтганговы индексы всех прёдтдных в Ру классов и подавляющего' большинства непредполных каркасных классов трёхзначной логики (их число конечно,,.но велико - не менее 500) и с помощью вычисленных индексов найдено три разных достаточных условия Qjt - устойчивой простоты базисов в Д при В двузначной логике ■• Д, явно выписаны все устойчиво простые а все устойчиво полупростыа базисы всевозыозшых типов, формула-руемах для оператора <о ; > и -типов с дослесуперйозицаоншм действием оператора (соотв., б* и ); дня операторов Di l (i-OJ; ¿&lO,l)) - '.в' _Рг перечислены все Du" устойчаво (соотв., -полуустойчиво н'-антиустойчиво)" простые.ба зисы и для фиксированного .базиса Б исследовано поведение отображения Ai.s ; [О,1]~* ¿У, ПУ ,АУ] , сопоставляющего числу £. е. [О, ¡] Di,i - устойчнзостннй тип этого

базиса, где У, ПУ, А У - сокращения от "устойчиво","полуустойчиво", "аятаустойчяво".

■ Апссбатри Ьабста.. Основные результаты диссертации докладывалась на 7-сй (Новосибирск, 1984) 2-8-ой Шосква, 1986) Bcs

союзных конференциях по математической логике, Всесоюзной конференции по теоретической информатике (Свердаовск, 1.987), П Всесоюзном' семинаре по дискретной математике (Москва,1987) ' и П математических чтениях памяти М.Я.Суслина (Саратов,1991), а также ва семинарах в- Институте математики и механики АН , Азербайджана и в Институте кибернетики АН Узбекистана. По теме диссертации опубликовано <2 работ.

Структура и об^ёц. работы,,. Диссертация состоит из введе-еея, двух глав и списка, цитированной литературы (67 наименований). Объём диссертации - 164 страницы машинописного текста.

СОДЕРЕАНЙЕ РАБОТЫ '

Во введении дается краткий обзор основных работ, связанных, с простыми и полупрсстыми базисами- К -значннх логик, и намечается общая схема выделения'подлежащих изучению типов устойчиво простых и устойчиво полупростых базисов. Глава I (§§ 1,2) носит' вспомогательный характер - здесь приведена необходимые определения*-обозначения, используемые в диссертации результаты других авторов (не сформулированные-во введении). и некоторые предварительные наблвдения. Все ноше результаты содеркатся в основной главе 2 (§§ 3 -'?. ).

Нумерация приводимых ниже утверждений не совпадает с использованной в диссертации, так как здесь мы объединяем неко--.торые утверждения вз диссертации в одно. Сначала приведём результата з Рг ; так как их получение связано .лишь-с техническими трудностями,- все они'ва эвзны предо ояеввями - з отличие от теорем о базисах в Р^ (и в Рк , К ^ 3 ), доказательства которых сталкиваются с трудностями теоретического характера.

Пусть. Bi\... , Вчч — перечисление всех простых базисов логики Р^ » причём - в том порядке, как они выписаны8^ t упомянутой статье Г.А.Шестопал; ввиду равенства ППб(^) — = ПБ(Р2) оно перечисляет ж все ее яолудростые базисы.

П р е д л о к е в и е I (§ 3). Базисы В^...,В20,В3i, В32>-->Bv/ (их число ревно 31) исчерпывают каждое из следующих (совпадавших ыекду собой) семейств в : - а) всех б^ —устойчиво простых базисов;

б) всех -устойчиво полупростых базисов;

в) всех б. ' -сверхустойчиво полупростых базисов;

г) всех простых базисов, содержащих лишь б* -устойчиво простые булевы функции.

П р е я л о г е н и е 2 (§ 3). Базисы В, - ]>

ß^-f2^^} исчерпывают все -устойчиво простые и все <5 -устойчиво полупростые бьзисы в Р. (в частности,семей-ства таких базисов совпадают).

Предложение - 3 (§3). Семейство всех б" -устойчиво простых базисов в совпадает с П5(Р2<) \ B^i > B^j»

> Bai? ^4} и ш Ч2СЛ0 Равно 37« Семейство

всех бГ -устойчиво полупростых базисов в Рг совпадает с {15 (Ра) \ {ßii , f. Вчч J и их число равно 41.

С л е д с т б и е. Для ше^феровой J-gPz следувдие 8 условий на базис jl"Jj эквивалентны: -устойчивая простота; б" —устойчива?, полупростота; -сверхустойчивая полупросто-

х) точнее говора, статье ошибочно (позже ошбка исправлена саш автором) указаны 4 лишни? базиса - мевду я В,3 ;

если .перечисление из статьи, записать в виде В1}.--, ,

■ то: .при {в{и.:.г1^} В{-В* при - Ч€ {¡9,..44}

В{— . а базисы ■ B^вJ..., &12 следует отбросить (они не является простыми)

та; . (соотв,, £ ) - устойчивая простота (соотв., полупростота); /^]б{Б1,Вг].

Нредлокеняз 4 (5 5). Базисы ЬиВ,. В<а~

• ' х ' / 9

•> } ч В20 ^ исчерпывав« все &

-устойчиво простые и все. б* -устойчиво полупростые базисы в Рг (в частности, семейства таких базисов совпадает).

Предло*ение-5(§ 5). 14 базисов Вч,

в9( В 1с> > , • • •, Б30, В, 63« исчерпывают каядое

иэ следуищюс (совпадающих мевду собой) семейств в Р2 : г) всех -устойчиво простых базисов;

б) всех -устойчиво полупрсетых базисов;

в) всех -устойчиво простых базисов;

г) всех ^ -устойчиво полупростых базисов. .

Предлокевие 6 (§ 6). При £е [О, все 44

простых базиса логики Р^ 'являются Цз(г -устойчиво простыми , в при £ € (1 ] таковых не существует. При £ е >1] не существует в Р и Д -устойчиво простых базисов, а при ¿ е [О, } таковыми являются лета те же 14, что в предложения 5.

Это совпадение несколько неожиданно, так как оператор Д>£ имеет близостнуп (слойно-метрическуа) природу, а .операторы & и X - групповую. Другой пример совпадения разнородных понятий: в Рг - полнота. эквивалентна введенной Р.В.Фрей-валдом^. полноте с точностьв до кодирования и поэтому, указан-

13) Фрейаалд Р.В. Полнота с точностью до кодирования систам . функций К.-звачной логики и сложность ее распознавания// Доклада АН СССР. 1968. 180. * 4. С.803-805.

ное-в предео*ении 4 семейство ■[Bit B2,'Bj9, В^} совпадает с семейством всех Cod -устойчиво простых (соотв.полупростых) базисов.

В § 6 дам какдого £ £ [О,I1 перечислены также все Dir t -полуустойчиво простые и все Di, £. -антиустойчкво

простые базисы логики R e дай фиксированного базиса В исследовано поведение вышеупомянутого отображения Л ig

0,1) , где полуустойчивость и антиустойчивость определяются, соответственно, условиями ~

Перейдем к результатам в R (ив Р. . К 3 ).

п

' Теорем а 7 (§ 4). При любом К > 3 • в существует простой базис, содерЕацЕй'лишь- (Э -устойчиво простые функции, но не являющийся 6" -устойчиво, простым (при К = 3 пример строится явно)»

Теореме 8 (§ 4),..ПрЕ любом К^З в f"^ существуют б" -устойчиво пслупростой базисне являющийся <Е> -сверх--устойчиво полупросткы, z б" -сверхустсйчиво полупростой базис, не'являющийся -устойчиво простым (при К- 3 примеры , строятся ; ЯВНО ) • •.

Отметш, что один из этих двух примеров одновременно является первым ксЕкретннм примером полупростого непростого базиса. • . . ■

Теорема 9 (§ 4). Следующие условия при ; экви-

- II

валентны для любого В £ б {Рц) - : а) В ■ . б\ -устойчаво прост;

б) В & -устойчиво подупрост;

в) В -{Л ' где Т ~~ пР0Стая по массу Слупецкяго шефферова футзкцая;

г)-181= I И -устойчиво полупрост;

д) |В!~ 1 и В '-сверхустойчиво полупрост;

е) | В | - 1 з В ^ -устойчиво прост.

В частности, не существует примеров' для' теоремы 8 с условием

\ъ\ -1 . ,

Т..е о р е и а- Ю (§4). Ери любом " к^З з . РК существуют шефферош функции / з ^ такие, что. базис устойчиво псдупрсст з не является <о -устойчиво простая, а базис -устойчиво, прост и. не удозлетвоетзоряет ни

одному из (эквивалентных) условий теоремы Э (при К = 3 ¿я

- страчтся явно). • ' •'"' ' ' ...... ' "'

Теорема II (§ 4). 3 Р^ ' существует ровно 24 отличных от Р3 . б"-полных.замкнутых класса: "6.предподных в классов М*, М1, Мг( классы монотонных) функций) , , ' Ы-г (классы сохранения нетривиальных разбиений множества ' £0, I, £ ]■ и по б собственных подклассов-в каждом из ¿¿¿, (все они явно указаны).

С помощью теоремы II найдены, различные условия -устойчивой простоты базисов в Р^ . Например, два из них внра--аются следЗвпей теоремой, где-под бицрестым базисом логики Рк понимается всякий'ее простой базис .$' , удовлетаоряэ-щзй условию: да любой '' /б. В существует не. менее, двух яред-полннх в Рк классов, содержаадх . ид. (*).

-.12 -

Теорема 12 (§4). Всякий бипростой базис дотики является её СГ-устойчиво простым базисом; таковым является и всякий её простой базис, содержащий хотя бн две функции вне объединения MouMi0MzuUo Ul^Ul^.

Теорема 13 (§ 5). Простой базис логики Р^ -устойчиво прост тогда и только тогда,, когда он не содержит ни одного базиса классов То,Х ,Т^ "Гц, ^ Р^:

/(а,..., а) - а} ). если В^П5(Р3) ¿-ус-

тойчиво полупрост, то В' является и' -устойчиво простым. Однако среди непростых базисов логик! f^ существуют ^ -устойчиво полупростые.(пример указывается явно).

Через п обозначим П . -арный слой замкнутого класса Л & Pfc и для функций / в А^1 положим

индексом класса ' i $ назовём вещественное число

Sup max {а(^ЯГп1):/£Г\АЫ1как уставов

дено С.В.Яблонским, предполными в . г помимо уже упомянутых классов Мс fU { >Ъ {i-Ql, Zj являются лишь следующие: классы сохранения двухэлементных подмножеств ^tjjjc

С {О, классы' Cjj сохранения бинарных центральных от вощений о "запрещенными" ларами 2 t > , класс L

линейных (по модулю-З ) функций, класс S . самодвойственных функций и класс Слупецкого Т .

Т е о р е м а 14 (§ 7). Хэмминговы индексы предполных а Р3 классов исчерпываются числами Уъ > iIx и ~/ъ » ПРИ~

чём; Е(А)^при Ae{TJaX,Z}i MAh'/l V

Фладл^.т^т«*}.

Каркасным классом в Рк назовём класс, представший в злде пересечения какого-либо множества (в том числе - пустого) предзслнызс з Рк классов; в частности, Рк и все предяслкые в Рк классы являются каркасными. Очевидно, £ (А}.- ОЬ-р Укэ при К = 3 каркасных классов достаточно ясного - не менее 500.

Теорема 15 С? 7). Хзммиеговы индексы непредполнкх каркасных классов логики Р3 исчершгзЕются числами Чз.»

% > % > %» * í быть монет, ещё несколь-

кими числами из затерзала ('/^ 7

Теоремы 14,15 позволяют найти некоторые нетривиальные достаточные условия 0О/(_ -устойчивой простоты базисов в Р3

(тривиально следующее: при у'к1 Ц>ь -устойчи-

вая простота базиса легаш равносильна его простоте; в

Р не существует 0а1 -устойчиво простых базисов).

Подполугруппу £ симметрической полугруппы й,,-^

^ ,' "У назовём ассоциированной с базисом Б^О(Ру), если существует В такая, что Я. совпадает с основанием (т.е. унарКоК слоем )• замкнутого класса и & \ij\-

Семейство все?: таких подполугрупп прг фгкезрезанаок • базисе. '6 обозначил через (Й-я'

Т е с р е. и а К (? 7). Прз 0 4 £ 1/г ' ■ следуй аие базгсы логккл Р5 являатся -устойчиво простят:

. а) .всякий простой базис, сод'ерэддай хотя бы две функции вне объединения

Г— Т» т-г*

! I/}„V.|{ V

-14-

б) всякий бипростсй базис; 1

в) всякий простой базис В. < для которого семейство

^^^(^■г/ не содержит следующих десяти подполугрупп •. полутруппы 52 5 — всех'семи подполугрупп 52. , удовлетворяющих включениям 52.3X6^.^ £2 £ . (где симметрическзя группа множества \0, 1,2] ) и оснований

Т^ Т"'1* -г(1) ' Т Т Т

. ; и , I, классов. |0, 1.2 •

Автор благодарит.своих научных руководителей.за постановку задач и постоянное внимание'к работе, а проф. Б.Б.Кудрявцева - за обсуждение результатов двух последних параграфов.

Основные .результаты диссертации опубликованы в .следуюащх •работах (из •двух./'?},[б]публикаций в соавторстве,, в-диссертацию включены лишь ;те результаты, которые получены диссертантом лично).: .' ; \

I. Ет амб ерди е в Б. Об" устойчиво простых .и устойчиво полупростых базисах в Р //'Щ Всесоюзная конференция по математической-логике. Тез. докл. Новосибирск: 1984. .

' 2. В г а ы б е р д и"' е в Б.' О .'некоторых критических базисах' ' к -значнкх логик. I // Изв. АК'УаСС?. СТН. Ташкент: 1Э84. #.6. С.55-5Б.

. . 3. Ега м 'б е р. д и н в. Б.' О близостно-устойчиво простых базисах к -значнсй логики // УШ Всессазная конференция по . математической'логике. Тез. докл. Москва: 1986'. С.65.

'4. Е г.а й б е р д и е в .Б, Хэшенговы'индексы дредпол--. ,ных классов.трехзначной логики //'Теоретическая ж прикладная "информатика. Тез. докл.'Свердловск: 1Э67. С.20, ' ' Б. :Е г в м б е -р д л е в Б. О,некоторых критическйх бази-

car к - значных логик. К. // Деп. в ВИКШ 2.11.198?. а IG96-B87. 20-с. . . ' * . ' '

6. Згам.бердиев Б. О Хэмминговых индексах пред-яолиых классов трёхзначной логики // Деп. в-ЕИБИТИ 5.1.1989. а 534-B89. 30 с.

.7. Б а й р ä'M о в P.A., ,Е г а м <5 е р д и е в . Б. О примитивно порожденных и .каркасных клонах // Вторые матем. чтения памяти Ы.Я.Суслина. Тез. докл. (Саратов: 23-28 - сентября 1991). Саратов. 1991. С.23.. ■■

' 8. Б 5 й р а м о в P.A., £ г а м б е р д ы а. в. • Б. € - насыщенные подклоны конечнозначных логик / / XI межреспубликанская конференция по математической логике'. Тезисы докладов.'Казань-: 1992, С.14. ■

А Н Н О Т А 4 И Я

Чеклз зса^лаздд логикада ызълум йулган куй:дэг;1 т л£клар: <5* - пермутаснон туллклак, £ - касо^з иаъноса-даги ?ул2кллк.ва , <5* , рб - грушалаилар каъно-

сидаг:! тУлагупклар асосяда (э ,£,,&, & , J& ~ туррун (утагургун, котугруя) одпй ва ку^тяк .

бззгслар туглунчасз каритплада.

Еяорвдагз туауеталар асосздая. бззлолор sncct ка&язтгэ лсг;:кг~2 анян маалгач, уч ¡сйлатлл дописала (£ ва маькосггага крлтгк базгслар гисглсса *ел кзлзкгак. Чекяя

лсгзка 'учун блр не~а критик теорз.^аларх:

гсботлакгап.

дер бар *ол учуй лозга сулгазда еддпй вз яриаоетй-ликна аяратузча кргтак Сазпслар курзлгак.

■ .SUMMARY

In frasework of well-known notions in the theory of finite-valued-logics such, аз- € - pernutational completeness, £ - completeness in the distance sense, the пе\ч no- -tiona 6? г - completeness in the split senso axe

introduced.

The above aentioned bases are found exactly -in two-valued logic» In three-valued logic сазе singular Ъаоеа are found ia ^Q and ^ senses. Зоне theorena on singular . completeness in finite-valued logic, сазе are proved.

pqr ever? сазе сог.сгз'е singular cases which distinguish sir:pleness and halfsisplsnisa are constructed.