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

• Панин, Дмитрий Юрьевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Панин, Дмитрий Юрьевич

Оглавление

Введение

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

1.1 Системы функций

1.2 Частично упорядоченные множества

2 Свойства семейства Та'

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

2.2 Отсутствие конечного базиса у всех замкнутых классов, принадлежащих отрезку [Ш1е; М]

2.3 Цепь и антицепь континуальной мощности в множестве Т

3 Порождение одноместных функций из множества А/<

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

3.2 Необходимое условие я-полноты в множестве Р

3.3 Достаточное условие з-полноты в множестве Р

3.4 Описание всех полных систем в множестве Р

3.5 Описание всех полных систем в множестве Р1

3.6 Описание всех 5-иолных систем в множестве Р1

4 Критерий порождения множества 9Яе(2)

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

4.2 Критерий полноты в множестве Р

4.3 Принцип двойственности

4.4 Критерий полноты в множестве Р< относительно композиции

и операции Ф

ч

5 Критерий порождения всех одноместных функций из мно-

жества Мр

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

5.2 Принцип двойственности

5.3 Необходимое условие полноты в множестве М( 1)

5.4 Достаточное условие полноты в множестве М( 1)

Список литературы

и

Введение диссертации (часть автореферата) на тему «О порождении монотонных функций из некоторых классов многозначной логики»

Введение

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

Одной из основных задач в теории функциональных систем является задача о полноте. В общем случае она может быть сформулирована следующим образом. Рассматривается функциональная система (Р; (/?), состоящая из некоторого множества Р и некоторого отображения <р : В(Р) —> В(Р), где В(Р) — множество всех подмножеств множества Р, a tp является оператором замыкания1. Требуется по заданным подмножествам 21 и £ множества Р установить, имеет ли место равенство <¿>(21) = то есть порождает ли множество 2( множество Можно уточнить эту задачу, потребовав, чтобы множество 21 обладало некоторыми дополнительными свойствами. Например, задача о конечной порождеппости заключается в том, чтобы определить, существует ли конечное множество 21, порождающее Другим примером является задача о базируемое™, которая состоит в том, чтобы определить, существует ли множество 21, такое, что <¿>(21) = & и для любого собственного подмножества 21' С 21 выполняется соотношение </?(21') ф £ (такое множество 21 называется базисом

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

1 Отображение ip : В{Р) —> В(Р) называется оператором замыкания, если для каждых 21,03 G В(Р) выполнены следующие свойства: 1) 21 С ip(21), 2) если 21 С 03, то <¿(21) с (¿(03), 3) с^(21)) = (¿(21) (см. [2,9]).

ста [40,41], где было показало, что семейство £2 счетно и каждый класс из семейства £2 имеет конечный базис. Описание классов Поста содержится также в работах [19-22,25,31,33,43]. Ряд результатов, полученных для двузначной логики, обобщается па случай многозначных логик, например, решение проблемы о функциональной полноте (см. [11,13-16,23,24,46,47,49]) и описание предполпых классовом. [44,45]). Однако есть и принципиальные различия между двузначной и /с-значной логикой при к > 3. В частности, Ю. И. Яновым и A.A. Мучником [28] были построены примеры замкнутых классов в Р3, как имеющих счетный базис, так и пе имеющих базиса. Из этих результатов следует, что семейство при к > 3 имеет мощность континуума. Более того, в работах Р. Псшеля и JI. А. Калужница [42] приводятся примеры цепей и антицепей континуальной мощности в решетке £3. При изучении свойств функций многозначной логики возникают существенные проблемы, связанные с труднообозрпмостыо структуры замкнутых классов в Р^ при к > 3. Поэтому одним из направлений исследований является изучение свойств отдельных семейств классов.

К наиболее изученным семействам замкнутых классов функций многозначной логики относится семейство предполпых классов. В работах A.B. Кузнецова [11,12] была доказана конечность числа предполпых классов в Pk при всех к > 3. Все предполные классы функций трехзначной логики были описаны C.B. Яблонским [23]. Отдельные семейства пред-полных классов в Р/. при к > 4 были найдены C.B. Яблонским [24], Ло Чжу-Каем [36,37,39], В. В. Мартышоком [17] и другими псследователя-мн(см. в частности, [1,7,8,35,38]). Полное описание всех предполпых классов функций многозначной логики было получено И. Розенбергом [44,45]. Стоить отмстить, что так же, как и решетка при к > 3, большинство решеток, состоящих из замкнутых классов, содержащихся в заданном пред-полном классе, имеет нетривиальную структуру. Так, в работах С. С. Мар-ченкова [18], Я. Деметровича и JI. Ханнака [29] было показано, что каждый предиолный класс в Р^ при к > 3 содержит континуальное множество замкнутых подклассов тогда и только тогда, когда он не является классом тина2 L.

2Под классами типа L понимаются классы линейных функций.

Одним из наиболее естественных вопросов, возникающих при изучении свойств предполных классов, являются вопрос о конечной порожден-ностп. Д. Лау [32] установила, что каждый предполный класс функций многозначной логики за исключением классов из семейства3 О имеет конечный базис, кроме того, она доказала, что классы типа О являются конечно-порожденными при к < 7. Результаты, связанные с указанными, также можно найти в работах [1,8,17,24,33,42,45,48]. Г. Тардош [50] привел пример частично упорядоченного множества Т?8 ширины 2, состоящего из восьми элементов, такого, что предполный класс всех функций, монотонных относительно множества не имеет конечного базиса. В работах О. С. Дудаковой [4-6] приводится необходимое п достаточное условие конечной порожденное™ для предполных классов функций, монотонных относительно частично упорядоченных множеств ширины 2 с наименьшим и наибольшим элементами.

На данный момент предполные классы монотонных функций - это единственное семейство предполных классов, для которых вопрос конечной порожденности исследован не полностью, таким образом, оказалось, что это семейство является в некотором смысле наиболее сложным для изучения. В связи с этим, исследования в данной области представляют особый интерес. Также стоит отметить, что множество — это такое наименьшее по мощности частично упорядоченное множество, что предполный класс функций монотонных относительно него, не имеет конечной порождающей системы. Поэтому класс М11& занимает особое положение среди классов типа О. В настоящее время вопрос, имеет ли класс М^8 бесконечный базис, остается открытым. Одним из возможных подходов к решению этой проблемы является изучение свойств «просто устроенных» подклассов М1*8, а также получение критериев полноты для множеств функций из МЙ8, зависящих от определенного числа переменных.

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

3Семеиство О эго классы функций, монотонных относительно некоторых частично

упорядоченных множеств с наименьшим и наибольшим элементами.

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

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

В главе 1 приводятся основные определения и обозначения, а также доказываются вспомогательные утверждения. В частности, определяется класс ограниченно селекторных функций, обозначаемый через , и понятие частично упорядоченного множества типа башня. Будем обозначать через А семейство всех конечных частично упорядоченных множеств с наименьшим и наибольшим элементами. Наименьший и наибольший элементы множества СР Е А будем обозначать через 0 и 1 соответственно. Шириной частично упорядоченного множества У Е А будем называть максимальное число попарно несравнимых элементов из СР. Будем обозначать через А2 подсемейство семейства А, состоящее из всех множеств, ширина которых не превосходит 2.

Пусть СР Е А2, а и Ъ — элементы множества О3. Элементы а и Ь называются 1-несравнимыми, если они несравнимы и не плюют точной верхней грани. Элементы а и 6 называются 2-несравнимыми, если они 1-иесравнпмы и найдутся две их минимальные верхние грани, являющиеся 1-несравнимыми.

Пусть СР Е А2. Будем обозначать через Му замкнутый класс всех функций /с-значпой логики, монотонных относительно частично упорядоченного множества СР, где к = |СР|.

Положим и — {0,1}. Пусть 1 < I < п. Будем обозначать через (п) множество всех функций /(х\,... ,хп) Е для которых выполнены следующие условия:

1) для любых элементов $1,..., 5п из множества 1С справедливо равенство

/(¿ъ • ■ - А) = й;

2) для любых элементов ¿>1,. ... 5п из множества У \ И справедливо равенство ... ,6п) — Определим множества и следующим образом. Положим

п

ш"е(п) = []ш!(п),

¿=1 ?г>1

Функции из множества будем для краткости называть ограниченно селекторными функциями. Будем обозначать через Т'-Р семейство всех замкнутых классов А, таких, что Шрс С А С М7.

Буднем обозначать через М< множество всех функций /(х\:..., хп) из класса таких, что /(5,..., < 6, для всех 6 Е У. Функции из множества М< будем для краткости называть невозрастающими функциями.

Пусть п > 1. Положим Уп = {0, а\. Ь\1.. ., ап, Ьп, 1},

Аа0 = Ь0 = 0, ап+1 = Ьп+1 = 1, Аг = {аг,6,}, где

^ 0 < % < п + 1. Введем на элементах множества СР7, от-ь

11 1 ношение частичного порядка < следующим образом (см. ! рис. 1):

1) < Для всех таких, что £{ Е Дг-, £3 Е Д^-, О < г < з < п + 1;

2) £ < £ для всех е Е Рис. 1

3) других сравнимых элементов нет.

Множество будем называть множеством типа башня высоты п с максимальным элемент,ом,. Множество = !Р„ \ { 1} будем называть мноэ/се-ством, типа башня высоты п без максимального элемента. Отметим, что множество /?,§ из работы Г. Тардоша [50]является множеством типа башня высоты 3 с максимальным элементом.

В главе 2 исследуются свойства семейства Т^, где У — произвольное частично упорядоченное множество из семейства А2, содержащее пару 2-несравпимых элементов. Семейство Ту состоит из всех замкнутых классов, содержащихся в классе Мт — множестве функций, монотонных относительно СР, и содержащих класс — множество ограниченно селекторных функций. Из результатов О. С. Дудаковой [6]следует, что класс М'у не является конечно порожденным. В §2.2 устанавливается отсутствие конеч-

ной порождающей системы для всех классов из семейства Т^. При дока-

зательстве используется метод из работы Г. Тардоша [50]и его обобщение из работы О. С. Дудаковой [6]. А именно, для каждого значения п, такого, что п > 4, определяется некоторое множество наборов элементов множества СР, которое сохраняется всеми функциями из класса М']\ зависящими от к (к < п/2) переменных (см. также [4]), и доказывается, что в классе УЯ^ найдется функция /(х1,...,х2?;+з), которая не сохраняет это множество наборов. В § 2.3 показано, что семейство содержит как цепь, так и антицепь замкнутых классов континуальной мощности. Основными результатами главы 2 являются следующие теоремы.

Теорема 1 (теорема 2.2.1). Пусть У — произвольное множество из семейства А2; содержащее пару 2-иссравнимых элементов, А — произвольный замкнутый класс, такой, что Ш^ С /I С М7'. Тогда класс А не является конечно порожденным.

Теорема 2 (теорема 2.3.9). Пусть У — произвольное множество из семейства А27 содержащее пару 2-несравнимых элементов. Тогда в семействе Т3, найдется как цепь, так и антгщепь континуальной мощности.

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

О У

М< и М<" — множеств певозрастающпх функций, монотонных относительно частично упорядоченных множеств типа башня (п > 3). Отметим, что множество М<" удовлетворяет соотношению С М<" С МТп, поэтому из теоремы 1 следует, что класс М<" не является конечно порожденным. Для удобства изложения положим

^ = М%п( 1) и Г1 = М£"(1). Сначала на множествах /'' и вводятся операции композиции и свертки, обозначаемые через о и V соответственно. Результатом применения операции свертки к функциям /ид является функция (/ V д), определяемая следующим образом:

Операция свертки интересна тем, что позволяет получить критерий порождения множества Г относительно только операции композиции, используя

х, если д(х) ^ 0; /(х), если д(х) = 0.

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

В §3.2 определяются множества функций С1, Za^ Zь, семейство множеств функций 6 и устанавливается критерий полноты для функциональной системы (Р, {о, у}) в терминах этих множеств. Далее, с использованием этого результата строятся множества функций £), I)1 и А'1, являющиеся единственными минимальными по включению порождающими множествами для функциональных систем (Т7, {о}), (^1,{о}) и (^1,{о,у}) соответственно. Основные результаты главы 3 могут быть сформулированы следующим образом.

Теорема 3 (теорема 3.3.18). Пусть А С .Р. Замыкание мноэюеетва А относительно операций {о, у} совпадает с Р тогда и только тогда, когда Сп С А и найдется С Е такое, что С С Л,

Теорема 4 (теорема 3.4.3). Пусть АСЕ. Замыкание мноэюеетва А относительно операций {о} совпадает с Р тогда и только тогда, когда ОСА.

Теорема 5 (теорема 3.5.6). Пусть А С Р1. Замыкание мноэюеетва А относительно операций {о} совпадает с И1 тогда и только тогда, когда Я1 С А.

Теорема 6 (теорема 3.6.6). Пусть А С Р1. Замыкание множества А относительно операций {о, у} совпадает с Р1 тогда и только тогда, когда К1 С А.

В главе 4 устанавливается критерий полноты для множества 9Л^(2) -множества двухместных ограниченно селекторных функций, монотонных относительно ф, где ф является частично упорядоченным множеством типа башня высоты п (п > 3) с максимальным элементом. Отметим, что из теоремы 1 следует, что класс 9Л® не является конечно порожденным, поэтому представляется интересным получение критериев полноты для мно-

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

В §4.1 вводятся множества одноместных функций и рассматри-

вается множество Г, которое состоит из упорядоченных пар одноместных функций, таких, что первый элемент пары принадлежит множеству а второй — множеству Далее определяются отображения до и д\, которые каждой функции из множества сопоставляет функцию из множеств .Р< и соответственно. После этого определяется отображение д : —> Г, которое каждой двухместной функции / из множества Ш® ставит в соответствие пару одноместных функций (до(/), Затем на множествах Е> определяются операции Фо и Ф1, являющиеся обобщениями операции свертки (см. главу 3). Далее на множестве Г рассматриваются операции специального вида 0 и Ф, определенные следующим образом:

(/о, /1) <8> (до, д\) = (/о о д0, /1 о д1), Ф((/о,Л), (90,91), (¿оА)) - (Фо(/о^о,Ло),Ф1(/ь5ьМ)-

Операции <8) и Ф интересны тем, что позволяют в некотором смысле сводить изучение вопросов порождения двухместных функций из множества Ш® к изучению порождения множества Р относительно этих операций. А именно, показывается, что замыкание произвольного множества А С 9Л®(2) содержит множество 9Л^(2) тогда и только тогда, когда замыкание множества д(А) и {е} относительно операций (2) и Ф совпадает с Р, где е — тождественная функция на множестве Р. В §4.2 устанавливается критерий полноты для системы (Р,{<8>,Ф}) в терминах свойств пар функций и порождения множеств Р> относительно множеств операций {о,Ф0}, {о, Ф1} соответственно. В §4.3 показывается, что множество В С Р< порождает относительно операций {о, Ф0}, тогда и только тогда, когда двойственное множество В* С порождает относительно операций {о, Фх}. В §4.4 определяется множество функций и с использованием теоремы 3 (см. главу 3) доказывается критерий порождения множества Р< относительно операций {о, ф0}. Основным результатом главы 4 является следующий критерий порождения множества Ш®(2) в терминах свойств

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

Теорема 7 (теорема 4.4.18). Пусть А С 9Л®(2). Соотношение С [Л] выполняется тогда и только тогда, когда выполнены следующие условия

1) для каоюдого а Е Лх и для каэ/сдого 5 Е и • ■ • и Ап, мпоэюеетво д{А) содерэ/сит элемент (/(>,/1), такой, что /о(а) — а и /\(5) ^ 6;

2) для каждого 5 Е А\ и • ■ ■ и Дп и для каждого а Е Ап, мпоэюеетво д{А) содерэюит элемент (/о, /г), такой, что /о(6) ^ 5 и /\(а) = а/

3) для каоюдого множества, С из семейства {¿»о(^), (Р1(^.))*} выполнены соотношения С С, С" ^ 2й, С ^ ^ и найдется миооюеетво В Е 65, такое, что В С С.

В главе 5 рассматривается задача о полноте для множества —

множества одноместных функций, монотонных относительно С}, где является частично упорядоченным множеством типа башня высоты п (п > 3) с максимальным элементом. Отмстим, что при п > 3 множество типа башня высоты п с максимальным элементом содержит пару 2-несравпимых элементов, поэтому класс всех функций, монотонных относительно <5, не является конечно порожденным.

Сначала определяются множество //1, состоящее пз функций множества принимающих все значения, и отображение Уе^ : Н{ —» Ъ1^, которое сопоставляет каждой функции из Н\ некоторый вектор из нулей и единиц длины п. Показывается, что множество А С Н\ порождает множество Н\, тогда и только тогда, когда ранг4 матрицы, составленной из векторов Уес1(/&), ¡г Е А, равен п. Далее вводится понятие неразложимых множеств, которое содержательно заключается в том, что функции пз неразложимого множества А С 1) нельзя получить используя только функции не из А. После этого строится семейство множеств такое, что каждое множество из построенного семейства является неразложимым. Наконец, доказывается следующий критерий полноты для систем функций из 1).

Теорема 8 (теорема 5.4.13). Пусть А С М®(1). Соотношение

'Под рангом матрицы понимается максимальное число линейно независимых столбцов.

[А] — 1) выполняется тогда и только тогда, когда справедливы следующие условия:

1) 11апк(Уес1(#1 П А)) = п;

2) для каждого Р 6 $ выполняется АП Р ф 0.

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

Глава 1

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

1.1 Системы функций

Пусть <5 — некоторое конечное множество. Через будем обозначать множество всех одноместных функций, определенных па ф и принимающих значение из множества . Пусть 05 С Отображение о> : 05д" —> 05, где к > 1, будем называть к-местной операцией на множестве 05. Пусть Е - некоторое множество операций на 05, 21 С 05. Пару (21, Е) будем называть системой в 05. Определим по индукции понятие формулы над системой (21, Е), а также понятие функции, реализуемой формулой. Выражение вида /. где / Е 21, является формулой над (21, Е). Такая формула называется тривиальной и реализует функцию /. Пусть сгь — некоторая к-местная операция из Е, а Фх,..., Ф/,. — формулы над (21, Е), реализующие функции /ь ..., Д, соответственно. Тогда выражение сг^(Фь ... , Ф^), является формулой над (21, Е) и реализует функцию сг/^Д... ., Д.). При этом предполагается, что других формул над 21 нет. Сложностью формулы Ф над (21, Е), обозначаемой через Ь{Ф), будем называть число символов операций, входящих в Ф. Замыкаииелг мноэ/сества 21 относительно Е, обозначаемым через /¿(21, Е), будем называть множество всех функций, которые могут быть реализованы формулами над (21, Е). Будем говорить, что система (21, Е) полна в 05, если /¿(21, Е) = 05.

Пусть / Е /¿(21, Е). Слоэюностью функции / над системой (21, Е) будем называть величину равную ттЬ(Ф), где минимум берется по всем

формулам Ф над 21 относительно Е, реализующим /.

Лемма 1.1.1. Пусть (А, 12) — некоторая система, / Е ¿¿(/1,Е); > 0. Тогда / = ат(/1.... ,/т), где т > 1, сгт 6 Е; /г 6 /г(ДЕ);

Доказательство. Пусть / £ ¿¿(ДЕ). Тогда существует формула Ф над (Л,Е), реализующая функцию /, такая, что Ь(Ф) = Ьд(/).

Так как Ь(Ф) > 0, то формула Ф имеет вид сгт(Ф15..., Ф7„), где ат Е Е, т > 1, Ф7 формулы над (ДЕ), г — 1 ,...,то. Пусть г Е {1,...,то}. Формула Ф7 реализует некоторую функцию /¿, поэтому Е Е) и — • Из определения следует, что Ь(Фг) < Ь(Ф). Поэтому

< Ь(Ф). Лемма доказана.

Пусть (55, Е) — некоторая система, А С 05. Будем говорить, что множество А неразложимо над 23 относительно Е, если для любой операции ат Е Е и для любых функций f,fl,■^^,fm 113 23, таких, что / = ат(/1, ■ ■ ■, 1т), / £ А следует, что найдется номер г, (1 < г < то), такой, что /,- Е А.

Лемма 1.1.2. Пусть (25, Е) — некоторая система, А и С — подмножества .множества 23; такие, что ц(А, Е) = 05, С неразложимо над 23 относительно Е, С ф 0. Тогда АП С Ф 0.

Доказательство. Предположим, что А П С = 0. Так как /л(А, Е) = 23, то С С ¡¿(А, Е). Пусть А: = пппЬ^(/), где минимум берется по всем функциям / из множества С, а д — функция из С, такая, что Ьд(д) = к. Из соотношения А П С — 0 следует, что к > 0. По лемме 1.1.1 найдутся число то > 1, операция сгт Е Е и функции д\,... ,дт из Е), такие, что 9 = &т{д\-, ■ ■ ■ ,9т)- Так как множество С неразложимо, то найдется помер (1 < я < тп), такой, что д\ Е С. Так как < Вд(д) = /с, то получаем

противоречие с минимальностью к. Поэтому АГ\С ф 0. Лемма доказана.

Пусть о\ — отображение из А в В, а о"2 — отображение из В в С, где А, В, С — некоторые конечные множества. Тогда произведением отображений о" 1 и 02 будем называть отображение <Т2°о"1 из А в С, значение которого на произвольном элементе 6 из множества А определяется равенством

((72 о сгх) (<5) — о"2(<71(5)). Произведение отображений является ассоциативной операцией, поэтому в выражении <т3 о (02 ° а\) будем для краткости опускать скобки и считать, что все операции выполняются справа налево.

Пусть а — некоторое отображение из А в В, А' С А. Положим а{А') = | 5 Е А'}.

Отображение сг : А А, такое, что для каждого элемента £ из множества А выполнено равенство а(д) = 5, будем называть тождественным и обозначать через Т^.

Пусть в — некоторое взаимно-однозначное отображение множества В на А. Определим отображение ^ : УК а —> следующим образом. Пусть / Е Положим

Будем говорить, что (д является сопряжением (относительно 9) на множестве

Лемма 1.1.3. Пусть £ — некоторое сопряжение на множестве 9Ка, 1,9 Тогда

Ш° я) = С(/)0 С (я)-

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

С(Я ° СЫ = о/ов)о (в~г одов) =

0-1о/овов'1одо9 = в~1о(/ово Г1) одов =

в~:1 О / о д о 9 = 9-1 о (/ о д) о 9 = С(/ о д).

Лемма доказана.

Пусть (21, Е) — некоторая система, о Е Е, £ — некоторое сопряжение на множестве 21. Определим операцию £(ст) на множестве С(21) следующим образом. Пусть Д,..., /т Е 21. Тогда

СИ(С(/1),---,С(/?п))=СИ/ь---,/т)).

Будем говорить, что операция £(сг) является двойственной к а относительно сопряжения Множество С(^) будем называть двойственным множеством операций к Е.

Лемма 1.1.4. Пусть (ДЕ), некоторая система, £ — некоторое сопряжение. Тогда

Доказательство. Положим А1 = — Докажем сначала

соотношение

El) С С (¿¿(А, Е)).

Пусть / Е ¡л{А\, Ei). Обозначим через к сложносггь функции / над системой (y4i,Ei). Докажем индукцией по к, что / Е ((¿¿(А, Е)). Если к = 0, то f Е А. Так как А\ = т0 найдется функция g Е А, такая, что ((g) = /. Поэтому /еС(МАЕ)).

Пусть к > 0 и для всех функций, сложность которых над системой (yli,Ei) строго меньше к, выполнено предположение индукции. Тогда по лемме 1.1.1 найдутся число т > 1, m-местная операция ат Е Еь функции fi,... . fm из множества Ai, такие, что / = erm(/i, • • •, fm). Так как

ул

^л\(fi) < т0 Функции fi выполнено предположение индукции.

Поэтому fi = ((gi), где gi Е /i(A, Е). Пусть а — это операция, такая что С(сг) = от. Положим g = &{gi, ■ ■ ■ ,gm)- Очевидно, что g Е /¿(Л, Е). Имеем

/ = М/ь ■ • ■, fm) = ((o-)(((gi),... , С(gm)) = t(<r(9i, • ■ •, 9т)) = СЫ-Таким образом, / € Е)). Докажем теперь, что

Нетрудно видеть, что системы (v4i,Ei) и (А, Е) являются двойственными относительно сопряжения Поэтому имеет место соотношение

Применяем к обоим частям отображение С и получаем требуемое включение. Лемма доказана.

1.2 Частично упорядоченные множества

Будем обозначать через А семейство всех конечных частично упорядоченных множеств с наименьшим и наибольшим элементами. Наибольший

и наименьший элементы элементы множества У 6 А будем обозначать через 0 и 1 соответственно. Шириной частично упорядоченного множества СР называется максимальное число попарно несравнимых элементов из У. Будем обозначать через А2 подсемейство семейства А, состоящее из всех множеств, ширина которых не превосходит 2. Пусть а,(3 Е У. Если для этих элементов выполняется по крайней мере одно из соотношений а < /3, /3 < а, то эти элементы называются сравнимыми, в противном случае —-несравнимыми.

Пусть У Е А2. Будем обозначать через М7 замкнутый класс всех функций /с-значной логики, монотонных относительно У, где к =

Положим 11 = {0,1}. Пусть 1 < г < п. Будем обозначать через Ш?(те) множество всех функций /(¿'1.... ,хп) Е для которых выполнены следующие условия:

1) для любых элементов ..., дп из множества К. справедливо равенство

/(¿ъ- • -А) =

2) для любых элементов 6\,... ,5п из множества У \ К справедливо равенство /(¿1,..., £„) =

Определим множества (те) и Ш^ следующим образом. Положим

^(те) = и9ЛГ(;г), Ш* = {] ШЦп).

¿=1 ?!>1

Лемма 1.2.1. Класс Ш1 замкнут относительно операции суперпозиции.

Доказательство. Пусть Ф — произвольная формула над множеством Ше, реализующая некоторую функцию /. Положим к = Ь(Ф). Докажем индукцией по к, что / Е Пусть к = 0. Тогда формула Ф реали-

зует селекторную функцию, которая, очевидно принадлежит множеству ШПусть к > 0 и выполнено предположение индукции. Тогда формула Ф имеет вид д(<Е>1,. -., Ф«), где д - некоторая функция из множества г — формулы над множеством ШТ^', реализующие функции Н\(х\,..., £„,),..., Ы(х 1,..., хщ) соответственно. Из определения сложности формулы следуют неравенства Ь(Ф1) < Ь(Ф),..., < Ь(Ф). Поэтому по предположению индукции функции ... ,}ц принадлежат множеству . Пусть формула Ф реализует некоторую функцию /, зависящую

от переменных х\,..., хп. Из определения множества следует, что найдется номер г, 1 < г < ¿, такой, что д Е Так как Е то по определению множества найдется найдется номер э, 1 < э < щ, такой, что }ц Е Докажем, что / Е Ш?(п). Пусть 61,...,5п — произвольные элементы из множества К. Пусть 1 < й < ¿. Положим — • ■ ■ 1 • Из определения множества следует, что выполнено соотношение 75 Е {$1,.. . , £?г,}> т0 есть 7я £ Так как /ц Е 9Л?(пг), то 7г = Поэтому верны следующие равенства

Список литературы диссертационного исследования кандидат наук Панин, Дмитрий Юрьевич, 2013 год

Литература

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

[2] Биркгоф Г. Теория решеток. — М.:Наука, 1984.

[3] Гниденко В. М. Нахождение порядков предполных классов в трехзначной логике // Проблемы кибернетики. Вып. 8. — М.: Физматгиз, 1962. - С. 341-346.

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

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

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

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

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

[9] Кон П. Универсальная алгебра. — М.: Мир, 1968.

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

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

[12] Кузнецов А. В. Алгебра логики и ее обобщения // Математика в СССР за 40 лет (1917-1957). Т. 1. - М.: Физматгиз, 1959. - С. 102-115.

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

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

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

[16] Мальцев А. И. Итеративные алгебры Поста. — Новосибирск, 1976.

[17] Мартпынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. — Т. 3. — 1960. — С. 49-60.

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

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

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

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

[22] Угольников А. Б. Классы Поста. — М.: Издательство Центра прикладных исследований при механико-математическом факультете МГУ, 2008. 64 с.

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

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

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

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

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

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

[29] Bemetrovics J., Hannah L. The number of reducts of a preprimal algebra. 11 Algebra Universalis. - 1983 — V. 16 — 1 — P. 178-185.

[30] Bemetrovis J., Hannak L. Construction of large sets of clones // Zeitschr. f. Math. Logik und Grundlagen, d. Math. 1987. 33. 127-133.

[31] Kuntzman J. Algebra de Boole. Bibliothegue de ringenieur // Automaticien. Paris: Dunod. — 1965.

[32| Lau В. Bestimmung der Ordnung maximaler Klassen von Funktionen der k-wertigen Logik // Z. math Log und Gründl. Math. — 1978. — 24. — P. 79-96.

[33] Lau B. On closed subsets of Boolean functions (A new proof for Post's theorem) // J. Process. Cybern. EIK. - 1991. Bd. 23, 3. - P. 167-178.

[34] Lau В. Function algebras on finite sets: a basic course on many-valued logic and clone theory. — Springer Monographs in Mathematics. Berlin: Springer, 2006. — 668 p.

[35] Pan Jun-Cze. A solving method for finding all precomplete classes in many-valued logics // Acta. Sei. Natur. Univ. Jilinesis. — 1962. — V. 2 (Chinese).

[36] Lo Czu-Kai. The precompleteness of a set and rings of linear functions // Acta. Sei. Natur. Univ. Jilinensis. - 1963. - V. 2. - P. 1-14 (Chinese).

[37] Lo Czu-Kai. On the precompleteness of the classes of functions preserving a partition // Acta. Sei. Natur. Univ. Jilinensis. - 1963. — V.2. - P. 105-116 (Chinese).

[38] Lo Czu-Kai, Lju Sjui-Hua. Precomplete classes defined by binary relations in many-valued logics // Acta. Sei. Natur. Univ. Jilinensis. — 1963. — V.4. - P. 27-33 (Chinese).

[39] Lo Czu-Kai. Precomplete classes defined by normal /j-ary relations in k-valued logics // Acta. Sei. Natur. Univ. Jilinensis. — 1964. V.3. — P. 39-50 (Chinese).

[40] Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43. 3. 163-185.

[41[ Post E.L. The two-valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton Univ. Press. - 1941. - 5.

[42] Pöschel R., Kaluznin L. A. Funktionen- und Relationenalgebren. Berlin. 219 p. - 1979.

[43] Reschke M., Denecke K. Ein neuer Beweis für die Ergebnisse von E. L. Post über abgeschlossene Klassen Boolescher Funktionen // J. Process. Cybern. EIK. - 1989. - Bd. 7. P. 361-380.

[44] Rosenberg I. G. La structure des functions de plusieurs variables sur en ensemble finil. Comptes Rendus, de l'Academ/ Paris, 260. — 1965. — P. 3817 3819.

[45] Rosenberg I. G. Uber die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpr. CSAV. MPV. - 1970. - 80. - P. 3-93.

[46] Salomaa A. Some completeness criteria for sets of functions over a finite domain I // Ann. Univ. Turkuensis, Ser. AI. - 1962. — 53. 9 p.

[47] Salomaa A. Some completeness criteria for sets of functions over a finite domain II // Ann. Univ. Turkuensis, Ser. AI. — 1962. — 63. - 19 p.

[48] Schofield P. Independent conditions for completeness of finite algebras with a single generator // J. London Math. Soe. - 1969. - V. 44. - P. 413-423.

[49] Slupecki J. Kryterium pelnosci wielowartosciowych systemow logiki zdan 11 C. R. Seanc. Soc. Sei. Varsovie, Cl. III. - 1939. - 32. - P. 102-109.

[50] Tardos G. A not finitely generated maximal clone of monotone operations // Order. - 1986. - V. 3. - P. 211-218.

[51] Панин Д. Ю. О порождении одноместных монотонных функций многозначной логики // Вестник Московского университета. Математика. Механика. - 2010. Вып. 6. - С. 52 55.

[52] Панин Д. Ю. Критерии полноты для некоторых классов монотонных одноместных функций в Рк // Вестник Московского университета. Математика. Механика. — 2013. Вып. 3. — С. 57-61.

[53] Панин Д. Ю. Об одном семействе классов монотонных функций многозначной логики, не имеющих конечного базиса // Известия Иркутского университета. Математика. — 2013. Т. 6, № 3. С. 97-108.

[54] Папин Д. Ю. О некоторых свойствах одноместных монотонных функций многозначной логики // Проблемы теоретической кибернетики. Материалы XVI Международной копференеции (Нижний Новгород, 20-25 июня 2011 г.). - 2011. - С. 349-352

[55] Панин Д. Ю. О свойствах одноместных монотонных функций многозначной логики // Материалы VIII Молодежной научной школы по дискретной математике и ее приложениям (Москва, 24-29 октяб-

[56] Панин Д. Ю. О полноте систем монотонных одноместных функций в Р)с // Дискретная математика и се приложения: Материалы XI Международного семинара (Москва, 18-23 июня 2012 г.). М., 2012. С. 210-212.

[57] Панин Д. Ю. Критерий порождения некоторых множеств монотонных функций многозначной логики // Материалы IX Молодежной научной школы по дискретной математике и ее приложениям (Москва,

ря 2011 г.). - 2011. - С. 23-25.

16-21 сентября 2013 г.). - 2013. - С. 88-92.

92. /7