Чтобы оставить комментарий, нужно зарегистрироваться.
Похожие темы научных работ
по математике, автор научной работы — ПАРВАТОВ НИКОЛАЙ ГЕОРГИЕВИЧ
Текст научной работы
на тему "СООТВЕТСТВИЕ ГАЛУА ДЛЯ ЗАМКНУТЫХ КЛАССОВ ДИСКРЕТНЫХ ФУНКЦИЙ". Научная статья по специальности "Математика"
2010 Теоретические основы прикладной дискретной математики №2(8)
УДК 519.7
СООТВЕТСТВИЕ ГАЛУА ДЛЯ ЗАМКНУТЫХ КЛАССОВ ДИСКРЕТНЫХ ФУНКЦИЙ1
Н. Г. Парватов
Томский государственный университет, г. Томск, Россия
E-mail: parvatov@mail.tsu.ru
Формулируется теория Галуа для S-замкнутых классов дискретных функций, совпадающих в частных случаях с замкнутыми суперпозицией классами функций многозначной логики, с клонами, с наследственными системами дискретных функций, а также с классами функций, вычисляемых схемами из переключательных элементов.
Ключевые слова: замкнутый класс, клон, предикат, сохранение предиката, соответствие Галуа, дискретная функция.
Введение
Один из классических объектов изучения дискретной математики — системы дискретных функций, рассматриваемые с замыканием относительно некоторых операций суперпозиции, таких, как операции перестановки и отождествления переменных, введения и удаления фиктивных переменных, операция композиции и другие. Подобными системами являются, например, замкнутые классы функций многозначной логики, клоны, наследственные системы, а также системы переключательных функций, вычисляемых схемами из переключательных элементов.
Следует отметить, что при изучении замыкания, заданного в некотором множестве P, часто важной оказывается возможность рассматривать это замыкание как замыкание Галуа, определяемое некоторым соответствием Галуа [1]. Последнее задаётся обычно посредством отношения а С P х Q между элементами множества P и элементами некоторого множества Q. Тогда замкнутыми классами элементов множества P являются его галуа-замкнутые классы
a(Y) = П а(у) при y с Q,
yeY
где а(y) = {х : (x,y) Е а} для любого у из Q, находящиеся во взаимно-однозначном соответствии с галуа-замкнутыми классами множества Q, то есть с классами
(X)а = П (х)а при X С P,
xEX
где (х)а = {х : (х, у) Е а} для любого х из P .В этом случае изучение замыкания в множестве P сводится к изучению замыкания Галуа в множестве Q и наоборот.
Так, при изучении клонов существенную роль играет соответствие Галуа, определяемое отношением сохранения функцией f : En ^ E предиката p : Em ^ {И, Л}.
1 Исследование выполнено при финансовой поддержке ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, гос. контракт № П1010.
В [2, 3] показано, что галуа-замкнутыми классами функций в этом случае являются всевозможные клоны на множестве Е, там же описаны галуа-замкнутые классы предикатов. Впоследствии эти результаты неоднократно обобщались.
При изучении наследственных систем функций f : Еп ^ С (то есть систем, замкнутых операциями отождествления и перестановки переменных, введения фиктивных переменных) большое значение имеет соответствие Галуа, определяемое отношением сохранения такими функциями пар предикатов р : Ет ^ {И, Л} и д : Ст ^ {И, Л}. В [4] показано, что галуа-замкнутыми классами функций в этом случае являются наследственные системы, там же описаны галуа-замкнутые классы пар предикатов.
Отметим также работы [5, 6]. В первой из них теория Галуа сформулирована для клонов многоосновных алгебр, состоящих из функций, вычисляемых термами с переменными нескольких сортов, а во второй — для систем функций f : Еп ^ С, замкнутых операциями перестановки переменных и введения фиктивной переменной.
В настоящей работе рассматриваются функции f : Еп ^ С, где Е и С — фиксированные конечные множества, а п принимает произвольные натуральные значения. В множестве Рс,е всех таких функций определяется операция Б-замыкания. В частных случаях Б-замкнутыми классами являются замкнутые классы функций многозначной логики, клоны, наследственные системы, а также классы переключательных функций, вычисляемых схемами из переключательных элементов. Теорию Галуа, сформулированную в [4] для наследственных систем, удаётся перенести на Б-замкнутые классы. Таким образом удаётся построить обобщённую теорию Галуа, в частных случаях включающую известные результаты для замкнутых классов функций многозначной логики, клонов и наследственных систем, а также ранее не известные результаты о классах функций, вычисляемых переключательными схемами.
Статья организована следующим образом. В п. 1 вводится понятие Б-замыкания. В п. 2 рассматривается отношение сохранения функцией пары предикатов. Это отношение рассматривается как отношение между функциями, принадлежащими множеству Рс,е, и парами предикатов, выбираемых из некоторого множества ПСе. Множество ПС е удаётся определить таким образом, что галуа-замкнутыми классами функций оказываются точно все Б-замкнутые классы функций из Рс,е . Это устанавливается теоремой 1. В п. 3 доказывается теорема 2, характеризующая галуа-замкнутые классы пар предикатов как классы, замкнутые некоторым набором операций.
Основная задача статьи — сообщить о возможности обобщения теории Галуа, единого для замкнутых классов функций многозначной логики, клонов, наследственных систем и систем переключательных функций. Само обобщение не является сложной задачей и, по всей видимости, может быть выполнено формально. Тем не менее автору удалось найти оригинальное доказательство теоремы 2, не повторяющее полностью схем рассуждений, использованных в аналогичной ситуации в [2] или в [3, 4].
1. Замкнутые классы дискретных функций
Будем обозначать через Ре множество всех функций f : Еп ^ Е, где Е — фиксированное конечное множество и п — произвольное натуральное число. Замкнутые операциями суперпозиции из [7, 8] множества функций из Ре называются замкнутыми классами, а замкнутые классы, включающие класс Бе всех селекторных (тождественно равных некоторому своему аргументу) функций, называются клонами.
Будем обозначать через Рс,Е множество всех функций f : Еп ^ С, где Е, С — фиксированные конечные множества и п — произвольное натуральное число. Для заданных конечных множеств Е, С и Д, а также множеств X и У функций из соответ-
ствующих классов Р_о,с и Рс,е через XY будет обозначаться множество всех функций f (^(х),... , $п(х)), где f — п-местная функция из X; $1,... , $п — ш-местные функции из У; через х обозначен набор переменных х1,... , хт, а числа п и ш принимают произвольные натуральные значения.
Далее будем считать заданными конечные множества Е и С и набор Б = (Ь,О, Я, и), состоящий из клонов Ь, Я и множеств О, и функций из соответствующих классов Рс, Ре и РС,е, Ре,С. Множество М функций из РС,е назовём Б-замкнутым классом, если выполняются включения
О С М, ЬМЯ С М, мим С М.
Частными случаями Б-замкнутых классов являются замкнутые классы и клоны функций из Ре (возникающие при выполнении равенств Е = С и Ь = Я = и = Бе и соответствующего равенства О = 0 или О = Бе), а также изучавшиеся в [4, 9] (Ь, Я)-замкнутые наследственные классы (возникающие при пустых множествах и и О). Это делает Б-замкнутые классы привлекательными для изучения.
Помимо этого, Б-замкнутые классы имеют приложения в теории управляющих систем как классы функций, вычисляемых схемами из переключательных элементов с неограниченным числом каскадов. При этом элементы множеств Е и С интерпретируются соответственно как состояния узлов и как проводимости между узлами, возможные в схемах. Функции клонов Ь и Я интерпретируются как допустимые используемой технологией синтеза операции над проводимостями и состояниями. В множестве О находятся функции переключательных элементов, используемых при синтезе наравне с базисными переключательными элементами. Наконец, множество и состоит из функций узлового соединения, каждая из которых определяет состояние произвольного узла схемы набором проводимостей от него до полюсов питания. Очень часто в схемах с г-полюсным источником питания состояние любого узла однозначно определяется набором проводимостей от него до полюсов питания; тогда множество Е совпадает с Сг, а множество и состоит из единственной тождественной функции и(г) : Сг ^ Е. Естественной также является ситуация, когда в дополнение к сказанному выше множество О содержит все селекторы : Е ^ С, такие, что зг(х) = хг; при этом переменная х = (х1,...,хг) принимает значения в множестве Е = Сг, её г-я компонента хг принимает значения в множестве С и 1 ^ г ^ г. Следует отметить, однако, что в этом последнем случае при выполнении равенств Е = Сг и Ь = Бе, О = {з1,... ,}, Я = Бс, и = {и(г)} изучение Б-замкнутых классов сводится к изучению клонов функций из Ре, чего нельзя гарантировать в других случаях.
2. Сохраняемые пары предикатов
Обозначим через Пе множество всех ш-местных предикатов р : Ет ^ {И, Л} при всевозможных натуральных ш. Пару (р1,р2) ш-местных предикатов из соответствующих множеств Пс и Пе будем называть ш-местным 2-предикатом на паре множеств С и Е. Множество всех таких 2-предикатов при всевозможных натуральных ш обозначим через ПС,е. Говорят, что п-местная функция f из РС,е сохраняет ш-арный 2-предикат, (р1,р2), если для любых наборов Х1,... ,Хп, удовлетворяющих предикату р2, набор У = f N (Х1,...,Хп) удовлетворяет предикату р1 . При этом набор У состоит из значений функции f, вычисленных последовательно от строк матрицы (Х^,... ,Х_Т), где верхний индекс Т означает транспонирование. Если при совпадающих множествах Е и С предикаты р1 и р2 также совпадают, то говорят о сохранении функцией f предиката р1. В этой ситуации предикат р удобно отождествить с 2-предикатом (р,р).
Обозначим через ро1СЕ (У) множество всех функций из Рс,е , сохраняющих все 2-предикаты множества У С Пс,е. Через шус,е (Х) будем обозначать множество всех 2-предикатов из Пс,е , сохраняемых всеми функциями из множества Х С Рс,е. Положим также
ПС,е = (тус(Ь) х шуе(Я)) П тус-Е(О) П ту'Е,с(и); тус,Е(У) = ПС,е П 1ПУс,е(У),
где 1пуЕс(и) —множество 2-предикатов (р2,р1), полученных перестановкой координат у 2-предикатов (р1,р2) из класса 1ПуЕ,с(и).
Предметом данного исследования является соответствие Галуа между системами подмножеств в Рс,е и ПСе, определяемое отношением сохранения функцией из Рс,Е 2-предиката из ПСе. При пустых множествах О и и это отношение изучалось в [2, 3]. А при выполнении равенств С = Е и Ь = О = Я = и = Бе это отношение по сути совпадает с изучавшимся в [2, 3] отношением сохранения функцией из Ре предиката из Пе (и совпадает с ним формально, если всякий 2-предикат (р,р) из ПСе отождествить с предикатом р из Пе). В обоих упомянутых случаях галуа-замкнутыми классами функций являются Б-замкнутые классы. Это свойство выполняется и в общем случае, так как имеет место
Теорема 1. Для любого множества N 2-предикатов из ПСе множество ро1СЕ(Ж) является Б-замкнутым классом функций из Рс,е. Для любого Б-замкнутого класса М функций из РС,е имеет место равенство М = ро1СЕ(шуСе(М)).
Доказательство. Первое предложение теоремы проверяется непосредственно. Во втором — включение М С ро1сЕ(1пуС е(М)) очевидно. Докажем обратное включение. Для этого рассмотрим произвольную п-местную функцию f из множества ро1с е(шуС е(М)). Пусть ш = |Е|п и наборы Х1,... ,Хп выбраны в множестве Ет так, что множество строк матрицы (ХТ,...,Х_Т) совпадает с Еп. Рассмотрим ш-арный 2-предикат (р1,р2) из Пс, е, такой, что предикату р2 удовлетворяют всевозможные наборы $[т] (Х1,... , Хп), где п-местная функция $ принадлежит множеству Я(иМи Бе), а предикату р1 удовлетворяют всевозможные наборы $[т](Х1,... ,Хп), где п-местная функция $ принадлежит множеству М. Непосредственно проверяется, что этот 2-предикат принадлежит множеству шуСе(М) и, следовательно, сохраняется функцией f. Тогда, поскольку наборы Х1,...,Хп удовлетворяют предикату р2, набор f [т1(Х1,...,Хп) удовлетворяет предикату р1. Это означает, что для некоторой функции $ из М выполняется равенство f [т](Х1,..., Хп) = $[т](Х1,..., Хп). Так как в строках матрицы (ХТ,... , Х_Т) содержатся все наборы из Еп, то функции f и $ совпадают. Таким образом, функция f принадлежит классу М. Теорема доказана.
Итак, теорема 1 характеризует классы функций из Рс , е, сохраняющих множества 2-предикатов из ПС е. Классы 2-предикатов, сохраняемых множествами функций, будут охарактеризованы в п. 3.
3. Замкнутые классы пар предикатов
Введём в рассмотрение необходимые далее операции над 2-предикатами из Пс,е. Конъюнкцией п- и ш-местных 2-предикатов (р1,р2) и (д1,д2) из ПС,е будем называть (п + ш)-местный 2-предикат (г1, г2) из ПС,е, где
гДхЬ . . . ,хп+т) = Рг(х1, . . . , хп) Л &(хп+1, . . . , хп+т)
для г = 1, 2. Проекцией п-местного 2-предиката (р1,р2) по ]-й координате будем называть 2-предикат (р1,р2), где
р'(хь . . . ,х^_1,х^+1, . . . ,хп) = Зх, (Рг(х1, . . . ,хп))
для г = 1, 2. Для п-местного предиката р из Пе и набора I чисел г1,... , гп из множества {1,... , ш} положим
р1т)(х1, ...,хт) = р(х41, . . . ,х^п ).
Тогда для п-местного 2-предиката (р1,р2) будем говорить, что ш-местный 2-предикат (рй*^)) получен из 2-предиката (р1 ,р2) подстановкой переменных. Наконец, 2-предикат (р1,р2) будем называть 2-диагональю, если предикаты р1,р2 — тождественно истинные или тождественно ложные, или оба выражаются одной и той же формулой вида хг = х^- Л ... Л х^ = х8, интерпретируемой в соответствующих множествах С и Е.
Множество 2-предикатов из класса ПСе, включающее все 2-диагонали, назовём Б-замкнутым, если оно содержит конъюнкцию любых двух своих 2-предикатов, вместе с любым своим 2-предикатом содержит все его проекции и все 2-предикаты, получаемые из него подстановкой переменных, а также вместе с любым своим ш-местным 2-предикатом (р1,р2) содержит всякий ш-местный 2-предикат (д^д2) из ПСе, такой, что р1 С д1 и д2 С р2. При этом включение р С д для ш-местных предикатов р и д из Пе (или из Пс) означает, что для любого набора х из множества Ет (соответственно из Ст) верна импликация р(х) ^ д(х). Имеет место
Теорема 2. Для любого множества М функций из РС,е множество шуСе(М) является Б-замкнутым классом 2-предикатов. Для любого Б-замкнутого класса N 2-предикатов верно: N = шуСе(ро1с,Е(Ж)).
Доказательство. Для доказательства можно воспользоваться схемой рассуждений из [2] или из [3, 4]. Приведём, однако, независимое доказательство. Первое предложение теоремы проверяется непосредственно; во втором — включение N С шуСе(ро1СЕ(Ж)) очевидно. Докажем обратное включение. Для этого выберем произвольно /-арный 2-предикат (р1,р2) в множестве шуС е(ро1с Е(N)). Пусть предикату р2 удовлетворяют наборы Х1,... ,Хп из множества Е1, и только они. Дополним их до наборов ^1,... , ^п из множества Ет при некотором ш ^ / (добавив ш — / новых координат к каждому набору) так, чтобы в строках матрицы (^Т,... , ) со-
держались все наборы из множества Еп. Очевидно, это можно сделать. Рассмотрим ш-местный 2-предикат (д1 , д2), где предикату д2 удовлетворяют всевозможные наборы $[т](^1, . . . , ^п) для всевозможных п-местных функций $ из Я(иро1с Е(N) и Бе), а предикату д1 — наборы $[т] (^1,... , ^п) для всевозможных п-местных функций $ из ро1с е^). Можно проверить непосредственно, что 2-предикат (д1,д2) принадлежит
классу 1ПуС,Е (ро1С,Е(N)).
Для 2-предиката (д/, д2), полученного из (д1,д2) проектированием по добавленным ш — / координатам, верно, что р2 С д2 и д/ С р1. Отсюда, поскольку класс N Б-замкнут, для завершения доказательства достаточно показать, что 2-предикат (д1,д2) принадлежит классу N. Для этого рассмотрим 2-предикат (д//,д2/), такой, что
д"(хь . . . ,хт) = Л г г (х1, . . . ,!т)
А
для г = 1, 2, где конъюнкция вычисляется по всем ш-местным 2-предикатам (г1,г2) из N, таким, что д2 С г2. Множество таких 2-предикатов (г1,г2) обозначено выше
буквой A. Очевидно, что 2-предикат (qi,q20 вслед за 2-предикатами из множества A принадлежит классу N и выполняется включение q2 С ?2. Докажем включение q'( С qi (тогда из принадлежности 2-предиката (q;/, q2') S-замкнутому классу N следует принадлежность 2-предиката (qi, q2) тому же классу, и всё доказано). Выберем произвольно набор Z0, удовлетворяющий предикату q", и определим n-местную функцию g из Pe при помощи выражения g[m](Zi,... , Zn) = Z0. Функция g определена корректно. Действительно, если в матрице (Z^,... , Z^) k-я и j-я строки совпадают, то множеству A принадлежит 2-предикат (ri,r2), где
ri(xi, . . . ,Xm) = xfc = Xj
при i = 1, 2. Следовательно, k-я и j-я координаты совпадают у всех наборов, удовлетворяющих предикату q;/, в частности у набора Z0. Аналогично, функция g сохраняет все предикаты из N. Действительно, если t-местный 2-предикат (r^, r2) принадлежит классу N и предикату r2 удовлетворяют наборы (Zj,i1,... , Zj,it) (через Zj,j обозначена i-я координата набора Zj) при 1 ^ j ^ n, то множеству A принадлежит 2-предикат ( r 1 , r2 ) , где
ri (xi, ...,Xm) = ri (Xii, . . . ,Xit)
при i = 1, 2. Отсюда набор Z0 удовлетворяет предикату ri, а набор (Z0,i1,... , Z0,it) — предикату r\. Функция g, таким образом, сохраняет 2-предикат (r^, r2).
Итак, функция g сохраняет все предикаты из множества N и принадлежит, таким образом, классу polCe(N). Функция g сохраняет, следовательно, и принадлежащий множеству invCE(polCE(N)) 2-предикат (qi,q2). Отсюда, так как наборы Zi,...,Zn удовлетворяют предикату q2, то набор Z0 = g[m](Zi,... , Zn) удовлетворяет предикату qi. Включение q[ С qi доказано. Теорема доказана.
ЛИТЕРАТУРА
1. Курош А. Г. Лекции по общей алгебре. СПб.: Изд-во «Лань», 2005.
2. Боднарчук В. Г., Калужнин Л. А., Котов В. Н., Ромов Б. А. Теория Галуа для алгебр Поста // Кибернетика 1969. №3. С. 1-10; №5. С. 1-9.
3. Geiger D. Closed systems of functions and predicates // Pacific journal of mathematics. 1968. V. 27. No. 1. P. 95-100.
4. Pippenger N. Galois theory for minors of finite functions // Discrete Mathematics. 2002. V. 254. P. 405-419.
5. Poshel R., Kaluznin L. A. Funktionen- und Relationenalgebren. Berlin: WEB Deutscher Verlag der Wissenschaften, 1979.
6. Hellerstein L. On generalized constraints and certificates // Discrete Mathematics. 2001. V. 226. P. 211-232.
7. Мальцев А. И. Итеративные алгебры Поста. Новосибирск: Изд-во Новосиб. ун-та, 1976.
8. Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1966. Т. 5. № 2. С. 5-24.
9. Парватов Н. Г. Наследственные системы дискретных функций // Дискрет. анализ и ис-след. операций. Сер. 2. 2007. Т. 14. №2. С. 76-91.
