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

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

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

Ларионов Виталий Борисович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат

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

2 8 ОКТ 2010

Москва - 2010

004611657

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

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

профессор

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

Защита дисертации состоится 29 октября 2010 г. в 11:00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ имени М. В. Ломоносова http://www.cmc.msu.ru в разделе „Наука" — „Работа диссертационных советов" — „Д 501.001.44".

Автореферат разослан сентября 2010 г.

Ученый секретарь диссертационного совета

профессор Н. П. Трифонов

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

кандидат физико-математических наук, доцент Московского энергетического института (технического университета) Мещанинов Дмитрий Германович.

Ведущая организация: Вычислительный центр

им. А. А. Дородницына РАН.

Общая характеристика работы

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

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

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

Уже сейчас многозначная логика с успехом применяется при решении многих задач и во множестве технических разработок. Среди них flash-память, различные арифметические устройства, системы искусственного интеллекта и обработки данных, обработка сложных цифровых сигналов и т. д.

Одной из основных задач в многозначной логике является проблема выразимости функций: заданную fc-значную функцию или класс функций требуется выразить, используя суперпозицию функций некоторого имеющегося множества. Указанную задачу, несколько уменьшив общность постановки, можно переформулировать в задачу описания решетки замкнутых относительно операции суперпозиции классов функций fc-значной логики.

Следуя авторам, будем обозначать через Рj. множество всех fc-значных функций.

Задача описания всех замкнутых классов функций двухзначной логики была решена Э. Постом1,2. Было показано, что в Рг счетное число замкнутых классов, каждый из которых имеет конечный базис. Существует в точности

1 Post Е. L. Introduction to a gênerai theory of elementary propositions. Amer. J. Math. 1921. Volume 43, № 4. P. 163-165.

2 Post E. L. Two valued iterative système of mathematical logic. Annals of Math. Studies, Princeton Univ. Press, 1951. V. 5.

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

Ю. И. Яновым, А. А. Мучником было показано?, что в Р* при к > 3 существуют замкнутые классы со счетным базисом, а также замкнутые классы, не имеющие базиса. Следствием этого результата является континуальная мощность множества замкнутых классов fc-значных функций при к ^ 3. Оказалось, что описать решетку классов в Рк для к ^ 3, как это было сделано Э. Постом для Рг, невозможно. В связи с этим важной проблемой является описание именно фрагментов решетки замкнутых классов fc-значных функций.

И. Розенберг изучил4 все предполные классы в решетке замкнутых классов fc-значных функций. Указанные классы были описаны через сохраняемые отношения в виде шести семейств, два из которых, обозначаемые через M и S, являются соответственно подмножествами всех монотонных и самодвойственных классов в Рк.

B. В. Мартынюком установлено5, что класс монотонных функций, сохраняющих частичный порядок г, принадлежит семейству M (то есть является предполным) тогда и только тогда, когда г имеет в точности единственный минимальный и единственный максимальный элементы.

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

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

Цель диссертационной работы. Основной целью диссертации является изучение надрешеток классов монотонных функций и классов самодвойственных функций в Рк при к ^ 3.

Научная новизна. Все результаты диссертации являются новыми. Исследованы новые фрагменты решетки замкнутых классов в Рк-

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

* Rosenberg I. G. La structure des fonctions de plusiers variables sur un ensemble fini. Comptes Rendus Acad. Sci. Paris. 1965. Volume 260. P. 3817-3819.

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

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

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

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

Публикации и апробирование. По теме диссертации опубликовано 9 работ. Результаты диссертации докладывались на следующих конференциях: XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2—7 июня 2008 г.), XVII Международной школе-семинаре «Синтез и сложность управляющих систем» имени академика О. Б. Лу-панова (Новосибирск, 27 октября—1 ноября 2008 г.), VIII Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 6—9 апреля 2009 г.), VII молодежной научной школе по дискретной математике и ее приложениям (Москва, 18—23 мая 2009 г.), XVIII Международной школе-семинаре «Синтез и сложность управляющих систем» имени академика О.Б.Лупанова (Пенза, 28 сентября—3 октября 2009 г.), X Международном научном семинаре «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.).

Также результаты диссертации обсуждались на спецсеминаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики факультета ВМК МГУ.

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

Краткое содержание диссертации

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

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

В разделе 1.1 приводятся основные определения.

Обозначим Ек = {0,1,..., к — 1}.

Определение 1. Функция... ,х„) называется функцией к-значной

логики (k ^ 2), если она определена на Щ и все ее значения принадлежат Ек.

Множество всех функций fc-значной логики обозначим Рк- Для любого подмножества А из Ль через [А] будем обозначать замыкание относительно операции суперпозиции.

Пусть на Eh задано некоторое отношение частичного порядка г. Возьмем два произвольных набора а = (oi,..., о„) и b = (bi,..., bn) из Е£. Будем говорить, что а не превосходит Ь относительно частичного порядка г и записывать а Ь, если для любого 1 ^ г ^ п справедливо неравенство щ <r £>;.

Определение 2. Функция f(xi,... ,хп) называется монотонной относительно частичного порядка г, если для любых двух наборов a,b S таких, что а 6, выполнено /(о) <r f(b). Множество всех функций из Рк, монотонных относительно г, называется классом монотонных функций МТ.

Для краткости будем задавать частичный порядок г частично упорядоченным множеством (ЧУМ) Я из элементов Ек, а соответствующий монотонный класс обозначать М#.

Определение 3. Пусть р(хi,..., xm) - произвольный предикат, определенный на множестве Е™, f(yi,... ,уп) - некоторая функция из Рк. Говорят, что функция f(yi,..., уп) сохраняет предикат р(х i,..., хт), если для любых п наборов а; = (an,..., а*т) (г € {1,...,п}), удовлетворяющих предикату р, набор /(flu,. • •, ani)i • • • j /(aim) • • •, <зпт) также удовлетворяет предикату р. По определению будем считать, что тождественно ложный предикат сохрг няет любая функция.

Будем обозначать через Ро1(р) множество функций, сохраняющих прс дикат р.

Класс М# является замкнутым классом функций, сохраняющих пред! кат R(x, у) — TRUE х у 7. Везде далее, когда будем писать, что монотонный класс задается предикатом R, будет подразумеваться именно описанный предикат R(x,y).

Определение 4. Замкнутый класс А называется предикатно-опиа емым, если существует предикат р, такой что справедливо представлени А = Pol р.

В дальнейшем нам понадобятся некоторые семейства предполных кла

сов.

Определение 5. Класс функций В принадлежит семейству С, если В -

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

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

1. Абсолютная симметричность. Для любой подстановки а на множестве {1,...,п} и любого набора a £ Щ справедливо р(а1,...,ап) = TRUE р(аа{1),..., аа{п)) = TRUE.

2. Абсолютная рефлексивность. Предикат р истинен на любом наборе а, таком что найдутся различные номера 1 ^ г, j ^ т (т — местность р), удовлетворяющие а, = aj (в а присутствуют хотя бы две равные компоненты).

3. Существует центр предиката р, то есть существует элемент h £ Ek такой, что для любого набора а £ у которого есть компонента, равная h, справедливо р(а) = TRUE.

Определим следующий предикат:

Ртах{хи Xi) = ЭУ (Л(жЬ y)&R{x2, у)) ,

где R — предикат, задающий класс монотонных функций.

Определение 6. Конечное ЧУМ Я будем называть связным множеством, если для любых двух элементов а, b £ Я существует последовательность ui,...,un из элементов Я такая, что и\ = а, ип = Ь, для любого г £ {1,..., п — 1} справедливо щ ^ щ+1 или щ ^ щ+\. В ином случае ЧУМ Я называется несвязным. Любое ЧУМ, являющееся связным максимальным подмножеством Я с сохранением отношения частичного порядка Я, назовем компонентой связности множества Я.

В разделе 1.1 также приводятся основные сведения о соответствии Галуа между решетками замкнутых классов функций и замкнутых классов предикатов. Доказываются вспомогательные утверждения, описывающие свойства формул над {Д}, где R — предикат, задающий класс монотонных функций, а также некоторые используемые в дальнейшем свойства произвольных замкнутых классов функций и задающих их предикатов.

В разделе 1.2 вводится специальное семейство ЧУМ.

Определение 7. Пусть L — произвольное ЧУМ, v, vx,... ,vs — некоторые его элементы. Элемент и будем называть максимумом элементов vi,...,vs тогда и только тогда, когда для любого i £ {1,..., s} выполняется соотношение V ^ V{.

Определение 8. Определим L\ как множество, состоящее из всех ЧУМ Я, которые содержат подмножество Я из четырех элементов, изображенное

на рисунке 1. Причем в Я не появляются пути из 0 в 3 по вершинам, являющимся максимумами 1 и 2. Уточним это понятие: не существует последовательности элементов ... в Ь\ такой, что г>1 = 0, ит = 3, сравнимо с г/,-+1 (г € {1,..., т — 1}) (то есть либо и,- < иг+1, либо г/<+1 < все V,- -максимумы 1 и 2.

Пусть ¿2 ~ множество всех ЧУМ, полученных из ЧУМ, принадлежащих множеству Ь\, инвертированием, пусть Ь =

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

Теорема 1. В решетке замкнутых классов над классом монотонных функций, сохраняющих любое ЧУМ из определенного выше множества Ь, находится бесконечная цепочка вложенных друг в друга различных замкнутых классов.

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

Теорема 2. Любой класс монотонных функций в Рк, где к ^ 4, построенный на ЧУМ с одним минимальным элементом и не являющийся предпол-ным, строго содержится только в классе Ро1ртах, принадлежащем семейству С, и во всем Рк-

Теорема 3. Минимальной логикой с монотонным классом с бесконечной надструктурой является Р4.

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

h

Определение 9. Пусть Ек — tj Щ — разбиение D множества Ек на

4=1

непересекающиеся подмножества. Элементы а,Ъ € Ек называются эквивалентными относительно указанного разбиения (обозначение а 6), если они принадлежат одной его компоненте Я;. Наборы а,Ь 6 Е% называются эквивалентными относительно разбиения Д если для любого i € {1,..., п} справедливо щ 6;. Функция f(xi,...,x„) сохраняет разбиение D, если для любых а b выполнено /(а) /(&).

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

Обозначим через Щщу класс семейства U, все функции которого сохра-h

няют разбиение Ек = IJ Щ.

¿=1

Известно8, что для разбиения D = {Я;}-!=1 множества Ек справедливо представление Щщ = Po\Rd(xi,X2), где Яд^ьЖг) ~ двухместный предикат, определяемый следующим образом: Rjy(a,b) — TRUE тогда и только тогда, когда а Ь.

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

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

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

Теорема 4. Справедливо включение Мн С Ан, и любой класс В, строго содержащий класс монотонных функций Мц, содержит класс Ан-

Если ЧУМ Я обладает единственным минимальным элементом, то удается получить следующие важные свойства надрешетки классов монотонных функций.

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

Теорема 5. Пусть Ми — Pol R — класс монотонных функций, сохраняющих ЧУМ Я с единственным минимальным элементом. Тогда справедливы следующие утверждения:

1. Для любого преджатно-описуемого класса А такого, что Мн С А, число замкнутых классов, содержащих класс А, конечно.

В. Класс Ац (см- предыдущую теорему) предикатно-описуем тогда и только тогда, когда надрешетка класса Мн конечна.

3. Класс монотонных функций Мц содержится в предполном классе Сн семейства С, представимом в виде Polртах> других предполных классов, содержащих класс Мц, нет.

В разделе 2.3 рассматривается случай несвязного ЧУМ Я (см. определение 6). Пусть Hi,... ,Hh — все компоненты связности Я, |Я,| = /¿. Строятся классы монотонных функций Мщ в Pit, порожденные ЧУМ Щ.

Теорема 6. Если ЧУМ Н несвязно, Hi — все компоненты связности Н (i G {1,..., К]), то класс монотонных функций Мц содержится в предполном классе Щн{}! состоящем из функций, сохраняющих разбиение {Я*} множества Ек, другие предполные классы не содержат Мц.

Теорема 7. Пусть предикат R задает класс монотонных функций, сохраняющих ЧУМ Я. Все компоненты связности Я суть Н\,..., Нн, |Я<| = k-Тогда:

1. Если для некоторого т класс монотонных функций Мцт в Pim имеет бесконечную наструктуру, то Мн в Pk также имеет бесконечную надструктуру.

2. Если каждое ЧУМ Иг, ...,Ни имеет единственный минимальный или максимальный элемент, то класс Мц имеет бесконечную надструктуру тогда и только тогда, когда хотя бы один из классов Мщ,..., Мц имеет бесконечную надструктуру.

3. Если каждое ЧУМ Ни ■ ■■ ,Hh имеет единственный минимальный и максимальный элемент, то класс Мд строго содержится только в классах 11ц. и Р^.

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

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

Определение 10. Через Ь^ будем обозначать множество ЧУМ, имеющих г максимальных элементов и ] минимальных.

Рассмотрим произвольное ЧУМ Я из элементов множества Ек, принадлежащее множеству £5д. Пусть Лх,..., — все максимальные элементы множества Я.

Пусть Щ — некоторое непустое подмножество множества У/ ~ {1,..., 5}. Обозначим через Нщ ЧУМ, состоящее из элементов й € Я таких, что в. < для любого .7 6 ЭД й <2 если ] $ И^. Для любых двух элементов

¿1, ¿2 £ выполнено Ь\ ^ Ь2 тогда и только тогда, когда ^ в Я.

Определение 11. Множество Я е назовем простым, если выполнены следующие условия:

1. Для любого непустого подмножества множества IV множество Нщ непусто.

2. Каждое множество Нщ имеет единственный максимальный элемент Мщ.

3. Если С то Мщ > Мцл для любых подмножеств множества ЧУ.

Теорема 8. Любой класс монотонных функций, сохраняющих простое ЧУМ, имеет конечную надструктуру.

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

Определение 12. Для произвольного к обозначим через С}\ множество ЧУМ Я € ¿21, составленных из элементов Ек таких, что ЧУМ Я содержит подмножество Я из четырех элементов (с точностью до пометок элементов), изображенное на рисунке 1, причем во множестве Я пары элементов 0,3 и 1,2 остаются несравнимыми, не появляется элемента а такого, что а ^ О, а<3иа>1, и элементы 0,3 являются максимальными в Я.

Теорема 9. Для того, чтобы в Рк класс монотонных функций Мн, где Н £ ¿2,ь обладал бесконечной надструктурой, необходимо и достаточно, чтобы ЧУМ Я принадлежал семейству Q\. В случае конечной надсгпрук-туры класс Мн содержится только в классах Polртах Е С и Рк.

Определение 13. Для произвольного к обозначим через Q\ множество ЧУМ Я 6 Z/22, составленных из элементов таких, что ЧУМ Я содержит подмножество Я из четырех элементов (с точностью до пометок элементов), изображенное на рисунке 1, причем во множестве Я не появляется элемента а такого, что а^О, а > 2; элементы 0,3 являются максималь-

ными в Н или элементы 1,2 — минимальными.

Теорема 10. Для того, чтобы в Рк класс монотонных функций Мн, где Я £ Lii, обладал бесконечной надструктурой необходимо и достаточно, чтобы ЧУМ Я принадлежало семейству Q\.

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

Теорема 11. Для любого числа п > 0 существует k-значная логика Рк с монотонным классом Мн таким, что число различных классов В, удовлетворяющих Мн С В С Рк, конечно, но превосходит число п.

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

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

Определение 14. Функция fc-значной логики f(xi,..., хп) называется самодвойственной относительно подстановки а, если выполнено следующее тождество: f(x\,...,хп) = <j~l{f{cr(xi),... ,а(хп))), где через а-1 мы обозначаем подстановку, обратную к а. Известно 9, что множество всех функций из Рк, самодвойственных относительно а, является замкнутым классом. Обозначим этот класс через Sa. Справедливо Sa — Pol Ra, где предикат Ra истинен на всех парах вида (а, сг(а)).

Доказываются основные свойства классов самодвойственных функций j задающих их предикатов. Основным результатом является следующая теор< ма.

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

Теорема 12. Решетка классов Sai изоморфна решетке делителей числа ha относительно свойства делимости.

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

Определение 15. Обозначим через SCT множество классов Sai, где i — делитель числа h^, i ф 1, i ф ha.

Определение 16. Через будем обозначать подмножество множества Ек, состоящее из всех элементов Ек, образующих циклы подстановки сг, длины которых делят число d.

Определение 17. Пусть подстановка 7Г определена на подмножестве Md,a множества Ек таком, что ф 0, Md,a ф Ек, и равна <т на указанном множестве. Классом Hdx назовем множество функций А;-значной логики, сохраняющих следующий предикат: Rni(xi, хг) = TRUE тогда и только тогда, когда xi,X2 £ Mdt,г и Х2 = где г — произвольный делитель числа hn,

являющегося минимальным, удовлетворяющим irh" = е.

Определение 18. Через Тст будем обозначать множество классов #<fi7rt, где d — наименьшее общее кратное длин циклов подстановки <т, элементы которых образуют множество М^, 7Г — подстановка, определенная на множестве Mdl<r, где Md,a Ф 0 и Md,iт ф Ек, и совпадающая с подстановкой а на нем, t — произвольный делитель числа hT, являющегося минимальным, удовлетворяющим ith' = е.

В разделе 4.2 исследуется структура формул над {Ra}, где Ra — предикат, задающий класс самодвойственных функций. Основным результатом раздела является следующая теорема, описывающая все классы, содержащие классы самодвойственных функций.

Теорема 13. В решетке замкнутых классов k-значной логики над классом самодвойственных функций Sff находятся только классы семейств Sa, Та, их пересечения и Р^.

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

Определение 19. Рассмотрим множество Mjia для некоторого числа.;, являющегося наименьшим общим кратным длин некоторого подмножества циклов подстановки а, причем ф 0. Пусть 7Г — подстановка, определенная на множестве Mj)Cr и совпадающая с а на указанном множестве (в случае Mjp — Ек справедливо 7Г = а). Пусть i — делитель числа h„, являющийся

минимальным, удовлетворяющим соотношению кн* = е на множестве М^, где е — тождественная подстановка. В случае, если М^ = обозначим через класс в противном случае (то есть, если С Е^) обозначим через Зу класс Н^у.

Теорема 14. 5г-ьг1 С тогда и только тогда, когда выполнены следующие условия:

1. М^ С М1иа.

2. НОД(гь/2)|г2.

3. Для любого цикла С' длины V подстановки а на множестве М^ДМ^ число V не делит НОЩгх, /г).

Основные результаты диссертации

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

2. Найдена минимальная логика, содержащая класс монотонных функций с бесконечной надструктурой, а также минимальная логика, содержащая класс монотонных функций с бесконечной надструктурой, порожденный ЧУМ, обладающим единственным минимальным элементом.

3. Доказано, что в случае, когда класс монотонных функций М порожден ЧУМ, обладающим единственным минимальным элементом, над-структура любого предикатно-описуемого класса А такого, что М С А, конечна.

4. Описаны основные свойства надрешетки классов монотонных функций (верхняя окрестность, предполные классы).

5. Описана связь надструктуры класса монотонных функций, сохраняй: щих несвязное ЧУМ, с надструктурой классов монотонных функций, сохраняющих компоненты связности ЧУМ.

6. Найдено необходимое и достаточное условие для наличия бесконечно] надструктуры у класса монотонных функций, сохраняющих ЧУМ с н более чем двумя максимальными и двумя минимальными элементами.

7. Показана неограниченность конечной надструктуры у классов монотонных функций.

8. Полностью описана над структура классов самодвойственных функций.

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

1. Ларионов В. Б. О некоторых свойствах монотонных функций в многозначных логиках // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2—7 июня 2008 г.), издательство «Отечество», Казань, 2008. С. 71-72.

2. Ларионов В. Б. О положении некоторых классов монотонных к-зпач-ных функций в решетке замкнутых классов // Материалы XVII Международной школы-семинара «Синтез и слжность управляющих систем» имени академика О. Б. Лупанова (Новосибирск, 27 октября—1 ноября 2008 г.), Издательство Института математики, Новосибирск, 2008. С. 90-95.

3. Ларионов В. Б. О положении некоторых классов монотонных к-знач-ных функций в решетке замкнутых классов // Дискретная математика. 2009. Т. 21, № 5. С. 111-116.

4. Ларионов В. Б. О надструктуре классов самодвойственных функций в многозначных логиках // Труды VIII Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 6—9 апреля 2009 г.), издательский отдел факультета ВМК МГУ, Москва, 2009. С. 197-201.

5. Ларионов В. Б. О монотонных замкнутых классах функций многозначной логики с бесконечной надструктурой // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (18-23 мая 2009 г.), М.: ИПМ им. М. В. Келдыша РАН, 2009. С. 7-12.

6. Ларионов В. Б. О положении самодвойственных к-значных функций в решетке замкнутых классов // Сборник статей молодых ученых факультета ВМК МГУ, вып. 6, издательский отдел факультета ВМК МГУ, Москва, 2009. С. 90-105.

7. Ларионов В. Б. О надструктуре некоторого семейства замкнутых классов монотонных к-значных функций // Материалы XVIII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (Пенза, 28 сентября—3 октября 2009 г.), изд-во механико-математического факультета МГУ, Москва, 2009. С. 56-61.

8. Ларионов В. Б. Критерий конечности надструктуры некоторых классов монотонных к-значных функций, сохраняющих частичный порядок с единственным минимальным элементом // Материалы X Международного научного семинара «Дискретная математика и ее приложения» (1—6 февраля 2010 г.), изд-во механико-математического факультета МГУ, Москва, 2010. С. 186-189.

9. Ларионов В. Б. О надструктуре классов монотонных функций в многозначных логиках // Сборник статей молодых ученых факультета ВМК МГУ, вып. 7, издательский отдел факультета ВМК МГУ, Москва, 2010. С. 42-59.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 07.09,2010 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 80 экз. Заказ 383. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение.

Глава 1. Монотонные классы с бесконечной надструктурой

1.1. Основные понятия.

1.2. Семейство классов монотонных функций с бесконечной надструктурой

1.3. Минимальные логики, содержащие классы монотонных функций с бесконечной надструктурой.

Глава 2. Свойства надрешетки классов монотонных функций

2.1. Невырожденные предикаты

2.2. Общие свойства надрешеток классов монотонных функций

2.3. Надструктура классов монотонных функций, сохраняющих несвязное ЧУМ

Глава 3. Необходимые и достаточные условия для бесконечной надструктуры класса монотонных функций.

3.1. Достаточные условия для конечной надструктуры класса монотонных функций

3.2. Необходимые и достаточные условия для наличия бесконечной надструктуры у некоторых семейств классов монотонных функций.

3.3. Неограниченность конечной надструктуры классов монотонных функций.

Глава 4. Надструктура замкнутых классов самодвойственных функций.

4.1. Семейства классов, содержащих замкнутый класс самодвойственных функций.

4.2. Надструктура классов самодвойственных функций.

4.3. Структура решетки замкнутых классов над Sa

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

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

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

Уже сейчас многозначная логика с успехом применяется при решении многих задач и во множестве технических разработок. Среди них flash-память, различные арифметические устройства, системы искусственного интеллекта и обработки данных, обработка сложных цифровых сигналов и т. Д

Одной из основных задач в многозначной логике является проблема выразимости функций: заданную к-значную функцию или класс функций требуется выразить, используя суперпозицию функций некоторого имеющегося множества. Указанную задачу, несколько уменьшив общность постановки, можно переформулировать в задачу описания решетки замкнутых относительно операции суперпозиции классов функций fc-значной логики.

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

Следуя авторам, будем обозначать через Pk множество всех &-значных функций.

Задача описания всех замкнутых классов функций двухзначной логики была решена Э. Постом [75, 76]. Было показано, что в Pi счетное число замкнутых классов, каждый из которых имеет конечный базис. Существует в точности пять предполных классов, образующих критериальную систему для разрешения проблемы полноты. В более простой форме результаты Поста появились позднее в СССР и Франции [62, 66, 67, 70]. В дальнейшем рядом авторов были предложены различные подходы к изучению замкнутых классов булевых функций, а также несколько вариантов доказательств результатов Поста (в хронологическом порядке: С. В. Яблонский — [60, 61]; С. С. Марчен-ков — [25]; Г. П. Гаврилов — [5, 6]; А. Б. Угольников — [53]; С. С. Марченков и А. Б. Угольников — [36]). Отметим результаты А. И. Мальцева [22, 23], предложившего алгебраический подход. В рамках этого подхода рассматривается так называемая алгебра — множество функций &-значной логики, замкнутое относительно некоторого набора операций (через эти операции выражается операция суперпозиции).

В [57] С. В. Яблонским были описаны все 18 предполных классов в Им же в [58] описываются некоторые предполные классы в и их свойства для произвольных к (также см. [8]). И. Розенбергом в [77] были окончательно описаны все предполные классы fc-значной логики. Было показано, что они образуют шесть семейств. Сами классы описываются через множества сохраняемых предикатов. Детальное описание и свойства указанных семейств и соответствующих предикатов можно найти в работе [63].

В [9] была установлена асимптотика числа предполных классов в Рк-Оказалось, что это число растет очень быстро с ростом к, поэтому критериальная система из предполных классов для разрешения проблемы полноты является неэффективной. Но самые большие трудности в изучении решетки замкнутых классов к-значных функций показал результат Ю. И. Яно-ва, А. А. Мучника [64], где было доказано, что в Рк существуют замкнутые классы со счетным базисом, а также замкнутые классы, не имеющие базиса. Следствием этого результата является континуальная мощность множества замкнутых классов fc-значных функций при к ^ 3. Оказалось, что описать решетку классов в Рк для к ^ 3, как это было сделано для невозможно.

Отношение сохранения предиката функцией было определено А. В. Кузнецовым в [10]. В работе [11] он указывал на возможность построения теории Галуа для решетки замкнутых классов булевых функций. Само построение для решетки замкнутых классов &-значных функций было проведено независимо В. Г. Боднарчуком, JI. А. Калужниным, В. Н. Котовым, Б. А. Ромовым в [2] и Д. Гейгером в [69]. Был установлен антиизоморфизм между частично упорядоченным множеством замкнутых классов fc-значных функций, содержащих все селекторные функции и частично упорядоченным множеством замкнутых относительно некоторых операций классов предикатов, содержащих все диагонали. Этот результат позволил изучать решетку замкнутых классов функций новым методом. Сначала устанавливаются требуемые свойства для решетки замкнутых классов предикатов, а потом, используя антиизоморфизм, указанные свойства переносятся на решетку замкнутых классов функций. Отметим в этой области работу С. С. Марченкова [26], в которой доказана минимальность предикатов, задающих предполные классы в Рк, к ^ 2. С. В. Яблонским в работе [59] рассмотрена связь предикатной опису-емости замкнутого класса функций со строением его верхней окрестности в решетке замкнутых классов.

В связи с указанными выше трудностями работы по изучению решетки замкнутых классов в Р& для к ^ 3 разделились на два направления. Первое из них - разработка более сильных операторов замыкания, которые позволяли бы сжимать решетку замкнутых классов до счетного или конечного множества, которое уже возможно описать и исследовать. Второе направление -изучение различных подмножеств решетки замкнутых классов в Pk

В первом направлении отметим работу А. В. Кузнецова [12], в которой вводится понятие параметрического замыкания и доказывается, что существует 25 параметрически замкнутых классов булевых функций. С. С. Марченковым в работе [29] изучается параметрическое и lL-замыкание.

5-замыкание, при котором в каждом замкнутом классе наряду с функцией есть двойственные ей функции, исследуется в работах [27, 40, 41]. В [31] С. С. Марченковым описаны все ^-замкнутые классы трехзначных функций. В работах [33, 34] определяется эквациональное замыкание и доказывается, что в Pk существует конечное число эквационально замкнутых классов. Ряд работ посвящен описанию операторов замыкания с дополнительными операциями программного типа. К таким работам относятся [49, 50], где вводится операция разветвления по предикату и описываются все замкнутые с использованием указанной операции классы в Pk (их конечное число). Другие операторы замыкания описаны в работах [7, 39, 51, 52]. Большая часть этих операторов позволяет сжать решетку замкнутых классов к-значных функций до конечного множества.

Данная диссертация принадлежит ко второму направлению по изучению решетки замкнутых классов fc-значных функций при к ^ 3. В работе И. Ро-зенбергом [77] изучены все предполные классы в решетке замкнутых классов

6-значных функций (то есть первый уровень указанной решетки), в его же работе [79] изучается второй уровень решетки в Pk- В случае к = 3 в работе [71] второй уровень решетки описан полностью.

Минимальные клоны (то есть замкнутые классы, содержащие все селекторные функции) в Рк описаны в работе [78], там же доказано, что при фиксированном к их конечное число.

Надструктура классов самодвойственных функций в Р3 изучалась в работе [35]. В [80] исследована надструктура классов линейных функций в случае, когда число к свободно от квадратов. Г. А. Бурле в работе [4] описал все замкнутые классы в Р&, содержащие все функции одной переменной.

Ряд работ посвящен изучению надструктуры класса полиномов. В [58] было показано, что для простого к любая fc-значная функция может быть представлена полиномом по модулю к, то есть класс полиномов при указанном к совпадает со всем Pk. Там же было доказано, что при составном к класс полиномов не является даже предполным. А. А. Нечаевым в работе [42] описаны все предполные классы, содержащие класс полиномов.

А. Н. Череповым в работах [55, 56] и Д. Г. Мещаниновым в [37] была полностью описана надструктура класса полиномов при составном к, свободном от квадратов, а также при к = р\р2, где Pi, Р2 ~ простые числа. В [38] Д. Г. Мещаниновым были установлены необходимые и достаточные условия представимости А;-значных функции полиномом по модулю к, приведен алгоритм построения полинома по функции. А. Б. Ремизов в [43] показал, что при к = р\р2, где р\, Р2 — простые числа, существует бесконечная цепочка содержащих друг друга различных замкнутых классов, каждый из которых содержит класс полиномов. Данный результат свидетельствует о сложности надструктуры класса полиномов в общем случае.

В [28] С. С. Марченковым были описаны все классы в Pk, содержащие дуальный дискриминатор, то есть функцию: х: если х — у] z, если х фу.

Отметим, что конечность множества подобных классов следует из работы [65]. В [32] описаны все 144 замкнутых класса функций в Рз, содержащие тернарный дискриминатор.

В работах [68, 72, 73] рассматриваются подклассы класса Р^ = {/ Е Рк-> f(x) £ {0,1,., £ — 1} для любого 5}. Для каждой функции из Pk,i определяется проекция — функция из Pi, получающаяся сужением области определения до ЕИзучается вопрос о мощности множества 1(A) классов такого, что 1(A) С Рк 2 и проекция любого класса из 1(A) равна А.

К смежному направлению относится исследование решетки замкнутых классов частичных функций (Р£). В работе [54] Р. Фрейвальдом была решена проблема полноты для случая к = 2, а Б. А. Ромовым в [48] — для к ^ 3. В работе [3] исследовалась надрешетка в Р2* предполных классов из Р2. Подробный обзор изучения решетки замкнутых классов частичных &-значных функций можно найти в [74].

Еще одним близким направлением является исследование решетки вектор-функций. В. А. Тайманов в [50] описал все замкнутые классы вектор функций двухзначной логики (Р$)- Б. А. Ромов в работах [44-47] получил альтернативное описание указанных классов, перенес результаты теории Галуа на прямые произведения алгебр Поста, описал все минимальные fc-основые предикаты.

Целью данной диссертации является изучение надструктуры замкнутых классов монотонных и самодвойственных функций в Р& при произвольном к^Ъ. Среди шести семейств предполных классов в Pj~ при к ^ 3, установленных в [77], существует два, обозначаемые через М и S и являющиеся соответственно подмножествами всех монотонных и самодвойственных классов в Рк

В работе [24] В. В. Мартынюком установлено, что класс монотонных функций, сохраняющих частичный порядок г, принадлежит семейству М (то есть является предполным) тогда и только тогда, когда г имеет в точности единственный минимальный и единственный максимальный элементы.

В [58] С. В. Яблонским доказано, что класс функций, самодвойственных относительно некоторой подстановки сг, принадлежит семейству S тогда и только тогда, когда подстановка а разлагается в произведение циклов одинаковой длины, являющейся простым числом.

Возникает вопрос: какое положение в решетке замкнутых классов занимают классы монотонных и самодвойственных функций, не являющиеся предполными. Отметим, что из работ [28, 65] следует конечность надструк-туры произвольного класса самодвойственных функций.

В диссертации ставятся следующие задачи:

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

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

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

4. Описать основные свойства надрешетки классов монотонных функций.

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

Структура и объем диссертации. Объем диссертации 158 страниц. Работа состоит из введения, четырех глав и списка литературы. Во введении

1. Арнольд И. В. Теоретическая арифметика. Учпедгиз, Москва, 1938.

2. Бондарчук В. Г., Калужнин В. А., Котов В. Н., Ромов Б. А. Теория Талу а для алгебр Поста // Кибернетика. 1969. № 3. С. 1-10. № 5. С. 1-9.

3. Алексеев В. Б., Вороненко А. А. О некоторых замкнутых классах в частичной двухзначной логике // Дискретная математика. 1994. Т. 6, № 4. С. 58-79.

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

5. Гаврилов Г. П. Индуктивное представление булевых функций и конечная порождаемость классов Поста // Алгебра и логика. 1984. Т. 23, № 1. С. 3-26.

6. Гаврилов Г. П. Функциональные системы дискретной математики. М.: Изд-во МГУ, 1985.

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

8. Захарова Е. Ю. Критерий полноты системы функций из // Проблемы кибернетики. 1967. № 18. С. 5-10.

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

10. Кузнецов А. В. Алгебра логики и ее обобщения // Яновская С. А. Математическая логика и основания математики. Математика в СССР за сорок лет, Физматгиз, 1959. Т. 1. С. 13-120.

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

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

13. Ларионов В. Б. О некоторых свойствах монотонных функций в многозначных логиках // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2—7 июня 2008 г.), издательство «Отечество», Казань, 2008. С. 71-72.

14. Ларионов В. Б. О полооюении некоторых классов монотонных к-знач-ных функций в решетке замкнутых классов // Дискретная математика. 2009. Т. 21, № 5. С. 111-116.

15. Ларионов В. Б. О монотонных замкнутых классах функций многозначной логики с бесконечной надструктурой // Материалы VII молодежной научной школы по дискретной математике и ее приложениям (18-23 мая 2009 г.), М.: ИПМ им. М. В. Келдыша РАН, 2009. С. 7-12.

16. Ларионов В. Б. О положении самодвойственных k-значных функций в решетке замкнутых классов // Сборник статей молодых ученых факультета ВМК МГУ, вып. 6, издательский отдел факультета ВМК МГУ, Москва, 2009. С. 90-105.

17. Ларионов В. Б. О надструктуре классов монотонных функций в многозначных логиках // Сборник статей молодых ученых факультета ВМК МГУ, вып. 7, издательский отдел факультета ВМК МГУ, Москва, 2009.

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

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

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

21. Марченков С. С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика. 1984. Т. 23, № 1. С. 88-99.

22. Марченков С. С. Предполнота замкнутых классов в Рпредикатный подход // Математические вопросы кибернетики, вып. 6. М.: Наука, 1996. С. 117-132.

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

24. Марченков С. С. Клоповая классификация дуально дискриминаторных алгебр с конечным носителем // Математические заметки. 1997. Т. 61, вып. 3. С. 359-366.

25. Марченков С. С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискретная математика. 1999. Т. 11, № 4. С. 110-126.

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

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

28. Марченков С. С. Дискриминаторные классы трехзначной логики // Математические вопросы кибернетики. 2003. Вып. 12. С. 12-26.

29. Марченков С. С. Эквационалъное замыкание // Дискретная математика. 2005. Т. 17, № 2. С. 117-126.

30. Марченков С. С. О строении эквационалъно замкнутых классов // Дискретная математика. 2006. Т. 18, №- 4. С. 18-30.

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

32. Марченков С. С., Угольников А. Б. Замкнутые классы булевых функций. М.: Изд-во ИПМ АН СССР, 1990.

33. Мещанинов Д. Г. О надструктуре класса полиномов в Р^ // Тезисы докладов VII Всесоюзной конференции «Проблемы теоретической кибернетики» (18-20 сентября 1985). Ч. I, Иркутск, 1985, С. 135.

34. Мещанинов Д. Г. Метод построения полиномов для функций к-значной логики // Дискретная математика. 1995. Т. 7, № 3. С. 48-60.

35. Нгуен Ван Хоа Об L-эквивалентности систем функций в многозначной логике // Алгебра и логика. 1988. Т. 27, № 1. С. 37-47.

36. Нгуен Ван Хоа О структуре самодвойственных замкнутых классов трехзначной логики Р% // Дискретная математика. 1992. Т. 4, № 4. С. 82-95.

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

38. Нечаев А. А. Критерий полноты систем функций рп-значной логики, содержащий операции сложения и умножения по модулюрп // Методыдискретного анализа в решении комбинаторных задач, вып. 34. Новосибирск, 1980. С. 74-89.

39. Ремизов А. Б. О надструктуре замкнутого класса полиномов по модулю к // Дискретная математика. 1989. Т. 1, № 1. С. 3-15.

40. Ромов Б. А. Алгоритм решения проблемы полноты в классе векторных функциональных систем // Математические модели сложных систем, Киев: ИК АН УССР, 1973. С. 151-155.

41. Ромов Б. А. О решетке подалгебр прямых произведений алгебр Поста конечной степени j j Математические модели сложных систем, Киев: ИК АН УССР, 1973. С. 156-158.

42. Ромов Б. А. О полноте на квадрате функций алгебры логики и в системе Pkx Pi // Кибернетика. 1987. № 4. С. 9-14.

43. Ромов Б. А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика. 1989. № 3. С. 11-16.

44. Ромов Б. А. О проблеме полноты в алгебре частичных функций многозначной логики // Кибернетика. 1990. № 1. С. 102-106.

45. Соловьев В. Д. Замкнутые классы k-значной логики с операцией разветвления по предикату // Дискретная математика. 1990. Т. 2, № 4. С. 19-25.

46. Тайманов В. А. О функциональных системах k-значной логики с операциями программного типа // Доклады АН СССР. 1983. Т. 268, JV5 6. С. 1307-1310.

47. Тарасова О. С. Классы к-значной логики, замкнутые относительно расширенной операции суперпозиции // Вестник МГУ. Серия 1. Математика. Механика. 2001. № 6. С. 54-57.

48. Тарасова О. С. Классы функций трехзначной логики, замкнутый относительно операции суперпозиции и перестановки // Вестник МГУ. Серия 1. Математика. Механика. 2004. № 1. С. 25-29.

49. Угольников А. Б. О замкнутых классах Поста // Известия вузов. Математика. 1988. № 7. С. 79-88.

50. Фрейвальд Р. Критерии полноты для частичных функций алгебры логики и многозначных логик // Доклады АН СССР. 1966. Т. 167, № 6. С. 1249-1250.

51. Черепов А. Н. Описание структуры замкнутых классов в Pk, содержащих класс полиномов // Проблемы кибернетики, вып. 40. М.: Наука, 1983. С. 5-18.

52. Черепов А. Н. Надструктура класса сохранения отношений сравнения в многозначной логике // Тезисы докладов XII Всесоюзной конференции «Проблемы теоретической кибернетики» (18-20 сентября 1985). Ч. I, Иркутск, 1985. С. 135.

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

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

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

56. Яблонский С. В. О некоторых результатах в теории функциональных систем // Труды Международного конгресса математиков, Хельсинки, 1978. С. 963-971.

57. Яблонский С. В. О замкнутых классах в Р2 / / Проблемы кибернетики, вып. 39. М.: Наука, 1982. С. 262.

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

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

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

61. Baker К. A., Pixley A. F. Polynomial interpolation and the Chinese remainder theorem for algebraic systems // Math. Z. 1975. Volume 143. P. 165-174.

62. Benzaken C. Definitions et proprieties de certains families de fonctions booleennes croissantes // C. R. Acad. Sci. Paris. 1964. T. 259, group I. P. 1369-1371.

63. Benzaken C. Les families de fonctions booleennes deduites de certaines families de fonctions booleennes croissantes. Criteres de determination de I'indice d'une function croissante // C. R. Acad. Sci. Paris. 1965. T. 260, group I. P. 1528-1531.

64. Burosch G., Dassow J., Harnau W., Lau D. On subalgebras of an algebra of predicates // J. Inf. Process Cybern. 1985. EIK 21, 1/2. P. 9-22.

65. Geiger D. Closed systems of functions and predicates // Pacific J. Math. 1968. Volume 27. P. 95-100.

66. Kuntzman J. Algebre de Boole. Paris Dunod, 1965.

67. Lau D. Submaximale Klassen von P% / / J. Inf. Process. Cybern. 1982. EIK 18, 4/5. P. 227-243.

68. Lau D. Uber abgeschlossene Mengen linearer Funktionen in mehrwertigen Logiken // J. Inf. Process. Cybern. 1988. EIK 24, 7/8. P. 367-381.

69. Lau D. Uber abgeschlossene Teilmengen von Pkj2 // J- Inf. Process. Cybern. 1988. EIK 24, 10. P. 495-513.

70. Lau D. Function algebras on finite sets. Springer Monographs in Mathematics, 2006.

71. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. Volume 43, № 4. P. 163-165.

72. Post E. L. Two valued iterative systems of mathematical logic // Annals of Math. Studies, Princeton Univ. Press, 1951. V. 5.

73. Rosenberg I. G. La structure des fonctions de plusiers variables sur un ensemble fini // Comptes Rendus Acad. Sci. Paris. 1965. Volume 260. P. 3817-3819.

74. Rosenberg I. G. Minimal clones I: The five types // Lectures in Universal Algebra (L. Szabo, A. Szendrei eds.), Colloq. Math. Soc. J. Bolyai 43, North Holland, 1986. P. 405-427.

75. Rosenberg I. G. Completeness properties of multi-valued logic algebras // Computer science and multivalued logic: Theory and Applications, second edition, D.C. Rine, ed., Amsterdam: North-Holland, 1984. P. 144-186.

76. Szendrei A. On closed sets of linear operations over finite sets of square -free cardinality // Electron. Inform. Verarb. und Kibern. 1978. Volume 14,14. P. 547-559.