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



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

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.716

Михайлович Анна Витальевна

О ЗАМКНУТЫХ КЛАССАХ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ, ПОРОЖДЕННЫХ СИММЕТРИЧЕСКИМИ ФУНКЦИЯМИ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Москва - 2009

003476635

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

Научный руководитель: Официальные оппоненты:

Ведущая организация:

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

профессор А. Б. Угольников.

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

профессор В. В. Алексеев;

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

доцент В. А. Стеценко.

Казанский государственный университет.

Защита диссертации состоится " о? " 2009 г.

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

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

Автореферат разослан " " 2009 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических профессор

Общая характеристика работы Актуальность темы

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

Э. JL Пост1 описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что множество замкнутых классов в Р2 счетно, при этом каждый такой класс имеет конечный базис.

Многозначные логики во многом похожи на двузначную логику. В них сохраняются многие результаты, имеющие место в двузначной логике. Можно, например, отметить решения проблемы функциональной полноты и задачи описания предполных классов. В то же время имеются существенные различия между Р2 и Рк при к > 3. К их числу относятся примеры2 Ю. И. Янова о существовании замкнутых классов в Pk, не имеющих базиса, и А. А. Мучника о существовании замкнутых классов в Pk со счетным базисом (к > 3). Из этих результатов следует, что мощность семейства замкнутых классов в P¡. при всех к > 3 континуальна. Это делает труднообозримой структуру данного множества.

Поскольку при к > 3 изучение замкнутых классов /с-значной логики наталкивается на значительные трудности, то, с одной стороны, многие авторы стали рассматривать задачу изучения классов, замкнутых относительно более сильных операций замыкания, которые позволили бы получить множество замкнутых классов конечной или счетной мощности. С другой стороны, изучались отдельные семейства замкнутых классов функций fc-значной логики, содержащих конечное, счетное или континуальное множество подклассов. К настоящему времени получено описание свойств некоторых семейств замкнутых классов. Отметим некоторые из этих результатов.

Наиболее хорошо изучены свойства предполных классов функций /с-значной логики. Конечность числа предполных классов в Рк установил

1Post Е. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, 3. 163-185.

Post E. L. The two-valued iterative systems of mathematical logic. Annals of Math. Studies 5, Princeton Univ. Press. 1941. 122 p.

2Янов Ю. И., Мучник А. А. О существовании /t-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. Т. 127, № 1. С. 44 - 46.

A.B. Кузнецов3. Все предполные классы функций трехзначной логики описал С. В. Яблонский4. Полное описание предполных классов в Pk при всех к > 3 было дано И. Розенбергом5. Асимптотически точная формула для числа 7г(к) всех предполных классов в Pk найдена в работе6 Е. Ю. Захаровой, В. Б. Кудрявцева и С. В, Яблонского. Конечная порожденность всех предполных классов при к < 7 доказана Д. Лау7. Пример предпол-ного класса в Р% типа О (замкнутого класса функций, монотонных относительно частичного порядка специального вида), не имеющего конечной порождающей системы, приведен Г. Тардошем8. Необходимые и достаточные условия конечной порожденности предполных классов функций ъРк(к> 3), монотонных относительно частично упорядоченных множеств ширины 2, получены О. С. Дудаковой9.

В ряде работ изучались свойства минимальных классов и минимальных клонов в решетке Шк (семействе замкнутых классов функций fc-значной логики, упорядоченных по включению). В книге10 Р. Пешеля и Л. А Калужнина приведена формула для числа минимальных классов функций fc-значной логики, к > 3, и дано описание свойств функций, порождающих эти классы. Все минимальные клоны в Рз описаны Б. Ча-канем11. И. Розенберг12 установил конечность множества минимальных клонов в Pk при всех к > 3 и привел классификацию функций, определяющих минимальные клоны в решетке

В задаче изучения свойств замкнутых классов в Pk, содержащих заданное множество функций одной переменной, можно отметить следую-

3 Математика в СССР за 40 лет. М.: 1959. Т. 1. С. 102-108.

4 Яблонский С. В. О функциональной полноте в трехзначном исчислении // Доклады АН СССР.

1954. Т. 95, № 6. С. 1152-1156.

6Rosenberg I. G. La structure des functions de plusieurs variables sur un ensemble fini // C. R. Acad. Sei. Paris, Group 5. 1965. 260. 3817-3819.

Rosenberg I. G. Über die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpr. ÖSAV Üada Mat. Pïiv. Vëd., Praha. 1970. 80. 3-93.

eЗахарова Е.Ю., Кудрявцев В.Б., Яблонский C.B. О предполных классах в к-значных логиках И ДАН СССР. 1969. Т. 186, № 3. С. 509-512.

7 Lau D. Bestimmung der Ordnung maximaler Klassen von Funktionen der fc-wertigen Logik // Zeitschr. f. Math. Logik und Grundlagen, d. Math. 1978. 24. 79 - 96.

8 Tardos G. A not finitely generated maximal clone of monotone operations // Order. 1986. 3. 211-218.

яДудакова О. С. О конечной порожденности предполных классов монотонных функций многозначной логики // Математические вопросы кибернетики. М.: Физматлит, 2008. Вып. 17. С. 13-104.

10Pôschel П., Katuznin L. A. Funktionen- und Relationenalgebren. Berlin. 1979. 260 p.

11 Csákany В. All minimal clones on the three-element set // Acta Cybemetica. 1983. 6, 3. 227 - 238.

12Rosenberg I. G. Minimal clones X: The five types. Lectures in Universal Algebra (L. Szabo, k. Szendrei eds.) // Colloquia Mathematica Societatis Jaiios Bolyai 43, North Holland. 1986. 405 -427.

щие результаты. Б. Слупецкий13 предложил критерий полноты для систем функций в Рк, содержащих множество всех функций &-значной логики, зависящих от одной переменной, к > 3. Все замкнутые классы в Рк, содержащие множество 1), перечислены Г. А. Бур-ле14. С. В. Яблонский15 получил критерий полноты для систем функций в Рк при к > 3, содержащих множество всех функций из принимающих не более к — 1 значения. Некоторое усиление этого результата получено А. И. Мальцевым16. Критерии полноты для систем функций /с-значной логики при к > 5, содержащих группу &к всех подстановок на множестве Ек = {0,1,..., к — 1}, получены А. Саломаа17. В работах С. С. Марченкова18 и Нгуен Ван Хоа19 получено описание семейства замкнутых классов, содержащих группу б*, при всех к > 3; изучены свойства семейств замкнутых классов в Рк, содержащих некоторые подгруппы группы <3кВ работах В. Б. Кудрявцева2® изучаются свойства систем функций

13Shipecki J. Kriterium pelnosci wielowartosciowych systemow logiki zdaú // С. R. Séanc. Soc. Sei. Varsovie, Cl. Ш. 1939. 32.102-109.

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

15Яблонский C.B. Функциональные построения в fc-значной логике // Труды матем. ин-та АН СССР им. Стеклова. 1958. Т. 51. С. 5-142.

16Мальцев А. И. Об одном усилении теорем Слупецкого и Яблонского // Алгебра и логика. 1967. Т. 6, № 3. С. 61-74.

17 Saloma a A. Some completeness criteria for sets of functions over a finite domain I // Ann. Univ. Turkuensis, Ser. AI. 1962. 53. 9 p.

Salomaa A. Some completeness criteria for sets of functions over a finite domain П // Ann. Univ. Turkuensis, Ser. AI- 1963. 63.19 p.

18 Марченков С. С. S-классификация функций многозначной логики // Дискретная математика. 1997. Т. 9, вып. 3. С. 125 -152.

Марченков С. С. G-предполные классы многозначной логики // Дискретный анализ и исследование операций. 1996. Т. 3, № 3. С. 47-70.

Марченков С. С. А-классификация функций многозначной логики // Докл. РАН. 1999. Т. 366, № 4. С. 455 -457.

19Нгуен Ван Хоа. О структуре самодвойственных замкнутых классов fc-значной логики, сохраняемых всеми внутренними автоморфизмами // Дискретная математика. 1993. Т. 5, вып. 4. С. 87-108.

Нгуен Ван Хоа. Описание замкнутых классов fc-значной логики, сохраняемых всеми автоморфизмами // Докл. АН Беларуси. 1994. Т. 38, № 3. С. 16-19.

Нгуен Ван Хоа. К описанию семейства G-псшвых замкнутых классов fc-значной логики // Кибернетика. 1990. № 5. С. 9-12.

Нгуен Ван Хоа. Структура симметрических замкнутых классов fc-значной логики. Докт. диссертация. Минск, 1995.

20Кудрявцев В. Б, Относительно 5-систем функций fc-значной логики // ДАН СССР. 1971. Т. 199, № 1. С. 20-22.

Кудрявцев В. Б. О свойствах ¿-систем функций fc-значной логики // Дискретный анализ. 1971. Вып. 19. С. 15-47. Кудрявцев В. Б. Функциональные системы. М.: Изд-во МГУ, 1982. 158 с.

/с-значной логики, состоящих только из функций, принимающих все значения из множества Еь (такие системы называются 5-системами); приводятся критерии ¿'-полноты для рассматриваемых систем функций, устанавливается асимптотическое поведение числа S'-предполных ¿"-множеств и их типов.

Свойства замкнутых классов из множества Рщ всех функций к-знач-ной логики, принимающих значения только из множества Ei, 2 < I < к, изучаются в работах Г. Буроша21 и других исследователей. Рассматривается отображение замкнутых классов из Рц в замкнутые классы Pi и для каждого класса В С Pi описывается семейство СГ^ДВ) замкнутых классов из Рц, состоящих из функций, ограничение которых на множестве Ei определяет функции из класса В. В работах Н. Грюнвальда22 и Д. Jlay23 изучен ряд важных свойств замкнутых классов из Рз^; в частности, для каждого замкнутого класса В булевых функций установлена мощность семейства 9Тз,2(В), для некоторых классов В С Р2 приведено описание фрагментов решетки Шз, содержащих классы из диаграммы включений, соответствующих семейству 9t3i2(.B).

Ряд работ посвящен изучению семейств замкнутых классов в Р^, содержащихся в заданных предполных классах. Этот вопрос рассматривался в работах24 С. С. Марченкова,.Я. Деметровича, Л. Ханнака, Я. Ба-гинского, Д. Лау, А. Саломаа и других авторов. Показано, что предпол-

71 Burosch G. Uber die Ordnung der prevoUständigen Klassen in Algebren von Prädikaten. Preprint, WPU Rostock. 1973.

Burosch G. Über Algebren von Prädikaten. Preprint Univ. Rostock. 1974.

22 Grünwald N. Bestimmung sämtlicher abgeschlossenen Mengen aus Рз,2, deren Projektion Fg ist // Rostock, Math. Kolloq. 1983. 23. 5- 26.

Grünwald N. Beschreibung aller abgeschlossenen Mengen aus Рзд, deren Projektion Fg ist, mit Hilfe von Relationen // Rostock, Math. Kolloq. 1983. 23. 27-34.

Grünuiald N. Strukturaussagen über den Verband der abgeschlossenen Mengen von 2, insbesondere von Рз,2. Dissertation A, Universität Rostock. 1984.

22Lau D. Über abgeschlossene Teilmengen von // J. Inform. Process Cybern. EIK. 1988. 24, 11/12. 561-572.

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

Марченков С. С. О замкнутых классах самодвойственных функций многозначной логики П // Проблемы кибернетики. 1983. Выл 40. С. 261-266.

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

Bagyinszki J., Demetrovics J. Linearis osztälyok ■ szerkezete primszäm frWkü logikäban // MTA SZTAKI. 1976. 16. 25-52.

Bagyinszki J.t Demetrovics J. The lattice of linear classes in prime-valued logics // Banach Center Publications (Warszawa). 1982. 7. 105-123.

Demetrovics J., ffanndk L. The cardinality of closed sets in precomplete classes in fc-valued logics // Acta Cybernetica. 1979. 4, 3. 273 - 277.

ный класс в Pk при к > 3 содержит континуальное множество замкнутых классов тогда и только тогда, когда он не является классом типа L (классом линейных функций). Все предмаксимальные классы в Р3 найдены в работах Д. Лау25, С. С. Марченкова, А. Саломаа и других исследователей. В работе26 А. А. Булатова, Д. Лау и Б. Штрауха для каждого предмаксимального класса в установлена мощность семейства замкнутых классов, содержащихся в рассматриваемом классе. Все максимальные классы для предполных классов типа Р (классов самодвойственных функций) при всех к > 3 найдены в работах С. С. Марченкова, Я. Деметровича и Л. Ханнака.

Существование континуального семейства классов в Pk (к > 3), содержащих цепи неограниченной длины, установлено в работах А. Саломаа27. Примеры цепей и антицепей в Шк (к > 3) континуальной мощности приведены работе28 Я. Деметровича и Л. Ханнака. Достаточные условия того, что заданный класс функций в Рк (к > 3) содержит не более чем счетное семейство подклассов, приведены в работах Д. Лау29, приведены также примеры классов, удовлетворяющих этим условиям. Ряд свойств решетки Шк изучен в работах А. А. Булатова, И. А. Мальцева и других авторов. Верхние и нижние окрестности замкнутых классов различного вида в решетке Шк описаны в работах С. В. Яблонского30 и Б. А. Михеевой31. Примеры замкнутых классов в Рк (к > 3), не явля-

Demetrovics J., Ranndk L., Marchenkov,. S- S. Some remarks on the structure of P3 // C. R. Math. Rep. Acad. Sei. Canada. 1980. 2. 215-219.

Lau D. Über die Anzahl von abgeschlossenen Mengen linearer Funktionen der n-wertigen Logik // Elektron. Informationsverarb. Kybernet. EIK. 1978. 14,11. 561-563.

Salomaa A. On infinitely generated sets of operations in finite algebras // Ann. Univ. Turkuensis, Ser. AI. 1964. 74. 12 p.

25lau D. Submaximale Klassen von P3 // J. Inform. Process Cybern. EIK. 1982. 18, 4/5. 227-243.

wBulatov A. A., Lau D., Strauch В. The cardinalities of sublattices of depth 2 in the lattices of clones on a 3-elementary set. Preprint Univ. Rostock. 1996.

"Salomaa A. On the heights of closed sets of operations in finite algebras // Ann. Acad. Sei. Fennicae, Ser. AI. 1965. 363. 12 p.

Salomaa A. On some algebraic notions in the theory of truth-functions // Acta Philos. Fennicae. 1965. 18.193-201.

2iDemetrovics ]., Hannah L. Construction of large sets of clones // Zeitschr. f. Math. Logik und Grundlagen, d. Math. 1987. 33. 127—133.

29Lau D. Ein Kriterium für den Nachweis der Abzählbarkeit gewisser Teilverbände des Verbandes der abgeschlossenen Mengen von Funktionen der /с-wertigen Logik // Rostock, Math. Kolloq. 1986. 30. 11-18.

Lau D. Function Algebras on Finite Sets: Berlin, Heidelberg: Springer, 2006. 668 p.

™ Яблонский C.B. Строение верхней окрестностей для предикатно-описуемых классов в Р* // Доклады АН СССР. 1974. Т. 218, № 2. С. 304-307.

31Михеева Е. А. Классификация нижних окрестностей замкнутых классов из решетки // Дискретная математика. 1991. Т. 3, вып. 4. С. 3-15.

ющихся конечно порожденными, в которых каждый предполный класс имеет конечный базис, приведены в работе Е. А. Михеевой32; показано также, что мощность семейства таких классов не более чем счетная.

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

Как уже говорилось, семейство замкнутых классов из работы Ю. И. Янова и А. А. Мучника является первым примером континуального семейства замкнутых классов функций Ызначной логики (к > 3). Следует отметить, что функции из этих примеров обладают следующими свойствами: каждая функция является симметрической, принадлежит множеству Р^г (то есть принимает значения только из множества {0,1}), принимает значение 0 на единичном наборе и на всех наборах, содержащих хотя бы одну нулевую компоненту, и, кроме того, замыкание произвольного множества Р этих функций совпадает с множеством и[{/}], где объединение берется по всем функциям из Р. В диссертации рассматриваются семейства замкнутых классов в Рк, порожденных функциями, которые обладают аналогичными свойствами.

Цель работы

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

Основные методы исследования

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

32Мшеева Е.А. Построение в Р* максимальных классов, ие имеющих конечных базисов // Дискретная математика. 1998. Т. 10, вып. 2. С. 137-159.

Научная новизна

Все результаты работы являются новыми. В диссертации получены следующие основные результаты.

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

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

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

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

Теоретическая и практическая ценность

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

Апробация результатов

Результаты диссертации докладывались на семинаре "Функции многозначной логики и смежные вопросы" под руководством профессоров A.B. Угольникова, C.B. Гашкова и P.M. Колпакова (2007, 2008 гг.), на семинаре "Математические вопросы кибернетики" под руководством

профессора О. М. Касим-Заде (2009 г.), на IX Международном семинаре "Дискретная математика и ее приложения" (Москва, МГУ, 18-23 июня 2007 г.), на XV Международной конференции "Проблемы теоретической кибернетики" (Казань, 2-7 июня 2008 г.), на XVII Международной школе-семинаре "Синтез и сложность управляющих систем" (Новосибирск, 27 октября-1 ноября 2008 г.), на Международной конференции "Современные проблемы математики, механики и их приложений" (Москва, 30 марта-2 апреля 2009 года), на VIII Международной научная конференция "Дискретные модели в теории управляющих систем" (Москва, 6-9 апреля 2009).

Публикации

Основные результаты диссертации опубликованы в 6 работах, список которых приведен в конце автореферата [1-6].

Структура и объем работы

Диссертация состоит из введения, четырех глав и списка литературы. Полный объем диссертации — 111 страниц, список литературы содержит 165 наименований.

Содержание работы

Пусть Ек — {0,1,..., к — 1}, Щ — множество всех наборов вида (ai,...,ап), где «i,... ,an € Ек, F — замкнутый (относительной операции суперпозиции и введения фиктивной переменной) класс функций /г-значной логики, к > 2, п > 1. Множество функций 21С F называется базисом классаF, если [21] = Fu для любого множества S С 21 выполняется неравенство [В] ф F. Замкнутый класс F называется базируемым, если существует множество 21, такое, что 2Í — базис класса F. Класс F называется конечно порожденным, если он имеет конечный базис.

Пусть 21 С Рк, к > 2. Множество всех функций, которые могут быть получены из функций системы 21 применением операций переименования, отождествления переменных и введения фиктивной переменной, будем называть р-замыканием множества 21 (обозначение < 21 >). Множество 21 называется р-замкнутым, если 21 = < 21 >; р-замкнутые множества называются также р-замкнутыми классами.

Обозначим через Rk множество всех функций fc-значной логики, к' > 3, принимающих значения только из множества {0,1} и равных нулю на единичном наборе и на всех наборах, содержащих хотя бы одну нулевую компоненту. Множество всех наборов из которые получаются друг из друга перестановкой компонент, называется слоем. Функцию f(x\,... ,хп) из Rk будем называть симметрической, если для любого слоя L С и любых двух наборов а, /3 £ L выполняется равенство /(а) = /(/?). Множество всех симметрических функций из Rk будем обозначать через S*. Функция из Rk называется m-слойной симметрической, если существуют т слоев, ш > 1, таких, что эта функция равна единице на всех наборах из этих слоев и равна нулю на всех остальных наборах. Множество всех m-слойных симметрических функций из Rk будем обозначать через S™, тп > 1. Множество всех однослойных симметрических функций из Rk, равных нулю на всех наборах, все компоненты которых совпадают, будем обозначать через NSj[., к > 3.

Пусть33 а £ Q, а > 0, a f(xi,...,xn) — однослойная симметрическая функция. Будем говорить, что / является функцией типа а (тип функции / равен а), если отношение числа единиц к числу двоек в слое, на наборах которого эта функция равна единице, равно а. Множество всех функций из Sj, тип которых равен и, будем обозначать через Fa, а е Q, а > 0. Функцию из Рз будем называть монотонной, если она монотонна относительно порядка 0 < 1 < 2 на множестве Рз. Множество всех монотонных функций из R3 будем обозначать через MS. Пусть / — монотонная симметрическая функция из R3. Обозначим через ej и df число единиц и двоек соответственно в слое с наибольшим числом единиц, на котором функция / принимает значение 1. Пусть G С MS, к G Z+. Будем называть множество G fc-ограниченным, если для любой функции / е G выполняется неравенство е/ < к и найдется функция д € G, такая, что ед = к. Пусть G — ¿-ограниченное множество. Положим JC[G) = {де G\eg = к}.

Пусть А С Рк, к > 3. Будем говорить, что множество А обладает свойством (*), если для любого б С А выполняется равенство (и[{5}]) П А = [иЫ] П А, где объединение берется по всем функциям д из множества G. Таким образом, если функция / из множества А выражается некоторой формулой над G, то найдется функция д из G, такая, что / € [{<?}]. Будем говорить, что функция / не превосходит функцию

33 Через Q и N обозначаем множество всех рациональных и множество всех натуральных чисел соответственно, Z+ = N U {0}.

д относительно отношения X (обозначение / ;< д), если / € [{#}]. Функции /ид называются эквивалентными (обозначение / ~ д), если / ;< д и д ^ /. Будем говорить, что функция / не превосходит функцию д относительно отношения (обозначение / <!а5), если существует формула Ф над А, реализующая функцию / и содержащая подформулу вида д{В\1..., Вт), где Ви ..., Вт — формулы34 над А. Будем говорить, что множество А обладает свойством (**), если для любых /, д € А, таких, что /<?а<7 и 9 —А/, выполняется соотношение и для любых функций /, д, /1 € А, таких, что / 9 —АЛ, / ^ Л, выполняется по крайней мере одно из следующих соотношений: / г< д, д ^ Н.

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

В главе 1 приводятся основные определения, обозначения и вспомогательные утверждения.

В главе 2 изучаются замкнутые классы, порожденные однослойными симметрическими функциями. Вводится специальное отношение порядка на множестве В параграфе 2.1 доказывается, что класс .Р, порожденный множеством С, С? С N83, имеет базис тогда и только тогда, когда каждая функция из С? содержится в некоторой ограниченной максимальной цепи множества б? относительно введенного отношения порядка; при этом .Р имеет конечный базис тогда и только тогда, когда множество б конечно (теорема 2.1). В параграфе 2.2 сопоставляются замкнутые классы и р-замкнутые классы, порожденные однослойными симметрическими функциями. Показывается, что замыкание множества Бз совпадает с р-замыканием этого множества (теорема 2.2). Далее, для любой функции / из N83 и любого а € а > 0, приводятся необходимые и достаточные условия выполнения соотношения [{/}] С < ^ и {/} > (теорема 2.3). Наконец, доказывается, что замкнутый класс, порожденный функциями из множества Бз, является конечно порожденным тогда и только тогда, когда существуют рациональные числа 01,..., £ > 1, такие, что каждая функция из этого класса принадлежит множеству < Р1 >, где Р = Р^ и ... и Р^ (теорема 2.4).

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

34 Символы переменных являются тривиальными формулами.

рассматривается отношение порядка г^ш на множестве МБ. Показывается, что класс порожденный множеством б, б С МБ, имеет базис тогда и только тогда, когда каждая функция из О содержится в некоторой ограниченной максимальной цепи множества С? относительно введенного отношения порядка; при этом Р имеет конечный базис тогда и только тогда, когда множество С? является ^-ограниченным и множество /С(С) конечно (теорема 3.1). В параграфе 3.2 рассматривается представление монотонных симметрических функций точками на плоскости из множества Z+ х N. Каждой функции / из МБ ставится в соответствие точка на плоскости с координатами (е/,й/) и указываются все точки плоскости, соответствующие функциям д и Ъ из МБ, таким, что д гшэ / Гшэ Л (следствие 3.2.3). В параграфе 3.3 приводятся критерии базируемости и конечной порожденности замкнутых классов, порожденных монотонными симметрическими функциями, в терминах свойств множеств точек из2+хМ, соответствующих порождающим системам этих классов (теоремы 3.2 и 3.3).

В главе 4 изучаются множества, обладающие свойствами (*) и (**). Доказывается критерий базируемости для классов, порождающие системы которых содержатся в множествах, обладающих этими свойствами. Приводятся также примеры множеств, обладающих свойствами (*) и (**). В параграфе 4.1 доказывается критерий базируемости для замкнутых классов, порождающие системы которых состоят из попарно неэквивалентных функций и содержатся в множествах, обладающих свойствами (*) и (**). Показано, что каждый такой класс Р имеет базис тогда и только тогда, когда всякая функция из системы С?, порождающей класс Р, содержится в некоторой ограниченной максимальной цепи множества С? относительно порядка ^ (теорема 4.1). Этот критерий является обобщением критерия базируемости для однослойных симметрических функций, полученного в параграфе 2.1. Кроме того, показывается, что если класс Р имеет базис, то существует базис класса Р, состоящий из всех верхних граней ограниченных максимальных цепей множества С? (следствие 4.1.1). В параграфе 4.2 приводятся примеры множеств функций, удовлетворяющих условиям полученных критериев (теоремы 4.2-4.4). Показывается, что свойствами (*) и (**) обладают следующие множества функций: множество всех немонотонных функций из Б™, т > 1, множество ЫБ^, к > 3, а также некоторые подмножества множества Бз, обладающие рядом дополнительных свойств.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, профессору А. В. Уголь-никову за постановку задачи и постоянное внимание к работе.

Публикации автора по теме диссертации

1. Михайлович А. В. О замкнутых классах трехзначной логики, порожденных симметрическими функциями // Вестн. Моск. ун-та. Матем. Механ. 2008. № 4. С. 54-57.

2. Михайлович А. В. О классах функций трехзначной логики, порожденных монотонными симметрическими функциями // Вестн. Моск. ун-та. Матем. Механ. 2009. № 1. С. 33-37.

3. Михайлович А. В. О некоторых свойствах симметрических функций трехзначной логики // Материалы IX междунар. семинара "Дискретная математика и ее приложения" (Москва, МГУ, 18-23 июня 2007 г.). М.: Изд-во Центра прикладных исследований при механико-математическом факультете МГУ, 2007. С. 165-167.

4. Михайлович А. В. О замкнутых классах в Рз, порожденных монотонными симметрическими функциями // Тезисы докладов XV междунар. конференции "Проблемы теоретической кибернетики" (Казань, 2-7 июня 2008 г.). Казань, 2008. С. 83.

5. Михайлович А. В. О замкнутых классах многозначной логики, порожденных функциями со специальными свойствами // Материалы XVII междунар. школы-семинара "Синтез и сложность управляющих систем" (Новосибирск, 27 октября-1 ноября 2008 г.). Новосибирск, Изд-во Института математики, 2008. С. 117-122.

6. Михайлович А. В. О свойствах классов трехзначной логики, порожденных симметрическими функциями // Материалы междунар. конференции "Современные проблемы математики, механики и их приложений" (Москва, МГУ, 30 марта-2 апреля 2009 г.). М.: Издательство "Университетская книга", 2009. С. 396.

Подписано в печать 26. Об. 0& Формат 60x 90 1/16. Усл. печ. л. 1,0 Тираж {00 экз. Заказ 2$

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

Введение

1 Основные определения и вспомогательные утверждения

1.1 Определения и обозначения

1.2 Вспомогательные утверждения.

2 Классы, порожденные функциями из множества NS

2.1 Критерии базируемости и конечной порожденности.

2.2 Замыкание относительно отождествления переменных.

3 Классы, порожденные функциями из множества MS

3.1 Критерии базируемости и конечной порожденности.

3.2 Изображение монотонных функций на плоскости.

3.3 Критерии базируемости и конечной порожденности в терминах свойств множества точек на плоскости.

4 Классы, порожденные функциями со специальными свойствами

4.1 Критерий базируемости для множеств, обладающих свойствами (*)и(**)

4.2 Примеры множеств, обладающих свойствами (*) и (**)

4.2.1 Классы, порожденные функциями из множества NSm.

4.2.2 Классы, порожденные симметрическими функциями с согласованными типами.

4.2.3 Классы, порожденные функциями из множества NS^.

4.2.4 Классы, порожденные функциями из множества MS.

В данной работе изучаются свойства замкнутых классов функций многозначной логики. Рассматривается задача о существовании базисов для некоторых семейств замкнутых классов.

Э. JI. Пост [134,135] описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что множество замкнутых классов1 в Р2 счетно, при этом каждый такой класс имеет конечный базис (см. также [136]). Описание классов Поста можно найти также в работах [33,42,62,63,67,104,119,124,132,139]. Предикатное описание классов Поста дано в [4] (см. также [33,42,124]). Алгебраический подход к понятиям суперпозиции и замкнутого класса предложен А. И. Мальцевым [24,28].

Многозначные логики во многом похожи на двузначную логику. В них сохраняются многие результаты, имеющие место в двузначной логике. Можно, например, отметить решения проблемы функциональной полноты [21, 22, 25, 65, 66,146,147,151] и задачи описания предполных классов [16,29,66,126-129,137,140,141]. В то же время имеются существенные различия между Р2 и Рк при к > 3. К их числу относятся примеры Ю. И. Янова о существовании замкнутых классов в Рк, не имеющих базиса, и А. А. Мучника о существовании замкнутых классов в Рк со счетным базисом [71] (к > 3). Из этих результатов следует, что мощность семейства замкнутых классов в Рк при каждом к > 3 континуальна. Это делает труднообозримой структуру данного множества.

Поскольку при к > 3 изучение замкнутых классов fc-значной логики наталкивается на значительные трудности, то, с одной стороны, многие авторы стали рассматривать задачу изучения классов, замкнутых относительно более сильных операций замыкания, которые позволили бы получить множество замкнутых классов конечной или счетной мощности (см., например, [1,8,9,23,34,36,38,51-54,56-61,76]). С другой стороны, изучались отдельные семейства замкнутых классов функций /с-значной логики, содержащих конечное, счетное или континуальное множество подклассов. К настоящему времени получено описание свойств некоторых семейств замкнутых классов2 в Рк- Отметим некоторые из этих результатов.

Наиболее хорошо изучены свойства предполных3 классов функций £;-значной логики. Конечность числа предполных классов в Рк установил А. В. Кузнецов [44]. Все предполные классы функций трехзначной логики описал С. В. Яблонский [65,66]. Отдельные семейства предполных классов в Рк найдены в работах [2,13,14,29,66,126-129]. Полное описание всех предполных классов в Рк при всех к > 3 было дано И. Розенбер-гом [140,141] (см. также [5,15,35,69,124,137]). Асимптотически точная формула для числа 7Г(к) всех предполных классов в Рк найдена в [15]. Конечная порожденность всех

1 Через Р^ обозначается множество всех функций /с-значнон логики, к > 2.

2 Обзор результатов, полученных в этом направлении, можно найти, например, в [124,133].

3 Предполные классы в Рк называются также максимальными. предполных классов при к <7 доказана Д. Лау [108]. Пример предполного в Р8 класса типа1 О (замкнутого класса функций, монотонных относительно частичного порядка специального вида), не имеющего конечной порождающей системы, приведен Г. Тардо-шем [158]. Необходимые и достаточные условия конечной порожденное™ предполных классов функций в Рк (к > 3), монотонных относительно частично упорядоченных множеств ширины 2, получены в [10-12].

Свойства минимальных классов и минимальных клонов5 в решетке (семействе замкнутых классов функций /с-значпой логики, упорядоченных по включению) изучались в работах [87-89,100-103,124,125,131,133,138,144,145,152,159]. В [133] приведена формула для числа минимальных классов функций &-значной логики, к > 3, и дано описание свойств функций, порождающих эти классы (см. также [124]). Все минимальные клоны в Р3 описаны Б. Чаканем [87,88]. В [101,102,133] описаны все минимальные клоны в Рк (к > 3) порядка 1. Розенберг [144] установил конечность множества минимальных клонов в Рк при всех к > 3 и привел классификацию функций, определяющих минимальные клоны в решетке SDtfc. Отдельные семейства минимальных клонов в Рд изучены в [159]; в работе [131] приведены примеры минимальных клонов в Рк, к > 3, порядка t, 1 < t < к.

В работах [6,25,30-32,36-41,47-55,66,146,147,151] изучаются свойства замкнутых классов в Рк, содержащих заданное множество функций одной переменной. Е. Слу-пецкий [151] предложил критерий полноты для систем функций /с-значиой логики, содержащих множество6 Р/.(1), к > 3. Все замкнутые классы в Рк, содержащие множество Pfc(l), перечислены Г. А. Бурле [6]. Яблонский [66] получил критерий полноты для систем функций в Рк, содержащих множество всех функций из Р/„.(1), принимающих не более к — 1 значения, к > 3. Некоторое усиление этого результата получено А. И. Мальцевым [25]. Критерии полноты для систем функций из Рк при к > 5, содержащих группу &/; всех подстановок на множестве = {0,1,., к — 1}, получены в [146,147]. Все замкнутые классы в Рк, содержащие заданный предполный в [Р/;(1)] класс функций, для всех к > 3 описаны в [55]. Описаиие семейства замкнутых классов в Рк, содержащих группу @к, при всех к > 3 получено в [30-32,43,51-53]. Свойства семейств замкнутых классов в Р/;, содержащих некоторые подгруппы группы & к, изучены в работах [37,39-41,47-50,54].

В работах В. Б. Кудрявцева [17-20] изучаются свойства систем функций /г-значной логики, состоящих только из функций, принимающих все значения из множества Ек (такие системы называются ^-системами); приводятся критерии 5"-полноты для рассматриваемых систем функций, устанавливается асимптотическое поведение числа 5-предполных ^-множеств и их типов.

Замкнутые классы функций из множества7 Pkj изучаются в работах [83-86,97-99, 105-107,112,116,117,124]. Рассматривается отображение замкнутых классов из Pk)i в замкнутые классы Pi и для каждого класса В С Рг описывается семейство 9^(5) замкнутых классов из Pk,i, состоящих из функций, ограничение которых на множестве Et определяет функции из класса В. Ряд важных свойств замкнутых классов из P3i2 изучен в [97-99,112,117]; в частности, для каждого замкнутого класса В булевых функций

4 Будем использовать обозначения семейств предполных классов из книги [69].

5 Клоном называется замкнутый класс, содержащий все селекторные функции.

6 Через -Pfc(l) обозначается множество всех функций f(x) из Рк, к >2.

7 Через Pk,i обозначается множество всех функций /с-значной логики, принимающих значения только из множества Ei, 2 <1 < к. установлена мощность семейства 9t3i2(В), а также для некоторых классов В С Р2 приведено описание фрагментов решетки 9Я3, содержащих классы из диаграммы включений, соответствующих семейству 0?з,2(-В). В работах [83-86,99,116] найдены все максимальные и все предмаксимальные8 замкнутые классы множества Pki2, изучены некоторые свойства семейств (В) для всех В С Р2.

Семейства замкнутых классов в Рк (к > 3), содержащихся в заданном предполном классе, изучаются в работах [30-32,74,75,77,79,80,90-95,109-111,113,115,118,120-124, 130,142,143,148,153-157]. Показано [30-32,74,75,90,92,109,148], что предполный класс в Рк {к > 3) содержит континуальное множество замкнутых классов тогда и только тогда, когда он не является классом типа L (классом линейных функций). Некоторые свойства замкнутых классов линейных функций изучены в [74,75,79,80,109,115,118,148,153-157]. Все предмаксимальные классы в Рз найдены в [31,75,92,110,130,148]; в работе [77] для каждого предмаксимального класса в Р3 установлена мощность семейства замкнутых классов, содержащихся в рассматриваемом классе. Все максимальные классы для пред-полных классов типа Р (классов самодвойственных функций) при всех к > 3 найдены в [30-32,90,91,113,143]. Описание некоторых семейств предмаксимальных классов в Р% при к > 4 содержится в [111,120-124,142].

Существование континуального семейства классов в Рк, содержащих цепи неограниченной длины (к > 3), доказано в [149,150]. Примеры цепей и антицепей в (к > 3) континуальной мощности приведены в [96,133]. Достаточные условия, при выполнении которых заданный класс функций в Рк (к > 3) содержит не более чем счетное семейство подклассов, приведены в [114,124]; приведены также примеры классов, удовлетворяющих этим условиям. Ряд свойств решетки Шк изучен в работах [26,27,78,81,82]. Верхние и нижние окрестности замкнутых классов различного вида в решетке DJlk описаны в [45,68]. Примеры замкнутых классов в Рк (к > 3), не являющихся конечно порожденными, в которых каждый предполный класс имеет конечный базис, приведены в [46]; показано также, что мощность семейства таких классов не более чем счетная.

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

Как уже говорилось, семейство замкнутых классов из работы Янова и Мучника является первым примером континуального семейства замкнутых классов функций к-значной логики (к > 3). Следует отметить, что функции из этих примеров обладают следующими свойствами: каждая функция является симметрической, принадлежит множеству Pkt2 (то есть принимает значения только из множества {0,1}), принимает значение 0 на единичном наборе и всех наборах, содержащих хотя бы одну нулевую компоненту и, кроме того, замыкание произвольного множества F этих функций совпадает с множеством и[{/}], где объединение берется по всем функциям из множества F.

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

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

Дадим некоторые определения. Пусть Е= {0,1,., к — 1}, Е£ — множество всех наборов вида («i,., <уп), где а\,., ап € Ек, к > 2, п > 1, а X — счетное множество переменных. Пусть 21 = {f\(x4,., Xini), /2(^1, ■ • •, ж?„2)>.,} — некоторое множество функций из Pk■ Дадим определение понятия формулы над 21.

1) Символ переменной из множества X является формулой над 21; такие формулы называются тривиальными.

2) Если <&!,., Фп — формулы над 21, a f(xi,., хп) 6 21, то выражение Ф = /(Ф1, • • ■, Фп) является формулой над 21, п > 1, при этом Ф, Ф15., Фп называются подформулами формулы Ф. Подформулами формулы Ф называется также сама формула Ф и все подформулы формул Фх,., Фп.

Формула Ф называется простой, если она имеет вид . ,Х{п), где д Е 21, аз;,,,. ., Xin — символы переменных, п > 1.

Пусть F — замкнутый (относительной операции суперпозиции и введения фиктивной переменной) класс функций fc-значной логики, к >2. Множество функций 21 С F называется базисом класса F, если [21] = F и для любого множества ЯЗ С 21, 03 Ф 21, выполняется неравенство [23] ф F. Замкнутый класс F называется базируемым, если существует множество 21, такое что 21 — базис класса F. Замкнутый класс F называется конечно порожденным, если он имеет конечный базис.

Пусть 21 С Рк, к > 2. Множество всех функций, которые могут быть получены из функций системы 21 применением операций переименования, отождествления переменных и введения фиктивной переменной, будем называть р-замыканием множества 21 (обозначение < 21 >). Множество 21 называется р-замкнутым, если 21 = < 21 >; р-замкнутые множества называются также /^-замкнутыми классами.

Обозначим через Rk, к > 3, множество всех функций /с-зпачной логики, принимающих значения только из множества {0,1} и равных нулю на единичном наборе и на всех наборах, содержащих хотя бы одну нулевую компоненту. Множество С всех наборов из которые получаются друг из друга перестановкой компонент, называется слоем. Функцию f(x 1,. ,хп) из Rk будем называть симметрической, если для любого слоя С С и любых двух наборов а, (3 G L выполняется равенство /(й) = /(/?)- Множество всех симметрических функций из Rk будем обозначать через S^. Функция из Rk называется ?7г-слойной симметрической, если существуют т слоев, т > 1, таких, что эта функция равна единице на всех наборах из этих слоев и равна нулю на всех остальных наборах. Множество всех m-слойных симметрических функций из R/c будем обозначать через S£\ та > 1. Множество всех однослойных симметрических функций из Rk, равных нулю на всех наборах, все компоненты которых совпадают, будем обозначать через NS^., к > 3.

Пусть9 а £ Q, а > 0, a f(xi,., хп) — однослойная симметрическая функция. Будем говорить, что / является функцией типа сг (тип функции / равен а), если отношение числа единиц к числу двоек в слое, на наборах которого эта функция равна единице, равно а. Множество всех функций из S3, тип которых равен а, будем обозначать через

9 Через Q и N обозначаем множество всех рациональных и множество всех натуральных чисел соответственно, Z+ = NU {0}.

Fa, 0" G Q, о" > 0. Функцию из P3 будем называть монотонной, если она монотонна относительно порядка 0 < 1 < 2 на множестве Е3. Множество всех монотонных функций из i?3 будем обозначать через MS. Пусть / — монотонная симметрическая функция из i?3- Обозначим через е/ и dj число единиц и двоек соответственно в слое с наибольшим числом единиц, на котором функция / принимает значение 1. Пусть G С MS, к Е Будем называть множество G /с-ограниченным, если для любой функции / G G выполняется неравенство е/ < к и найдется функция д € G, такая, что е3 = к. Пусть G — ^-ограниченное множество. Положим JC(G) = {д G G | еа = А;}.

Пусть А С Pfc, к > 3. Будем говорить, что множество А обладает свойством (*), если для любого G С А выполняется равенство (и[{<7}]) П А = [и{д}] П А, где объединение берется по всем функциям д из множества G. Таким образом, если функция / из множества А выражается некоторой формулой над G, то найдется функция д из G, такая, что / G [{#}]- Будем говорить, что функция / не превосходит функцию д относительно отношения ^ (обозначение / ^ д), если / G [{#}]• Функции fug называются эквивалентными (обозначение / ~ д), если / ^ д и д ^ /. Будем говорить, что функция / не превосходит функцию д относительно отношения <д (обозначение / <5а д), если существует формула Ф над А, реализующая функцию / и содержащая подформулу вида д(Вг,., Вт), где Bi,., Вт — формулы над А. Будем говорить, что множество А обладает свойством (**), если для любых /, д & А, таких, что / <1д g и <7 <а /) выполняется соотношение f ~ д и для любых функций /, <7, /г Е А, таких, что / <а 9, 9 ^а h, f ^ h, выполняется по крайней мере одно из следующих соотношений: / dg, 9 dth.

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

1. Андреева О. В., Голунков Ю. В. Программно-замкнутые классы функций алгебры логики и предикатов // Кибернетика. 1981. № 5. С. 133.

2. Байрамов Р. А. Об одной серии предполных классов в fc-значной логике // Кибернетика. 1967. № 1. С. 7-9.

3. Биркгоф Г. Теория решеток. М.: Наука, 1984. 568 с.

4. Блохина Г. Н. О предикатном описании класссов Поста // Дискретный анализ. 1970. Вып. 16. С. 16-29.

5. Буевич В. А. Вариант доказательства критерия полноты для функций /с-значной логики // Дискретная математика. 1996. Т. 8, вып. 4. С. 11-36.

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

7. Гаврилов Г. П.,- Сапоженко А. А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. 416 с.

8. Голунков Ю. В. Полнота систем функций в операторных алгоритмах, реализующих функции /г-значиой логики // Вероятностные методы и кибернетика. 1980. Вып. 17. С. 23-24.

9. Данилъченко А. Ф. О параметрической выразимости функций трехзначной логики // Алгебра и логика. 1977. Т. 16, № 4. С. 397-416.

10. Дудакова О. С. Об одном семействе предполных классов функций fc-значной логики, не имеющих конечного базиса // Вестн. Моск. ун-та. Матем. Механ. 2006. № 2. С. 29-33.

11. Дудакова О. С. О классах функций /с-значной логики, монотонных относительно множеств ширины два // Вестн. Моск. ун-та. Матем. Механ. 2008. № 1. С. 31-37.

12. Дудакова О. С. О конечной порожденное™ предполных классов монотонных функций многозначной логики // Математические вопросы кибернетики. М.: Физматлит, 2008. Вып. 17. С. 13-104.

13. Захарова Е. Ю. Об одном достаточном условии полноты в Pk // Проблемы кибернетики. М.: Наука, 1966. Вып. 16. С. 239-244.

14. Захарова Е. 10. Критерий полноты системы функций из Р& // Проблемы кибернетики. М.: Наука, 1967. Вып. 18. С. 5-10.

15. Захарова Е.Ю., Кудрявцев В. Б., Яблонский С. В. О предполных классах в к-значных логиках // ДАН СССР. 1969. Т. 186, № 3. С. 509-512.

16. Кудрявцев В. В. О покрытиях предполных классов Ахзначной логики // Дискретный анализ. 1970. Вып. 17. С. 32-44.

17. Кудрявцев В. В. Относительно 5-систем функций &-значной логики // ДАН СССР. 1971. Т. 199, № 1. С. 20-22.

18. Кудрявцев В. Б. О свойствах S'-систсм функций А;-значной логики // Дискретный анализ. 1971. Вып. 19. С. 15-47.

19. Кудрявцев В. Б. О свойствах ^-систем функций А;-значной логики // Akademie-Verlag Berlin. EIK. 1973. 9, № 1/2. С. 81-105.

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

21. Кузнецов А. В. О проблемых тождества и функциональной полноты для алгебраических систем // Труды 3-го Всесоюзного матем. съезда. М.: Изд-во АН СССР, 1956. Т. 2. С. 145-146.

22. Кузнецов А. В. Структуры с замыканием и критерии функциональной полноты // Усп. мат. наук. 1961. Т. 16 (98). С. 201-202.

23. Кузнецов А. В. О средствах для обнаружения невыводимости и невыразимости // Логический вывод. М.: Наука, 1979. С. 5-33.

24. Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1966. Т. 5, № 3. С. 5-24.

25. Мальцев А. И. Об одном усилении теорем Слупецкого и Яблонского // Алгебра и логика. 1967. Т. 6, № 3. С. 61-74.

26. Мальцев И. А. Некоторые свойства клеточных подалгебр Поста и их основных клеток // Алгебра и логика. 1972. Т. 11, № 5. С. 571-587.

27. Мальцев И. А. Некоторые свойства клеток алгебр Поста // Дискретный анализ. 1973. Вып. 23. С. 24-31.

28. Мальцев А. И. Итеративные алгебры Поста. Новосибирск: Изд-во НГУ, 1976. 100 с. .

29. Мартынюк В. В. Исследование некоторых классов в многозначных логиках // Проблемы кибернетики. М.: Наука, 1960. Вып. 3. С. 49-60.

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

31. Марченков С. С., Деметрович Я., Ханнак Л. О замкнутых классах самодвойственных функций в Рз // Методы дискретного анализа и решение комбинаторных задач. 1980. Вып. 34. С. 38-73.

32. Марченков С. С. О замкнутых классах самодвойственных функций многозначной логики II // Проблемы кибернетики. 1983. Вып 40. С. 261-266.

33. Марченков С. С., Угольников А. Б. Замкнутые классы булевых функций. М., Инст. Прикл. Матем. им. М. В. Келдыша, 1990. 148 с.

34. Марченков С. С. Основные отношения б1-классификации функций многозначной логики // Дискретная математика. 1996. Т. 8, вып. 1. С. 99-128.

35. Марченков С. С. Предполнота замкнутых классов в предикатный подход // Математические вопросы кибернетики. М.: Наука. Физматлит, 1996. Вып. 6. Под ред. С. В. Яблонского. 368 с.

36. Марченков С. С. ^-классификация идемпотентных алгебр с конечными носителями // Докл. РАН. 1996. Т. 348, № 5. С. 587-589.

37. Марченков С. С. С?-предполные классы многозначной логики // Дискретный анализ и исследование операций. 1996. Т. 3, № 3. С. 47-70.

38. Марченков С. С. ^-классификация функций многозначной логики // Дискретная математика. 1997. Т. 9, вып. 3. С. 125-152.

39. Марченков С. С. ^-классификация конечных инъективных функций // Дискретный анализ и исследование операций. 1997. Т.4, № 2. С. 15-42.

40. Марченков С. С. А-замкнутые классы идемпотентных функций многозначной логики, определяемые двуместными отношениями // Дискретный анализ и исследование операций. 1998. Т.5, № 1. С. 32-59.

41. Марченков С. С. А-классификация функций многозначной логики // Докл. РАН. 1999. Т. 366, № 4. С. 455-457.

42. Марченков С. С. Замкнутые классы булевых функций. М.: Физматлит, 2000.126 с.

43. Марченков С. С. S-классификация функций трехзначной логики. М.: Физматлит, 2001. 80 с.

44. Математика в СССР за 40 лет. М.: 1959. Т. 1. С. 102-108.

45. Михеева Е. А. Классификация нижних окрестностей замкнутых классов из решётки // Дискретная математика. 1991. Т. 3, вып. 4. С. 3-15.

46. Михеева Е. А. Построение в Рк максимальных классов, не имеющих конечных базисов // Дискретная математика. 1998. Т. 10, вып. 2. С. 137-159.i li.HU.l. . 1 ' .

47. Яблонский С. В. О функциональной полноте в трехзначном исчислении // Доклады АН СССР. 1954. Т. 95, № 6. С. 1152-1156.

48. Яблонский С. В. Функциональные построения в к-значной логике // Труды ма-тем. ин-та АН СССР им. Стеклова. 1958. Т. 51. С. 5-142.

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

50. Яблонский С. В. Строение верхней окрестности для предикатно-описуемых классов в Рк // Доклады АН СССР. 1974. Т. 218, № 2. С. 304-307.

51. Яблонский С. В., Гаврилов Г. П., Набебин А. А. Предполные классы в многозначных логиках. М.: Изд-во МЭИ, 1997. 142 с.

52. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2008. 384 с.

53. Янов Ю. И., Мучник А. А. О существовании А;-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. Т. 127, № 1. С. 44-46.

54. Дискретная математика и математические вопросы кибернетики / Под ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974. 312 с.

55. Конспект лекций О. Б. Лупанова по курсу "Введение в математическую логику" / Отв. ред. А. Б. Угольников. М.: Изд-во ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова, 2007. 192 с.

56. Bagyinszki JDemetrovics J. Linearis osztalyok szerkezete primszam erteku logikaban // MTA SZTAKI. 1976. 16. 25-52.

57. Bagyinszki J., Demetrovics J. The lattice of linear classes in prime-valued logics // Banach Center Publications (Warszawa). 1982. 7. 105-123.

58. Barris S., Willars R. Finitely many primitive positive clones // Proc. of the American Mathematical Society. 1987. 101, 3. 427-430.

59. Bulatov A. A., Lau D., Strauch B. The cardinalities of sublattices of depth 2 in the lattices of clones on a 3-elementary set. Preprint Univ. Rostock. 1996.

60. Bulatov A. A., Krokhin A., Safin K., Sukhanov E. On the structure of clone lattices // General Algebra and Discrete Mathematics. Heldermann-Verlag, Berlin. 1995. 27-34.

61. Bulatov A. A. Polynomial reducts of modules I. Rough classification // Mult.-Valued Log. 1998. 3, 2. 135-154.

62. Bulatov A. A. Polynomial reducts of modules II. Algebras of primitive and nilpotent functions 11 Mult.-Valued Log. 1998. 3, 3. 173-193.

63. Bulatov A. A., Krokhin A., Safin K., Semigrodskikh A., Sukhanov E. On the structure of clone lattices II // Mult.-Valued Log. 2001. 7, 5/6. 379-389.

64. Bulatov A. A. Conditions satisfied by clone lattices // Algebra Universalis. 2001. 45, 1/2. 237-241.

65. Burosch G. Uber die Ordnung der prMvollstandigen Klassen in Algebren von Pradikaten. Preprint, WPU Rostock. 1973.

66. Burosch G. Uber Algebren von Pradikaten. Preprint Univ. Rostock. 1974.

67. Burosch G., Dassow J., Harnaw W., Lau, D. Uber Algebren von Pradikaten. Preprint, WPU Rostock. 1979.

68. Burosch G., Dassow J., Harnaw W., Lau, D. On subalgebras of an algebra of predicates // J. Inform. Process Cybern. EIK. 1985. 21, 1/2. 9-22.

69. Csakany B. Three-element groupoids with minimal clones // Acta Sci. Math. 1983. 45. 111-117.

70. Csakany B. All minimal clones on the three-element set // Acta Cybernetica. 1983. 6, 3. 227-238.

71. Czedli G., Halas R., Kearnes K. A., Palfy P. P., Szendrei A. The join of two minimals clones and the meet of two maximal clones j j Algebra Universalis. 2001. 45, 2/3. 161-178.

72. Demetrovics J., Hannak L. The cardinality of closed sets in precomplete classes in /с-valued logics // Acta Cybernetica. 1979. 4, 3. 273-277.

73. Demetrovics J., Hannak L. On the cardinality of self-dual closed classes in ^-valued logics // MTA SZTAKI Kozlemenyek. 1979. 23. 7-16.

74. Demetrovics J., Hannak L., Marchenkov S. S. Some remarks on the structure of P3 // C. R. Math. Rep. Acad. Sci. Canada. 1980. 2. 215-219.

75. Demetrovics J., Hannak L. The number of reduct of a preprimal algebra // Algebra Universalis. 1983. 16, 1. 178-185.

76. Demetrovics J., Hannak L., Ronyai L. On algebraic properties of monotone clones // Order. 1986. 3. 219-225.

77. Demetrovics J., Hannak L., Ronyai L. On monotone clones // MTA SZTAKI Tanulmanyok. 1987. 202. 39-62.

78. Demetrovics J., Hannak L. Construction of large sets of clones // Zeitschr. f. Math. Logik und Grundlagen. d. Math. 1987. 33. 127 — 133.

79. Griinwald N. Bestimmung samtlicher abgeschlossenen Mengen aus P3i2, deren Projektion Fg ist // Rostock, Math. Kolloq. 1983. 23. 5-26.

80. Griinwald N. Beschreibung aller abgeschlossenen Mengen aus P3i2, deren Projektion Fg ist, mit Hilfe von Relationen // Rostock, Math. Kolloq. 1983. 23. 27-34.

81. Griinwald N. Strukturaussagen iiber den Verband der abgeschlossenen Mengen von Pk,2, insbesondere von Р3)2. Dissertation A, Universitat Rostock. 1984.

82. Haddad L., Rosenberg I. G. An interval of finite clones isomorphic to (P(N), C) // C. R. Math. Rep. Acad. Sci. Canada (6). 1986. 8. 375-379.

83. Harnau W. Die Definitions der Vertauschbarkeitmengen in der fc-wertigen Logik und das Maximalitatsproblem // Zeitschr. f. Math. Logik und Grundlagen. d. Math. 1974. 20. 339-352.

84. Harnau W. Die vertauschbaren Funktionen der wertigen Logik und ein Basisproblem // Zeitschr. f. Math. Logik und Grundlagen. d. Math. 1974. 20. 453463.

85. Kearnes K.A., Szendrei A. The classification of commutative minimal clones // Discuss. Math., Algebra Stoch. Methods. 1999. 19, 1. 147-178.

86. Kuntzman J. Algebra de Boole. Paris: Dunod. 1965. 319 p.

87. Lau D. Pravollstandige Klassen von Pkii // Elektron. Informationsverarb. Kybernet. EIK. 1975. 11, 10-12. 624-626.

88. Lau D. Eigenschaften gewisser abgeschlossener Klassen in Postschen Algebren. Dissertation A, Universitat Rostock. 1977.

89. Lau D. Kungruenzen auf gewissen Teilklassen von Pk,i // Rostock, Math. Kolloq. 1977. 3. 37-43.

90. Lau D. Bestimmung der Ordnung maximaler Klassen von Funktionen der k-wertigen Logik I j Zeitschr. f. Math. Logik und Grundlagen. d. Math. 1978. 24. 79-96.

91. Lau D. Uber die Anzahl von abgeschlossenen Mengen linearer Funktionen der n-wertigen Logik // Elektron. Informationsverarb. Kybernet. EIK. 1978. 14, 11. 561563.

92. Lau D. Submaximale Klassen von P3 // J. Inform. Process Cybern. EIK. 1982. 18, 4/5. 227-243.

93. Lau D. Die maximalen Klassen von Ро1к{0) // Rostock, Math. Kolloq. 1982. 19. 29-47.

94. Lau D. Funktionenalgebren uber endlichen Mengen. Dissertation B, Unversitat Rostock. 1984.

95. Lau D. Die maximalen Klassen von Polk{x, x + lmodk) \ x € Ek} // Rostock, Math. Kolloq. 1984. 25. 23-30.

96. Lau D. Ein Kriterium fur den Nachweis der Abzahlbarkeit gewisser Teilverbande des Verbandes der abgeschlossenen Mengen von Funktionen der k-wertigen Logik // Rostock, Math. Kolloq. 1986. 30. 11-18.

97. Lau D. Uber abgeschlossene Mengen linearer Funktionene in mehrwertigen Logiken // J. Inform. Process Cybern. EIK. 1988. 24, 7/8. 367-381.

98. Czu Kai. Precompleteness of'a set'arid rings of linear functions // Acta Sci. Natur. Univ. Jilinensis. 1963. 2.

99. Czu Kai. On the precompleteness of the classes of functions preserving a partition // Acta Sci. Natur. Univ. Jilinensis. 1963. 2.

100. Czu Kai, Lju Sjui Hua. Precomplete classes defined by binary relations in manyvalued logics // Acta Sci. Natur. Univ. Jilinensis. 1963. 4.i 11

101. Post E. L. The two-valued iterative systems of mathematical logic. Annals of Math. Studies. Princeton Univ. Press. 1941. 5 122 p.

102. Solvability, provability, definability: the collected works of Emil L. Post / Martin Davis, editor. Boston, Basel, Berlin: Birkhauser. 1994. 554 p.

103. Quackenbush R. W. A new proof of Rosenberg's primal algebra chacterization theorem // Colloquia Mathematica Societatis Janos Bolyai 28, Finite Algebra and multiplevalued logic; Szeged (Hungary). 1981. 603-604.

104. Quackenbush R. W. A survey of minimal clones // Aequationes Math. 1995. 50, 1-2. 3-16.

105. Reschke M., Denecke K. Ein neuer Beweis fur die Ergebnisse von E. L. Post iiber abgeschlossene Klassen Boolescher Funktionen // J. Inform. Process Cybern. EIK. 1989. 25, 7. 361-380.

106. Rosenberg I. G. La structure des functions de plusieurs variables sur un ensemble fini // C. R. Acad. Sci. Paris, Group 5. 1965. 260. 3817-3819.

107. Rosenberg I. G. Uber die funktionale Vollstandigkeit in den mehrwertigen Logiken // Rozpr. CSAV Rada Mat. Priv. Ved., Praha. 1970. 80. 3-93.

108. Rosenberg I. G. Completeness, closed classes and relations in multiplevaued logics // Proc. Internat. Sympos. on multiple-valued logics, Morgantown, 1974. 1-26.

109. Rosenberg I. G., Szendrei A. Submaximal clones with a prime order automorphism // Acta Sci. Math. (Szeged). 1985. 49. 29-48.

110. Rosenberg I. G. Minimal clones I: The five types. Lectures in Universal Algebra (L. Szabo, A. Szendrei eds.) j I Colloquia Mathematica Societatis Janos Bolyai 43, North Holland. 1986. 405-427.

111. Rosenberg I. G., Machida H. Gigantic pairs of minimal clones — characterization and existence j I Mult.-Values Log. 2001. 7, 1/2. 129-148.

112. Salomaa A. Some completeness criteria for sets of functions over a finite domain I j j Ann. Univ. Turkuensis, Ser. AI. 1962. 53. 9 p.

113. Salomaa A. Some completeness criteria for sets of functions over a finite domain II // Ann. Univ. Turkuensis, Ser. AI. 1963. 63. 19 p.

114. Salomaa A. On infinitely generated sets of operations in finite algebras // Ann. Univ. Turkuensis, Ser. AI. 1964. 74. 12 p.

115. Salomaa A. On the heights of closed sets of operations in finite algebras // Ann. Acad. Sci. Fennicae, Ser. AI. 1965. 363. 12 p.

116. Salomaa A. On some algebraic notions in the theory of truth-functions // Acta Philos. Fennicae. 1965. 18. 193-201.

117. Shipecki J. Kriterium pelnosci wielowartosciowych systemow logiki zdan // C. R. Seanc. Soc. Sci. Varsovie, CI. III. 1939. 32. 102-109.

118. Szabo L. On minimal and maximal clones // Acta Cybernetica. 1992. 10, 4. 323-327.

119. Szendrei, A. Idempotent reducts of abelian groups // Acta Sci. Math. (Szeged). 1976. 38. 171-182.

120. Szendrei, A. On closed classes of linear operations over a finite set of squarefree cardinality // Elektron. Informationsverarb. Kybernet. EIK. 1978. 14, 11. 547-559.

121. Szendrei, A. On closed classes of quasilinear functions // Czechoslovak Math. J. 1980. 80. 498-509.

122. Szendrei, A. On the idempotent reducts of modules I // Universal algebra, Proc. Colloq., Esztergom/Hung. 1977, Colloquia Mathematica Societatis Janos Bolyai 29. 1982. 753-767.

123. Szendrei, A. On the idempotent reducts of modules II // Universal algebra, Proc. Colloq., Esztergom/Hung. 1977, Colloquia Mathematica Societatis Janos Bolyai 29. 1982. 769-780.

124. Tardos G. A not finitely generated maximal clone of monotone operations // Order. 1986. 3. 211-218.

125. Waldhauser T. Minimal clones generated by majority operations // Algebra Universalis. 2000. 44, 1/2. 15-26.

126. Михайлович А. В. О замкнутых классах в Рз, порожденных монотонными симметрическими функциями // Тезисы докладов XV междунар. конференции "Проблемы теоретической кибернетики" (Казань, 2-7 июня 2008 г.). Казань, 2008. С. 83.

127. Михайлович А. В. О замкнутых классах трехзначной логики, порожденных симметрическими функциями // Вестн. Моск. ун-та. Матем. Механ. 2008. № 4. С. 54-57.

128. Михайлович А. В. О классах функций трехзначной логики, порожденных монотонными симметрическими функциями // Вестн. Моск. ун-та. Матем. Механ. 2009. № 1. С. 33-37.