Содержание к диссертации
Введение
1 Определения и основные свойства операции расширенной суперпозиции 12
1.1 Основные определения и обозначения 12
1.2 Операция расширенной суперпозиции 15
1.3 Свойства операции расширенной суперпозиции 17
2 Критерий выразимости функций в терминах расширенной суперпозиции 21
2.1 Формулировка и доказательство критерия выразимости . 21
2.2 Критерии согласованности 24
3 Критерий универсальной разложимости классов булевых функций 36
3.1 Вспомогательные утверждения 36
3.2 Формулировка и доказательство критерия универсальной разложимости 42
4 P-пополнения замкнутых классов булевых функций 45
4.1 Вспомогательные определения 47
4.2 Базовые P-пополнения классов L, U01 и SU 48
4.3 Базовые P-пополнения класса M01 52
4.4 Базовые P-пополнения класса T0 56
4.5 Базовые P-пополнения классов вида Om 57
4.6 Базовые P-пополнения класса K01 63
4.7 Базовые P-пополнения класса S 67
4.8 Теорема о множестве базовых P-пополнений 69
4.9 Теорема о множестве P-пополнений 70
4.10 Отличие некоторых P-пополнений от замкнутых классов 81
5 Вопросы полноты для P2 и предполных классов булевых функций 84
5.1 Вспомогательные утверждения 84
5.2 Полнота в классе P2 89
5.3 Полнота в классе T1 94
5.4 Полнота в классе S 100
5.5 Полнота в классе M 108
5.6 Полнота в классе L 111
Список литературы
- Операция расширенной суперпозиции
- Критерии согласованности
- Базовые P-пополнения классов L, U01 и SU
- Полнота в классе P2
Операция расширенной суперпозиции
В этом случае будем говорить, что функция / существенно зависит от переменной Х{. В противном случае переменную ХІ будем называть несущественной и будем говорить, что функция / не зависит существенно от переменной ХІ. Функции будем называть равными, если одну из них можно получить из другой путем добавления и удаления несущественных переменных. Пусть й = {а\,... ,ап) Є Еп, /3 = (/Зі,... ,/Зп) Є Еп, п 1. Набор /3 не превосходит набора й (обозначение й /3), если для любого г, 1 і п, выполнено неравенство CKJ Д. Функцию /(жі,..., хп), п 1, будем называть монотонной, если для любых двух наборов а?, /З Є Еп, таких, что й /3 выполняется соотношение /(й) /(/3). Функцию /(жі,... , хп) Є Рг будем называть селекторной, если существует такой номер г, 1 і п, что для любого набора й = («і,..., скп) из Еп выполняется равенство /(5?) = CKJ. Будем обозначать эту функцию через е\п (х\,..., хп) или через Х{. Будем называть функцию f(x\,..., хп) Є Р2 константой 0 (соответственно константой 1), если она принимает значение 0 (соответственно 1) на всех наборах из Еп, п 1, и обозначать через 0 (соответственно через 1).
Функцию будем называть двойственной к функции f(xi,..., жп) (обозначение / (#i,..., жп)). Функцию /(жі,..., жп) будем называть самодвойственной, если / = / . Пусть В С Р2. Обозначим через множество всех функций g Є Р2, таких, что д Є , а через — множество всех функций g Є Р2, таких, что д Е В. Будем называть отображение ф : В — В операцией двойственности.
Пусть А — множество булевых функций. Дадим индуктивное определение формулы над А. 1. Выражение Хі, где ХІ — символ переменной, является формулой над А. Такие формулы будем называть тривиальными. 2. Пусть Фі,..., Фп — формулы над А, п 1, а /(жі,..., хп) Є А. Выражение Ф вида /(Фі, , Фп) является формулой над А. Будем называть Фі,..., Фп подформулами формулы Ф. Формулу Ф и все подформулы формул Фі,... , Фп будем также называть подформулами формулы Ф.
Произвольная формула естественным образом задает некоторую булеву функцию. Будем говорить, что формула реализует эту функцию. Формулу G, реализующую некоторую функцию /(жі,... ,хп) п 1, будем также обозначать через 0(жі,... ,хп). Способ реализации булевых функций нетривиальными формулами указанного вида будем называть операцией суперпозиции. Формулы называются эквивалентными, если они реализуют равные функции. Множество всех булевых функций, реализуемых с помощью операции суперпозиции над множеством А будем называть замыканием А относительно операции суперпозиции и обозначать через [А]. Множество А называется замкнутым относительно операции суперпозиции, если А = [А].
Пусть f(xi,..., Хп) Є Р2, п 1. Согласно теореме Жегалкина, функция / может быть представлена в виде К\ + ... + КГ, где Кі,..., КГ, — различные выражения вида XjxXj2... Xjn 0 или 1,1 j\ j2 ... ji n, 1 I п. Такую формулу будем называть полиномом Жегалкина функции /, а выражения Ki,... , Кг мономами. Из соображений двойственности следует также, что / может быть представлена в виде D\ + ... + Dr, где Di,... , Dr, — различные выражения вида Xjx V Xj2V ... V Xjn 0 или 1, 1 ji j2 ... ji n, 1 / п. Такую формулу будем называть дизъюнктивным полиномом Жегалкина функции /, а выражения D\,... , Dr дизъюнктивными мономами.
Будем называть количество различных переменных в произвольном мономе рангом этого монома. Будем называть наибольший ранг мономов, входящих в полином Жегалкина произвольной булевой функции, рангом этой функции.
Пусть т 2. Будем говорить, что функция /(жі,..., хп) удовлетворяет условию 0т (соответственно Vй ), если любые т наборов, на которых / равна 0 (соответственно 1), имеют общую нулевую (соответственно единичную) компоненту. Будем говорить, что функция f(xi,... ,хп) удовлетворяет условию О00 (соответственно I00 ), если все наборы, на которых / равна 0 (соответственно 1), имеют общую нулевую (соответственно единичную) компоненту.
Следуя работам [37, 38], перечислим некоторые множества булевых функций: Ті — множество всех функций, сохраняющих константу 1; То — множество всех функций, сохраняющих константу 0; S — множество всех самодвойственных функций; М — множество всех монотонных функций; L — множество всех линейных функций; К — множество всех конъюнкций; D — множество всех дизъюнкций; От — множество всех функций, удовлетворяющих условию 0т , т = 2,..., оо; 1т — множество всех функций, удовлетворяющих условию 1т , т = 2,..., оо; U — множество всех функций, существенно зависящих не более чем от одной переменной; С — множество всех функций, не имеющих существенных переменных. Нетрудно показать, что все перечисленные множества булевых функций являются замкнутыми классами относительно операций суперпозиции и введения несущественных переменных (см, например, [38,41,42]). Будем называеть замкнутый класс А неконстантным, если А . С.
Пусть Т — множество булевых функций, содержащее все селекторные функции и замкнутое относительно операций введения несущественных переменных и переименования переменных (включая отождествление). Будем называть такие множества инвариантными классами. Поскольку равенство функций полагается с точностью до добавления и удаления фиктивных переменных, то операцию введения несущественных переменных в определении инвариантного класса можно опустить. Очевидно, что всякий замкнутый класс булевых функций, отличный от классов С, Со и Сі, является инвариантным. Необходимо подчеркнуть, что данное понятие инвариантного класса отличается от понятия инвариантного класса, введенного С.В.Яблонским (см., например, [39,40]). Отметим также, что инвариантный класс в описанном выше смысле является инвариантным классом в терминах, введенных в работах [12,13].
Критерии согласованности
Доказательство. Пусть частичная функция г является согласованной с классами S и Тої, и выполняются соответствующие условия согласованности. Построим доопределение функции г в классе SQ\. Рассмотрим множество доопределяющих функций частичной функции г. Обозначим это множество через F\. Очевидно, что F\ ф 0. Рассмотрим подмножество множества Ті, содержащее все функции /(#i,... ,хп) Є Ті, принимающие на нулевом и единичном наборах нулевое и единичное значение соответственно. Обозначим это множество через F i. Заметим, что согласно условию согласованности с классом Тої (утверждение 2.2.8), если существует такое о? Є Л, что а = (с,... , с) Є R, с Є {0,1}, то г(а) = с. Следовательно, Т2 Ф 0. Рассмотрим подмножество множества Т2, содержащее все функции f(xi,... , Хп) Є Т2, удовлетворяющие следующему условию: если для набора 7 длины п, отличного от нулевого и единичного, выполняются соотношения 7 Є R и 7 R, то /От) = /От), и, если для набора 5 = (ді,..., дп), отличного от нулевого и единичного, выполняются соотношения 6 R и 5 Л, то f(5) = 5\. Обозначим это множество через Тз. Очевидно, Тз Ф 0. Рассмотрим произвольную функцию /(жі,... ,хп) Є Тз. Несложно видеть, что функция / принадлежит классу 5оъ то есть / является искомым дополнением функции г в классе Soi, откуда следует требуемое утверждение.
В обратную сторону утверждение следует из леммы 2.1.2. Утверждение доказано. Следствие 2.2.21 Для любого инвариантного класса F выполнено равенство [SQ\\F = [S]F П [ТО]І? П [TI]F Утверждение 2.2.22 Пусть R С Еп, п 1, а r(xi,... ,хп) — частичная функция, определенная на множестве R. Функция г является согласованной с классом SM тогда и только тогда, когда она является согласованной с классами М, О2 и I2.
Доказательство. Пусть частичная функция г является согласованной с классами М, О2 и I2, и выполняются соответствующие условия согласованности. Построим доопределение функции г в классе SM. Рассмотрим множество доопределяющих функций частичной функции г. Обозначим это множество через F\. Очевидно, что F\ ф 0. Пусть 7 — набор длины п, такой, что существует набор а Є Т, такой, что J а, г (а) = 1. Множество всех таких наборов обозначим через Гі. Заметим, что это множество может быть пустым. Рассмотрим подмножество F2 множества Ті, содержащее все функции f(xi,..., хп) Є Ті, удовлетворяющих следующему условию: для любого набора j Є Ті выполняется соотношение /(7) = 1. В силу согласованности функции г с классом М, для любых двух наборов а, (З Є Т, таких, что а (3, для произвольной функции /(жі,... ,хп) Є Ті выполняется соотношение /(5?) /(/3). Следовательно, Т2 Ф 0. Пусть 7 набор длины п, такой, что существует набор а Є Т, такой, что J а, /(5?) = 0. Множество всех таких наборов обозначим через Го. Рассмотрим подмножество множества Т2, содержащее все функции /(жі,... , хп) Є Т2, удовлетворяющих следующему условию: для любого набора 7 Го выполняется соотношение /(7) = 0. Обозначим это множество через Тз. Аналогично доказывается, что Тз Ф 0. Несложно видеть, что R Є Го U Гі, Го П Г і = 0.
Докажем, что в множестве Го нет двух противоположных наборов. Предположим противное. Пусть существует такой набор 7 Є Го, что 7 Є Го. Согласно определению множества Го существуют такие наборы а,(3 Є Т, что 5? 7?/3 — 7?r(5?) = r{fi) = 0. Несложно видеть, что поскольку наборы 7 и 7 не имеют общей нулевой компоненты, то и наборы а и /3 не имеют общей нулевой компоненты. Следовательно, функция г не согласована с классом О2. Получили противоречие, следовательно, в множестве Го нет двух противоположных наборов. Аналогично доказывается, что в множестве Гі нет двух противоположных наборов.
Пусть Го — множество всех таких наборов д: что существует набор 7 Є Го, такой, что 5 = 7- Аналогично определим множество Гі. Из доказанного ранее следует, что Го П Го = 0, Г і П Г і = 0. Поскольку выполняется соотношение Го П Гі = 0, то также верно соотношение Го П Г і = 0. Рассмотрим подмножество множества F3, содержащее все функции f(xi,... ,хп) Є і з, удовлетворяющих следующему условию: на всех наборах из Го функция / принимает единичное значение, а на всех наборах из Гі — нулевое значение. Обозначим это множество через F . Из соотношений Го П Гі = 0, Го П Гі = 0, Го П Го = 0, Гі П Гі = 0 следует, что F Ф 0.
Докажем, что для любых наборов 7 и , таких, что выполняются соотношения 7 Гі U Го и 6 7, выполняется соотношение 6 Є Г і U Го. Действительно, если 7 Гі, то это утверждение выполняется согласно определению множества Гі. Если 7 Го, то выполняются соотношения 7 Є Го, 5 7, откуда согласно определению класса Го следует, что 5 Є Го, то есть 6 Є Го. Аналогично доказывается, что, для любых наборов 7 и , таких, что выполняются соотношения 7 Го U Г і и 6 7, выполняется соотношение 6 Є Го U Гі.
Рассмотрим множество Л = Еп \ (Гі U Го U Г і U Го). Несложно видеть, что для любого набора о? Є Л выполняется соотношение о? Є Л. Обозначим через Лі множество всех наборов из множества Л, в которых более единичных компонент либо ровно 7т единичных компонент и первая ком-понента равна 1. Положим Ло = Л \ Лі. Очевидно, что если а Є Ло, то а Є Лі.
Рассмотрим подмножество множества F4, содержащее все функции f(xi,..., хп) Є і 4, удовлетворяющих следующему условию: на каждом наборе из Лі функция / принимает единичное значение, а на каждом наборе из Ло — нулевое значение. Обозначим это множество через F$. Очевидно, что F5 Ф 0. Рассмотрим произвольную функцию f(xi,..., Хп) Є F ,. Докажем, что функция / является монотонной. Предположим противное. Тогда существуют такие два набора 7 и Iі , что выполняются соотношения 7о 7ь /(То) = 0, f(ll) = 1. Согласно доказанному ранее выполняется соотношение 7і і U о, поскольку иначе бы выполнялось соотношение ті) і U о, то есть /(то) = 1 (т. к. / Є F±). Аналогично доказывается, что выполняется соотношение То о U і. Отсюда следует, что ть Є о, 7і Є ь Но тогда либо 71 содержит больше единичных компонент, чем то, либо первая компонента 71 является единичной, а первая компонента ті) является нулевой. Следовательно, соотношение ті) 7і не верно. Получили противоречие. Следовательно, предположение не верно и функция / является монотонной.
Докажем, что функция / является самодвойственной. Предположим противное. Тогда существуют такие два набора 7 и 71, что выполняются соотношения 7 = 71, /(7) = / ("Г1). Не умаляя общности будем полагать, что /(7) = /(т1) = 1. Тогда заметим, что либо 7і Є і U о, либо 7і Є і. Отсюда следует, что либо 7 oUi, либо 7 о. Следовательно, /(71) = 0. Получили противоречие. Следовательно, предположение не верно и функция / является самодвойственной. Таким образом доказано, что функция / принадлежит классу SM, то есть / является искомым дополнением в этом классе, откуда следует требуемое утверждение.
Базовые P-пополнения классов L, U01 и SU
Обозначим через ф2 множество всех неконстантных замкнутых классов, а также классов получающихся из них добавлением констант. Обозначим через ф2 множество всех таких классов булевых функций Д что существует замкнутый класс булевых функций , такой, что А = В U В, а также классов, получающихся из этих классов одновременным добавлением обеих констант. Обозначим через 0 множество, состоящее из классов, содержащихся в 0, а также классов То П Gm , (То П Gm ) U {1}, Тої П GL П HL , GSL П HSL, Gsu П Hsu, т = 2,3, ...,оо, и двойственных к перечисленным. Обозначим через (5 множество, состоящее из классов, содержащихся в классе (5, классов ТіП/(5 оі),ТіП/(5 М), MoiC\l(SM), классов, получающихся из них добавлением констант, а также классов, двойственных перечисленным. Обозначим через 3 множество, состоящее из классов SuASiToP\(SuAS)iTiP\(SuAS), а также двойственных к перечисленным. Обозначим через множество, состоящее из классов, содержащихся в множестве , классов, получающихся из них добавлением констант, а также классов, двойственных к перечисленным.
Пусть F = S. Тогда согласно лемме 4.4.2 выполняется равенство [TO]F = Т2. Согласно следствию из утверждения 4.2.2 выполняется равенство [L]F = S U AS. Согласно лемме 3.2.2 выполняются соотношения
Лемма 4.9.3 Для произвольного замкнутого класса F из множества J-выполняется соотношение [SL]F Є ф2 U ф2. Доказательство. Пусть F Є {Тої, То, Ті, T,To,Ti, Om,/m, STv, 577}. Заметим, что согласно леммам 4.2.4 и 4.7.5 выполняются соотношения [L]p Є фг и [S]F фг. Поэтому согласно лемме 3.2.2 выполняются соотношения [SL]p = [L]F П [S]F Є фг.
Пусть F Є {і оь Ан, Мэь Тої, о\ Д, МО, МІ}. Заметим, что согласно леммам 4.2.4 и 4.7.5 выполняются соотношения [Ь]р = Р2 и [S]F = Тої U Тої. Согласно лемме 3.2.2 выполняются соотношения
Доказательство. Пусть А Є {Дн, Ті, m,Ti, і], Мі]}. Заметим, что выполняется соотношение А Є {і оь L/o, Om, To, OQ1, MOJ1}. Заметим, что для произвольного замкнутого класса из множества J- в этом множестве содержится класс, двойственный к данному. Следовательно, F Є Т. Тогда согласно леммам 4.6.6, 4.9.2, 4.5.10, 4.4.2, 4.9.7 выполняется соотношение [у4 ]_р Є G. Значит, из леммы 4.9.1 следует, что [А]р = ([А ]р ) G. Лемма доказана.
Доказательство. Заметим, что существует такой замкнутый класс В Є {і оь Ми, Мої, Uoi} и такое множество константных функций С Є {Со, Сі, С}, что А = В U С. Согласно утверждениям 4.6.7, 4.3.6, 4.2.7 и 4.9.1 выполняется соотношение [В]р Є 2UU(5. Согласно определениям классов ф2,ф2 Ф2,, и лемме 1.3.4 выполняются соотношения Лемма доказана. Лемма 4.9.10 Пусть выполняется соотношение А Є {МОт, М1т}. Для произвольного замкнутого класса F из множества J- выполняется соотношение [А]р Є G.
Доказательство. Заметим, что МОт = MOQ71 U {1}. Согласно лемме 1.3.4 выполняется равенство [МОт]р = [MO ]F U {1}. 1. Пусть F Є {Кої, Doi,L,Lo, Мої,To,Ti, Тої,0 ,1 , O0, Ii, MO0, MIX }, где к = 2,3,...,оо. Тогда согласно лемме 4.9.7 выполняется соотношене [МОт]р Є { 2, 0 U {1}, Ті, Тої U {1}, Мі, МОт, Om, МОк, Ок} С ф2. 2. Пусть Т Є {5 , Soi, SM}. Тогда согласно лемме 4.9.7 выполняется соотношение [МО]р Є (5, откуда согласно определению множества & следует, что [МОт]р Є (5.
Доказательство. Заметим, что U = SU U {0,1}. Согласно лемме 1.3.4 выполняется равенство [U]p = [SU]p U {0,1}. Согласно лемме 4.2.6 выполняется соотношение [SU]F Є Ф2 U фг. Согласно определениям классов ф2 и ф2 выполняется соотношение [U]F Є фг U ф2. Лемма доказана. Лемма 4.9.12 Для произвольного замкнутого класса F из множества J- выполняется соотношение [SM]p Є ф2 U6U6. Доказательство. Согласно лемме 3.2.2 и принципу двойственности выполняются соотношения
Таким образом, доказано, что для произвольного неконстантного замкнутого класса А и замкнутого класса Т, принадлежащего множеству Т, выполнено соотношение [А]р Є G.
Докажем, что [А]р Є G, если А — неконстантный замкнутый класс, а F — неконстантный замкнутый класс, не принадлежащий множеству J- . Заметим, что множество неконстантных замкнутых классов, не принадлежащих множеству Т, исчерпывается следующим списком:
Таким образом, если А и F — неконстантные замкнутые классы, то выполняется соотношение [А]р Є G. Таким образом, необходимость доказана.
Докажем теорему в обратную сторону. Докажем, что для произвольного класса И из G существуют такие замкнутые классы А и F, что И = [А]р. Перечислим всевозможные классы из G, не являющиеся замкнутыми. Согласно определениям множеств ф2 3, и & множество таких классов исчерпывается следующими списками. Ті П 1{SM). Согласно леммам 1.3.7 и 4.5.10 и принципу двойственности выполняется равенство \MIYl]sm = Мої П USM). Заметим, что согласно лемме 1.3.5, заменив в равенствах класс KQI на Ко, К\ или К, а класс 7 на MI, можно получить классы, получающиеся добавлением констант. Заменив оба класса А и F на двойственные им, можно получить оставшиеся двойственные классы.
Полнота в классе P2
В теории функциональных систем важное место занимают задачи классификации функций в соответствии с различными свойствами этих функций. Исследование свойств функций позволяет объединить эти функции в отдельные классы и зачастую помогает получить более полное понимание структуры функциональных множеств и на основе полученной классификации выделить некоторый более общий подход, применимый к другим задачам теории дискретных функций. Описание и изучение множеств функций, замкнутых относительно операции суперпозиции, является одним из наиболее известных подходов к решению задач классификационного характера. Классическим результатом в этой области является описание множества всех классов булевых функций, замкнутых относительно операции суперпозиции. Это описание было получено Э. Постом [46,47] в 1920 году. Как показал Пост, мощность множества классов булевых функций, замкнутых относительно операции суперпозиции, является счетной. Ю.И.Янов и А. А. Мучник [43] установили, что в /с-значной логике при к 3 существуют примеры замкнутых классов, не имеющих базиса, а также классов со счетным базисом. Отсюда, в частности, следует, что множество всех замкнутых классов /с-значной логики при к 3 имеет континуальную мощность, что значительно затрудняет исследование.
В связи с указанными трудностями в изучении классов функций k-значной логики в научной литературе были предложены несколько подходов, позволяющих в некоторой степени избегать эти трудности. Один из таких подходов заключается в рассмотрении различных усилений операции суперпозиции, позволяющих получить более просто устроенную решетку классов функций k-значной логики, замкнутых относительно данных усилений. Другой подход состоит в изучении различных фрагментов решетки замкнутых классов в Pk, в частности, фрагментов, состоящих из всех замкнутых классов, содержащих в качестве подмножества некоторый заданный замкнутый класс (такой фрагмент обычно называют надрешеткой этого класса).
Перечислим работы, относящиеся к первому направлению исследований. В работах С.С.Марченкова [16–18] и Нгуен Ван Хоа [26–28] исследуется S-замыкание, в котором наряду с операцией суперпозиции применяется операция перехода к двойственным функциям относительно фиксированной группы подстановок. Другими словами, S-замкнутый класс для каждой принадлежащей ему функции содержит также всякую двойственную ей относительно указанной группы подстановок функцию. Таким образом, авторами изучается структура решетки замкнутых классов функций k-значной логики при отождествлении похожих, в определенном смысле, функций. В частности, для симметрической группы множества Ek в этих работах установлено, что множество S-замнутых классов функций k-значной логики для любого k 3 конечно.
В работе А.В.Кузнецова [11] вводятся понятия параметрической выразимости и параметрического замыкания. В этой работе получено описание параметрически замкнутых классов булевых функций. В работе А.Ф.Данильченко [5] показано, что при k = 3 множество параметрически замнутых классов функций k-значной логики конечно, а в работе C.Барриса и Р.Уилларда [45] аналогичное утверждение доказано для k 3.
В работах Ю.В.Голункова и О.В.Андреевой [2, 4], В.А.Тайманова [32, 33] и В.Д.Соловьева [31] изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа. Каждая операция программного типа определяется своим множеством предикатов. В работах В.А.Тайманова показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума.
В работах А. В.Кузнецова [11], О. М. Касим-Заде [6,8,10], Е. А. Ореховой [30] и Е.В.Михайлец [21,22] рассматриваются классы функций, допускающих неявное представление над некоторой системой функций.
В работах О.С.Тарасовой [34–36] исследуются классы k-значной логики, k 2, замкнутые относительно операций суперпозиции и перестановки с множеством наборов специального вида.
В ряде работ рассматривается классификация функций многозначной логики, не связанная с замыканием относительно суперпозиции, посредством введения классов функций, инвариантных относительно иных операций. В частности, в работах С.В. Яблонского [39,40], О. М.Касим-Заде [7,9] и Г.Г.Аманжаева [1] рассматриваются классы, инвариантные относительно подстановки некоторого множества функций одной переменной. В работах Ю.В.Кузнецова [12, 13] рассматриваются классы, инвариантные относительно отождествления переменных.
Необходимо отметить, что существуют также подходы к классификации функций k-значной логики на основе их свойств. Так, например, работах Нгуена Ван Хоа [23–25] изучается подход, состоящий в разбиении множества замкнутых классов функций k-значной логики на классы эквивалентности, где отношения эквивалентности определяются свойствами входящих в них функций.
Дополнительный обзор результатов, полученных в этом направлении, содержится, например, в [35]. Теперь отметим работы, относящиеся ко второму направлению исследований. В работе Г.А.Бурле [3] описана надрешетка класса Uk всех функций k-значной логики от одной переменной, и показано, что эта надрешетка содержит конечное число замкнутых классов. В работе И.Розенберга [48] описаны все минимальные классы в Рk, содержащие все селекторные функции, и показано, что при фиксированном к их конечное число. В работе А. А. Нечаева [29] описаны все предполные классы, содержащие класс полиномов. В работе С. С. Марченкова [19] были описаны все классы в Рk, содержащие дуальный дискриминатор, т. е. функцию вида
В работе Бейкера и Пиксли [44] показано, что множество таких классов при фиксированном к конечно. В работе В. Б Ларионова [14] исследуются надрешетки замкнутых классов, состоящих из самодвойственных или монотонных функций /с-значной логики.
Отметим, что даже в случае такого узкого класса, как Uk, надрешетка этого класса является конечной и очень просто устроенной. Тем самым рассмотрение надрешеток замкнутых классов в значительной части случаев представляет собой чрезмерное упрощение задачи описания структуры решетки замкнутых классов в Рk. Поэтому представляет интерес выработка новых подходов к изучению решетки классов в Pk, являющихся в некотором смысле промежуточными между подходом, связанным с изучением отдельных надрешеток в Pk и непосредственным изучением всей решетки замкнутых классов функций /с-значной логики. В качестве одного из таких подходов в настоящией работе предлагается некоторое обобщение операции суперпозиции. Для корректного обоснования данного обобщения заметим, что задачу описания надрешетки некоторого фиксированного класса F функций /с-значной логики можно переформулировать следующим образом. Вместо стандартной операции суперпозиции для функций /с-значной логики мы можем рассмотреть модифицированную операцию суперпозиции, заключающуюся в реализации функций формулами, в которых помимо функциональных символов функций из исходного порождающего функционального множества могут быть также использованы функциональные символы любых функций из F. Тогда надрешетка класса F в точности совпадает с решеткой функциональных классов, замкнутых относительно данной модифицированной операции суперпозиции.
