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

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

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


Pages:     | 1 || 3 |

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

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

Теорема 3. Для произвольной последовательности недо определенных матриц {An } фиксированного размера p 2 с неотрицательными элементами при условии D(An ) вы полняется соотношение Lкр (An ) 3 log3 D (An ).

ВС Работа выполнена при финансовой поддержке РФФИ (про ект 08-01-00863).

Список литературы [1] Pippenger N. The mimimum number of edges in graphs with prescribed paths // Math. Systems Theory. 1979. V. 12, № 4. P. 325–346.

[2] Лупанов О. Б. О вентильных и контактно-вентильных схемах // ДАН СССР. 1956. Т. 111, № 6. С. 1171–1174.

[3] Кочергин В. В. О сложности вычислений в конечных абелевых группах // ДАН СССР. 1991. Т. 317, № 2.

С. 291–294.

[4] Кочергин В. В. О сложности вычислений в конечных абелевых группах // Математические вопросы кибернетики.

Вып. 4. М.: Наука, 1992. С. 178–217.

[5] Кочергин В. В. О сложности вычисления систем одно членов и систем целочисленных линейных форм // Дискретная математика и ее приложения. Сборник лекций. Выпуск III.

М.: Изд-во Ин-та прикладной математики РАН, 2007. С. 3– 63.

[6] Pippenger N. On evaluation of powers and monomials // SIAM J. Comput. 1980. V. 9, N 2. P. 230–250.

[7] Кочергин В. В. О сложности вентильных схем с кратным числом путей // Материалы XVIII Международной школы семинара "Синтез и сложность управляющих систем"имени ака демика О. Б. Лупанова (Пенза, 2009 г.). М.: Изд-во механи ко-математического ф-та МГУ, 2009. C. 51–56.

СХЕМНАЯ РЕАЛИЗАЦИЯ АЛГЕБРЫ НЕПРЕРЫВНОЙ ЛОГИКИ В.И. Левин В 1970-е годы автором была построена непрерывно-логичес кая теория динамического поведения конечных автоматов [1,2].

Была установлена адекватность математического аппарата ал гебры непрерывной логики динамическим процессам, возника ющим на выходах схем конечных автоматов в ответ на динами ческие воздействия на их входах. Кроме того, были разработа ны методы и алгоритмы, позволяющие с помощью указанного аппарата находить в аналитической форме динамические про цессы на выходах автоматов любой сложности [3–5]. Большой интерес представляет обратная задача, а именно, построение схемы автомата и динамических воздействий на его входах, обеспечивающих получение на выходах автомата заданных ди намических процессов. С точки зрения математической логики эту задачу можно рассматривать как конструктивную интер претацию заданных формул алгебры непрерывной логики в ка честве формул, описывающих заданные динамические процес сы на выходах некоторого автомата. С точки же зрения теории автоматов – это задача синтеза схемы автомата, реализующего на выходах заданные процессы.

Заданы динамические процессы y1 (t),..., ym (t), т.е. после довательности переключений 1 0 и 0 1, на всех m вы ходах неизвестного логического (n, m)-полюсника, путем зада ния некоторых формул алгебры непрерывной логики, выража ющих моменты всех указанных переключений через моменты аналогичных переключений в некоторых инициировавших про цессы y1 (t),.

.., ym (t), динамических процессах x1 (t),..., xn (t), на входах указанного (n, m)-полюсника. При этом названные вход ные динамические процессы многополюсника, как и сам мно гополюсник, неизвестны. Требуется построить этот логический Пензенская государственная технологическая академия e-mail: levin@pgta.ru (n, m)-полюсник и указать процессы x1 (t),..., xn (t), на его вхо дах, приводящие к выработке на выходах (n, m)-полюсника за данных выходных процессов y1 (t),..., ym (t). Такую задачу есте ственно называть задачей синтеза логического многополюсни ка, реализующего на выходах заданные динамические процес сы. Ее можно еще назвать задачей конструктивной интерпре тации заданной системы формул алгебры непрерывной логики как формул, выражающих моменты последовательных пере ключений вида 1 0 и 0 1 в выходных динамических про цессах построенного логического (n, m)-полюсника через ана логичные моменты найденных динамических входных процес сов этого (n, m)-полюсника.

Любой логический (n, m)-полюсник является представимым в виде совокупности m логических (n, 1)-полюсников, имею щих одни и те же n входов. Поэтому без ограничения общности мы будем оперировать только логическими (n, 1)-полюсниками, решая соответственно этому задачу синтеза нашего логическо го (n, 1)-полюсника, реализующего на своем выходе заданный динамический процесс. Кроме того, мы ограничимся идейной стороной проблемы и оставим в стороне вопросы, связанные с размерностью (числом переключений вида 0 1 и 1 0) за данного выходного динамического процесса (n, 1)-полюсника.

Будем рассматривать только простейшие динамические про цессы, имеющие не более одного переключения 0 1 и 1 0.

Следуя [1–5], введем обозначения: 0 – переключение сигнала, a определяющего динамический процесс, типа 1 0 в момент времени a;

1 – аналогичное переключение сигнала 0 1 в мо a мент a. Рассмотрим n-входовый элемент-дизъюнктор, т.е. ло гический элемент, реализующий в статике на выходе y булеву n логическую дизъюнкцию y = xi своих входов xi, i = 1,..., n.

i= Пусть на всех входах дизъюнктора действуют однократные переключения 0 1, т.е. xi (t) = 1 i, i = 1,..., n. Тогда динами a ческий процесс на выходе элемента-дизъюнктора будет иметь вид такого же переключения 0 1, происходящего в момент n ai, – конъюнкция непрерывной логики [1,2,4,5]. В фор t= i= мульном виде это соотношение между входными и выходным динамическими процессами дизъюнктора n 1 i = 1 n (1).

a ai i=1 i= Обратим внимание, что логическая операция дизъюнкции в основной строке (1) означает булеву дизъюнкцию, опери рующую с двоичными элементами 0 и 1 – значениями сигнала и их изменениями 0 и 1, в то время как логическая опера ция конъюнкции в индексе этой формулы означает конъюнк цию непрерывной логики, оперирующую с любыми элемента ми некоторого непрерывного множества B2, означающими мо менты непрерывного времени. Это замечание относится также ко всем последующим формулам, описывающим соотношения между входными и выходными динамическими процессами в логических элементах. Пусть теперь на всех входах дизъюнк тора действуют процессы в виде однократных переключений сигнала 1 0, т.е. xi (t) = 0 i, i = 1,..., n. Тогда процесс на вы a ходе будет иметь вид такого же переключения, совершаемого n ai, где – дизъюнкция непрерыв в момент времени t = i= ной логики [1,2,4,5]. В формульном виде соотношение между входными и выходным процессами дизъюнктора n 0 i = 0 n (2).

a ai i=1 i= Совершенно аналогично выглядят формулы, выражающие зависимость между входными и выходным динамическими про цессами рассматриваемого простейшего класса (однократные переключения сигнала) в логическом элементе-конъюнкторе, который в статическом режиме реализует на выходе y булеву n конъюнкцию y = xi своих входов xi, i = 1,..., n.

i= Для входных процессов xi (t) = 1 i, i = 1,..., n, эта формула a имеет вид n 1 i = 1 n (3), a ai i=1 i= а для входных процессов xi (t) = 0 i, i = 1,..., n, будет иметь a такой вид n 0 i = 0 n (4).

a ai i=1 i= Рассмотрим еще одновходовый логический элемент, кото рый в статическом режиме реализует на выходе y булеву ло гическую функцию повторения своего входа x, т.е. y = x, а в динамическом режиме сдвигает каждый момент a переклю чения сигнала во входном процессе в точку a, где означает операцию отрицания непрерывной логики [1–5]. Решение по ставленной задачи в типовых случаях не составляет большого труда. Таких случаев шесть.

Рис. 1 Рис. Случай 1. Задан динамический процесс y(t) на выходе неизвестного логического (n, 1)-полюсника, имеющий вид оди ночного переключения сигнала n y(t) = 1, гдеb = (5) ai.

b i= В формуле (5) b означает момент переключения заданного выходного процесса, причем сам момент b выражается в виде дизъюнкции непрерывной логики от моментов ai аналогичных переключений на входах искомого (n, 1)-полюсника.

Требуется построить логический (n, 1)-полюсник и указать динамические процессы x1 (t),..., xn (t) на его входах, которые приводят к выработке на выходе (n, 1)-полюсника динамиче ского процесса (5).

Решение. Просматриваем формулы (1)–(4), описывающие все возможные случаи вход-выходных динамических соотно шений в логических (n, 1)-полюсниках, когда выходные процес сы имеют вид одиночного переключения сигнала. Единствен ная формула, в которой выходной процесс (n, 1)-полюсника совпадает с заданным выходным процессом (5), это формула (3). Но эта формула описывает динамический процесс, выра батываемый на выходе y логического (n, 1)-полюсника, реали зующего в статике n-входовую булеву конъюнкцию и получа ющего на входах x1,..., xn динамические процессы в виде оди ночных переключений сигнала x1 (t) = 1 1,..., xn (t) = 1 n.

a a Названные логический (n, 1)-полюсник и динамические про цессы на его входах и приводят к выработке на выходе задан ного динамического процесса (5) и, таким образом, являются решением поставленной задачи. Получающееся в этом случае решение показано на рис. 1.

Другие случаи рассматриваются аналогично случаю 1. По лученные в них решения показаны на рис. 2–6.

Рис. 3 Рис. Рис. 5 Рис. Список литературы [1] Левин В.И. Бесконечнозначная логика и переходные про цессы в конечных автоматах // Автоматика и вычислительная техника. – 1972. – №6.

[2] Левин В.И. Введение в динамическую теорию конечных автоматов. – Рига: Зинатне, 1975.

[3] Левин В.И. Таблицы для расчета и анализа переходных процессов в дискретных устройствах. – Рига: Зинатне, 1975.

[4] Левин В.И. Динамика логических устройств и систем. – М.: Энергия, 1980.

[5] Левин В.И. Теория динамических автоматов. – Пенза:

Изд-во Пензенского гос. технического ун-та, 1995.

[6] Левин В.И. Непрерывная логика в задачах динамики ко нечных автоматов // Известия РАН. Теория и системы управ ления. – 2010. – №1.

[7] Поспелов Д.А. Логические методы анализа и синтеза схем. – М.: Энергия, 1974.

ОБЗОР ПРИЛОЖЕНИЙ ЛОГИКО-ЭВРИСТИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ В.И. Мартьянов, В.В. Архипов, М.Д. Каташевцев, Д.В. Пахомов, А.С. Симонов Формализм многоосновных алгебраических систем А.И. Ко корин считал очень гибким [1] и всегда призывал своих учени ков использовать его в своих исследованиях.

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

В рамках данного подхода успешно решен ряд прикладных задач большой размерности, а именно:

– организация учебного процесса (например, НИУ ИрГТУ:

1309 групп, 29439 студентов, [3, 4]);

– преобразования нуклеотидных последовательностей РНК во вторичные структуры (например, установлено для генома человека: Х-хромосома имеет 217 микроРНК, а Y-хромосома 24 микроРНК [5], что подтверждает “истощенность” мужской хромосомы человека);

– управление содержанием региональной сети автомобиль ных дорог (например, организация зимнего содержания авто дорог Иркутской области [6]).

В рамках данного подхода имеются теоретические предпо сылки для успешного решения и других классов прикладных задач большой размерности, а именно:

Национальный исследовательский университет Иркутский государ ственный технический университет e-mail: ad@istu.edu – эскизное проектирование трасс автомобильных дорог на электронной топооснове [7];

– анализ плоских изображений [8, 9].

Рассматриваемые задачи в общей постановке, как правило, N P -полны, поэтому нельзя утверждать, что логико-эвристи ческий подход реализуется всюду одинаково. Тем не менее, есть две очень важные вычислительные процедуры, выполнение ко торых должно иметь линейную или квадратичную сложность либо от числа аргументов, либо от числа основных множеств модели.

Пусть рассматриваются многоосновные модели вида M = A1,..., As ;

p1,..., pk, (1) где Ai основные множества (домены для реляционной БД), отношения (таблицы реляционной БД) на основных мно pi жествах, где определены ограничения R1, R2,..., Rm.

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

Следующей задачей является обеспечение быстрой провер ки ограничений R1, R2,..., Rm, где идеальной является ситуа ция, когда сложность их проверки не зависит от m и является также линейной от числа основных множеств s.

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

а) просмотру вперед (checking forward) для уменьшения ко личества применяемых преобразований;

б) определению точки возврата для тупика (intelligent back tracking или глубокий возврат по принятой у ряда авторов в России терминологии). Отметим, что в логико-эвристическом подходе используется неполное восстановление среды точки воз врата, что экономит часть вычислительного ресурса, затрачен ного между тупиком и точкой возврата;

в) проверки выполнимости ограничений на многоосновной алгебраической системе, полученной после выполнения выбран ного преобразования (применение демонов для определения не вязок терминология специалистов по системам искусствен ного интеллекта и динамического программирования).

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

Теорема. Сложность анализа плоского связного изобра жения с упорядоченными связями дуг не превышает O n3, где n количество дуг анализируемого изображения.

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

Строится представление изображения вида (x1, x2 ), где x множества дуг, а x2 A2 множества связей дуг.

A Дуга это пара вида (s, b), где s Z сектор дуги, а b {0, 1} направление обхода дуги (по солнцу, против солнца).

Всевозможные представления дуг образуют множество A1.

Связь дуг это 4-ка вида (d1, d2, s, t), где d1, d2 A1 со единяемые дуги, s Z угол соединения, t тип соединения.

Всевозможные представления связей дуг образуют множество A2.

Под ограничением Ri будем понимать искомые образцы.

Образец это обобщение некоторого класса изображений.

Список литературы [1] Кокорин А.И., Пинус А.Г. Вопросы разрешимости рас ширенных теорий // УМН. 1978. Т. 33, вып. 2. С. 49–84.

[2] Мартьянов В.И. Логико-эвристические методы сетево го планирования и распознавание ситуаций // Тр. Междунар.

конф. “Проблемы управления и моделирования в сложных си стемах”. Самара, 2001. С. 203–215.

[3] Мартьянов В.И., Пахомов Д.В. Математические вопросы и программная реализация поддержки организации учебного процесса // Вестник Иркутского гос. техн. ун-та. Иркутск, 2007. № 1 (29). С. 143–147.

[4] Пахомов Д.В. Поддержка информационной составляю щей технологии организации учебного процесса // Вестник Ир кутского гос. техн. ун-та. Иркутск, 2006. № 4 (28). С. 42– 44.

[5] Архипов В.В., Константинов Ю.М., Мартьянов В.И. Ло гико-эвристические методы поиска вторичных структур РНК // Современные технологии. Системный анализ. Моделирование / ИрГУПС. 2010. № 1 (25). С. 162–167.

[6] Мартьянов В.И., Пахомов Д.В., Архипов В.В. Организа ция рационального управления содержанием региональной се ти автомобильных дорог // Современные технологии. Систем ный анализ. Моделирование / ИрГУПС. 2009. № 2 (22).

С. 55–62.

[7] Мартьянов В.И., Симонов А.С. Анализ и проектирова ние трассы автомобильной дороги // Современные техноло гии. Системный анализ. Моделирование / ИрГУПС. 2008.

№ 4 (20). С. 16–23.

[8] Мартьянов В.И., Паюк П.С. Эвристические методы ана лиза плоских изображений // Тез. докл. конф. “Ляпуновские чтения и презентация информационных технологий”. Ир кутск: ИДСТУ СО РАН, 2002. С. 26.

[9] Каташевцев М.Д., Мартьянов В.И. Логико-эвристические методы анализа плоских изображений // Тез. докл. студ. конф.

“Информационные технологии”. Иркутск: ИМЭИ ИГУ, 2010.

(В печати).

О КЛАССАХ ФУНКЦИЙ ТРЕХЗНАЧНОЙ ЛОГИКИ, ПОРОЖДЕННЫХ СИММЕТРИЧЕСКИМИ ФУНКЦИЯМИ А. В. Михайлович В работе изучаются свойства замкнутых классов функций трехзначной логики. Рассматривается задача о существовании базисов для замкнутых классов, порожденных симметрически ми функциями.

Известно [1], что все замкнутые классы булевых функций имеют конечный базис. В случае многозначных логик это не так. В [2] показано, что при всех k 3 в Pk существуют за мкнутые классы как со счетным базисом, так и классы, не имеющие базиса. В [3, 4] изучались некоторые семейства за мкнутых классов, порожденных симметрическими функциями трехзначной логики, для этих классов приведены критерии ба зируемости и конечной порожденности. В [5] рассматривались некоторые семейства замкнутых классов, порождающие систе мы которых состоят из симметрических функций и конечно го числа функций специального вида. В данной работе также рассматриваются классы трехзначной логики, порождающие системы которых состоят из симметрических функций. Пока зано, что задача базируемости для таких классов сводится к задаче базируемости для классов, порождающие системы ко торых являются подмножествами порождающих систем изу чаемых классов. Все недостающие определения можно найти в [3–5].

Московский государственный университет леса e-mail: avmikhailovich@gmail.com Обозначим через R множество всех функций трехзначной логики, принимающих значения только из множества {0, 1} и равных нулю на единичном наборе и на всех наборах, содержа щих хотя бы одну нулевую компоненту. Пусть f (x1,..., xn ) n R. Будем обозначать через Nf множество всех наборов из E3, на которых функция f принимает значение 1. Множество L n всех наборов из E3, которые получаются друг из друга переста новкой компонент, будем называть слоем. Функция f (x1,..., xn ) из P3 называется симметрической, если для любого слоя L n E3 и любых двух наборов, из L выполняется равенство f () = f (). Множество всех симметрических функций из R обозначим через S. Функцию f (x1,..., xn ) из R будем назы вать m-слойной симметрической функцией, если существует m различных слоев L1,..., Lm {1, 2}n, m 1, таких, что Nf = L1... Lm. Функцию из R будем называть монотон ной, если она монотонна относительно порядка 0 1 2 на множестве E3. Множество всех монотонных симметрических функций из R обозначим через MS. Множество всех немоно тонных m-слойных симметрических функций из R обозначим через NSm.

Пусть f, g S. Определим отношение следующим обра зом. Будем говорить, что функция f не превосходит функцию g относительно, если f [{g}]. Множество H S называ ется цепью, если любые два элемента множества H сравнимы относительно. Цепь H S называется максимальной цепью множества G, если для любой цепи H1 S, такой, что H H1, H = H1, цепь H1 не является подмножеством множества G.

Функция f H называется верхней гранью цепи H, если для любой функции g H выполняется отношение g f. Цепь называется ограниченной, если она имеет верхнюю грань.

Пусть f R. Обозначим через ef число единиц в слое с наибольшим числом единиц, на котором функция f принимает значение 1. Пусть k 0. Множество G S будем называть k ограниченным, если для любой функции f G выполняется неравенство ef k и найдется функция g G, такая, что eg = k.

Утверждение. Пусть F S и существует функция f F, такая, что ef 0. Пусть k 0, а H k-ограниченное мно жество симметрических функций из R, G = [F ], G1 = [H F ].

Тогда G1 имеет базис в том и только том случае, когда G имеет базис.

Используя критерий базируемости для немонотонных m слойных симметрических функций из [3], получаем следую щую теорему.

Теорема 1. Пусть F NSm, m 1, k 0, H k-ограни ченное множество функций из S, G = [F H]. Тогда G имеет базис в том и только том случае, когда каждая функция из F содержится в некоторой ограниченной максимальной цепи множества F.

Используя критерий базируемости для монотонных сим метрических функций из [4], получаем следующую теорему.

Теорема 2. Пусть F MS и существует функция f F, такая, что ef 0. Пусть k 0, H k-ограниченное множе ство функций из S, G = [F H]. Тогда G имеет базис в том и только том случае, когда каждая функция из F содержится в некоторой ограниченной максимальной цепи множества F.

Следствие. Пусть k 0, F k-ограниченное множество функций из S, G = [F ]. Тогда класс G имеет базис.

Работа выполнена при финансовой поддержке РФФИ (про ект 08–01–00863) и программы фундаментальных исследова ний ОМН РАН Алгебраические и комбинаторные методы ма ” тематической кибернетики и информационные системы нового поколения“.

Список литературы [1] Post E. L. The two-valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton Univ. Press. 1941.

5.

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

[3] Михайлович А. В. О замкнутых классах трехзначной ло гики, порожденных симметрическими функциями // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2008. № 4.

С. 54–57.

[4] Михайлович А. В. О классах функций трехзначной ло гики, порожденных монотонными симметрическими функция ми // Вестник Моск. ун-та. Сер. 1. Математика. Механика.

2009. № 1. С. 33–37.

[5] Михайлович А. В. О свойствах замкнутых классов функ ций трeхзначной логики, порожденных симметрическими функ циями // Материалы X междунар. семинара “Дискретная ма тематика и еe приложения” (Москва, МГУ, 1–6 февраля 2010 г.).

М.: Изд-во мех-мат факультета МГУ, 2010. С. 193–196.

РЕЗУЛЬТАТЫ АПРОБАЦИИ КОМПЬЮТЕРНОЙ СИСТЕМЫ MATHSTYLETEST С.Р. Мусифулина Компьютерная система MathStyleTest [1] создана для фор мирования и внедрения тестов по определению индивидуально го стиля математического мышления. Теоретическая база со здания тестов и описание системы представлены в [2], [3].

Для апробации системы была создана база данных заданий и блоков теории по темам: основные понятия теории множеств, алгебра множеств, основы теории отношений, основы теории функций, применение теории множеств к решению логических задач. Общее количество заданий в системе равно 132, зада ния распределены следующим образом: 69 задание на опреде ление стиля математического мышления (порядка 17 заданий на каждую стилевую характеристику), 63 на проверку зна ний, из них 20 на проверку правдивости испытуемого (по 4 в Восточно-Сибирская государственная академия образования (Ир кутск) e-mail: sml24@rambler.ru каждом блоке). В системе 15 блоков теории, из которых 5 ос новных и 10 смысловые гиперссылки. Созданная база пред назначена для студентов младших курсов и учащихся старших классов.

Система MathStyleTest позволяет определять следующие по казателями качества теста:

для заданий на контроль знаний: трудность, дискримина тивность, достаточная вариация тестовых баллов, надёжность;

для заданий на определение стиля математического мыш ления: содержательная и критериальная валидности.

В системе трудность заданий на контроль знаний и провер ку правдивости пользователя рассчитываются как доля непра вильных ответов из общего числа ответов. За тестовые задания также принимаются задания с трудностью меньшей 0.15, име ющие статус правдивость пользователя. Это обусловлено тем, что такие задания должны быть правильно выполнены почти всеми пользователями.

Дискриминативность в системе определяется по индексу дискриминации и точечно-бисериальному коэффициенту. Для заданий на определение правдивости пользователя коэффици енты дискриминативности должны быть не отрицательны. До статочная вариация задания определяется значением диспер сии ответов. Коэффициент надёжности в системе считается по формуле Кьюдера–Ричардсона.

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

Пусть имеются множество пользователей A, ответивших на задания X, определяющих некоторую психологическую харак теристику i. Ai – множество пользователей, которые при ответе на задания из X проявили сильную выраженность характери стики i.

Если более 50 процентов респондентов из множества Ai при ответе на вопрос x из X проявили выраженность характеристи ки i, то задание x будем считать содержательно валидным. В противном случае, содержательно не валидным.

За количественную оценку содержательной валидности за дания x из X, определяющую характеристику i, можно при нять долю ответов пользователей из Ai, проявивших выражен ность характеристики i:

mi (x) SV (x) = 100, n(x) где SV (x) – содержательная валидность задания ;

mi (x) – количество людей из Ai, которые при ответе на за дание x проявили выраженность характеристики i;

n(x) – количество людей из Ai, ответивших на задание x.

Содержательная валидность заданий рассчитывается отдельно для каждой характеристики стиля математического мышления.

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

Первая версия системы была апробирована на студентах первого курса Иркутского государственного педагогического университета (2006-2007), первого курса Иркутского педагоги ческого колледжа №1 (2006-2007), первого курса Иркутского государственного университета (2006-2007). Общий состав вы борки составил 75 человек. Первая версия системы позволила отобрать содержательно и критериально валидные задания по мотивации и восприятию пользователей, определить направ ление составления заданий на метод получения результатов и качество создаваемых моделей.

Вторая версия программы была апробирована на студентах первого и второго курса Иркутского государственного педаго гического университета (2007-2008), первого и второго курса Иркутского педагогического колледжа №1 (2007-2008), перво го курса Иркутского государственного технического универси тета (2007-2008). Общий состав выборки составил 60 человек.

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

Третья версия системы была апробирована на студентах Восточно-Сибирской государственной академии образования (2009-2010), студентах Байкальского государственного универ ситета экономики и права (2009-2010), учащихся старших клас сов 25 гимназии г.Иркутска (2009-2010). Общий объем выбор ки составил 170 человек. Третья версия системы позволила отобрать содержательно и критериально валидные задания по качеству создаваемых моделей пользователей.

Конструктивная (концептуальная) валидность заданий бы ла обеспечена за счёт построения теста по методикам В.М. Мельникова и Л.Т. Ямпольского, которые представлены в методических рекомендациях к системе.

По результатам работы над всеми версиями системы была доказана валидность заданий по определению стиля математи ческого мышления. Надёжность заданий на определение сти ля математического мышления была обеспечена достаточным числом вопросов для каждой характеристики стиля. Общий объём 3-х выборок составил порядка трёх ста человек. Данный объём выборки достаточен для доказательства надёжности и валидности критериальных тестов [3],[4].

Проведённая апробация системы MathStyleTest показала эф фективность применения системы для конструирования тестов на определение стиля математического мышления.

Список литературы [1] Свидетельство об официальной регистрации програм мы для ЭВМ №2010611108. Компьютерная система по опре делению индивидуального стиля математического мышления.

/ Н.А. Перязев, С.Р. Мусифулина. М.: РосПатент, 2010.

[2] Перязев Н.А., Перязева Ю.В., Мусифулина С.Р. Особен ности математического образования с учётом типологии лич ности, основанной на стилях математического мышления.// Вестник Бурятского университета. Серия 8: б) теория и мето дика обучения естественно–математическим дисциплинам. Вы пуск 2.– Улан–Удэ, Издательство Бурятского госуниверситета, 2005.– С.8–14.

[3] Мусифулина С.Р. Экспертная система для определения стиля математического мышления. // Программные продукты и системы. 2008. №1 С.87 89.

[4] Клайн П. Справочное руководство по конструированию тестов: Введение в психометрическое проектирование: Пер. с англ. / Под ред. Л.Ф. Бурланчука. Киев: ПАН Лтд., 1994.

[5] Майоров А.Н. Теория и практика создания педагогиче ских тестов для системы образования. М.: Интеллект центр, 2002.

ПРОДОЛЖЕНИЯ ЧАСТИЧНЫХ 1-ИЗОМОРФИЗМОВ КОНЕЧНЫХ ПРЕДИКАТНЫХ СИСТЕМ Е.В. Овчинникова Для алгебраической системы A = A, любой изомор физм между ее подсистемами A1 и A2 (мощности k) называется частичным (k-) изоморфизмом системы A.

Хрушовский [1] установил, что для любых конечного неори ентированного графа без петель A и его частичных изоморфиз мов p1,..., pm существует конечный граф B, расширяющий A, и автоморфизмы графа B, расширяющие p1,..., pm.

Новосибирский государственный технический университет e-mail: eovchin@ngs.ru Хервиг [2] доказал эту теорему для конечных структур ко нечной предикатной сигнатуры, на основе метода Хрушовского построения расширяющей модели.

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

Теорема. Пусть A = A, предикатная система мощно сти n. Тогда существует система B = B, мощности не более чем en, расширяющая систему A и в которой любой частичный 1-изоморфизм продолжается до автоморфизма.

Работа продолжает исследования, начатые в [3], и выполне на при финансовой поддержке Российского фонда фундамен тальных исследований, проект 09-01-00336-а.

Список литературы [1] Hrushovski E. Extending Partial Isomorphisms of Graphs // Combinatorica.– 1992.– Vol. 12.– P. 411–416.

[2] Herwig B. Extending Partial Automorphisms on Finite Struc tures // Combinatorica.– 1995.– Vol. 15.– P. 365–371.

[3] Овчинникова Е.В. 1-однородные расширения конечных предикатных структур // Алгебра и теория моделей, 7. Сбор ник трудов.– Новосибирск: изд-во НГТУ, 2009.– С. 54–59.

О СТРУКТУРАХ С КАТЕГОРИЧНОЙ СТЕПЕНЬЮ ФРЕШЕ Е.А. Палютин Структура A языка L называется h-категоричной, если тео рия T h(AF ) ее приведенной степени AF по фильтру Фреше F на множестве категорична в мощностях |L| +.

Определение P -формулы можно найти в [1]. Если в извест ном определении элементарной определимости вместо произ вольных формул рассматривать только P -формулы, то полу чится понятие P -определимости.

Институт математики СО РАН, г. Новосибирск e-mail: palyutin@math.nsc.ru Структура A называется P -антиаддитивной, если в ней нельзя P -определить нетривиальную группу.

Теорема 1. Если структура A является h-категоричной и P -антиаддитивной, то теорию T h(AF ) ее Фреше-степени мож но обогатить до категоричного квазимногообразия с тем же рангом Морли.

Категоричные квазимногообразия полностью описаны (см.

[2]), таким образом, теорема 1 дает полное описание h-катего ричных структур, в которых нельзя с помощью P -формул опре делить нетривиальных групп. Проблема полного описания h категоричных структур представляется чрезвычайно трудной.

Отметим, что категоричные квазимногообразия являются по чти сильно минимальными. Это свойство существенно упро щает проблему описания. Следующая теорема показывает, что существование P -определимой нетривиальной группы в струк туре A принципиально осложняет строение ее h-категоричной Фреше-степени.

Теорема 2. Для любого простого числа p и натурального числа n 1 циклическая группа порядка pn h-категорична и теорию T h(AF ) ее Фреше-степени нельзя обогатить до почти сильно минимального хорнова класса.

Доказательство теоремы 2 по существу содержится в руко писи [3]. Отметим, что в [4] указана некоторая связь проблемы обогащения категоричных хорновых классов до почти сильно минимальных хорновых классов с вопросами расщепления точ ных последовательностей групп.

Работа поддержана грантом РФФИ № 09-01-00336-а и Со вета по грантам Президента РФ для поддержки ведущих на учных школ (проект НШ-3669.2010.1).

Список литературы [1] Палютин Е.А. Интерпретация графов в некоммутатив ных теориях степеней Фреше// Фундаментальная и приклад ная математика, т. 15, выпуск 2, 2009, стр. 145-167.

[2] Палютин Е.А. Описание категоричных квазимногообра зий// Алгебра и логика, т.14, N 2(1975), с. 145-185.

[3] Палютин Е.А. Спектр и структура моделей хорновых теорий// Докторская диссертация, Новосибирск, 1986, 314 стр.

[4] Палютин Е.А. О категоричных нормальных теориях ран га 3// Тезисы докладов Междуна родной конференции Маль цевские чтения, посвященная 70-летию академика Ю.Л.Ершо ва, Новосибирск, 2-6 мая 2010 г. с. 140.

ОБ ОДНОМ СЕМЕЙСТВЕ МАКСИМАЛЬНЫХ ЧАСТИЧНЫХ ГИПЕРКЛОНОВ В.И. Пантелеев Пусть A конечное множество. n-местной мультифункци ей на множестве A называется отображение f : An 2A, а отображение ei : (x1,..., xn ) n-местной мультипроекцией n {xi }, 1 i n.

Суперпозиция f (f1,..., fm ) с внешней мультифункцией f и внутренними мультифункциями f1 (x1,..., xn ),..., fm (x1,..., xn ) определяет мультифункцию h1 (x1,..., xn ) следующим образом:

, если существует i {1,..., m} такое, что fi (a1,..., an ) = ;

h1 (a1,..., an ) = f (b1,..., bm ), иначе.

bi fi (a1,...,an ) Частичным гиперклоном называется множество мульти функций, содержащее все мультипроекции и замкнутое отно сительно суперпозиции. Максимальный частичный гиперклон определяется обычным образом.

Для, принадлежащего A, определим множество T :

T = {f (x1,..., xn ) | f (,..., ) или f (x1,..., xn ) }.

Теорема. Для любого из A множество T является максимальным частичным гиперклоном.

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

TE = {f | f (a1,..., an ) = B, ai E, B E}, где E непустое подмножество множества A.

Список литературы 1. Пантелеев В. И. О некоторых максимальных частичных гипер- и ультраклонах // Материалы XVIII Международной школы-семинара "Синтез и сложность управляющих систем" имени академика О. Б. Лупанова (Пенза, 28 сентября – 3 октяб ря 2009 г.) / под ред. О. М. Касим-Заде. М.: Изд-во механико математического факультета МГУ, 2009. С. 73–75.

О ПОЛНОТЕ НЕКОТОРЫХ КЛАССОВ ЧАСТИЧНО УПОРЯДОЧЕННЫХ ПОЛИГОНОВ М.А. Первухин В [1] рассматривались полигоны, удовлетворяющие усло вию (EP ). В частности, доказывается, что полигон, удовле творяющий условию (EP ) является свободным. В. Гоулд и Л.

Шахиин в [2] были рассмотрены частично упорядоченные по лигоны, удовлетворяющие условию (EP ), и получены условия аксиоматизируемости класса частично упорядоченных полиго нов, удовлетворяющих условию (EP ). Условие (EP ) : если для любого b B и любых s, s S выполняется sb s b, то суще ствуют b B и u, u S такие, что b = ub = u b и su s u.

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

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

Владивостокский государственный университет экономики и сервиса e-mail: pervukhinma@yandex.ru Также в [2] получена характеризация частично упорядочен ного моноида с аксиоматизируемым классом частично упоря доченных полигонов, удовлетворяющих условию (Pw ). Условие (Pw ) : если для любых b, b B и любых s, s S выполняется sb s b, то существуют b B и u, u S такие, что su s u, b ub и u b b. В работе получен следующий результат:

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

Работа выполнена при поддержке РФФИ, проект 09-01 00336-а.

Список литературы [1] Golchin A. On Condition (EP) // International Mathematical Forum 2. 2007. №19 P. 911–918.

[2] Gould V., Shaheen L. Axiomatisability problems for S-posets // Semigroup forum. (в печати) МИНИМАЛЬНЫЕ СУПЕРКЛОНЫ РАНГА Н.А. Перязев, Ю.В. Перязева Пусть B(A) множество всех подмножеств A, в том числе. Отображение из An в B(A) называется n-местной мультио перацией на A (допускается случай n = 0). Для множества всех n n-местных мультиопераций на A используем обозначение HA.

n.

Используем также обозначения HA = n0 HA Пусть K HA. Следуя [1], алгебру K = K;

,,,, µ, с операциями определенными ниже называем суперклоном над A:

• (f g)(a1,..., an+m1 ) = {a|существует a0 g(a1,..., am ) Восточно-Сибирская государственная академия образования e-mail: nikolai.baikal@gmail.com, peryazeva@list.ru такой, что a f (a0, am+1,..., am+n1 )} при n 1, (f g)(a1,..., am ) = f (), если g(a1,..., am ) = и (f g)(a1,..., am ) =, если g(a1,..., am ) = при n = 0;

• (f )(a1,..., an ) = f (a2,..., an, a1 ) при n 1, (f ) = f при n 1;

• ( f )(a1,..., an ) = f (a2, a1, a3,..., an ) при n 1, ( f ) = f при n 1;

• (f )(a1,..., an1 ) = f (a1, a1, a2,..., an1 ) при n 1, (f ) = {a|a f (a)} при n = 1, (f ) = f при n = 0;

• (µf )(a1,..., an ) = {a|a1 f (a, a2,..., an )}, при n 1, (µf ) = при n = 0;

• = e, где e(a1, a2 ) = {a1 }.

Суперклон называется наименьшим над A, если он явля ется подалгеброй любого суперклона над A. Суперклон над множеством A называется минимальным, если он не содер жит никаких суперклонов отличных от себя и наименьшего над A. Рангом суперклона называется |A|. Все суперклоны одного ранга изоморфны.

Ниже приводится описание всех минимальных суперклонов ранга 3.

Мультиоперации f MA, где A = {a0,..., ak1 } можно представлять как отображения f : {20, 21,..., 2k1 }n {0, 1,..., 2k 1}, получаемые из f при кодировке ai 2i ;

0;

{ai1,..., ais } 2i1 +... + 2is.

При этом n-местную мультиоперацию f задаем векторной формой f = (1,..., kn ), где f (2i1,..., 2in ) = i и (i1,..., in ) есть представление i в системе исчисления по основанию k. Через f будем обозначать суперклон, порожденный мультиопе рацией f.

Теорема. Любой минимальный суперклон ранга 3 является одним из суперклонов из следующего списка (1), (2), (4), (3), (5), (6), (166), (334), (525), (764), (175), (327), (735), (376), (567), (241), (735376567), (124241412241412124412124241).

Как легко видно, 6 минимальных суперклонов порожда ются 0-местными мультиоперациями, 10 1-местными муль тиоперациями, 1 2-местной мультиоперацией и 1 3 местной мультиоперацией. При этом интересно, что суперклон (735376567) является подалгеброй некоторых суперкло нов, порожденных 1-местной мультиоперацией, например, су перклона (653).

Работа выполнена при поддержке РФФИ, проект 09-01 00476.

Список литературы [1] Перязев Н.А. Суперклоны мультиопераций // Труды VIII Международной конференции “Дискретные системы в тео рии управляющих систем”. – М.: МАИС Пресс. – 2009. – С.

233–238.

МУЛЬТИОПЕРАЦИИ И ИХ ПРЕДСТАВЛЕНИЯ СТАНДАРТНЫМИ ФОРМАМИ Н.А. Перязев, И.А. Яковчук Пусть B(A) множество всех подмножеств A, в том числе. Отображение из An в B(A) называется n-местной мультио перацией на A. Для множества всех n-местных мультиопераций Восточно-Сибирская государственная академия образования e-mail: nikolai.baikal@gmail.com, inna_andrey@list.ru n на A используем обозначение HA. Рангом суперклона называ ется |A|. Так как все суперклоны одного ранга изоморфны, то n используем обозначение Hk для суперклона ранга k.

n Мультиоперации f HA, где A = {a0,..., ak1 } можно пред ставлять как отображения f : {20, 21,..., 2k1 }n {0, 1,..., 2k 1}, получаемых из f при кодировке ai 2i ;

0;

{ai1,..., ais } 2i1 +... + 2is.

При этом n-местную мультиоперацию f задаем векторной формой f = (1,..., kn ), где f (2i1,..., 2in ) = i и (i1,..., in ) есть представление i в системе исчисления по основанию k.

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

Пусть мультиоперация Hk, определяется следующим образом: (a, b) = {a} {b}. Как принято для бинарных опера ций будем вдальнейшем использовать суфиксную форму запи си (a, b) = (a b). Очевидно, что эта мультиоперация комму тативна и ассоциативна. Поэтому, как обычно, несущественные скобки будем опускать.

Следующие мультиоперации p Hk и dn Hk определим n i, через их векторное задание p = (2, 4,..., 2k1, 1);

i di, = (2k 1,..., 2k 1,, 2k 1,..., 2k 1), (1 i k n ), n где {0,..., 2k 2}. В частности d0 = ().

1, n Пусть f Hk. Тогда следующее представление назовем стандартной формой мультиоперации [1] f (x1,..., xn ) = dj (xi1,..., xim ), j где dj {di, | 0 m n, {0,..., 2k 2}}.

m Очевидно, что представление мультиоперации стандарной формой не единственно. Поэтому правомерна задача миними зации, то есть по векторному заданию мультиоперации найти ее представление в классе стандартных форм с наименьшим количеством компонент пересечения. Для решения этой зада чи разработан алгоритм [2], позволяющий найти минималь n ное представление n-местной мультиоперации f Hk в классе стандартных форм с использованием алгоритма минимизации булевых функций в классе дизъюнктивных нормальных форм.

Для тестирования алгоритма была написана компьютерная программа и проведена минимизация всех мультиоперций на двухэлементном множестве в классе стандартных форм для n = 2 и n = 3. Статистические данные числа мультиопераций распределения по сложности минимального представления в классе стандартных форм приведены ниже.

Cредняя сложность:

Laver (2) = 2.38, Laver (3) = 4.14.

Распределение по сложности при n = 2:

L1 2 3 K 24 124 92 %9.4548.8236.225. Распределение по сложности при n = 3:

L1 2 3 4 5 K 78 17651331928966171443724 512 %0.12 2.69 20.32 44.2 26.16 5.69 0.780. Из [2] следует, что сложность алгоритма является экспо ненциальной. В тоже время, он хорошо распараллеливается.

Поэтому в настоящее время разрабатывается программная ре ализация алгоритма, основанная на принципах параллельного программирования.

Работа выполнена при поддержке РФФИ, проект 09-01 00476.

Список литературы [1] Перязев Н.А. Суперклоны мультиопераций // Труды VIII Международной конференции “Дискретные системы в тео рии управляющих систем”. – М.: МАИС Пресс. – 2009. – С.

233–238.

[2] Перязев Н.А., Яковчук И.А. Алгоритм нахождения пред ставления мультиопераций минимальной стандартной фор мой // Материалы X Международного семинара “Дискрет ная математика и ее приложения“. – М.: Изд-во Механико математического факультета МГУ. – 2010. – С. 203–206.

О -КВАЗИМНОГООБРАЗИЯХ А.Г. Пинус В алгебраической геометрии универсальных алгебр важную роль играют так называемые -квазитождества (см., к приме ру, [1]), т. е. формулы вида x ((x) s(x) = t(x)), где x конечная совокупность переменных, (x) конъюнк ция (возможно бесконечная) равенств между термами неко торой фиксированной сигнатуры от переменных x, а s(x), t(x) термы сигнатуры от переменных x.

-Квазимногообразием назовем любой класс алгебр K фиксированной сигнатуры, состоящий из всех алгебр сиг натуры, на которых истинны -квазитождества из некото рой фиксированной совокупности таковых (-q-теории класса K). Цель настоящей работы рассмотрение основных свойств -квазимногообразий. Некоторые сведения об аналогах ква зимногообразий в бесконечных языках можно найти в моно графии [2].

Новосибирский государственный технический университет Очевидно, что любое -квазимногообразие замкнуто отно сительно перехода к подалгебрам и относительно прямых про изведений, т. е. SK = K и P K = K. Здесь, традиционно, SK класс всех подалгебр K-алгебр, а P K класс всех прямых про изведений K-алгебр.

Через IK будем обозначать класс всех алгебр, изоморфных какой-либо из K-алгебр.

Напомним, что прямым спектром Ai, ij, I;

алгебр Ai называется совокупность алгебр Ai (i I), где I;

неко торое направленное вверх частично упорядоченное множество, и для i j элементов из I ij гомоморфизм алгебры Ai в алгебру Aj, при этом для i j k: jk ij = ik.

Если, кроме того, все гомоморфизмы ij являются изо морфными вложениями (алгебры Ai в алгебру Aj, соответ ственно), то будем говорить о прямом K-спектре вложимости.

Через lim K обозначим совокупность прямых пределов лю бых прямых K-спектров вложимости. Очевидным образом лю бое -квазимногообразие K замкнуто относительно своих пря мых пределов вложимости, т. е. lim K K.

Теорема 1. Класс алгебр K сигнатуры является -квази многообразием тогда и только тогда, когда IK K, SK K, P K K и lim K K.

Теорема 2. Для любого класса -алгебр K имеет место ра венство Q (K) = lim ISP (K).

Список литературы [1] А. Г. Пинус. Геометрические шкалы многообразий алгебр и квазитождества. Математические труды, т. 12, № 2, с. 160–169.

[2] В. А. Горбунов. Алгебраическая теория квазимногообра зий. Новосибирск, Изд-во Научная книга, 1999.

[3] А. Г. Пинус. О геометрически полных многообразиях. в печати.

РЕШЕТКИ СЛАБЫХ КОНГРУЭНЦИЙ УНАРНЫХ АЛГЕБР Д.О. Птахов В данной работе рассматриваются унары с решетками сла бых конгруэнций специального вида.

Напомним некоторые определения.

Пусть A – алгебра. Симметричная, транзитивная подалгеб ра алгебры A2 называется слабой конгруэнцией алгебры A. Со вокупность слабых конгруэнций алгебры A является частично упорядоченным множеством относительно, т.е. образует ре шетку.

Введем обозначения: Cw (A) – решетка слабых конгруэнций алгебры A;

C(A) – решетка конгруэнций алгебры A;

S(A) – решетка подалгебр алгебры A.

Для любой слабой конгруэнции Cw (A) через A обозна чим наименьшую конгруэнцию алгебры A, содержащую.

Говорят, что алгебра A обладает свойством CIP(congruence intersection property), если для любых, Cw (A) A A = ( )A.

Заметим, что A =, т.е. CIP эквивалентно дистрибутив ности, где = {(x, x)|x A}.

Говорят, что алгебра A обладает свойством CEP(Congruence extension property), если каждая конгруэнция собственной по далгебры алгебры A является ограничением некоторой конгру энции алгебры A.

Унарной алгеброй называется алгебра сигнатуры = {fi }iI, где fi – унарные операции.

Унаром называется унарная алгебра сигнатуры, состоящей из одной унарной операции.

В работе [1] приводится критерий модулярности решетки слабых конгруэнций алгебры, а именно:

Дальневосточный государственный университет e-mail: ptaxov@mail.ru Решетка Cw (A) слабых конгруэнций алгебры A модулярна тогда и только тогда, когда 1) C(A) – модулярна;

2) S(A) – модулярна;

3) A обладает свойством CIP;

4) A обладает свойством CEP.

Используя данное утверждение, несложно доказать следу ющую теорему.

Теорема 1. Решетка Cw (A) слабых конгруэнций унарной алгебры A модулярна тогда и только тогда, когда модулярна решетка C(A) конгруэнций унарной алгебры A.

Теорема 2. Решетка Cw (A) слабых конгруэнций унарной алгебры A дистрибутивна тогда и только тогда, когда дистри бутивна решетка C(A) конгруэнций унарной алгебры A.

В работе [2] описываются унары, решетки конгруэнций ко торых модулярны, дистрибутивны. Таким образом, теоремы и 2 дают, в частности, описание унаров с модулярными и дис трибутивными решетками слабых конгруэнций.

Для формулировки следующей теоремы понадобится пона добится ряд определений. Унар A называется циклом длины n, где n N, если A = {a0, a1,..., an1 }, где f (ai ) = ai+1, (0 i n 1) и f (an1 ) = a0. Пусть x, y – элементы некоторого унара.

Тогда запись x y означает, что f k (x) = y для некоторо го k N. Нетрудно заметить, что является квазипорядком.

Хвостом цикла A называется неодноэлементное подмножество унара, являющееся цепью относительно. Хвост длины 1 на зывается коротким хвостом.

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


Унары с линейной решеткой слабых конгруэнций так же описаны в работе [2]. Из этого описания и теоремы 3 следу ет, что класс унаров с линейной решеткой слабых конгруэнций строго содержится в классе унаров с линейной решеткой кон груэнций.

Список литературы [1] Vojvodic, G., Seselja, B.: On the lattice of weak congruence relations// Algebra Universalis. 1988.V.28. C.121–130.

[2] Егорова Д. П.: Структура конгруэнций унарной алгеб ры// Упорядоченные множества и решётки: Межвуз. науч. сб.

Вып. 5. 1978. C.11–44.

NP-ПОЛНОТА ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО СБАЛАНСИРОВАНИЯ 3-МЕРНОЙ МАТРИЦЫ В.С. Рублев, А.В. Смирнов В [1-5] изучалась задача целочисленного сбалансирования 3-мерной матрицы и подходы к построению эффективного ал горитма ее решения. Напомним постановку задачи.

Дана 3-мерная матрица A с неотрицательными рациональ ными элементами aijp и размерности (n + 1) (m + 1) (t + 1), для которой выполнены условия баланса:

n m t m t aijp (i 1, n);

a000 = aijp ;

ai00 = i=1 j=1 p=1 j=1 p= n t n m aijp (j 1, m);

aijp (p 1, t);

a0j0 = a00p = i=1 p=1 i=1 j= t aijp (i 1, n, j 1, m);

aij0 = p= m aijp (i 1, n, p 1, t);

ai0p = j= n aijp (j 1, m, p 1, t).

a0jp = i= Ищется целочисленная сбалансированная матрица D той же размерности, для которой выполнены условия:

dijp {aijp, aijp } (i 0, n, j 0, m, p 0, t);

Ярославский государственный университет им. П.Г. Демидова e-mail: roublev@mail.ru n m t d000 = a000 + 0.5;

d000 = dijp ;

i=1 j=1 p= m t n t dijp (i 1, n);

d0j0 = dijp (j 1, m);

di00 = j=1 p=1 i=1 p= nm (p 1, t);

d00p = dijp i=1 j= t dijp (i 1, n, j 1, m);

dij0 = p= m dijp (i 1, n, p 1, t);

di0p = j= n dijp (j 1, m, p 1, t).

d0jp = i= Для 2-мерной матрицы задача сводится к потоковой зада че, всегда имеет решение, которое может быть найдено эффек тивным алгоритмом [6]. Однако данная задача уже не имеет эффективного сведения к потоковой задаче и может не иметь решения. Причина этого кроется в ее NP-полноте.

Теорема. Задача распознавания существования решения целочисленного сбалансирования 3-мерной матрицы является NP-полной.

Доказательство. Покажем полиномиальное сведение клас сической NP-полной задачи 3-мерного сочетания (3-С) [7] к за даче распознавания существования целочисленного сбаланси рования 3-мерной матрицы (ЦС3). Напомним постановку зада чи 3-С:

Дано подмножество M I J P, где |I| = |J| = |P | = n.

Верно ли, что M содержит трехмерное сочетание, т. е. подмно жество M, такое, что |M | = n и никакие 2 разных элемента M не имеют ни одной равной координаты?

Таким образом, индивидуальная задача 3-С определяется множеством M 3-мерных индексов. Поставим ей в соответствие следующую систему линейных неравенств (1)–(6):

(i, j, p) M ;

(1) xijp = 0, xijp 1 (n 1), (i, j, p) M ;

(2) n n xijp 1, p 1, n;

(3) i=1 j= n n xijp 1, j 1, n;

(4) i=1 p= n n xijp 1, i 1, n;

(5) j=1 p= n n n 1 n (6) xijp n +, 2 i=1 j=1 p= где = 4n3.

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

1. Пусть индивидуальная задача 3-С имеет решение M. То гда это решение индуцирует решение задачи ЦС3, полу ченной решением системы (1)–(6).

2. Пусть матрица X является решением системы (1)–(6), и задача, определяемая этим решением, имеет в свою оче редь решение M = {xijp | xijp = 1}. Тогда очевидно, что сочетание индексов этого решения определяет решение задачи 3-С. Поэтому это решение M является решением любой задачи ЦС3, матрица которой определяется реше нием системы (1)–(6).

3. Если индивидуальная задача 3-С не имеет решения, то либо система (1)–(6) не имеет решения, либо любая за дача ЦС3, матрица которой определяется решением си стемы (1)–(6), не имеет решения (иначе такое решение определяло бы решение индивидуальной задачи 3-С).

4. Если какая-либо задача ЦС3, определяемая решением си стемы (1)–(6), не имеет решения, то индивидуальная за дача 3-С также не имеет решения (в противном случае ре шение последней определяло бы и решение любой задачи ЦС3, матрица которой определяется решением системы (1)–(6)).

Утверждение теоремы полностью обосновано.

Работа поддержана государственным контрактом № П161 в рамках ФЦП Научные и научно-педагогические кадры инно вационной России на 2009-2013 годы.

Список литературы [1] Кондаков А.С., Рублев В.С., Задача округления много мерной матрицы и обобщение теории потоков // Алгебра, ло гика и кибернетика: материалы международной конференции, посвященной 75-летию со дня рождения профессора А.И.Коко рина.– Иркутск: ИГПУ, 2004.– С. 247 – 248.

[2] Рублев В.С., Смирнов А.В., Целочисленное сбалан сирование 3-мерной матрицы плана // Дискретные модели в теории управляющих систем: труды VII Международной конференции.– М.: МГУ, 2006.– С. 302 – 308.

[3] Рублев В.С., Смирнов А.В., Послойный алгоритм цело численного сбалансирования трехмерной матрицы // Дискрет ная математика и ее приложения: материалы IX Международ ного семинара, посвященного 75-летию со дня рождения ака демика О.Б.Лупанова.– М.: МГУ, 2007.– С. 351 – 353.

[4] Рублев В.С., Смирнов А.В., Минимизация ошибок округ ления в задаче целочисленного сбалансирования трехмерной матрицы // Синтез и сложность управляющих систем: мате риалы XVII Международной школы-семинара им. академика О.Б.Лупанова.– Новосибирск: ИМСОРАН, 2008.– C. 153 – 157.

[5] А. В. Смирнов. Задача целочисленного сбалансирова ния трехмерной матрицы и сетевая модель // Моделирование и анализ информационных систем, 2009, Т. 16, №3. C. 70 – 76.

[6] 3. Н.М. Коршунова, В.С. Рублев, Задача целочисленного сбалансирования матрицы // Современные проблемы матема тики и информатики, вып.3.– Ярославль: ЯрГУ им. П.Г. Де мидова, 2000.– С. 145 – 150.

[7] Гэри М., Джонсон Д., Вычислительные машины и труд норешаемые задачи. М.: Мир, 1982.

ОБОБЩЕННАЯ СТАБИЛЬНОСТЬ АБЕЛЕВЫХ ГРУПП БЕЗ КРУЧЕНИЯ М.А. Русалеев В [1] Е.А.Палютин ввел новое понятие E -стабильности полной теории, которое обобщает понятие стабильности, вве денное Шелахом [2]. Обобщенная стабильность дает сразу шка лу понятий, в которой параметром является отображение ти пов E. Одним из частных случаев обобщенной стабильности является (P, a)-стабильность, исследованию которого посвяще на данная работа.

Определение. Полная теория T языка L называется (P, a)-стабильной в мощности, если для любого множества переменных X мощности, не превосходящей, и для любого полного типа t(X) теории T над множеством переменных X, тип t(X) {P (x)|x X} {P (M ) является алгебраически за мкнутым множеством относительно языка L для любой мо дели M} имеет не более пополнений в языке LP, полученном добавлением к L нового одноместного предиката P. Теория T Институт математики им. Соболева СО РАН e-mail: rusma@ngs.ru называется (P, a)-стабильной, если она (P, a)-стабильна в неко торой бесконечной мощности.

В работе рассматривается вопрос о (P, a)-стабильности абе левых групп. Основным результатом является следующая тео рема:

Теорема. Если T полная теория абелевой группы без кручения, то T является (P, a)-стабильной.

Так же интересными являются следующие примеры. Пер вый пример показывает, что существуют абелевы группы, не являющиеся (P, a)-стабильными. Второй пример показывает, что существуют абелевы группы, не являющиеся группами без кручения, но являющиеся (P, a)-стабильными.

Пример 1. Пусть G = Gi, где Gi Z4 циклические i группы порядка 4, для i. Теория T = Th(G) не (P, a) стабильна.

Пример 2. Пусть G группа, являющаяся прямой сум мой бесконечного числа циклических групп порядка p, где p простое. Теория T = Th(G) является (P, a)-стабильной.

Работа выполнена при поддержке РФФИ, проект 09-01 00336-а.

Список литературы [1]Е. А. Палютин, "E -стабильные теории Алгебра и логи ка, т.42, N 2(2003), с. 194-210.

[2]S.Shelah, Stable theories, Israel J. Math. 7 (1969) 187-202.

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

Полиномиальной нормальной формой (ПНФ) функции f называется ее представление в виде суммы по модулю 2:

f (x1,..., xn ) = K1 · · · Ks, (1) в которую в качестве слагаемых входят элементарные конъ произведения Ki = z1 · · · · · zki, где zj = xt или юнкции zj = xt для некоторой переменной xt, причем переменная мо жет входить в произведение не более одного раза. В сумму мо жет входить Ki, не содержащее ни одной переменной. Такое Ki считается равным 1.

Для функции f представление (1) не единственно. Поэтому естественно рассмотреть сложность представления (1) функ ции f (x1,..., xn ) как s число слагаемых.

Сложность L(f ) функции f (x1,..., xn ) определяется как сложность минимального представления этой функции.

Обычно корнекеровы формы записывают в виде кронеке рова произведения трех видов базисов [x, x], [1, x], [1, x]. Число кронекеровых произведений определяется количеством пере менных функции.

В [1] показано, что задача нахождения минимальных пред ставлений булевых функций в классе кронекеровых форм мо жет быть сведена к задаче нахождения сложности вложения Восточно-Сибирская государственная академия образования e-mail: l.riabets@gmail.com специальной операторной формы функции (SOF (f )) в клас сы операторных пучков специального вида. Всего таких клас сов 3n и они однозначно определяются своими порождающими операторами. Действие операторов и операторных пучков по дробно описано в [2]. Свойства специальной операторной фор мы булевой функции можно найти в [3].


Так же в [1] предложен алгоритм получения минимальных кронекеровых форм булевых функций. Алгоритм позволяет находить точный минимум, но является экспоненциальным, и уже для функций, зависящих от 13 переменных, требует зна чительного времени выполнения.

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

В начале работы алгоритма создается случайная популя ция. На каждой итерации происходит определенное число крос соверов и мутаций. Как показали эксперименты, наилучшие результаты получаются при популяции из 1000 особей после 10000 итераций. Каждая итерация состоит из одного кроссо вера и одной мутации. На каждой итерации особи для приме нения генетических преобразований выбираются случайно сре ди всей популяции с одинаковой вероятностью. Более сложный выбор особей (например, логарифмический) не дает ощутимых изменений в работе алгоритма.

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

Работа выполнена при поддержке РФФИ (проект 09-01 00476-а).

Список литературы [1] Винокуров С.Ф.,Рябец Л.В. Алгоритм точной минимиза ции булевых функций в классе кронекеровых форм// Алгебра и теория моделей 4. Новосибирск: Из-во Новосиб. гос. тех. ун та.– 2003.– С. 148 159.

[2] Избранные вопросы теории булевых функций// Под ред.

Винокурова С.Ф. и Перязева Н.А.– М.: ФИЗМАТЛИТ, 2001.– 192 с.

[3] Винокуров С.Ф. Казимиров А.С. Некоторые свойства специальной операторной формы булевых функций// Дис кретные модели в теории управляющих систем: Труды VI Международной конференции.– М.: Издательский отдел Фа культета ВМиК МГУ.– 2004.– С. 19–21.

ПРИМЕНЕНИЕ РЕШАЮЩИХ ДИАГРАММ В СИСТЕМАХ ПРОПОЗИЦИОНАЛЬНОГО ВЫВОДА А.А. Семенов, А.С. Игнатьев Двоичные диаграммы решений (двоичные решающие диа граммы, BDD) представляют булевы функции в классе графов специального вида [1, 2]. Такое представление дает возмож ность осуществлять ряд важных операций над двумя булевыми функциями за полиномиальное время от размера (числа вер шин) представляющих их ROBDD (ROBDD это сокращенная BDD). В настоящее время ROBDD активно используются в ре шении задач верификации дискретных управляющих систем и программных логик. В работе [3] были исследованы возможно сти системы пропозиционального вывода, в качестве правила вывода в которой использовался алгоритм APPLY [1]. Некото рые результаты статьи [3] представляются искусственными и Институт динамики систем и теории управления СО РАН, Иркутск e-mail: biclop@rambler.ru, alexey.ignatiev@gmail.com требуют дальнейшей доработки. В частности, к таковым сле дует отнести результаты, аргументирующие большую эффек тивность ROBDD-вывода в сравнении резолютивным выводом на специальных классах формул. Между тем очень просто по казать неэффективность процедуры построения ROBDD для формул, заданных в виде хорновских КНФ [4], в предположе нии, что P = N P.

Двоичные диаграммы в чистом виде малопригодны и при решении задач обращения сложных дискретных функций (на пример, криптографических). На таких тестах ROBDD-реша тель существенно проигрывает лучшим современным SAT-ре шателям, модифицированным с учетом особенностей исходных постановок.

В работе [4] в отношении задач обращения полиномиально вычислимых дискретных функций была предложена идея по строения гибридного SAT+ROBDD решателя, в котором пред полагалось использовать ROBDD для представления баз кон фликтных дизъюнктов, накапливаемых модифицированным нехронологическим DPLL-алгоритмом. Эксперименты в этом направлении показали, что массивы порождаемых в процессе DPLL-вывода ограничений дизъюнктов допускают очень ком пактные ROBDD-представления (сотни мегабайт накопленных ограничений сжимаются в ROBDD на нескольких десятках вершин). Полученные результаты сделали актуальной следую щую задачу. Разработать и реализовать решатель, ориентиро ванный на задачи обращения полиномиально вычислимых дис кретных функций и основанный на гибридном SAT+ROBDD выводе. При этом требуется реализовать алгоритмы подста новки и вывода значений булевых переменных в ROBDD (диа грамма при этом ведет себя фактически как формула исчис ления высказываний). Данные алгоритмы были реализованы и приведены в работе [5]. Кратко остановимся на основных ре зультатах [5].

Определение 1. Пусть B ROBDD-представление про извольной тотальной булевой функции fn : {0, 1}n {0, 1}, булевы переменные, приписанные вершинам B.

x1,..., xn Каждой переменной xi, i {1,..., n}, и терминальным вер шинам 0, 1 ROBDD B поставим в соответствие множества значений данной переменной, задаваемых всевозможными пу тями в B из корня в соответствующую терминальную вершину.

Данные множества обозначим через 0 (xi ), 1 (xi ).

Предположим, что в некоторой ROBDD B выполнены пе речисленные ниже условия.

1. Для некоторой переменной xk X, X = {x1,..., xn }, любой путь из корня B(f ) в терминальную 1 обяза тельно проходит через некоторую вершину, помеченную переменной xk.

2. Справедливо 1 (xk ) = 1.

Результатом данной ситуации является заключение о том, что в любом наборе значений истинности переменных из мно жества X, на котором значение функции f, представленной B, равно 1, переменная может принимать только одно значение (соответствующее значение в 1 (xk )).

Определение 2. Определяемую условиями 1–2 ситуацию далее называем ROBDD-следствием соответствующего значе ния для переменной xk.

Теорема 1 (см. [5]). Пусть в ROBDD B подставляются значения переменных xi1 = i1,..., xim = im, m n, ij {0, 1}, j {1,..., m}.

Сложность детерминированной процедуры, осуществляющей данную подстановку и проверяющей наличие всевозможных ROBDD-следствий, есть O (n · |B|).

Также справедливо следующее утверждение.

Теорема 2 (см. [5]). Если результатом некоторой подста новки в B является ROBDD-следствие xk = k, k {0, 1}, для некоторой xk X, то подстановка в B xk = k не может привести к возникновению нового ROBDD-следствия, индуци рованного данной подстановкой.

Данная теорема демонстрирует следующее свойство RO BDD как структуры данных: порождаемые произвольной под становкой ROBDD-следствия сами по себе новых ROBDD-след ствий породить не могут и, таким образом, вся информация, индуцируемая данной подстановкой, извлекается в результате однократного обхода ROBDD. Это свойство контрастирует со свойствами КНФ при применении стратегии распространения булевых ограничений (BCP): данная стратегия может потребо вать многократных итеративных подстановок выводимых зна чений булевых переменных (тем самым требуется многократ ный обход формулы).

На основе перечисленных результатов, а также ряда резуль татов, приведенных в [5], был построен параллельный гибрид ный SAT+ROBDD-решатель [6], показавший хорошие резуль таты на задачах обращения некоторых криптографических функций. Стратегия параллелизма в данном решателе осно вывается на возможности межпроцессорной передачи накап ливаемых булевых ограничений в виде ROBDD.

Список литературы [1] Bryant R. E. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Transactions on Computers. 1986. Vol. 35, no. 8. Pp. 677–691.

[2] Meinel Ch., Theobald T. Algorithms and Data Structures in VLSI-Design: OBDD-Foundations and Applications. Springer Verlag, 1998.

[3] Groote J. F., Zantema H. Resolution and binary decision diagrams cannot simulate each other polynomially // Journal of Discrete Applied Mathematics. 2003. Vol. 130, no. 2. Pp. 157–171.

[4] Семенов А. А. Декомпозиционные представления ло гических уравнений в задачах обращения дискретных функ ций // Известия РАН. Теория и системы управления. 2009.

№ 5. С. 47–61.

[5] Игнатьев А. С., Семенов А. А. Алгоритмы работы с ROBDD как с базами булевых ограничений // Прикладная дис кретная математика. 2010. № 1. С. 86–104.

[6] Игнатьев А. С. Методы обращения дискретных функций с применением двоичных решающих диаграмм / автореферат дисс. канд. физ.-мат. наук. Иркутск, 2010. С. 18.

ПРИМЕНЕНИЕ СЕТЕЙ ПЕТРИ ДЛЯ АНАЛИЗА КС-ГРАММАТИК И.Я. Спекторский Предлагается схема использования сетей Петри для иссле дования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покры ваемости соответствующей сети Петри. Кроме того, предло женный метод позволяет сформулировать необходимые усло вия порождения заданного слова КС-грамматикой в терминах матричного анализа соответствующей сети.

Пусть G = N,, P, S контекстно-свободная (КС) по рождающая грамматика, где N нетерминальный алфавит, терминальный алфавит, P множество продукций, S N источник. Для грамматики G введем в рассмотрение сеть Пет ри NG с множеством позиций N, множеством переходов P и весовой функцией W, определяемой для продукции A и символа (N ) соотношениями:

• W (A, ) = || (количество вхождений в );

1, если = A, • W (, A ) = 0, если = A.

Ряд свойств сети Петри NG при фиксированной начальной маркировке µ0 : (N ) (N {0}) эффективно анализиру ются с помощью дерева покрываемости (см., напр. [1,2]).

Национальный технический университет Украины Киевский поли технический институт;

e-mail: spectorsky@mail.ru Символ A N называют порождающим, если A w для некоторого w. Очевидно, что все продукции, содержащие непорождающие символы, можно исключить из P, не сужая язык, порождаемый грамматикой. Продукцию A называ ют рекурсивной, если содержит A. Очевидно, что исключе ние рекурсивных продукций не влияет на порождаемость или непорождаемость нетерминальных символов.

Через µA (A N ) обозначим такую маркировку, что 1, если = A, µA () = 0, если (N ) \ {A}.

Через TA обозначим дерево покрываемости для начальной nr маркировки µA. Через TA обозначим дерево покрываемости для начальной маркировки µA, построенное без учета перехо дов, соответствующих рекурсивным продукциям.

Теорема 1. Символ A N является порождающим тогда nr и только тогда, когда дерево TA содержит не менее одной мар кировки µ, такой, что µ() = 0 для всех N.

Очевидно, что язык, порождаемый грамматикой G, явля ется непустым тогда и только тогда, когда порождающим яв ляется источник S.

Теорема 2. Грамматика G порождает бесконечный язык тогда и только тогда, когда дерево TS содержит не менее одной маркировки µ, такой, что µ() = 0 для всех N, и µ(a) = для некоторого a.

Для анализа порождаемости грамматикой G слова w можно использовать уравнение состояний сети NG (см., напр., [1,2]). Обозначим через µw (w ) маркировку, такую, что µw () = |w|. Очевидно, что для порождаемости слова w необ ходимо (но недостаточно), чтобы уравнение состояния имело хотя бы одно решение для правой части (µ = µw µS ).

Пример.

Рассмотрим грамматику G = {S}, {a, b}, P, S, где P = {S aSb|bSa|}. Выпишем матрицу инцидентности для сети NG, предполагая упорядоченность позиций (нетерминальных и терминальных символов) и переходов (продукций) в соответ ствии с перечислением в определении грамматики:

0 A = 0 1 1 0 Уравнение состояния A u = µ имеет решение относитель но вектора запусков u = (u1, u2, u3, u4, u5 ) лишь для правых частей вида µ = (x, y, y). Таким образом, из начальной мар кировки µS = (1, 0, 0) могут достигаться только маркировки с одинаковыми второй и третьей координатами. Это означает, что грамматика G может генерировать лишь слова с одинако вым числом вхождений a и b. Однако разрешимость уравне ния состояния лишь необходимое условие для порождаемо сти слова грамматикой;

в данном примере G порождает лишь слова вида wwr.

Список литературы [1] Питерсон Дж. Теория сетей Петри и моделирование си стем. – М.: МИР, 1984. – 264 с.

[2] Котов В. Е. Сети Петри. – М.: Наука, 1984. – 160 с.

ПРИМИТИВНО НОРМАЛЬНЫЕ КЛАССЫ РЕГУЛЯРНЫХ ПОЛИГОНОВ А.А. Степанова Примитивно нормальные теории S-полигонов изучаются в работах [1–2]. В [1] дана характеризация моноидов S таких, что класс всех S-полигонов примитивно нормален. В [2] опи сывается строение S-полигонов с примитивно нормальной тео рией. В данной работе исследуются коммутативные моноиды Дальневосточный государственный университет e-mail: stepltd@mail.ru S, над которыми аксиоматизируемый класс всех регулярных S полигонов примитивно нормален. Описание моноидов S с акси оматизируемым классом регулярных S-полигонов приводится в [3].

Напомним некоторые определения. Класс K алгебр назы вается примитивно нормальным, если теория каждой алгебры из K примитивно нормальна.

Пусть S – моноид. Под (левым) S-полигоном S A понима ется множество A, на котором определено действие элементов S слева, причем единица моноида S действует на A тожде ственно. Пусть S A – S-полигон. Элемент a A называется act–регулярным, если существует гомоморфизм : S Sa S S такой, что (a)a = a. Регулярным S-полигоном называется S полигон, все элементы которого act–регулярны. Предположим в S-полигоне S A существует регулярный подполигон. Заметим, что объединение всех регулярных подполигонов S-полигона S A есть регулярный подполигон, который обозначим через S R. Че рез R обозначим класс всех регулярных S-полигонов.

Полугруппу T назовем линейно упорядоченной, если для любых a, b T либо T a T b, либо T b T a.

Теорема. Пусть S – коммутативный моноид и класс R ре гулярных S-полигонов аксиоматизируем. Тогда класс R при митивно нормален в том и только том случае, когда полугруп па R линейно упорядочена.

Работа поддержана грантом Российского фонда фундамен тальных исследований (проект 09-01-00336-а).

Список литературы [1] Степанова А.А. Примитивно связные и аддитивные тео рии полигонов// Алгебра и логика. 2006. Т.45. №3. С.300-313.

[2] Степанова А.А. Полигоны с примитивно нормальными и аддитивными теориями // Алгебра и логика. 2008. Т.47. №4.

С.491-508.

[3] Степанова А.А. Аксиоматизируемость и модельная пол нота класса регулярных полигонов // Сиб. мат. журн. 1994.

Т.35. №1. С.181-193.

О ЧИСЛЕ ПРЕДЕЛЬНЫХ МОДЕЛЕЙ НАД ТИПОМ В КЛАССЕ -СТАБИЛЬНЫХ ТЕОРИЙ С.В. Судоплатов Напомним [1], что модель M называется предельной (над типом p), если M не является простой моделью ни над каким кортежом и M = Mn для некоторой элементарной цепи n (Mn )n простых моделей над некоторыми кортежами (реа лизациями типа p). Напомним также [1, теорема 5.4.2], что лю бая счетная модель малой теории проста над некоторым кор тежом или предельна. В книге [1] представлены всевозмож ные распределения числа предельных моделей в классе малых теорий. Основные построения реализаций этих распределений проведены в классе теорий, у которых некоторые типы имеют бесконечный собственный вес. В примере 1.2.3 из [1] свобод ная ориентированная псевдоплоскость с упорядоченной рас краской вершин задает графовую структуру, теория которой -стабильна и имеет максимальное число (равное 2 ) предель ных моделей над 1-типом p (x) элементов бесконечного цвета.

Модифицируя основную конструкцию из [1], получаем следую щие возможные значения для числа Il (p) предельных моделей -стабильной теории над типом p.

Теорема. Для любого кардинала {, 2 } существу ет -стабильная теория T с некоторым типом p(x) S 1 (T ), собственный вес которого равен 1 и Il (p) =.

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 09-01-00336-а, а также Совета по грантам Президента РФ для поддержки ве дущих научных школ, проект НШ-3669.2010.1.

Список литературы [1] Судоплатов С.В. Проблема Лахлана.– Новосибирск:

Изд-во НГТУ, 2009.– 336 с.

Институт математики им. С.Л. Соболева СО РАН, Новосибирск e-mail: sudoplat@math.nsc.ru О БИНАРНЫХ ЭРЕНФОЙХТОВЫХ ТЕОРИЯХ БЕЗ СВОЙСТВА СТРОГОГО ПОРЯДКА С.В. Судоплатов, П. Танович † Напомним, что полная элементарная теория T называется эренфойхтовой, если T имеет конечное, но большее единицы число попарно неизоморфных счетных моделей.

Тип p теории T называется властным, если любая мо дель M, реализующая p, реализует все типы теории T.

Известно [1], что любая эренфойхтова теория имеет власт ный тип.

Говорят, что теория T имеет свойство строгого порядка (со кращенно SOP), если T имеет формулу (, y ) и кортежи an x в некоторой модели M теории T, n, для которых (M, an+1 ) (M, an ), n.

Теория T называется бинарной, если в T имеется элимина ция кванторов до формул, содержащих не более двух свобод ных переменных.

Понятия глобального и локального свойств попарного пере сечения (GPIP и LPIP) введены в [2, 3]. Свойство GPIP для ти па p() означает, что существует формула (, y ), l() = l(), x x x y образующая бесконтурный орграф на множестве реализаций типа p(), (, y ) p(), формула (, y ) эквивалентна дизъ x a y a юнкции главных формул над a, и для любых реализаций a и b типа p() существует c |= p, удовлетворяющая условию x |= (, a) (, (7) c c b).

Если формулы (, y ) зависят от окрестностей () p() x x x типа p() и кортеж c для (7) может быть выбран с условием x |= () (не обязательно c |= p), получается понятие LPIP.

c Институт математики им. С.Л. Соболева СО РАН, Новосибирск e-mail: sudoplat@math.nsc.ru † Математический институт САНУ, Белград, Сербия e-mail: tane@mi.sanu.ac.rs П. Танович [4] доказал, что любая теория, имеющая бес конечное множество dcl() и ровно три неизоморфные счетные модели, интерпретирует пример Эренфойхта или пример Пере тятькина (эти примеры являются бинарными теориями с GPIP для в властных типов и с SOP).

Предложение 1 [2, 3]. Если p неглавный властный тип, то p имеет LPIP.

Реализации LPIP&¬GPIP построены в [3, § 3.7] и [5]. Вместе с тем основные конструкции эренфойхтовых теорий в [3] (без свойства SOP) используют GPIP.

Предложение 2. Если T эренфойхтова теория без SOP и с GPIP для властного типа теории T, то теория T не является бинарной.

Теорема. Для любого n \ {0, 2} существует бинарная теория без свойства строгого порядка и имеющая ровно n счет ных моделей.

Работа первого автора выполнена при финансовой под держке Российского фонда фундаментальных исследований, проект 09-01-00336-а, а также Совета по грантам Президен та РФ для поддержки ведущих научных школ, проект НШ 3669.2010.1.

Список литературы [1] Benda M. Remarks on countable models // Fund. math.– 1974.– Vol. 81, No. 2. P. 107–119.

[2] Судоплатов С.В. Властные орграфы // Сиб. матем.

журн.– 2007.– Т. 48, № 1.– С. 205–213.

[3] Судоплатов С.В. Проблема Лахлана.– Новосибирск:

Изд-во НГТУ, 2009.– 336 с.

[4] Tanovi P. Theories with constants and three countable c models // Archive for Math. Logic.– 2007.– Vol. 46, No. 5–6.– P. 517–527.

[5] Судоплатов С.В. Эренфойхтовы теории, не имеющие властных орграфов // Статья сдана в Сибирский математиче ский журнал.– 6 с.

ИИНФОРМАЦИОННЫЕ СИСТЕМЫ И РАЗМЕРНОСТЬ ПРОСТРАНСТВ ЧУ А.Г. Сухонос Напомним определение пространства Чу [1]. Тройка A = (A, r, X), где r : A X {0, 1}, называется пространством Чу над алфавитом {0, 1}. Пространство Чу, где каждая область является функцией из A {0, 1}, то есть X 2A, называется нормальным пространством Чу и обозначается (A, X).



Pages:     | 1 || 3 |
 





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

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