авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 ||

«Министерство образования и науки Российской Федерации Восточно-Сибирская государственная академия образования Институт математики им. С.Л. Соболева СО РАН СИНТАКСИС И ...»

-- [ Страница 3 ] --

На пространстве Чу A = (A, X) зададим топологию Гротен дика, а именно положим, что для любого a из 2A определяется семейство = {ai 2A |i I} (a) ai = a;

X a.

iI Число n называется -размерностью a [4-5], если в каждое -покрытие можно вписать -покрытие a кратности n + 1, и имеется -покрытие a кратности n+1, в которое нельзя вписать -покрытие a меньшей кратности. Число DimA называется размерность нормального пространства Чу (A, X). Когомоло гическую размерность элемента a 2A определим следующим n+k образом: c Da n H (a, A) = 0, A - абелева предпучка и k 0.

Впервые понятие информационная система ввел Дан Скотт в компьютерной науке [3]. Информационной системой назы вается тройка (A, Con, ), где A – множество (набор инфор мации), Con – множество не пустых конечных подмножеств множества A и отношение Con A, удовлетворяющее пя ти аксиомам [2-3]. Отношение x a указывает на то, что x Институт прикладной математики г.Владивосток ДВО РАН e-mail: agsukh@mail.ru "больше, чем"a (как в логике, где означает, что фор мула следует из гипотезы ). Интуитивно понятно, что ин формационная система представляет собой набор "предложе ний"(элементы из Con), которые можно сделать из "возмож ной информации"(элементы множества A).

Через AI обозначим пространство Чу над алфавитом = {0, 1} такое, что множество X = Con и отображение r(a, x) = 1 a x.

Теорема Пусть AI = (A, Con) – пространство Чу индуци рованное информационной системой, (Con, B) = (A, Con) и – B-топология на 2A. Тогда 1) Dim Con = n тогда и только тогда когда длина макси мального "предложения"равна n;

2) Dim Con = c D Con;

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

Список литературы [1] V.Gupta and V.R. Pratt. Gates accept concurrent behavior.

In Proc. 34th Ann. IEEE Symp. on Foundations of Comp. Sci., pages 62-71, 1993.

[2] K.G, Larsen and G. Winskel, Using information systems to solve recursive domain equations eectively, in: Semantics of Data Types, International Symposium Sophia-Antipolis 1984 (G. Kahn, D.B. MacQueen and G. Plotkin, eds.), Springer LNCS 173 (1984), pp. 109-129.

[3] D.S. Scott, Domains for denotational semantics, Proc. 9th International Coll. on Automata, Languages and Programming, Aarhus, Springer LNCS 140 (1982), pp. 577-613.

[4] Скурихин Е.Е., Пучковые когомологии и размер ность частично упорядоченных множеств. Тр.Мат. ин-та В.А.Стеклова РАН, 2002. Т239. С.289-317.

[5] E.E. Скурихин, А.Г. Сухонос, Топология гротендика на пространствах Чу // Математические труды. Том.11 №2. Но восибирск. 2008. c.159–186.

НЕКОТОРЫЕ КЛОНЫ В АЛГЕБРЕ ЧАСТИЧНЫХ УЛЬТРАФУНКЦИЙ С.Ю. Халтанова Пусть E2 = {0, 1}, P2,n = {f | f : E2 2E2 }, P2 = n P2,n, n P2,n = {f : f P2,n и | f (1, 2,..., n ) | 1 для любого набора n (1, 2,..., n ) E2 }, P2 = P2,n, P2,n = {f : f P2,n и n | f (1, 2,..., n ) | 1 для любого набора (1, 2,..., n ) n E2 }, P2 = P2,n, P2,n = {f : f P2,n и | f (1, 2,..., n ) |= n n для любого набора (1, 2,..., n ) E2 }, P2 = P2,n.

n Очевидно, что выполняются следующие включения:

P2 P2 P2, P2 P2 P2.

Функции из P2 называют булевыми, из P2 частичными функциями, из P2 ультрафункциями, из P2 частичными ультрафункциями.

Пусть даны f (x1, x2,..., xn ) P2, f1 (x1, x2,..., xm ),...,, тогда суперпозиция f (f (x,..., x ), fn (x1, x2,..., xm ) P2 11 m..., fn (x1,..., xn )) определяет функцию g(x1,..., xm ), принад лежащую P2, следующим образом [2]:

, если существуетi (1 i n)такое, что fi (1,..., n ) = f (1,..., n ), если это пересече g(1,..., n ) = i fi (1,...,n ) ние не равно ;

f (1,..., n ), иначе.

i fi (1,...,n ) Функция f (x1,..., xn ) : f (1,..., n ) = {i } называется селек торной.

Восточно-Сибирская государственная академия образования e-mail: soelabad@mail.ru Клон класс функций, замкнутый относительно суперпо зиции и содержащий все селекторные функции.

В дальнейшем для удобства изложения будем использовать следующую кодировку: {0} 0, {1} 1, {}, {0, 1}.

Известно, что клоны T0,0 = {f P2 | f (0, 0,..., 0) = 0} и T1,1 = {f P2 | f (1, 1,..., 1) = 1} являются максимальными в P2. В работе [1] описаны все клоны, содержащие T0,0, T1,1 в P2. Доказано, что для каждого из клонов T0,0, T1,1 существуют ровно 9 таких клонов.

В данной работе исследуются клоны, содержащие T0,0 (T1,1 ) в P2. Показано, что в P2 существуют ровно 20 клонов, со держащих T0,0 (20 клонов, содержащих T1,1 ).

Достаточно очевидной является следующая лемма.

Лемма 1. Если A клон в P2, {} = {f | f (1,..., n ) = n }, тогда A {} для любого (1,..., n ) E2 клон.

Замечание. Будем считать в дальнейшем, что каждый клон содержит {}.

Определим следующие множества ультрафункций:

= {f P | f (0, 0,..., 0) = 0} {};

T = {f P | T0,0 2 0,0 f (0, 0,..., 0) = 0} {};

T0,0 = {f P2 | f (0, 0,..., 0) = 0} {};

T0, = {f P2 | f (0, 0,..., 0) = };

T0, = {f P2 | f (0, 0,..., 0) = };

T0,0 = {f P2 | f (0, 0,..., 0) {0, }};

= {f P | f (0, 0,..., 0) {0, }};

T 0,0 T0 ;

T0,0 T0 ;

T0,0 T0,0 T0 ;

T0,0 T0.

Легко показать, что эти множества являются клонами.

В дальнейшем под P2 в соответствии с замечанием будем понимать P2 {} и вместо P2 понимаем P2 {}.

Теорема 1. Следующие клоны различны и вложены друг в друга так, как показано на рис. 1.

Теорема 2. Существуют ровно 14 различных клонов A в P таких, что T0,0 A, а именно, клоны, представленные на рис.1.

Для клона T1,1 результат аналогичен теореме 1, при этом в определениии классов везде 0 заменяется на 1.

P T0, P P2 T0,0 T0 T0,0 T T0, T0,0 T P T0, T0,0 T T0, T0, T0, Рис. 1. Решетка клонов, содержащая клон T0,0 в P2.

Список литературы [1] Алексеев В. Б., Вороненко А. А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная мате матика, 1994, т. 6, вып. 4, с. 58-79.

[2] Пантелеев В. И. Критерий полноты для доопределяе мых булевых функций // Вестник Самарского государствен ного университета. Естественнонаучная серия, № 2 (68), 2009.

КОНСТАНТНЫЕ ФОРМУЛЫ И ФИНИТНАЯ АППРОКСИМИРУЕМОСТЬ НОРМАЛЬНЫХ МОДАЛЬНЫХ ЛОГИК А.В. Чагров Константными (модальными) формулами будем называть формулы, не содержащие пропозициональных переменных, т.е.

построенные из константы с помощью обычных связок, на пример,,, 2, остальные связки считаем производными (так, ¬ =, 3 = ¬2¬, = ¬).

Несмотря на свою, как кажется, простоту (правило подста новки их не меняет), константные формулы порой ведут се бя довольно неожиданно. Так, проблемы принадлежности кон стантных формул таким стандартным логикам, как K, K4, оказываются PSPACE-полными, хотя для GL, а уж тем бо лее для S4 аналогичные проблемы решаются полиномиальны ми алгоритмами (см. [1]). Другой пример: свойство аксиомати зируемости над K4 константными формулами неразрешимо, см. [2].

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

Всегда ли при добавлении к финитно аппроксимируемой логи ке константной формулы в качестве новой аксиомы (схемы аксиом, что в данном случае одно и то же) получается фи нитно аппроксимируемая логика?

Легко заметить, что ответ на этот вопрос положителен для случая расширений K4. Достаточно воспользоваться теоремой о дедукции, которая в этом случае имеет вид: L, тогда и только тогда, когда L 2. Еще проще эта про блема положительно решается для расширений D, поскольку в этом случае существует с точностью до эквивалентных всего лишь две константные формулы: и. В общем же случае справедлива Теорема 1. Существуют такие финитно аппроксимируемая Тверской государственный университет email: chagrov@mail.ru нормальная модальная логика L и константная формула, что нормальное расширение L этой формулой не является финитно аппроксимируемой логикой.

Приведу краткое описание построенного для обоснования этого утверждения примера.

Логика L задаётся как множество формул, истинных во всех шкалах (фреймах) Fn. Шкала Fn изображена на рисунке •a  Qd k   T s e !u   ed   e d    ed   d e     e d    e d     • · · · • · · · e•' d' •' •' • • T0 T1 T2 T Tn2 Tn1 Tn b b b b b b c0 E• c1 E• c2· · · cn2 E cn1 E cn • • ··· • • • Подчеркну, что на рисунке стрелками отмечены все связи точек по достижимости.

Поскольку все шкалы Fn конечны, логика L финитно аппроксимируема. Однако среди её шкал есть и бесконеч ные (имеются в виду шкалы с корнем, конечно). Таковой, например, является шкала F, изображенная на рисунке ниже.

В качестве формулы, о которой идет речь в утверждении теоремы, можно взять формулу = 332 ¬32 3(332 ¬32), которая истинна в шкале F.

Несложно (но для данного текста слишком громоздко) по казать с помощью шкалы F, что если добавить к L в ка честве аксиомы, то получившейся логике L не принадлежит формула = 332 ¬32 2(32 22). Однако вся кая шкала, отделяющая от L должна быть бесконечной. Это завершает доказательство.

•a Qs d k   T e !

u   e d  e d      ed   d e     e d    e d     ··· • ··· e' d' • •' •' • • • ··· T T T T T bn1 Tn Tn+ b0 b1 b2 b b ··· c0 E• c1 E• c 2 · · · cn1 E cn E• cn+1· · · • • ··· • • Аналоги рассмотренного вопроса, такие как поиск конечно аксиоматизируемого варианта L и/или замена свойства финит ной аппроксимируемости на, скажем, разрешимость, полноту по Крипке и т.д. могут оказаться довольно трудными задача ми.

Наконец, приведу ещё два утверждения, относящихся к этой тематике.

Теорема 2. Результат добавления к K конечного множе ства константных аксиом всегда является финитно аппрокси мируемой логикой.

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

Работа выполнена при поддержке РФФИ, гранты 08–06– 00414–а и 10–06–00360–а.

Список литературы [1] A.V. Chagrov, M.N. Rybakov. How many variables does one need to prove PSPACE-hardness of Modal Logics? // Advances in Modal Logic, vol. 4. London, King’s College Publications, 2003, pp. 71–82.

[2] А.В. Чагров. Неразрешимые свойства суперинтуици онистских логик // Математические вопросы кибернетики.

Вып. 5. М., Физматлит, 1994, с. 62–108.

ОБ ОДНОМ ВАРИАНТЕ МОДЕЛЬНОЙ ОБЛАСТИ ЛЯМБДА-ИСЧИСЛЕНИЯ В. Л. Чечулин В работе рассматривается вариант построения модельной области лямбда-исчисления в семантике теории множеств с самопринадлежностью (множества c cамопринадлежностью впервые описаны русским математиком Миримановым в 1917 г [1]). Показано, что модельной областью для лямбда исчисления являются конечные натуральные числа.

Как отмечалось ещё в 60-е гг. в бестиповом лямбда-ис числении объекты служат как аргументами, так и функция ми, которые применяются к этим аргументам [2, c. 99], по этому ввиду бестипового характера этой теории было неясно как строить модели для неё, [2, c.17] в идеале семантика для лямбда-исчисления соcтояла бы из области D, такой, что её пространство функций DD изоморфно D [2, с. 99]. В теории несамопринадлежащих множеств такое вложение DD = D или Exp(D) = D невозможно, виду теоремы Кантора для несамо принадлежащих множеств.

В теории множеств с самопринадлежностью [3], [4], [5] кро ме пустого множества и множества всех множеств имеется ряд множеств обладающих свойством равенства множества всех подмножеств самому множеству Exp(X) = X. Минимальны ми непустыми множествами, образующими упорядоченную от ношением принадлежности структуру, и обладающими этим свойством, являются натуральные числа вида: 1 = 1, 2 = 1, 2, 3 = 1, 2, 3 и т. д.,– определяемые непредикативно. Для любого конечного натурального числа n выполняется Exp(n) = n.

Пермский государственный университет e-mail: chechulinvl@mail.ru На основании свойств множеств с самопринадлежностью, доказана теорема Теорема. В теории множеств с самопринадлежностью мо дельными областями для лямбда-исчисления являются только конечные натуральные числа.

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

Доказанный результат удивительно точно совпадает с действительностью,– в действительной цифровой электронной вычислительной машине, множество её внутренних состояний определяется конечным (вполне упорядоченным) набором ма шинных слов (команд процессора и массива обрабатываемых данных), мощностью равной n = 2m, где m – количество разрядов в машинном слове.

Список литературы [1]. Френкель А., Бар-Хиллел И., Основания теории мно жеств, М.:Мир, 1966, пер с англ. Ю. А. Гастева, под. ред. А. С.

Есенина-Вольпина,– 366 с.

[2] Барендрегт Х., Лямбда-исчисление, его синтаксис и се мантика, пер с. англ. Минц Г. Е., М.: Мир, 1985.– 606 с.

[3] Чечулин В. Л., О множествах с самопринадлежностью // Вестник Пермского университета, сер. Математика. Механика.

Информатика, вып. 2 (2), 2005 г., сс. 133-138. (реферат 06.07 13А.48 РЖ Математика, ВИНИТИ, 2006 г., №7.) [4] Чечулин В. Л., Об упорядоченных структурах в теории множеств с самопринадлежностью // Вестник Пермского уни верситета, сер. Математика. Механика. Информатика, вып. 6, 2008 г., с. 37-45. (реферат 08.11-13А.247 РЖ Математика ВИ НИТИ, 2008 г. №11) [5] Chechulin V. L., About the selfconsidering semantic in the mathematical logic // Bull. Symbolic Logic Volume 16, Issue (2010), рр. 111-112. (2009 European Summer Meeting of the Asso ciation for Symbolic Logic, Logic Colloquium ’09, Soa, Bulgaria, July 31–August 5, 2009, pp. 90-142.) РАСШИФРОВКА БЕСПОВТОРНЫХ ФУНКЦИЙ ПО ДВУМ МЛАДШИМ БИТАМ ЧИСЛА ЕДИНИЦ ПОДФУНКЦИЙ Д. В. Чистиков Рассмотрим следующую задачу диагностического те стирования. Требуется построить алгоритм, позволяющий точно идентифицировать неизвестную (находящуюся в чер ном ящике) бесповторную в элементарном базисе функцию f (x1,..., xn ), не имеющую фиктивных переменных. Алгоритм может запрашивать значения si (f ) (i = 0, 1) двух младших бит числа единиц sl... s1 s0 произвольной подфункции f функции f. Сложность алгоритма есть число выполняемых им запросов в худшем случае.

(2k ) Обозначим символом TB0 (n) минимально возможную сложность алгоритма, решающего данную задачу и вы полняющего запросы с i k. А. А. Вороненко доказал [1], что (2) TB0 (n) n2 n + 1.

Настоящая работа посвящена получению асимптотически (4) меньшей верхней оценки значения TB0 (n).

Лемма 1 (см., например, [1]). Если функция f беспо вторна в элементарном базисе, то s0 (f ) = 1 в том и только том случае, когда все ее переменные существенны.

Для бесповторной функции f (x1,..., xn ) будем называть правильным корневое дерево, представляющее структуру бес повторной формулы для f с поднятыми отрицаниями и функ циональными символами & и произвольной арности. Более Факультет вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова e-mail: dd1email@gmail.com строго, листья дерева должны быть помечены литералами раз личных переменных из {x1,..., xn }, а внутренние вершины символами & и, причем смежные вершины не могут быть по мечены одинаковыми символами. Единственность правильного дерева фактически показана еще В. А. Гурвичем в работе [2].

Пусть c(f ) {0, 1} сравнимо с числом нелистовых вершин в правильном дереве для f по модулю 2, а d(f ) равно 1, если корень этого дерева помечен символом &, и 0 иначе. Справед ливо следующее утверждение:

Лемма 2. Если функция f (x1,..., xn ) бесповторна в эле ментарном базисе, то s1 (f ) = c(f ) d(f ).

Доказательство можно провести методом математической индукции.

Лемма 3. Пусть функция f (x1,..., xn ) бесповторна в эле ментарном базисе и существенно зависит от всех своих n переменных. Пусть известна существенно зависящая от всех своих переменных функция g(x1,..., xn1 ) такая, что f (x1,..., xn1, n ) g(x1,..., xn1 ) для известного n {0, 1}. Тогда функцию f можно восстано вить, используя не более 3/2 · (n 1) запросов двух младших бит числа единиц ее подфункций.

Доказательство. Истинное дерево f может быть получено из дерева g одним из следующих трех способов: присоединение листа к уже имеющейся вершине, введение нового корня или введение новой некорневой вершины со степенью захода 2. Ис пользуем результат предыдущей леммы и определим, как свя заны величины s1 (f ) и s1 (g). В первых двух случаях выполнено равенство s1 (f ) = s1 (g). Рассмотрим подробнее третий случай.

Если оба потомка новой вершины листья, то s1 (f ) = s1 (g)1, в противном случае, как и прежде, s1 (f ) = s1 (g). Таким обра зом, s1 (f ) = s1 (g) тогда и только тогда, когда f получается из g добавлением множителя xn или слагаемого xn к литералу n n переменной, связанной в дереве g с дизъюнкцией или конъюнк цией соответственно.

Воспользуемся этим фактом для ускорения алгоритма рас шифровки. Возьмем за основу рассуждения из доказательства леммы 2 работы [1]. Пусть, без ограничения общности рассуж дений, g монотонна по всем своим переменным. Будем рассмат ривать представления вида g(x1,..., xn1 ) = (x1... xs, xs+1,..., xn1 ), где s 2 и {&, }, и (далее для определенности полагаем = ) искать f в виде f (x1,..., xn ) = (x1... xs, xs+1,..., xn1, xn ), где бесповторная функция, допуская альтернативы типа f = ((xi1... xir ) · xn xir+1... xis, xs+1,..., xn1 ).

n Описанный в [1] процесс исключает из рассмотрения на каж дом шаге s1 переменную, делая при этом s запросов значений f в отдельных точках. В случае s 3 на каждую переменную приходится в среднем не более 3/2 запросов. Модифицируем алгоритм, запуская в случае s = 2 запрос второго младшего бита числа единиц f и вычисляя в соответствии с результатом леммы 2 величину s1 (g) по имеющемуся представлению g. Яс но, что для рассматриваемых в данном случае альтернатив, со гласно проведенным выше рассуждениям, должно выполнять ся неравенство s1 (f ) = s1 (g). Следовательно, если каждый раз при выборе отдавать предпочтение варианту с бльшим зна о чением s, то равенство s1 (f ) = s1 (g) будет означать невозмож ность осуществления хотя бы одной из них и, таким образом, возможность проведения параллельной замены переменных. В противном случае выбор из имеющихся альтернатив проводит ся так же, как в [1].


Вычислим число запросов, выполняемых алгоритмом в худ шем случае. На каждую исключаемую переменную при s по-прежнему приходится не более полутора запросов, а при s = 2, с учетом сделанных выше замечаний, не более одного.

Точечные запросы для выбора из альтернатив в случае s = учитываются за счет неисключенных переменных: неравенство 3/2 · (k 1) + 1 1 + k выполнено лишь в случае k 3, по этому при k = n 1 = 2 модификация не проводится, а оцен ка сложности увеличивается на 1/2 (ситуация n = 2, как и в [1], разрешается одним запросом). Всего требуется не более (n 2) · 3/2 + 1 + 1/2 = 3/2 · (n 1) запросов, что и доказывает утверждение леммы.

Теорема.

(4) TB0 (n) 3/4 · (n2 + 1/3).

Доказательство. Используя n 1 запрос младшего би та числа единиц, обнаружим последовательность из функций n 1,..., 2, 1 существенных переменных. Последнюю функцию в данной последовательности восстановим за один точечный запрос, все остальные в обратном порядке по алгоритму лем мы 3. Всего будет выполнено не более n n 3(k 1) 3k (n 1) + 1 + =n+ = 2 k=2 k= n n1 3 n(n 1) 1 n 3k · =n+ · · =n+ = 2 2 2 2 2 2 k= 1 n1 1 n 3 1 321 3 = ·n2 + ·n · = ·n2 + ·n + ·n · 4 4 2 2 4 4 2 2 4 запросов (отметим, что последнее число всегда является це лым). Теорема доказана.

Автор выражает признательность В. Б. Алексееву, предло жившему рассмотреть данный класс запросов. Работа выпол нена при поддержке РФФИ (проект 09-01-00817).

Список литературы [1] Вороненко А. А., Чистиков Д. В. Расшифровка беспо вторных функций оракулом счетчиком четности // Прикл.

матем. и информатика. 2010. 34.

[2] Гурвич В. А. О бесповторных булевых функциях // Успе хи математических наук. 1977. 32. № 1. С. 183–184.

ЧАСТОТНЫЕ ХАРАКТЕРИСТИКИ АСИМПТОТИЧЕСКИ НАИЛУЧШИХ ДООПРЕДЕЛЕНИЙ СИСТЕМ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ Л.А. Шоломов Рассматривается реализация систем F = (f1,..., fk ) ча стичных булевых функций схемами из функциональных эле ментов в произвольном конечном базисе [1]. Схема S реали зует систему F, если она реализует некоторое ее доопреде ление F = (f1,..., fk ). Систему F () = F (x1,..., xn ) будем x характеризовать параметрами l, {0, 1, }k, где означает F F неопределенное значение, а l число наборов x, на которых F () =. Положим lF = (l, {0, 1, }k ).

F x Зададимся набором пораметров l = (l, {0, 1, }k ) и класс всех систем F от n аргументов, для которых lF = l обо значим Fn (l). Для класса Fn (l) введем функцию Шеннона L(n, l) = max L(F ), F Fn (l) где L(F ) сложность минимальной реализации системы F.

Будем считать, что n, k = const и существует lim l 2n = p. (1) n Метод M реализации систем из Fn (l) назовем асимптотиче ски наилучшим, если для всех F Fn (l) он дает схемы слож ности LM (F ) L(n, l). Доопределение, возникающее при ре ализации системы F методом M, будем обозначать FM. Это Институт системного анализа РАН e-mail: sholomov@isa.ru доопределение называется асимптотически наилучшим, если таковым является метод M.

Для системы F и некоторого ее доопределения F обозна k, µ {0, 1}k ) число появлений па чим через u ( {0, 1, } µ x x ры (, µ) среди пар значений (F (), F ()), и введем частоты n. Структуру доопределения F системы появлений r = u µ µ F будем характеризовать матрицей R = RF,F = r. Для µ наборов {0, 1, }k и µ {0, 1}k будем употреблять запись µ, если µ доопределяет. Ненулевыми элементами r µ матрицы R могут быть лишь такие, для которых µ. Нас будет интересовать асимптотическое поведение матриц R для асимптотически наилучших доопределений систем из Fn (l).


Пусть P = (p, {0, 1, }k ), где p взяты из (1). Задав шись набором Q = (qµ, µ {0, 1}k ), qµ 0, µ qµ = 1, введем функцию H(P, Q) = p log qµ µ: µ (логарифмы двоичные) и положим H(P ) = min H(P, Q). При Q достаточно слабых условиях величина H(P ) достигается на единственном наборе Q = (µ, µ {0, 1}k ). Этот случай будем q называть невырожденным. В невырожденном случае положим p qµ r = µ (2) qµ µ: µ и образуем матрицу R = r. Расстояние между матрицами µ = r = r и R будем измерять величиной R µ µ d(R, R ) = max |r r |.

µ µ µ, Следующая теорема показывает, что асимптотически наилуч шие доопределения почти всех систем класса Fn (l) имеют по чти одинаковую структуру.

Теорема. Если выполнены условия (1), имеет место невы рожденный случай и метод M реализации систем из Fn (l) яв ляется асимптотически наилучшим, то для любых положитель ных и c доля систем F класса Fn (l), для которых d(RF,FM, R), не превосходит 2cn.

Доопределение F, возникающее при реализации системы F минимальной схемой будем называть лучшим (оно неедин ственно). Из теоремы вытекает следующий факт.

Следствие. При условиях теоремы доля систем F класса Fn (l), имеющих лучшее доопределение F, для которого d(RF,F, R), не превосходит 2cn.

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

1. При условиях теоремы имеет место асимптотика [2] 2n H(P ) L(n, l), n где приведенный вес базиса [1].

2. Для заданного класса G Fn (l) и матрицы R = r, µ удовлетворяющей условиям:

r µ, r = p, (3) µ µ µ обозначим через N (G, R) минимальную мощность доопределя ющего множества для G, содержащего для каждой системы F G доопределение F, для которого RF,F = R. Тогда если мощность класса G удовлетворяет условию |G| |Fn (l)| 2nc1, то log N (G, R) nI(R) c2 log n, где r µ I(R) = r log.

µ p r µ µ, 3.

Если значение H(P ) достигается в единственной точке то минимум функции I(R) при условиях (3) достигается на Q, единственной матрице R, задаваемой соотношениями (2).

На основе этих утверждений доказательство завершается следующим образом.

Обозначим через F множество всех систем F из Fn (l), для которых d(RF,FM, R). Допустим, что для некоторого c2 вы полнено |F | |Fn (l)|2c2 n. Множество F разобьем на груп пы, отнеся в одну группу системы F с одинаковой матрицей RF,FM. Обозначим через G группу, имеющую максимальную мощность, а через R соответствующую ей матрицу. Число раз личных наборов параметров u (а следовательно и матриц R) µ при k = const не превышает nc3, поэтому |G| |Fn (l)|2c4 n. По утверждению 2 отсюда заключаем, что log N (G, R ) nI(R ).

Поскольку матрица R -удалена от R, то из утверждения ) вытекает, что log N (G, R (1 + )nH(P ) при некотором 0. Мощностные соображения дают для систем F G ниж нюю оценку сложности LM (F ), асимптотически превосходя щую оценку утверждения 1. Это противоречит тому, что M асимптотически наилучший метод синтеза. Подобные сооб ражения использовались в [3].

Работа выполнена при поддержке ОНИТ РАН по програм ме фундаментальных исследований.

Список литературы [1] Лупанов О. Б. Об одном подходе к синтезу управляю щих систем принципе локального кодирования // Проблемы кибернетики. Вып. 14. – М.: Наука, 1965. – С. 31–110.

[2] Шоломов Л. А. Информационные свойства функциона лов сложности для систем недоопределенных булевых функ ций // Проблемы кибернетики. Вып. 34. – М.: Наука, 1978. – С. 133–150.

[3] Шоломов Л. А. О сложности последовательной реали зации частичных булевых функций схемами // Дискретный анализ и исследование операций. Сер. 1, 2007. – Т. 12, № 3. – С. 110–139.

ПОЛУГРУППЫ С ПРИМИТИВНО НОРМАЛЬНЫМИ ТЕОРИЯМИ Н.В. Трикашная В [1] изучены полугруппы, хорновы теории которых при митивно нормальны. Известно, что алгебры с примитивно нор мальными полными теориями абелевы. В [2] описаны абелевы полугруппы. В [3] получено более простое описание для абе левых полугрупп, удовлетворяющих условию (*), сформулиро ванному ниже.

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

Напомним некоторые определения. Пусть T – полная теория языка L, A – алгебра языка L. Кортежи элементов a1,..., an и переменных x1,..., xn обозначим соответственно a и x. Длину кортежа s обозначим через l(s). Если (x, y) – формула языка L, a – кортеж элементов и l(a) = l(y), то через (A, a) обозначим множество {b|A |= (b, a)}.

Формула вида x1...xn (0... k ), где i (i k) – атомарные формулы, называется примитивной.

Если (x, y) – примитивная формула языка L, a – кортеж элементов и l(a) = l(y), то множества (A, a) и (A, b) назы Дальневосточный государственный университет e-mail: trik74@mail.ru ваются примитивными копиями. Теория T называется прими тивно нормальной, если для любых примитивных копий X, Y выполнено X = Y или X Y =.

Для формулировки основного результата понадобятся неко торые понятия из теории полугрупп.

Полугруппа A, · называется прямоугольной связкой полу групп, если существует семейство {Ai | i I, }, являю щееся разбиением множества A, причем Ai, · – подполугруп пы полугруппы A, · и для любых i I,, µ выполня ется включение Ai · Ajµ Aiµ. Полугруппа A, · называет ся раздуванием полугруппы B, ·, если существует разбиение {Xa | a B} множества A такое, что a Xa и x · y = a · b для любых a, b B, x Xa, y Xb. Будем говорить, что полугруп па A, · удовлетворяет условию (*), если b, c A (bcA = bA и Abc = Ac) или множество A · A конечно.

Теорема. Пусть A, · – полугруппа. Следуюшие условия эквивалентны:

1) теория T h A, · примитивно нормальна;

2) полугруппа A, · является абелевой полугруппой, удо влетворяющей условию ();

3) полугруппа A, · является раздуванием прямоугольной связки абелевых групп и произведение идемпотентов из A яв ляется идемпотентом из A.

Список литературы [1] Степанова А.А. Полугруппы, порождающие категорич ные хорновы классы // Мат. заметки. – 1985. – Т.38, №2. – С.

317 - 324.

[2] Warne R.J. Semigroups obeying the term conditions // Algebra Universalis. – 1994. – No.31. – P. 113 - 123.

[3] Степанова А.А., Трикашная Н.В. Абелевы и гамильтоно вы группоиды // Фундаментальная и прикладная математика.

– 2009. – Т.15, №7. – С. 165 - 177.

УКАЗАТЕЛЬ АВТОРОВ Архипов В.В., 60 Семенов А.А., Викентьев А.А., 6 Симонов А.С., Викентьев Р.А., 6 Смирнов А.В., Винокуров С.Ф., 9 Спекторский И.Я., Власов Д.Ю., 13 Степанова А.А., Вороненко А.А., 17 Судоплатов С.В., 101, Галков Д.Ю., 23 Сухонос А.Г., Голованов М.И., 26 Танович П., Дьяконов А.Г., 28 Трикашная Н.В., Зубков О.В., 36 Францева А.С., Игнатьев А.С., 93 Халтанова С.Ю., Ильин Б.П., 37 Чагров А.В., Каташевцев М.Д., 60 Чечулин В.Л., Казимиров А.С., 42 Чистиков Д.В., Кириченко К.Д., 46 Шоломов Л.А., Кочергин В.В., 50 Яковчук И.А., Левин В.И., 54 Davletshin M.N., Мартьянов В.И., 60 Egorychev G.P., 32, Михайлович А.В., 64 Zima E.V., Мусифулина С.Р., Овчинникова Е.В., Пахомов Д.В., Палютин Е.А., Пантелеев В.И., Первухин М.А., Перязева Ю.В., Перязев Н.А., 76, Пинус А.Г., Птахов Д.О., Реймеров С.Ю., Рублев В.С., Русалеев М.А., Рябец Л.В.,

Pages:     | 1 | 2 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.