О порождении одноместных монотонных функций многозначной логики

(5, 3), (5, 5), (9). Теоремы 4-6 описывают первые семь из этих девяти случаев; для последних двух случаев вопрос о том, является ли фактор V/G (гладким) многообразием, остается открытым.

Теорема 4. Предположим, что последовательность (ni) совпадает с одной из последовательностей (4, 4), (4, 3) и (3, 3, 3). Тогда фактор V/G0 диффеоморфен вещественному векторному пространству размерности dim V — 3, причем группа G/G0 действует на нем линейно.

Замечание. Теорема 4 позволяет свести произвольное представление G : V, для которого последовательность (ni,...,n) совпадает с одной из последовательностей (4, 4), (4, 3) и (3, 3, 3), к линейному представлению конечной группы G/G0 в векторном пространстве V/G0.

Теорема 5. Если G = G0 и (ni,..., щ) = (5, 4), то фактор V/G не является гладким, многообразием.

Теорема 6. Если G = G0, а последовательность (ni,..., щ) совпадает с одной из последовательностей (7), (8), (5, 3), то фактор V/G гомеоморфен вещественному векторному пространству размерности dim V — 3.

СПИСОК ЛИТЕРАТУРЫ

1. Стырт О.Г. О пространстве орбит компактной линейной группы Ли с коммутативной связной компонентой // Тр. Моск. матем. о-ва. 2009. 70. 235-287.

2. Михайлова М.А. О факторпространстве по действию конечной группы, порожденной псевдоотражениями // Изв. АН СССР. Сер. матем. 1984. 48, № 1. 104-126.

Поступила в редакцию 23.04.2010

УДК 511

О ПОРОЖДЕНИИ ОДНОМЕСТНЫХ МОНОТОННЫХ ФУНКЦИЙ

МНОГОЗНАЧНОЙ ЛОГИКИ

Д. Ю. Панин1

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

Ключевые слова: функции многозначной логики, одноместные функции, замыкание, полные системы.

A set of unary monotone functions of the multi-valued logic is considered. These functions are monotone with respect to a partial order of special form. The composition and convolution operations are introduced. A criterion for the completeness of the functional system is obtained.

Key words: functions of multi-valued logic, unary functions, closure, complete systems.

В работе рассматривается некоторое множество одноместных функций многозначной логики, монотонных относительно частичного порядка специального вида. Вводятся операции композиции и свертки. Получен критерий полноты для рассматриваемой функциональной системы. Подобные вопросы возникают при изучении свойств предполных классов монотонных функций, не имеющих конечных порождающих систем [1-4], а также при решении задачи о полноте систем функций многозначной логики (см., например, [5-9]).

Пусть n ^ 1. Положим Qk = |0,ai,a'i,...,ak, a'fc}, где 0 ^ k ^ n. Положим Q = Qn, a0 = a0 = 0. Введем на элементах множества Q отношение частичного порядка ^ следующим образом:

1) £ ^ £j для всех £i, £j, таких, что £i G (a^, a^}, £j G (aj, aj}, 0 ^ i < j ^ n;

2) £ ^ £ для всех £ G Q.

Пусть a, в G Q. Если для этих элементов выполняется по крайней мере одно из соотношений a ^ в, в ^ а, то эти элементы называются сравнимыми, в противном случае — несравнимыми.

1 Панин Дмитрий Юрьевич — студ. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: pank.dm@gmail.com.

Будем обозначать через F множество всех функций f (ж), определенных на множестве Q, принимающих значения из Q, монотонных относительно частичного порядка ^ и таких, что f (5) ^ 5 для всех 5 G Q. Введем на множестве F операции композиции и свертки. Пусть f (ж), д(ж) G F. Композицией функций f и д будем называть функцию (f о д)(ж), значение которой на любом элементе а G Q определяется равенством (f о g)(a) = f (д(а)). Сверткой функций f и g будем называть функцию (f * д)(ж), значение которой на любом элементе а G Q определяется следующим образом:

(f * д)(а) Л а' если д(а)=0;

I f (а), если д(а) = 0.

Пусть A С F. Определим по индукции понятие формулы над A, а также понятие функции, реализуемой формулой.

1. Выражение вида f(ж), где f(ж) G A, является формулой над A. Такая формула называется тривиальной и реализует функцию f(ж).

2. Пусть Ф1 — формула над A, реализующая функцию Д(ж), а Ф2 — формула над A, реализующая функцию f2^). Тогда выражения Ф1 о Ф2 и Ф1 * Ф2 являются формулами над A и реализуют функции (fi о f2)(ж) и (fi * f2) (ж) соответственно.

При этом предполагается, что других формул над A нет. Замыканием множества A С F будем называть множество всех функций, которые могут быть реализованы формулами над A (обозначение < A >). Очевидно, что < A > С F. Систему A будем называть полной, если < A > = F. Сложностью формулы Ф над A будем называть число символов о и * в формуле Ф (обозначение £(Ф)). Сложностью функции f из множества < A > будем называть величину L(f) = min £(Ф), где минимум берется по всем формулам Ф над A, реализующим функцию f.

Цепью длины m, 1 ^ m ^ n + 1, будем называть последовательность элементов bo, bi, 62,..., bm-i G Q, таких, что bo = 0, bi G (ai, ai} для всех i = 1,...,m — 1. Множество всех цепей длины m будем обозначать через Cm.

Пусть Q С Q. Положим

Sn = (f G F | f (5) = 5 для всех 5 G Q}, NSn = (f G F | f (5) = 5 для всех 5 G Q}.

В частности, S{„n} — множество всех функций из F, сохраняющих элемент an.

Пусть Q — произвольная цепь длины n (n ^ 1). Нетрудно показать, что каждое из множеств

Sn П Sw} П NS{<}, Sn П NSW} П SK}, Sn П NSW} П NSK}

содержит ровно одну функцию. Обозначим эти функции через дп, дП, дП соответственно. Определим семейство G множеств функций из F следующим образом. Семейство G состоит из всех множеств A С F, таких, что для каждой цепи Q длины n выполнено по крайней мере одно из следующих двух условий:

дП G A, (дп,дП}С A.

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

1) д(а n) = ani д(аП) = an,

2) найдутся номер k, 2 ^ k ^ n, и цепь Q длины k — 1, такие, что д G Sn и (д(ак),д(а&)} = (a^-i, a'fc-i}.

Положим

Go = Gi U [J (дП,дп,дП}-

пеСг

Имеет место следующее необходимое условие полноты для систем функций из F.

Теорема 1. Пусть G — произвольная полная система. Тогда Gi С G и существует множество G2 G G, такое, что G2 С G.

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

Лемма 1. Пусть fif G F, д G Gi и д = f2 * fi или д = f2 о fi. Тогда f2 = д или fi = д.

При доказательстве леммы рассматриваются два случая: д = f2 * fi и д = f2 о fi . В первом случае устанавливается, что при всех 5 G Q выполняется равенство f2(5) = 0, из которого следует, что fi = д. Во втором случае из определения множества Gi следует, что найдутся номер k и цепь Q длины k — 1, такие,

что д £ £п и {д(а^),д(ак)} = {а^_1, ак_1}. После этого доказывается, что функции /2 и /1 принадлежат

множеству £п. Затем показывается, что найдется функция / £ {/1, /2}, такая, что равенство /(5) = д(5) выполнено для всех 5 £ Q \ ^-1, а значит, / = д.

Аналогичным образом устанавливается справедливость следующей леммы.

Лемма 2. Пусть О — произвольная цепь длины п (п ^ 1), /1, /2 £ ^ и д = /2 о /1 или д = /2 * /1. Тогда верны следующие утверждения:

1) если д £ |дп,дп}, то или /2 = д, или /1 = д, или /2 = д00;

2) если д = д00 , то или /2 = д, или /1 = д, или {/1, /2} = |дп,дп}.

Доказательство теоремы 1. Пусть О — произвольная полная система. Докажем сначала соотношение О1 С О. Пусть / — произвольная функция из О1. Покажем, что если / /О, то / / < О >. Доказательство будем вести индукцией по сложности £(/) функции /. Если £(/) = 0, то утверждение очевидно. Пусть теперь £(/) = к, к > 0. То есть найдется формула Ф над О, реализующая функцию /, такая, что £(Ф) = к. Тогда Ф = Ф2VФl, где V £ {о, *}, а Ф2, Ф1 — формулы над О, реализующие некоторые функции /2, /1 соответственно и такие, что £(Ф2),£(Ф1) < к. Тогда / = ^▽/1 и ¿(/2)^/1) < к. Из леммы 1 следует, что /2 = / или /1 = /. Поэтому £(/) < к, что противоречит равенству £(/) = к.

Докажем теперь, что найдется множество О2 £ 0, такое, что О2 С О. Предположим, что О2 ^ О для всех О2 £ 0. То есть найдется цепь О длины п, такая, что функция д00 и хотя бы одна из функций дп, д^ не принадлежат множеству О. Рассмотрим случай дп / О (другой случай рассматривается аналогично). Докажем индукцией по т, что £(дП),£(дП) > т. Для т = 0 это утверждение следует из предположения (дП,дп / О). Пусть неравенство £(д) > к выполнено для всех д £ {дП,дп}. Докажем, что соотношение £(д) > к + 1 имеет место для всех д £ {дП,дп}. Пусть £(д) = к + 1, где д £ {дП,дп}. То есть найдется формула Ф над О, реализующая функцию д, такая, что £(Ф) = к + 1. Аналогичным образом получаем равенство д = ^▽/1, где ¿(/2)^/1) ^ к и V £ {о, *}. Рассмотрим два случая.

Пусть д = дп. Тогда из леммы 2 следует, что или /2 = дп, или /1 = дп, или {/1, /2} = {дп,дп}. Если /2 = дп или /1 = дп, то £(дп) ^ к, что противоречит неравенству £(дп) > к. Если же {/1, /2} = {дп,дп}, то Ь(дп) ^ к, что противоречит неравенству Ь(дп) > к. Случай д = дп рассматривается аналогично.

Таким образом, £(дп),Ь(дп) > к + 1. Поэтому найдется множество О2 £ 0, такое, что О2 С О. Теорема доказана.

Пусть / £ ^, Q/ С Q. Положим 1ш(/, Q/) = {/(5) | 5 £ Q/}.

Будем обозначать через Н(т,й), 0^ й< т ^ п, множество всех функций из ^, для которых выполнены следующие условия:

1) {/(ат),/(ат)} = {ат_й,ат_й};

2) элементы /(а^) и /(а^) сравнимы для всех j = 1,...,т — 1.

Имеет место следующее достаточное условие полноты для систем функций из ^.

Теорема 2. Пусть О2 — произвольное множество из 0. Тогда О1 и О2 — полная система в ^.

Доказательство теоремы 2 опирается на следующие леммы.

Лемма 3. Пусть / — произвольная функция из ^, такая, что множество 1ш(/, Q) не содержит несравнимых элементов. Тогда / £ < Оо >.

Приведем схему доказательства этой леммы. Пусть 1ш(/, Q) = {51,..., 5т}, где 51 < ... < 5т, т ^ 1. Положим До = 0, Дк = {51,..., 5к} для всех к = 1,...,т. Сначала для каждого к = 1,...,т определяются функции Ьк £ < Оо >, такие, что Ьк £ и Ьк(е) = 5к для всех е ^ 5к, а также функции фк £ < Оо >, такие, что равенство фк(5) = 0 выполняется тогда и только тогда, когда 5 £ Дк. Далее для каждого к = 1,...,т определяются функции /к следующим образом: /к(е) = /(е), если /(е) £ Дк, и /к(е) = е в противном случае. Затем по индукции доказывается соотношение /к £ < Оо >. База индукции (к = 1) следует из равенства /1 = '1 * '1, а индукционный переход — из равенства /к = (Ьк о /к_ 1) * фк. В завершение показывается, что /т = /.

Нетрудно убедиться в справедливости следующей леммы.

Лемма 4. Пусть Ь £ Н(т, й), где й £ {0,1}, й < т ^ п. Тогда Ь £ < Оо >.

Лемма 5. Пусть Ь £ Н(т,й), где 2 ^ й < т ^ п. Тогда существуют функции Ьо £ Н(т, 0), д £ Н(т, 1) и / £ Н(т — 1,й — 1), такие, что Ь = / о (д о Ьо).

Приведем схему доказательства этой леммы. Сначала определяется функция Ьо из Н(т, 0), такая, что Ьо(5) = Ь(5) для всех 5 £ Qm_l и Ьо(5) = 5 для всех 5 £ Q \ Qm_l. Затем выбирается цепь О длины т — й, такая, что 1ш(Ь, Qm_l) С О. После этого строится функция д £ $п, такая, что выполнены соотношения д(а т) — am—1, д(а'т) = д(ат_1) и, кроме того, найдется функция / £ £п, для которой равенство /(д(5)) = Ь(5) выполняется для всех 5 £ Q \ Qm_l. В итоге доказывается, что д £ Н(т, 1), / £ Н(т — 1,й — 1), и проверяется равенство Ь = / о (д о Ьо).

Доказательство теоремы 2. Пусть G2 G G. Нетрудно показать, что выполняется соотношение Go С < Gi U G2 >. Поэтому для доказательства теоремы 2 достаточно доказать равенство < Go > = F.

Пусть h — произвольная функция из F. Покажем, что h G < Go >. Если множество Im(h, Q) не содержит несравнимых элементов, то по лемме 3 выполняется соотношение h G < Go >.

Пусть Im(h, Q) содержит несравнимые элементы. Покажем, что найдутся m, d, такие, что h G H(m, d), где О ^ d < m ^ n. Положим A = (i | элементы h(ai) и h(ai) несравнимы, О < i ^ n}. Так как Im(h, Q) содержит несравнимые элементы, то найдутся ß и y из Q, такие, что элементы f (ß) и f (y) несравнимы. Из монотонности функции f следует, что элементы ß и y несравнимы. Поэтому A = 0. Таким образом, множество A имеет минимальный элемент. Обозначим этот элемент через m. По определению множества Q выполняется равенство (h(am),h(am)} = (at, at}, где l ^ t ^ n. В силу определения множества F выполняется неравенство t ^ m. Таким образом, h G H (m, m — t), т.е. h G H (m, d), где d = m — t.

Докажем теперь индукцией по d, что при всех m, таких, что d < m ^ n, выполняется соотношение H (m, d) С < Go >. При d = О, l (база индукции) это соотношение следует из леммы 4. Докажем индукционный переход. Пусть h G H (mi, di ), где 2 ^ di < mi ^ n. Тогда по лемме Б найдутся функции ho G H(m1, О), g G H(m1, l), f G H(m1 — l, d1 — l), такие, что h = f о (g о ho). Для множеств H(m1, О), H (mi, l) и H (mi — l,di — l) выполнено предположение индукции. Поэтому функции ho, g и f принадлежат множеству < Go >. Таким образом, по построению имеет место соотношение h G < Go >. Теорема доказана.

Из теорем l и 2 непосредственно следует критерий полноты для систем функций из F. Теорема 3. Система G С F является полной тогда и только тогда, когда Gi С G и существует множество G2 из семейства G, такое, что G2 С G.

СПИСОК ЛИТЕРАТУРЫ

1. Tardos G. A not finitely generated maximal clone of monotone operations У У Order. 1986. 3. 211-218.

2. Lau D. Function algebras on finite sets: а basic course on many-valued logic and clone theory (Springer monogrpahs in mathematics). Secaucus (N.J.): Springer-Verlag New York Inc., 2006.

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

4. Дудакова О.С. О классах функций k-значной логики, монотонных относительно множеств ширины два У У Вестн. Моск. ун-та. Матем. Механ. 2008. № 1. 31-37.

5. Slupecki J. Kriterium pelnosci wielwartosciowych systemow logiki zdari У У C.R. Seanc. Soc. Sci. Varsovie. Cl. III. 1939. 32.102-109.

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

7. Salomaa A. Some completeness criteria for sets of functions over a finite domain I, II. Turun Ylopiston Jalkaisuja Annales Universitatis Turkuensis, sarja A 53. 1962. 1-9; A 63. 1963. 1-19.

8. Мальцев А.И. Об одном усилении теорем Слупецкого и Яблонского У У Алгебра и логика. 1967. б, вып. 3. 61-74.

9. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2008.

Поступила в редакцию 31.0Б.2010

УДК 511

О РАСПРЕДЕЛЕНИИ БОЛЬШИХ ЗНАЧЕНИЙ АРГУМЕНТА ДЗЕТА-ФУНКЦИИ РИМАНА НА КОРОТКИХ ИНТЕРВАЛАХ

Р. Н. Бояринов1

Получена верхняя оценка меры множества значений t G (T, T + H ] при H = T27/82+е, для которых |S(t)| ^ А.

Ключевые слова: аргумент дзета-функции Римана, мера множества.

1 Бояринов Роман Николаевич — канд. физ.-мат. наук, доцент каф. математического анализа мех.-мат. ф-та МГУ, e-mail: roma_boyarin@yahoo.com.