О классах функций k-значной логики, замкнутых относительно операций суперпозиции и перестановки

Тарасова, Ольга Сергеевна

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

Тарасова, Ольга Сергеевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «О классах функций k-значной логики, замкнутых относительно операций суперпозиции и перестановки»

Автореферат диссертации на тему "О классах функций k-значной логики, замкнутых относительно операций суперпозиции и перестановки"

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

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

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

Тарасова Ольга Сергеевна

О КЛАССАХ ФУНКЦИЙ Jfc-ЗНАЧНОЙ ЛОГИКИ, ЗАМКНУТЫХ ОТНОСИТЕЛЬНО ОПЕРАЦИЙ СУПЕРПОЗИЦИИ И ПЕРЕСТАНОВКИ

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

АВТОРЕФЕРАТ

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

Москва — 2004

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

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

Официальные оппоненты:

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

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

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

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

профессор В. А. Буевич;

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

профессор В. А. Стеценко.

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

Защита диссертации состоится 2004 г. в 16 ч.

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

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

Автореферат разослан

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

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

Актуальность темы

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

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

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

1 Post E. L. Two-valued iterative systems ofmathematical logic // Annals ofMath. Studies. Princeton Univ. Pryss. 1941. 5.

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

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

Идея операции в-замыкания, где наряду с операцией суперпозицией разрешается применять операцию перехода к двойственным функциям относительно фиксированной группы подстановок, т.е. в-замкнутый класс вместе с каждой функцией содержит двойственную относительно указанной группы подстановок функцию, высказывалась несколькими авторами. В настоящее время существуют две версии построения в-классификации множества функций &-значной логики (к ^ 3), представленные в работах С. С. Марченкова3 и Нгу-сн Ван Хоа4, где в частности установлено, что множество классов в данной классификации конечно, хотя и зависит от к сверхэкспоненциальным образом.

Понятия параметрической выразимости и параметрического замыкания введены А. В. Кузнецовым5. Им же получены критерий параметрической выразимости в А;-значной логике для всех к ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при к = 3

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

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

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

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

Нгуен Ван Хоа. О семействах замкнутых классов Ахзначной логики, сохраняемых всеми автоморфизмами // Дискретная математика. 1993. 5, Л*«4 87-108.

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

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

показана в работе А. Ф. Данильченко6, а при к > 3 в работе С. Бар-риса, Р. Уилларда7.

В работе Ю.В. Голункова8 изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа. В работах В.А Тайманова и В.Д. Соловьева исследуется семейство функциональных систем Аг-значной логики (к л 2) с операциями программного типа. Каждая операция программного типа определяется своим множеством предикатов. В работе В.А. Тайманова9 показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума. В случае конечного множества замкнутых классов приведено его полное описание, в случае счетного множества замкнутых классов показано, что каждый класс обладает конечным базисом, в случае континуального множества замкнутых классов представлены примеры классов со счетным базисом и классов без базиса, причем эти примеры совпадают с соотвествующими примерами Ю. И. Янова, А. А. Мучника. В работе В. Д. Соловьева10 рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.

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

• Данильченко А.Ф. О параметрической выразимости функций трехзначной логики // Алгебра и логика. 1977. 16, У»А. 397-416.

7 Barris S., WUlard R. Finitely many primitive- positive clones // Proc. of the American Mathematical Society. 1987. 101, Л*3. 427-430.

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

9 Тайманов В.А. О функциональных системах Ахзначной логики операциями программного типа // Докл. АН СССР. 1983. 268, Х*6.1307-1310.

10 Соловьев В.Д. Замкнутые классы в А;-значной логике с операцией разветвления по предикатам // Дискреная математика. 1990. 2, Л*4. 18-25.

кой подход рассматривался в работах Нгуена Ван Хоа11.

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

Цель работы

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

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

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

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

Результаты работы являются новыми. Основными являются следующие:

1) Показано, что в Рк при всех к множество классов, замкну-

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

Нгуен Ван Хоа. О О-полных замкнутых классах&-значнойлогики // Е1К. 1990. 26, ,Л5/6. 301-313

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

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

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

3) Для любого -регулярного множества угловых наборов показано, что в Рк при всех к ^ 3 множество классов, замкнутых относительно операции суперпозиции и ослабленной операции перестановки типа II, счетно, и любой такой класс представим в виде объединения четырех классов специального вида.

4) Доказано, что в множество классов, замкнутых относительно операции суперпозиции и ослабленной операции перестановки типа I с произвольным множеством угловых наборов, континуально при к 5, а множество классов, замкнутых относительно операции суперпозиции и ослабленной операции перестановки любого из двух типов с произвольным множеством угловых наборов, содержащемся в множестве {(0),(0,0),...} и {(к — 1), (к — 1, к — 1),...}, континуально при к ^ 3.

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

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

верситета им. М. В. Ломоносова, Института прикладной математики им. М.В. Келдыша РАН, Казанского государственного университета, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. М.В. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственного университета.

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

Результаты диссертации докладывались на V молодежной научной школе по дискретной математике и ее приложениям (Москва, 2001 г.), в МГУ им. М. В. Ломоносова на научно-исследовательском семинаре "Синтез управляющих систем" (2002 г.) и на спец. семинаре "Функции многозначной логики и смежные вопросы" (неоднократно), на XIV Международной школе-семинаре "Синтез и сложность управляющих систем" (Нижний Новгород, 2003 г.), на УШ Международном семинаре "Дискретная математика и ее приложения" (Москва, 2004 г.), в МГУ им. М. В. Ломоносова на научной конференции "Ломоносовские чтения" (2004г.).

Публикации

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

Объем и структура диссертации

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

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

Положим Ек = {0,1,..., к — 1}, Щ = Ек х ... х Ек, к > 2, п ^ 1. Набор (ах,...,а„) из называется угловым, если а,- Е {ОД — 1},

I = 1,..., п. Слой определяется двумя способами.

I. Наборы (¿1,..., 5„), (71,...,7„) принадлежат одному слою типа I относительно углового набора (аь..., а„) тогда и только тогда, когда наборы содержат

одинаковое число элементов, равных 0,1,..., к — 1.

П. Наборы (¿1, (л,..., 7„) принадлежат одному слою

типа II относительно углового набора (о^,...,ап) тогда и только тогда, когда суммы элементов наборов , (|71 - «1!» • • •»|Т» - <*п|) совпадают.

Заметим, что для произвольного углового набора а = (ац,..., а„) любой слой типа I относительно а содержится в некотором слое типа II относительно а, при этом каждый слой типа II относительно а представляется в виде объединения слоев типа I относительно а. Вначале дадим общее определение операции перестановки в независимости от конкретного определения слоя, пользуясь лишь тем свойством, что любое разбиение на слои является разбиением множества на непересекающиеся подмножества. Пусть у нас фиксированы функция /(XI,...,х„) из Р/с, угловой набор и разбиение множества на слои относительно этого углового набора. Тогда в результате действия на функцию операции перестановки с данным

угловым набором и разбиением на слои можно получить функцию из в том и только том случае, когда для каждого слоя q можно выбрать такое взаимно однозначное отображение ач наборов слоя qна себя, что функция <р{х 1,...,х„) будет совпадать с функцией на всех наборах этого слоя. Назовем операцией перестановки типа I и операцией перестановки типа II такие операции перестановки, для которых слой есть слой типа I и слой типа II соот-вествешю, причем в определении операции перестановки для случая операции перестановки типа I допускаются только такие взаимно однозначные отображения наборов слоя, в результате действия которых происходит перестановка компонент наборов этого слоя, а в опреде-

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

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

Дадим краткое описание содержания глав диссертации.

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

В главе 2 рассматривается операция перестановки типа I с множеством угловых наборов; О = {(0), (0,0),...}. В параграфах 2.1, 2.2 доказывается (Теорема 2.1.1), что любой класс в Рц, к ^ 2, замкнутый относительно операции суперпозиции и такой операции перестановки, порождается функциями от к переменных. Отсюда вытекает следствие (Следствие 2.1.2) о конечности множества всех таких классов. В теоремах 2.2.1, 2.2.2 приводится полное описание замкнутых классов в Рг и Рз. В параграфе 2.3 операцию перестановки разрешается применять только к функциям существенно зависящим от всех переменных, т.е. рассматривается ослабленная операция перестановки. Показывается, что в этом случае в П число замкнутых классов конечно (Теорема 2.3.1), а в Рк при к ^ 3 остается справедливым пример А. А. Мучника класса со счетным базисом, и, следовательно, множество замкнутых клаессов имеет мощность континуума (Теорема 2.3.2).

В главе 3 рассматривается операция перестановки типа I с произвольным множеством угловых наборов. При этом в параграфе 3.1 изучается ослабленная операция перестановки, а в параграфах 3.2, 3.3 операцию перестановки разрешается применять к произвольным

функциям 1с-значной логики.

В параграфе 3.1.1 исследуются классы трехзначной логики, замкнутые относительно операций суперпозиции и перестановки. Вначале доказывается, что существует множество П С Рз, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех его подмножеств, замкнутых относительно этих операций, счетно (Теорема 3.1.1). Затем вводится понятие правильного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {%,6„\п > 2}, где % £ {0,2}"\{0", 2"}, 6п £ {0П,2П} для всех п ^ 2. Устанавливается, что для любого правильного множества угловых наборов произвольный замкнутый класс представим в виде объединения двух классов: замыкания множества всех трехместных функций из Я и пересечения ПП21 (Теорема 3.1.2). Из теорем 3.1.1, 3.1.2 выводится основной результат параграфа 3.1.1 о счетности множества классов в P3, замкнутых относительно операций суперпозиции и перестановки с произвольным правильным множеством угловых наборов (Теорема 3.1.3). В параграфе 3.1.2 доказывается (Теорема 3.1.4), что для произвольных множеств угловых наборов классы к-значной логики, замкнутые относительно операций суперпозиции и перестановки, образуют континуальное множество при к ^ 5.

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

при к 3 справедливы примеры А. А. Мучника классов со счетным базисом, и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 4.4.1). Заметим, что данное утверждение о континуальности множества замкнутых классов для множества угловых наборов при к 3 справедливо и для операции перестановки типа I, поскольку операция перестановки типа II является более сильной операцией.

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

7„ € {О,А: — 1}"\{0",{к - 1)"} для всех п = 2,...,т. В параграфах 4.2-4.4 устанавливается, что для любого -регулярного множества угловых наборов множество классов в 3, замкнутых относительно операций суперпозиции и перестановки, является счетным. Доказательство этого факта проводится в три этапа. В параграфе 4.2 изучается множество Б функций ¿-значной логики специального вида. Показывается, что Б содержит некоторое подмножество Бо, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех подмножеств Бо, замкнутых относительно этих операций, счетно (Теорема 4.2.1). В лемме 4.2.3 представлено полное описание замкнутых подмножеств множества Бо. Кроме того, в параграфе 4.2 доказывается, что множество, состоящее из замыканий подмножеств

множества относительно операций суперпозиции и пере-

становки с произвольным множеством угловых наборов конечно, при этом указан способ построения конечных порождающих систем для каждого из этих замыканий (Теорема 4.2.2). В параграфе 4.3 исследуются свойства функций из множества (такие функции называются Г-фунщиями). Доказывается, что замыкание произвольной существенной И-функции /(х\,х„) относительно операцийсупер-позиции и перестановки с произвольным -регулярным множеством угловых наборов совпадает с множеством всех функций, принимающих значения из множества значений функции (Теорема 4.3.1). В параграфе 4.4 из теорем 4.2.1, 4.2.2, 4.3.1 выводится основной результат главы 4 о счетности множества классов в 3, замкнутых относительно операций суперпозиции и перестановки с произвольным ¿^-регулярным множеством угловых наборов (Теорема 4.4.1), а также описание указанных классов (Следствия 4.4.1, 4.4.2).

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

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

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

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

2) Тарасова О. С. О классах функций трехзначной логики, замкнутых относительно операции специального вида // Материалы пятой молодежной научной школы по дискретной математике и ее

приложениям. М.: Издательство механико-математического факультета МГУ, 2002. С. 87-94.

3) Тарасова О. С. О классах функций многозначной логики, замкнутых относительно операций специального вида // Материалы XIV Международной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 27 октября - 1 ноября 2003 г.) Нижний Новгород: Издательство Нижегородского государственного педагогического университета, 2003. С. 76-80

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

5) Тарасова О. С. О классах функций многозначной логики, замкнутых относительно операций специального вида // Материалы VIII Международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004 г.) М.: Издательство механико-математического факультета МГУ, 2004. С. 150-153

Подписано в печать 30.08.2004 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 120 экз. Заказ № 123 Отпечатано в ООО «Соцветие красок» 119992 гМосква, Ленинские горы, д. 1 Главное здание МГУ, к. 102

»16443

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Тарасова, Ольга Сергеевна

Введение

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

2. Операция перестановки типа I с множеством нулевых угловых наборов

2.1. Замкнутые классы в Р*.

2.2. Замкнутые классы в Р2 и Р3.

2.3. Ослабленная операция перестановки.

3. Операция перестановки типа I с произвольным множеством угловых наборов

3.1. Ослабленная операция перестановки.

3.1.1. Замкнутые классы трехзначной логики.

3.1.2. Примеры континуальных семейств

3.2. Замкнутые классы в Р*.

3.3. Замкнутые классы в Р2 и Р3.

4. Ослабленная операция перестановки типа II

4.1. Примеры континуальных семейств

4.2. Функции вида

4.3. Р-функции.

4.4. Основные утверждения.

Введение диссертация по математике, на тему "О классах функций k-значной логики, замкнутых относительно операций суперпозиции и перестановки"

Э. Пост описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что каждый замкнутый класс имеет конечный базис, а множество всех таких классов счетно [31, 32]. Описание множества замкнутых классов булевых функций содержится также в [8, 9, 23, 24, 30]. Многозначные логики во многом похожи на двухзначную логику и в них сохраняется ряд результатов, имеющих место в двухзначной логике. Среди таких результатов можно отметить решения проблемы функциональной полноты и задачи описания предполных классов (см. [2, 7, 10, 25, 26, 33-35]). В тоже время имеют место и существенные различия. К их числу относятся примеры Ю. И. Янова о существовании замкнутых классов в Р* (множестве всех функций Ахзначной логики), не имеющих базиса, и А. А. Мучника о существовании замкнутых классов в Рк со счетным базисом для всякого к ^ 3 (см. [27, 28]). Из этих результатов, в частности, следует континуальность множества замкнутых классов в Рк при к ^ 3, что делает труднообозримой структуру данного множества.

Поскольку при к ^ 3 проведение в к-значной логике исследований по изучению множества замкнутых классов наталкивается на значительные трудности, многие авторы стали рассматривать задачу изучения классов, , полученных в результате применения более сильных операций замыкания, которые позволяли бы получить множество замкнутых классов счетной или конечной мощности. В работах [1, 4-6, 11-16, 20-22, 29] приведены классификации и свойства классов функций /с-значной логики, к ^ 2, замкнутых относительно операций, являющихся усилениями операции суперпозиции. При этом в работах [11-16] изучается операция ¿"-замыкания, в работах [5, 6, 29] — операция параметрического замыкания, в работах [1, 4, 20-22] — операции замыкания программного типа.

Идея операции ¿-замыкания, где наряду с операцией суперпозицией разрешается применять операцию перехода к двойственным функциям относительно фиксированной группы подстановок, т.е. ¿-замкнутый класс вместе с каждой функцией содержит двойственную относительно указанной группы подстановок функцию, высказывалась несколькими авторами. В настоящее время существуют две версии построения ¿-классификации множества функций /г-значной логики (к ^ 3), представленные в работах С. С. Марченкова [11-13] и Нгуен Ван Хоа [14-16], где в частности установлено, что множество классов в данной классификации конечно, хотя и зависит от к сверхэкспоненциальным образом.

Понятия параметрической выразимости и параметрического замыкания введены А. В. Кузнецовым в работе [6]. В этой же работе получены критерий параметрической выразимости в А;-значной логике для всех к ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при к = 3 показана в работе А. Ф. Данильченко [5], а при к > 3 в работе С. Барриса, Р. Уилларда [29]. Кроме того в [5] построены все предполные классы в Р3

В работе Ю.В. Голункова [4] изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа (см. также [1]). В работах В.А. Тайманова [21, 22] и В.Д. Соловьева [20] исследуется семейство функциональных систем Ахзначной логики (к ^ 2) с операциями программного типа. Каждая операция программного типа определяется своим множеством предикатов. В работах [21г 22] показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума. В случае конечного множества замкнутых классов приведено его полное описание, в случае счетного множества замкнутых классов показано, что каждый класс обладает конечным базисом, в случае континуального множества замкнутых классов представлены примеры классов со счетным базисом и классов без базиса, причем эти примеры совпадают с соответствующими примерами из [27, 28]. В [20] рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.

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

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

Сначала рассматривается операция перестановки, при определении которой слой (слой типа I) задается как множество всех наборов одинаковой длины, содержащих фиксированное количество элементов равных 0,1,.,А; — 1. В результате применения этой операции к произвольной функции /(х 1,., хп), на наборах внутри каждого слоя происходит перестановка значений данной функции, определяемая по следующему правилу. Для каждого слоя выбирается перестановка чисел от 1 до и и для каждого набора слоя новое значение функции / на нем совпадает с исходным значением функции / на наборе, получающимся из данного соответствующей перестановкой его компонент. В работе показано (см. главу 2), что в этом случае множество классов в Рк, замкнутых относительно операций суперпозиции и перестановки, является конечным при всех к ^ 2. Таким образом, данная операция перестановки является слишком сильной. В связи с этим изучается ослабление этой операции за счет введения следующего ограничения. Операцию перестановки разрешается применять только к тем функциям, которые существенно зависят от всех своих переменных. Показано (см. главу 2), что при к = 2 мощность множества замкнутых классов конечна, а при к ^ 3 равна мощности континуума.

Далее в работе вводится понятие слоя относительно углового набора (т.е. набора, все компоненты которого принадлежат множеству {0, А; — 1}), и изучается (ослабленная) операция перестановки для этого нового определения слоя. При этом рассматриваемое ранее понятие слоя в новых терминах — слой относительно нулевого углового набора. Установлено (см. главу 3), что при к = 3 для любых множеств угловых наборов, удовлетворяющих определенным условиям (такие множества называются правильными, см. стр. 9), множество замкнутых классов счетно, а при к ^ Ъ для произвольных множеств угловых наборов множество замкнутых классов является континуальным.

Кроме того, в работе рассматривается разбиение всех наборов на такие подмножества (слои типа II), которые содержат все наборы, находящиеся на фиксированном расстоянии от заданного углового набора. Изучается (ослабленная) операция перестановки с указанными понятием слоя при произвольных перестановках значений функций на наборах внутри каждого такого слоя. Отметим, что каждый слой типа II представляется в виде объединения некоторых слоев типа I. Показано (см. главу 4), что при всех к ^ 3 для любого множества угловых наборов определенного вида (см. стр. 9) множество замкнутых классов А;-значной логики является счетным.

Дадим более точные определения понятия слоя и операции перестановки.

Положим Ек = {0,1,., к — 1}, = Ек х . х Ек, к ^ 2, п ^ 1. Набор (аь., ап) из называется угловым, если а* € {0, к — 1}, г = 1,., п. Слой определяется двумя способами.

I. Наборы .,5„), (71,.,7п) принадлежат одному слою типа I относительно углового набора .,ап) тогда и только тогда, когда наборы (|<5х—o;i|,., |<5П—ап|), (|7i — ai|> • • ч \ln ~ <*п|) содержат одинаковое число элементов, равных 0,1,., к — 1.

II. Наборы (5i,.,бп), (ji,7„) принадлежат одному слою типа II относительно углового набора («х,. , £*„) тогда и только тогда, когда суммы элементов наборов «i|,., |£„ - о„|), (|7i - Oil, • • •, |7п - Qinl) совпадают.

Заметим, что для произвольного углового набора а = (с*х> • • • > ап) любой слой типа I относительно <5 содержится в некотором слое типа II относительно а, при этом каждый слой типа II относительно а представляется в виде объединения слоев типа I относительно а. Вначале дадим общее определение операции перестановки в независимости от конкретного определения слоя, пользуясь лишь тем свойством, что любое разбиение на слои является разбиением множества на непересекающиеся подмножества. Пусть у нас фиксированы функция f(xi,.,xn) из Рк, угловой набор и разбиение множества Е% на слои относительно этого углового набора. Тогда в результате действия на функцию f(xi,., хп) операции перестановки с данным угловым набором и разбиением на слои можно получить функцию ср(хх,., ж„) из Рк в том и только том случае, когда для каждого слоя q можно выбрать такое взаимно однозначное отображение aq наборов слоя q на себя, что функция <р{х\,., хп) будет совпадать с функцией f(crq(xi,., £„)) на всех наборах этого слоя. Назовем операцией перестановки типа I и операцией перестановки типа II такие операции перестановки, для которых слой есть слой типа I и слой типа II соотвественно, причем в определении операции перестановки для случая операции перестановки типа I допускаются только такие взаимно однозначные отображения наборов слоя, в результате действия которых происходит перестановка компонент наборов этого слоя, а в определении операции перестановки для случая операции перестановки типа II взаимно однозначные отображения наборов слоя произвольны. В силу указанного выше свойства вложения слоев типа I в слои типа II и отсутствия ограничения на взаимно однозначные отображения, операция перестановки типа II является более сильной, чем операция перестановки типа I.

Дадим краткое описание содержания глав диссертации.

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

В главе 2 рассматривается операция перестановки типа I с множеством угловых наборов О = {(0), (0,0),.}. В параграфах 2.1, 2.2 доказывается (Теорема 2.1.1), что любой класс в Д, О 2, замкнутый относительно операции суперпозиции и такой операции перестановки, порождается функциями от к переменных. Отсюда вытекает следствие (Следствие 2.1.2) о конечности множества всех таких классов. В теоремах 2.2.1, 2.2.2 приводится полное описание замкнутых классов в Рг и Р3. В параграфе 2.3 операцию перестановки разрешается применять только к функциям существенно зависящим от всех переменных, т.е. рассматривается ослабленная операция перестановки. Показывается, что в этом случае в Р2 число замкнутых классов конечно (Теорема 2.3.1), а в Pk при к>Ъ остается справедливым пример класса со счетным базисом из [27, 28], и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 2.3.2).

В параграфе 3.1.1 исследуются классы трехзначной логики, замкнутые относительно операций суперпозиции и перестановки. Вначале доказывается, что существует множество Q С Р3, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех его подмножеств, замкнутых относительно этих операций, счетно (Теорема 3.1.1). Затем вводится понятие правильного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {7n, 5п \ п ^ 2}, где 7„ G {0,2}п\{0", 2П}, 5п <Е {0П, 2п} для всех п ^ 2. Устанавливается, что для любого правильного множества угловых наборов произвольный замкнутый класс 21 С Р3 представим в виде объединения двух классов: замыкания множества всех трехместных функций из 21 и пересечения f2 П 21 (Теорема 3.1.2). Из теорем 3.1.1, 3.1.2 выводится основной результат параграфа 3.1.1 о счетности множества классов в Р3, замкнутых относительно операций суперпозиции и перестановки с произвольным правильным множеством угловых наборов (Теорема 3.1.3). В параграфе 3.1.2 доказывается (Теорема 3.1.4), что для произвольных множеств угловых наборов классы А;-значной логики, замкнутые относительно операций суперпозиции и перестановки, образуют континуальное множество при к ^ 5.

В параграфах 3.2, 3.3 обобщаются результаты параграфов 2.1, 2.2 на случай операции перестановки с произвольным множеством угловых наборов, которую разрешается применять ко всем функциям /с-значной логики. Показывается, что в Pk при к ^ 2 любой класс, замкнутый относительно операций суперпозиции и перестановки с произвольным бесконечным множеством угловых наборов, порождается функциями от к переменных (Теорема 3.2.1), а множество всех таких классов конечно (Следствие 3.2.3). Кроме того, для указанного множества угловых наборов приводится полное описание замкнутых классов в Рг и Р3 (Теоремы 3.3.1-3.3.4). Поскольку операция перестановки типа II сильнее операции перестановки типа I, указанное выше утверждение о конечности множества классов, замкнутых относительно операций суперпозиции и перестановки с произвольным бесконечным множеством угловых наборов, при к ^ 2 выполняется и для операции перестановки типа II.

В главе 4 рассматривается ослабленная операция перестановки типа II с произвольным множеством угловых наборов. Для произвольного подмножества множества угловых наборов О и О, где О = {(к — 1), (к — 1, к — 1),.}, в Рк при к ^ 3 справедливы примеры классов со счетным базисом из [27, 28], и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 4.1.1). Заметим, что данное утверждение о континуальности множества замкнутых классов для множества угловых наборов О и О при к ^ 3 справедливо и для операции перестановки типа I, поскольку операция перестановки типа II является более сильной операцией.

Далее в главе 4 вводится понятие т-регулярного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {I72,.,7т}, где 5 е {О2, (к-1)2}, % е {0, & —1}П\{0П, (к — 1)п] для всех п = 2,., т. В параграфах 4.2-4.4 устанавливается, что для любого /^-регулярного множества угловых наборов множество классов в Рк, к ^ 3, замкнутых относительно операций суперпозиции и перестановки, является счетным. Доказательство этого факта проводится в три этапа. В параграфе 4.2 изучается множество .Р функций /г-значной логики специального вида. Показывается, что Р содержит некоторое подмножество которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех подмножеств -Р0, замкнутых относительно этих операций, счетно (Теорема 4.2.1). В лемме 4.2.3 представлено полное описание замкнутых подмножеств множества Кроме того, в параграфе 4.2 доказывается, что множество, состоящее из замыканий подмножеств множества ^ = относительно операций суперпозиции и перестановки с произвольным множеством угловых наборов конечно, при этом указан способ построения конечных порождающих систем для каждого из этих замыканий (Теорема 4.2.2). В параграфе 4.3 исследуются свойства функций из множества (такие функции называются Г-функциями). Доказывается, что замыкание произвольной существенной ^-функции /(хь., хп) относительно операций суперпозиции и перестановки с произвольным /¡^-регулярным множеством угловых наборов совпадает с множеством всех функций, принимающих значения из множества значений функции / (Теорема 4.3.1). В параграфе 4.4 из теорем 4.2.1, 4.2.2, 4.3.1 выводится основной результат главы 4 о счетности множества классов в Рк, к ^ 3, замкнутых относительно операций суперпозиции и перестановки с произвольным /^-регулярным множеством угловых наборов (Теорема 4.4.1), а также описание указанных классов (Следствия 4.4.1, 4.4.2).

В диссертации принята следующая нумерация теорем, лемм, следствия, утверждений и замечаний. Теоремы нумеруются тройками чисел, где первое число — номер главы, второе — номер параграфа, третье — номер теоремы внутри параграфа. Леммы и следствия нумеруются аналогичным образом. Утверждения (замечания) имеют двойную нумерацию: первое число — номер главы, второе — номер утверждения (замечания) внутри главы.

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Тарасова, Ольга Сергеевна, Москва

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

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

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

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

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

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

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

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

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

10. Нгуен Ван Хоа. О G-полных замкнутых классах fc-значной логики // EIK. 1990. 26, №5/6. 301-313

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

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

13. Тайманов В. А. Функциональные системы с операциями замыкания программного типа // Диссертация. 1983.

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

15. Угольников A.B. О замкнутых классах Поста // Изв. вузов. Сер. Матем. 1988. №7. 79-88.

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

17. Яблонский C.B., Гаврилов Г.П., Набебин A.A. Предполные классы в многозначных логиках. М.: МЭИ, 1997.

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

19. Яблонский C.B. Введение в дискретную математику. М.: Высшая школа, 2001.

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

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

22. Kuntzman J. Algebra de Boole. Bibliothegue de l'Ingenieur // Automaticien (Dunod, Paris). 1965. №.

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

24. Post E. L. Two-valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton Univ. Pryss. 1941. 5.

25. Rosenberg I. G. La structure des functions de plusieurs variables sur un ensemble finil. Comptes Rendus, de l'Academ. Paris, Ser. A-B. 260. 1965. 3817-3819.

26. Rosenberg I. G. Uber die funktionale Vollständigkeit in den mehrvertigen Logiken. // Rozpravy Ceskoslovenskë Academie vëd. Rada matematickych a prirodnich vëd. Praha, 1970, Rocnik 80, Sesit 4. 3-93.

27. Slupecki J. Kriterium pelnosci wielowar — tosclowych systemow logiki zdan. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Cl. III, 32, 1939, 102-109.

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

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