автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Метод логико-алгебраических уравнений в анализе динамических систем

На правах рукописи

<4

НАГУЛ НАДЕЖДА ВЛАДИМИРОВНА

Метод логико-алгебраических уравнений в анализе динамических систем

05 13 01 — Системный анализ, управление и обработка информации (в технике, экологии и экономике)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

СШЗ 166В08

Иркутск - 2008

Работа выполнена в Институте динамики систем и теории управления Сибирского отделения Российской академии наук (ИДСТУ СО РАН)

Научный руководитель

академик РАН,

доктор физико-математических наук Васильев Станислав Николаевич

доктор физико-математических наук Гончаров Сергей Савостьянович,

кандидат физико-математических наук, доцент

Абдуллин Рафаэль Зинатович

Официальные оппоненты

член-корреспондент РАН,

Ведущая организация

Иркутский государственный университет

Защита состоится 17 апреля 2008 г в 13 30 на заседании диссертационного совета Д 003 021 01 в ИДСТУ СО РАН по адресу 664033, г Иркутск, ул Лермонтова, 134

С диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН

Автореферат разослан 17 марта 2008 года

Ученый секретарь диссертационного совета, д ф -м н

А А Щеглова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В математической теории систем хорошо известна продуктивность междисциплинарных исследований В частности, в контексте данной диссертации, можно отметить исследования на стыке алгебры и логики (А И Мальцев, А Тарский, Ю Л Ершов, Ю И Журавлев, С С Гончаров и др ), динамики систем и алгебры (С Ли, Л В Овсянников, М А Арбиб и др ) Данная диссертация посвящена разработке на стыке динамики систем, алгебры и логики такого метода математической теории систем, который позволяет алгоритмически синтезировать критерии сохранения свойств систем при некоторых связывающих их отображениях типа морфизмов (эти и другие отображения, связывающие ту или иную рассматриваемую пару систем, далее называем отображениями связи, а априорно накладываемое на них условие — условием связи)

В качестве таких логико-алгебраических критериев назовем результаты о сохранении позитивных свойств алгебраических систем при гомоморфизмах (Р Линдон, 1954), хотя, например, проблема сохранения свойства устойчивости при координатных преобразованиях систем дифференциальных уравнений известна еще с XIX века устойчивость решения в одних переменных не означает его устойчивости в других переменных (А М Ляпунов, 1892) Одним из применений критериев сохранения явилось также сведение на их основе задачи изучения сложной модели к изучению более простой

Метод сравнения, предложенный В М Матросовым1 и развитый в его научной школе (Л Ю Анапольский, С Н Васильев, Р И Козлов и др), обеспечивал алгоритмическое получение критериев сохранения поначалу простых свойств (так называемых свойств степени 1), но для довольно широкого класса динамических систем и в терминах отображений связи, именуемых вектор-функциями сравнения (ВФС) В развитие этого метода был предложен более общий метод сравнения — в форме логических уравнений (далее — метод логических уравнений2 (ЛУ)), имевших структуру Эс&ОЛ&ф' —> ф, где Ш, ф', ф — известные члены уравнения, X подлежит отысканию, ф — свойство, рассматриваемое в одной системе (5), ф' — свойство второй системы (5'), — условие связи, которое в случае метода В М Матросова является условием мажорирования ВФС вдоль процессов

Матросов В М Метод сравнения в динамике систем I, II // Диф уравнения — 1974 — Т 10, N 9, 1975 - Т 11, N 3

2Васильсв С Н Метод сравнения в анализе систем I IV // Диф уравнения — 1981 — Т 17, N 9, Т 17, N 11, 1982 - Т 18, N 2, Т 18, N 6

изучаемой системы 5 соответствующими процессами вспомогательной системы 5" (более простой по замыслу и именуемой системой сравнения), но это могут быть и другие условия условие типа того или иного морфизма, условие топологической эквивалентности 5, 5' и другие Метод ЛУ пригоден для изучения свойств общего вида (произвольной степени), причем для разных математических моделей и их разных преобразований (отображений связи с разными условиями ЯН ВФС, морфизмов и др ) Следует подчеркнуть, что критерии, получаемые в терминах ВФС и в терминах морфизмов, вообще говоря, не сравнимы по силе хотя само условие связи Ш в случае морфизма жестче условия ВФС, прочие условия (условия ЭС), входящие в критерий сохранения (и, вообще говоря, более сложные, чем требования типа сохранения операций или отношений), тем не менее оказываются мягче в случае морфизма Кроме того, метод сравнения и метод ЛУ синтезируют искомые критерии гибко под конкретный вид изучаемого свойства Еще более общий метод решения логических уравнений известен как метод редукции3, оперирующий с уравнениями вида £&(&{£, г= 1,2, , те}) где п > 1

Для получения критериев сохранения, состоящих из условий, имеющих смысл условий типа сохранения операций или отношений (т е формулируемых в духе традиционных морфизмов), в развитие упомянутых результатов Р Линдона в теории алгебраических систем, а также в развитие так называемых критериев переносимости термов и соотношений в теории структур Н Бурбаки (1965), С Н Васильевым и С В Афанасьевой разработан метод представимости с применениями в динамике систем Его особенностью является то, что каждый критерий, в отличие от критериев, получаемых методом ЛУ, обслуживает сразу целый класс свойств (например, как у Р Линдона все позитивные свойства сохраняются при гомоморфизме) При применении метода представимости изучаемую модель системы следует перевести в форму многоосновной алгебраической системы и представить определение изучаемого свойства в соответствующем классе свойств, для которого имеется критерий сохранения К сожалению, задача представимости (эквивалентными преобразованиями) формулы изучаемого свойства в требуемом классе является, вообще говоря, алгоритмически неразрешимой Поэтому оказывается привлекательным путем развития метода ЛУ избежать этой задачи представимости, а также совместить гибкость формирования критерия сохранения по конкретному виду изучаемо-

3Васильев С Н Метод редукции и качественный анализ динамических систем I, II // Изв РАН, ТиСУ - 2006 - N 1, N 2

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

Эта задача была решена в случае одноосновных алгебраических систем (С H Васильев, 1988) Логические уравнения при этом имеют вид ЭС&ф' —> ф, те априорно никаких условий связи не задается, что полезно, так как тем самым повышается уровень алгоритмичности развиваемого аппарата При этом для получения достаточно эффективных критериев сохранения повышается нагрузка на алгоритмы формирования условий X в части сужения разнообразия скулемовских функций, отвечающих кванторам существования в условиях X Применение этих алгоритмов для конкретных ф помогает и в неалгоритмическом формировании критериев сохранения целых классов свойств алгебраических систем Между тем, например, именно случай морфизма динамических систем важен для тех процедур исследования устойчивости или других динамических свойств, когда требуется переход к новым переменным, поскольку надо гарантировать эквивалентность исследуемого свойства в старых и новых переменных или хотя бы однонаправленный его перенос4 Случай, когда отображения связи являются морфизмами, важен и в связи с решением задач стабилизации программных движений систем с управлением с помощью преобразования этих систем к некоторым эквивалентным каноническим формам5 В настоящее время морфизмы применяются в качественном исследовании динамических систем, в том числе с управлениями, и в ряде работ зарубежных авторов6 Однако в динамике систем предложенные алгоритмы не удобны, поскольку алгебраизация моделей динамических систем, осуществляемая для применения этих алгоритмов, приводит к многоосновным алгебраическим системам (основными множествами выступают пространство состояний, шкала времени и др ) Поэтому актуален вопрос о развитии метода ЛУ для многоосновного случая (в частности, без априорного задания условий связи), что и является предметом исследования в данной диссертации

Следует также подчеркнуть, что в силу большей сложности, по характеру своих определений, тех математических объектов, которые изучаются в динамике систем, в сравнении с традиционными алгебраическими системами, требуется рассматривать такие многоосновные алгебраические системы (MAC), функции и отношения которых определены не просто на

4Журавлев В Ф Основы теоретической механики — M Физматлит, 2001 — 320 с

5Кавинов А В , Крищенко А П Устойчивость решений в разных переменных // Диф уравнения — 2007 - Т 43, N 11 - С 1470-1473

sMichel А N , Kainmg W К , Во H Qualitative Theory of Dynamical Systems — N Y Marcel Dekker, Inc , 2001 — 706 p

базисных множествах или их декартовых произведениях, а на произвольных ступенях в смысле H Бурбаки и, более того, на ступенях с некоторыми дополнительными расширениями, вводимыми в диссертации (в частности, для охвата таких динамических систем, как дискретно-событийные системы) При этом в связи с такой общностью рассматриваемых MAC в логический язык вводятся дополнительные выразительные средства, и не только для представления схем и ступеней (образуемых по этим схемам), но также для представления канонических распространений отображений (КРО) основных множеств на ступени, ибо именно до класса таких функций — КРО — и сужается алгоритмически разнообразие упомянутых выше скулемовских функций, важных для эффективности получаемых критериев сохранения Для специализации уравнений в таком расширенном (логико-алгебраическом) языке будем их называть логико-алгебраическими уравнениями (ЛАУ) и рассматривать два типа уравнений Х&ф —» ф' и ЗЕ&^У —* ф (второе уравнение соответствует изучению сохранения свойства в направлении, обратном направлению отображения связи, действующего из S в S' ) Эти уравнения являются частным случаем уравнений метода редукции, поэтому предлагаемые в диссертации алгоритмы могут частично обосновываться с применением метода редукции, но лишь частично, поскольку формирование решения X осуществляется с дополнительными процедурами сужения скулемовских функций и некоторыми другими, также отсутствующими в методе редукции, процедурами

В качестве одного из примеров применения развиваемого метода рассматриваются дискретно-событийные системы (ДСС), главной отличительной особенностью которых является моделирование эволюции системы путем учета наступления каких-либо событий Потребность в ДСС обуславливается стремительным развитием производственных систем и сетей связи, транспортных сетей и других, в первую очередь антропогенных, систем Кроме того, ДСС широко применимы в технике С их помощью моделируются, например, автоматизированные отсеки сборки штоков поршней7, мультипроцессоры по производству полупроводников8, термостаты, перегонные колонны химического производства9, автономные мобильные

7Moody J О , Antsaklis Р 3 Petn Net Supervisors for DES with Uncontrollable and Unobservable Transitions // IEEE Transactions on Automatic Control - 2000 — Vol 45, N 3 - P 462-476

sBalemi S , Hoffmann G J , Gyugyi P, Wong-Toi H Franklin G F Supervisory Control of a Rapid Thermal Multiprocessor // IEEE Transactions on Automatic Control - 1993 — Vol 38, N 7 - P 10401059

9Stiver J A Antsaklis P J , Lemmon M D A Logical DES Approach to the Design of Hybrid Control Systems // Math Comput Modelling - 1996 - N 23 (11/12) - P 55-76

роботы10 и др

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

Цели работы:

• разработка метода алгоритмического синтеза критериев сохранения свойств многоосновных алгебраических систем,

• получение с помощью этого метода критериев сохранения свойств динамических систем, в частности, представление дискретно-событийных систем в виде многоосновных алгебраических систем и получение критериев сохранения различных динамических свойств ДСС в их собственных терминах,

• применение полученных результатов в анализе свойств модели сети общественного транспорта и некоторых других динамических систем

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

Научная новизна. В работе впервые решена задача алгоритмического синтеза критериев сохранения свойств многоосновных алгебраических систем как в направлении, совпадающем с направлением действующих между системами отображений, так и в противоположном направлении Изучены некоторые свойства дискретно-событийных систем Для представления ДСС в виде MAC произведено расширение понятия ступени H Бурбаки с использованием дополнительной операции образования последовательностей Исследована модель сети общественного транспорта Все результаты диссертации являются новыми и снабжены строгими доказательствами

Теоретическая и практическая ценность Диссертация носит теоретический характер Полученные результаты могут быть использованы

10Kosecka J , Bajcsy R Discrete Event Systems for Autonomous Mobile Agents // J of Robotics and Autonomous Systems - 1994 - N 12 — P 187-198

в дальнейших исследованиях дискретно-событийных систем и многоосновных алгебраических систем Работа выполнена по программе фундаментальных исследований СО РАН N 2 4 "Математическая теория управления", при финансовой поддержке в Программе N 19 Президиума РАН, N 2005-ИТ-12 1 002 ФЦНТП "Исследования и разработки по приоритетным направлениям науки и техники", Программе фундаментальных исследований N 22 Президиума РАН и грантом Президента Российской Федерации по государственной поддержке ведущих научных школ Российской Федерации НШ-9508 2006 1

Апробация работы. Основные результаты диссертации были представлены на II Всероссийской конференции "Инфокоммуникационные и вычислительные технологии и системы" ИКВТС'06 (пос Энхалук, 1-4 июля 2006 г), конференции "Ляпуновские чтения и презентация информационных технологий" (г Иркутск, 14-15 декабря 2006 г), XII Байкальской Всероссийской конференции с международным участием "Информационные и математические технологии в науке и управлении" (оз Байкал, г Иркутск, 2-10 июля 2007 г), а также неоднократно докладывались на семинарах Института динамики систем и теории управления СО РАН

Публикации. Основные результаты диссертации опубликованы в работах [1] - [7]

Структура и объем работы. Диссертационная работа изложена на 129 страницах и состоит из введения, трех глав, заключения и списка литературы, содержащего 78 наименований, включая работы диссертанта

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении дается обоснование актуальности темы исследований и приводится краткое содержание работы

В первой главе представлен обзор литературы по теме диссертации, начиная с объектов динамического анализа и кончая методами анализа П 1 1 посвящен описанию известных результатов использования логических уравнений, а также проблематике изучения вопросов сохранения свойств при отображениях систем В п 1 2 приводится краткий обзор литературы, касающейся традиционных многоосновных алгебраических систем В п 1 3 дан анализ некоторой литературы, посвященной ДСС, а в п 1 4 приводятся соответствующие базовые понятия и терминология, используемые в главе 3

Дискретно-событийной системой называется пятерка С = (X, £, {/е}ее£) 3) -Е«) Здесь X — множество состояний системы, £ — множество событий, {/е}ее£ — операторы перехода, /е X —> X для всех е € £, д X —> 2£\{&} — функция возможностей, те д{х) есть множество событий, которые могут произойти, если система находится в состоянии х € X Рассматривается дискретная шкала "времени" как шкала значений счетчика событий N = {0,1,2, }, и х/, € X представляет собой состояние в момент к & N Если в этот момент происходит событие е* € д(хк), то состояние Хк+1 задается применением оператора /еь, те х^+г = /е.к(хк)

Любая последовательность х = {х0,х\,х2,х$, } € Xм такая, что для всех к Х)к+1 = /Ск(хк), где е^ € д{хк), называется траекторией состояний (фазовой траекторией) Множество всех событийных траекторий, обозначаемое Е (Е С £м), состоит из тех последовательностей е = {ео, ех, ег, ез, } € для которых существуют траектории состояний х 6. Xм такие, что для всех к е* 6 д{хк) Здесь выражение ВА ДЛЯ любых множеств А и В обозначает множество всех отображений из Л в В

Через Е„ С Е С обозначается множество действительных событийных траекторий, те таких, которые физически возможны в системе В п 1 5 описана известная модель сети общественного транспорта, свойства которой изучаются в главе 3

Вторая глава посвящена разработке метода логико-алгебраических уравнений для алгоритмизации синтеза критериев сохранения свойств вводимых в главе общих многоосновных алгебраических систем конечного типа (ОМАСК)

Для определения ОМАСК в п 2 1 сначала вводится следующее понятие схемы ступеней (далее часто для краткости — просто схемы) Рассмотрим множество из к символов аа = {ал|А = 1, к} (/с > 0) и сигнатуру ао = {и х Определим множество схем ступеней над аа следующим

образом

1) для всех А = 1, к а\ есть схема,

2) если 5ь 5г — схемы, то (51 х 5г) — схема,

3) если 5 — схема, то £>(5) и Л/*(5) — схемы,

4) выражение является схемой только в том случае, когда это следует из правил 1-3

Множество всех схем ступеней 5[ега] над аа обозначим 5£[ста] Если имеется семейство множеств А = {у!а| А = 1, к}, то для любой схемы ступеней 5[<та] € 5£[а"а] индукцией по построению схемы 5[<та] очевидным образом и однозначно определяется множество 5[Л] —ступень над семейством А (по схеме 5) При этом символы а\ е аа интерпретируются как множества А\ € А (А = 1 ,к), бинарный символ □ х и е ао — как операция образования декартова произведения, те для схем 51, 5г € 54[сг0] полагаем (5х х 5г)[>1] = 5*1 [А] х 5г[Л], функциональный символ V € сто — как операция образования булеана, те для схемы 7^(5) 6 5^<та] полагаем 7->(5)[Л] = 25'-л1, символ N 6 ао — как операция образования множества последовательностей, те для схемы Л/*(5) € 5£[ста] полагаем Л/"(5)[Л] = (^[А])^ Таким образом, классические понятия схемы и ступени Бурбаки11 расширено введением в ао дополнительного символа N и указанной интерпретацией схем

Далее вводится язык первого порядка С — термов и формул, интерпретируемых естественным образом Для каждой схемы 5г = 5г[сга] € 5£[<7а] вводятся индивидные переменные иг\, иг2, — переменные сорта 5г[са] Рассматривается сигнатура а = ар и ар и ар Здесь

ар — {-Р^", /3 = 1 ,кр, П/з 6 {1,2, }} — множество функциональных символов, причем с каждым символом Гр" связываются схемы в количестве щз +1, обозначаемые 51/з[<та], 52/з[сга], , 5П(з/з[<та], 5П/3+1,/з[<7а] € 5г[<т0], при этом последняя схема в интерпретации символа Р^0 пр-местной функции позволит фиксировать область значений этой функции, а остальные схемы — области значений аргументов этой функции,

ар = {Ру~<, 7 = 1 ,кр, пу € {0,1,2, }} — множество предикатных символов со связанными с ними схемами Г17[(та], , ТПу1 [а„\ € 5^[<та], 7 = 1 ,кр,

"Бурбаки Н Теория множеств — М Мир, 1965 — 465 с

Ge = {Дь<5 = 1 Ле} — множество символов выделенных элементов со связанными с ними схемами U¡[cга] € St[aa), 5 = 1, ks

Используются также знаки "=" (равенства) и (L), U) (упорядоченной пары) Хотя эти символы могут связывать элементы различных пар схем S,[aa\ и 5j[<70¡, используются одни и те же символы для любой такой пары

Определяется множество правильно построенных выражений, обозначающих объекты и называемых термами, одновременно для термов вводится понятие сорта

1) всякая индивидная переменная иг] есть терм, сортом этого терма, как условлено, называется схема 5г[<та] переменной utJ, и для сорта вводится обозначение \иг]\ = 5г[<та],

2) всякий символ Es выделенного элемента есть терм, \Es\ = U¡{<j„\,

3) если £2 — термы сортов |íi|, |¿21, соответственно, то (ti,¿2) является термом сорта |íi| х |Í2|,

4) если t = ( ((ti,t2),t3), tn/¡) и |í,| = i = 1,щ, то F^ih, , tn„) является термом сорта Sn/3+L0{aa} (3 — 1, kF),

5) выражение является термом только в том случае, когда это следует из правил 1-4

Для формулировки утверждений об объектах определяются правильно построенные выражения, называемые формулами

1) если ti, Í2 — термы и |fi| = |£г|, то выражение ti = ¿2 является формулой,

2) если ti, ,tn^ ~ термы, \ti\ = Ti7[<r0], ,|í„7| = Тп^[сга) и Рр — предикатный символ, с которым связаны схемы Ti7[cra], , Тп,г/{ап], то Р"''{ti, , í,b) - формула,

3) если Зь $2 — формулы, то выражения -■(3ri), (í?i &З2), (Зл V £2), (í?i -► З2) являются формулами,

4) если 5 — формула, ша — типовый квантор (ТК) вида ша = Vza Za = Vza(Za —> U) (ТК всеобщности) или вида ша = 3za Za = 3za{Za&U) (ТК существования), где Za — формула, то выражения с2>а3 = Wza(Za —> 5), tl)Q$ = 3za{Za& $¡) — формулы, здесь za — индивидные переменные utJ,

5) выражение является формулой только в том случае, когда это следует из правил 1-4

Формулы, построенные по правилам 1 и 2, называются атомарными

Общей многоосновной алгебраической системой конечного типа сигнатуры сг называется объект 21 = {A, Qp, состоящий из семейства основных множеств А — {А = 1, fc} и отвечающих множествам

ар, ар и се следующих множеств множества функций Qp = F"f 5i/j[A] x S20IA} x x Sneíi{A) —> Snt3+ifi[A], (3 = 1, kF}, множества отношений Üp — P"** Q Tiy\A) x x ТПу7[А], 7 = 1, kP} и множества выделенных элементов Qe = {E¿| E¿ € Us\A], 5 = 1, k^} Благодаря обобщению понятия схемы и ступени Н Бурбаки, в форме ОМАСК легко представить разные модели динамических систем и, в частности, ДСС

Для любого семейства отображений р = А\ —> Ад, А = 1, к} и

любой ступени 5[Л] € Sí [А] определяется каноническое распространение отображений (КРО) <¿>a на S[A], те S[A] —S[A'] (оно обобщает

определение Н Бурбаки на расширенную шкалу ступеней) При этом используются обозначения * Ф2 — КРО "ф\, на Аг х A¡, i¡)\ — КРО на 2Al, tpi\N — КРО на Af (аналогичны обозначения для произвольных отображений с произвольной ступенью Si [А] вместо Ах и £>2 [А] вместо Аг) Пусть Т(х) Í Т{хх, ,хр) — произвольная формула сигнатуры а в языке С с переобозначенными через х^ для удобства всеми ее свободными переменными ut], ц = 1, р, р > 0 Не ограничивая общности, считаем, что переменных, одновременно связанных и свободных, нет, что отсутствуют ТК с одинаковыми кванторными переменными za и что Т является формулой, образованной из литер (заключительных формул) Tv, те из атомарных формул ТЧ или их отрицаний ТЧ, с помощью связок fe, V и ТК ша или lüq, а = 1,п, v = 1 ,М Такие формулы, в отличие от позитивных формул, используемых, например, в общей теории алгебраических систем, названы обобщенными позитивными формулами

Пусть 21, 21' — ОМАСК сигнатуры а с семействами основных множеств А — {Ал| А = и А' — {Ад| А = соответственно

Формула J-{x) определяет на системе 21 р-арный формульный предикат .Тч^ (в отличие от традиционного определения12, Т называется свойством ОМАСК даже при р ф 0) В п 2 2 предлагается способ синтеза условий Ж сохранения истинностных значений предиката относительно отображений <р = {<р\\ípx А\ —> Ад, А = 1, fc} Иначе говоря, алгоритмизировано получение нетривиальных условий 3G, при которых из выполнимости на системе 21 формулы Т при каких-либо фиксированных значениях с\, , ср переменных ari, ,хр вытекает выполнимость Т на 21' и соответствующих значениях КРО (<^)s,'j4'(c1), , (y)Sp'A'(cp), где SM[A] — сорт переменной (J. = hp

X ищется как формула языка первого порядка, расширяющего С Обо-

12Мальцев А И Алгебраические системы — М Наука, 1970 — 329 с

значим и* = сги<7'и{/л}, где сигнатура а' выбирается так, чтобы а'Пег = 0, и состоит из дубликатов сигнатуры а в новых обозначениях Функциональные символы /д интерпретируются в дальнейшем на множествах однозначных и всюду определенных на основных множествах А\ функций уэд А\ —> Ад, Л = 1, к Пусть язык С* построен естественным образом на базе а*, как С — на базе а, с ранее указанными внесигнатурными символами, к которым добавим символы и • и, В (и), операций образования КРО, интерпретируемые как и * и, □, соответственно Естественным образом определяется терм образованный из символов /д с помощью

символов этих трех операций по схеме 5[ега] построения КРО

Развивается метод формирования нетривиальных решений логико-алгебраического уравнения

Условия X будут иметь вид C&C'&fH 1 и формируются по следующим алгоритмам

Если ар U <7е Ф и, то формула Т преобразуется в формулу Ф так, чтобы ее заключительные формулы Ф" не содержали вхождений символов из crpUoE (если все Ти не содержат элементов из <jfU<Te, то Т — Ф) Это требуется для построения в дальнейшем на базе íKi более просто проверяемых условий, т к функциональные и предикатные символы не будут одновременно фигурировать ни в одной ее заключительной (атомарной) формуле Описываемая ниже процедура и позволяет в дальнейшем от ÍRi переходить к конъюнкции условий, в совокупности достаточных для íRi, каждое из которых выражает условие сохранения единственного сигнатурного символа — функционального или предикатного, в полном соответствии с традиционными определениями морфизмов алгебраических систем

Преобразование определяется следующим образом сначала в J-v, и = 1 , М, отыскивается терм ¿i либо а0) вида Е\, либо вида б°) с одним сигнатурным, а именно, функциональным символом F\, те терм вида Fi(sn, S12, , si„,), где F\ € crp, sn — переменные или za, г = 1,гц, п\ > О (переменные Su могут быть разного сорта, поэтому, хотя они являются индивидными переменными, ранее обозначавшимися иг], осуществлено переименование) Из числа переменных za, входящих в ti, если таковые найдутся, выделяется переменная sa 1, квантор по которой ¿¡а1 имеет наименьшую область действия Di, и по определению

Xkf{xu ,xp)->F(fM(x 0, ,/w(*p))

(1)

Ф1

Здесь 1^1(2/1/^1) — результат одновременной замены в Т>\ всех вхождений терма ¿1 на ранее нигде не встречавшуюся в Т переменную у\

Если же среди переменных отсутствуют переменные га (что заведомо имеет место в случае £1 = Е1), то

Фх = 3 У1(У1 = ЬкПуФх))

Те выражения, в которые переходят литеры Т" в процессе последовательного преобразования формулы Т, называются следами этих литер (в отличие от добавляемых литер, например, у\ — ¿1)

Продолжая, если необходимо, этот процесс, приходим к формуле Ф(ж) = Ф(ж1, , Хр). уже не содержащей символов й € и ? € в следах литер , и = 1, М

Пусть уе* — последняя из введенных переменных у£, те е = 1,£* Через у£ (соотв ус) обозначаются кванторы Уу£(у£ = Ь£ —► и) (соотв 3уе(у£ = ¿£&1_1)) Для любой формулы 0 через |0, е| обозначается слово, составленное из всех кванторов, управляющих в формуле 0 элементом е, а через ||0, е|| — это же слово, в котором все кванторы существования заменены на соответствующие кванторы всеобщности Через НО обозначается результат вычеркивания из 0 всех несущественных кванторов (те таких, кванторные переменные которых не входят в область действия квантора) Вводятся также следующие обозначения

€ = ,уе\\3у£(у£ = ге) е = к у£ е Ф>,

С = к,{Н\\Ъ',у'£Ш{у'£ = Ие) е & у'е е ф'},

где

Ф'(*0 = Ф'(^1, , х'Р) = Р'/Р, Е'/Е, г'а/га, ¿¿х», у'г/у£),

Ь'. = Ъ{и'£/иг,г'а/2а,у'т/ут,^х»\(х>1)/х11) (подстановки по всем Р € аР, ^ £ <тр, Е € ар, а = 1 ,п, ц = Т7р, т = 1,е*, т ф е), \]£ = Ес или 11£ = соответственно случаям а° и б°, е = 1,£* Пусть также

Ф'(Ж) = , /Ы(хр)/х'р),

= , /Ы(хр)/а/р)

Лемма 1. €к£' ((Ф(з?) -> Ф'(Я®))) -> №) —

Далее через Ф" обозначается след литеры в Ф, и = 1, М, а через й (соотв г>) — типовый квантор гиа (соотв гиа), если V — переменная га Если

V — переменная у£, то под V (соотв й) понимается квантор у£ (соотв у£) Аналогично используются обозначения Ф^, ФЦ, Ф+д, Ф1<д, <5 € ар и {=}, а также у', у' для кванторов по переменным г/ формулы Ф'(х')

Пусть также V, = (/'"»'(и,) = 3 = ТТп7 (п* = га + £*),

с- т/ч _ / если у3 — переменная га,

3 3 | 3у£(у£ = если у3 — переменная у£

Аналогично понимаются выражения (у' Через Е+д (соотв НЦ^) обозначается импликация Ф^ —► (Ф')+д (с°отв (Ф')+д ~* ф+(э)> гДе (ф')+<э — литера из Ф', отвечающая литере из Ф, когда не важно, каково ф, пишем 5+ и 3"_

Вводится преобразование формулы Ф в формулу

1) рассматриваются максимальные цепочки одноименных соседних кванторов, те максимальные цепочки #1 йт или г>1 Ът соседних кванторов, не разделенные в структуре формулы Ф ни кванторами 3 и V, соответственно, ни логическими связками &, V, все эти цепочки заменяются на цепочки соответственно Ц) (ут Ут), 1)1 йт(у[

Уг) (К. Кг),

2) все связки V заменяются на &,

3) все литеры Ф+<д, V = 1, М, заменяются на формулы Н^, а все литеры — на формулы Н1д,

4) после выполнения преобразований из п п 1-3 все переменные х' заменяются на и результат принимается в качестве

Следующая лемма обосновывает корректность решения

X £ С&С'&^х

рассматриваемого нами логико-алгебраического уравнения (1)

Лемма 2. €&£' (9^ (^(ш) Я(/(^))))

В п 2 3 построена модификация описанного алгоритма для построения условии <Г, £' и 9^1, которые являются достаточными условиями сохранения свойств ОМАСК в направлении, обратном направлению действующих между системами отображений

Х&^/М^), ,ХР)

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

iRi кванторов одного смысла кванторами другого смысла ухудшает его проверяемость по сравнению с условиями, накладываемыми на стандартные морфизмы, поэтому в п 2 4 ищутся условия 51, достаточные для выполнимости 5ii и представляющие собой более привычные условия — типа условий морфизмов или очевидным образом вытекающие из них Разработаны алгоритмы, аналогичные алгоритмам получения теорем сравнения из лемм сравнения13'14 При этом 5ti разбивается на более простые формулы, каждая из которых содержит в некотором смысле "минимальное" число кванторов существования

Первым преобразованием является расщепление формулы 5li на части относительно ее заключительных формул Получившиеся при этом формулы в общем случае допускают расщепление на конъюнкции более простых условий с помощью выделения из них подформул, соответствующих некоторым типовым кванторам существования Конъюнкция получившихся формул и будет искомой формулой 51 Обосновывается корректность этих алгоритмов

Теорема 1. -» (51 — (?(х) -> Т'(Щ)))

Аналогичная теорема формулируется для случая сохранения свойств в обратном направлении (с модифицированными алгоритмами синтеза 91)

В третьей главе рассматриваются примеры использования разработанных алгоритмов синтеза условий сохранения свойств ОМАСК В п 3 1 рассматривается свойство устойчивости движения общей динамической системы (ОДС) S в смысле В В Немыцкого, определяемой на топологическом пространстве X и группе Т15 ОДС S обобщенно представима в форме MAC (Л,= ({X,Г},{F ХхТ^Х})

Вектор-функция у? = {<р\, <£>2), ¥>1 X —> X', Т —> Т", называется гомоморфизмом ОДС S и S', если для любых р Е X, t Е Т

^{F{p,t)) = F'iipM^t))

Пусть X и X' — равномерные пространства с фильтрами окружений В и В', соответственно, а <¿>1 и <р2 — биекции, тогда гомоморфизм систем S и £>' называется изоморфизмом, если (pf*1pi(£>) — В', те <р\ — изоморфизм равномерной структуры пространства X на равномерную структуру пространства X'

13Матросов В M Метод сравнения в динамике систем I, II // Диф уравнения — 1974 — T 10, N 9, 1975 - T 11, N 3

HVassilyev S N Machine Synthesis of Mathematical Theorems // J of Logic Programming — 1990 — Vol 9, N 2, 3 — P 235-266

15Сибирский К С Введение в топологическую динамику — Кишинев РИО АН МССР, 1970 — 221 с

Теорема 2. Если X, X' — равномерные пространства с фильтрами окружений В и В', соответственно, p'Q — ¥>i(po), а <р = (<Рь <Рг) — изоморфизм ОДС систем S и S', то из устойчивости движения F(po,t) системы S следует устойчивость движения F'(Po, t') системы S'

С помощью модифицированных алгоритмов (п п 2 3 и 2 4) получено, что при изоморфизме ОДС S и 5' из устойчивости движения F'(p'0, t') также следует устойчивость движения F(po, t) Объединение этих результатов дает аналог теоремы об устойчивости ОДС, полученной с помощью метода представимости16

В п 3 2 рассматривается модель динамической системы с управлением в автоматной форме

x(t + 1) = F(x(t-m + l),x(t-m + 2), ,x(t - l),x(t),u(t)), (2)

где t € Tr = {0,1,2, ,т}, t e N = {1,2, }, m фиксировано, m e ЛГ, x = (xl5 ,x„) = (a;i(i), ,xn(t)) = x(t) G Wn, n 6 N, W — абстрактное множество состояний x, = xz(t), г = 1, n, u(t) 6 U, U — множество допустимых значений управления и из некоторого класса допустимых управлений U С Ur, F W"m xU->W"

Если в (2) задано начальное условие xq = х(0), управление и Тт U, а также значения x~m+1 = х(—m + 1) = х0(—m + 1), , х-1 — 1) = хо(—1) из множества W", то в (2) F = (Fi, ,Fn) единственным образом определяет процесс х Тт —> Wn Пусть задана "начальная" функция Xq —m + 1, , — 1 —* W" , расширяющая область определения х до множества D = {— т -1-1, , — 1} U ТТ Будем считать хо произвольной, но фиксированной, варьируя только начальное состояние хо и управление и € U

Рассматриваются разные динамические свойства (2) и, в частности, существование управления и &U, обеспечивающего достижимость целевого множества X* С Wn из области начальных состояний Хо С Wn при фазовых ограничениях Х\ С W", а также пребывание в X, в течение Д тактов после первого момента t\ попадания в X*

Т = Зи U{u) Vx0 Хо(хо) ((Vi > 0 Xrfxfcxcu))) & 3£г > 0

((V^ < ii -X*(x(i2,x0,u))) & Xt(x(tuxo,v)) & (3)

& Vi3 > ti i3 < 11 + A X.(®(t3,xo,ti))))

Здесь снова используется представление (2) в форме MAC Изучается ана-

16Васильев С Н Метод представимости в логико-алгебраическом подходе к качественному анализу динамических систем // Оптимизация, управление, интеллект — 2005 — N 3 (11) — С 248-254

логичная модель размерности к

x'(t + 1) = F'(x'(t — m + 1), x'(t — m + 2), ,x'(t - l),x'(t),u'{t)), (4)

где t € T, x'(t) € Wk, u'(t) e U', u' € U', F' Wkm x U' Wk Вектор-функция (г>, s), где v Wn —> Wk, s U —> U', называется гомоморфизмом для пары F, F' при управлении и* 6 U, если для всех xl G Wn, l = 1, m, t€TT

v(F(x\ , xm, ti*(i))) = F'ivix1), , v(xm), s(u*(t)))

При этом заведомо выполняется условие траекторного гомоморфизма для (v, 5) при и* £ U

v(x(t, хо, tí*)) = ar'(í, г;(хо), s о u*){t 6 Тт, хо € W)

Теорема 3. Пусть (v,s) — траекторный гомоморфизм систем (2) и (4) при фиксированном управлении и* G U и выполнены условия

1) V? € {~т + 1, , -1} v(xJ) = (х»)',

x¿ g «(Хо), v(xt) С х[, v{x,) с х'„

3)v(Wn\Xt) С (Wk\Xi)

Тогда из наличия в системе (2) свойства (3) с управлением и = и* следует, что система (4) обладает тем же свойством с управлением u'(t) = s(u*(t))

В п 3 3 исследуется вопрос о сохранении некоторых динамических свойств ДСС Получены условия сохранения свойств

1) оптимальной достижимости по быстродействию,

2) достижимости за ограниченное число шагов с пребыванием в целевом множестве не менее чем заданное число шагов,

3) оптимальной достижимости целевого множества при фазовых ограничениях и инвариантности целевого множества (ОДФИ)

Отметим, что в зависимости от свойства, ДСС G может иметь разное представление в виде ОМАСК В частности, для свойства ОДФИ G рассматривается как общая трехосновная алгебраическая система конечного типа Qí = Cíe), где А = {X, S, N}, Qp = {h}, iïP = {X, Xt, Xi, N, Ev, <}, ÇLe — 0 Здесь X — унарный предикат, тождественно совпадающий со множеством состояний X Он необходим, чтобы "вложить" формулу, описывающую свойство ОДФИ, в построенный язык £ Предикат Х(х) истинен для любого х € X Аналогично для предиката N, совпадающего с множеством N моментов "времени" (счетчиком состоянии)

Предикат Xt С X я Х,(х) истинен тогда и только тогда, когда а; € Л"» Подобным же образом определяется предикат Х\ Для бинарного предиката ёи пара (ж0, е) принадлежит Ev тогда и только тогда, когда е € Ev(xq) (Ёу € 2Xx£N) Здесь Ev(x0) С Ev обозначает множество всех действительных событийных траекторий g (Е Ец. начинающихся из состояния хо € X Функция h X х £n х TV —> X определяет состояние h(x0,e,k), в которое система перешла из начального состояния хо после того, как произошло к событий, принадлежащих действительной событийной траектории е G Ev(x0) _

Семейство отображений ц> = fx ^л -> А'л, Л = 1, к} называется гомоморфизмом ОМАСК 21 и 21', если

1) M(Fn/(Zl, = (F^)'«^^),

, М^Ы) W = 1, kF, Z! G SM , zne G Sne0[A}),

2) x^M(p„,} с (рщу (7 = hkp)t

3) {<p)uM(Es)=E's (6 = 1,кЕ)

Говорят, что <р — мощный гомоморфизм ОМАСК 01 и 21', если для всех Л = 1, Аг <р\ — сюръекции, выполняются условия 1), 3) определения гомоморфизма ОМАСК и для любых zQl € Т\7[А], , € Tnvr[A], 7 = 1, кР,

(Za,), , = и Р^, , z^) = И

Теорема 4. Пусть для ДСС G = (X, £, {/е}ее£, 9> существуют ДСС G' = и вектор-функция кр = (<¿>1, Уз>, гЭе

X —> X', 932 £ —» 5', уз N N, такие, что </з — гомоморфизм и мощный гомоморфизм ОМАСК, отвечающих системам G и G' Тогда, если событийная траектория <P2\N(e*) обеспечивает в системе G' свойство ОДФИ, то е* обеспечивает его в системе G

Ва 34 рассматривается особый подкласс ДСС, функционирование которых требует некоторую синхронизованность Характерные примеры ДСС такого типа возникают при моделировании сетей общественного транспорта, например, железных дорог или метро Событиями здесь являются отправления или прибытия поездов на станции, причем синхронизация вытекает из требования обеспечения для пассажиров возможности пересаживаться с поезда на поезд Для решения этой задачи традиционно применяется так называемая (max, +)-алгебра (A, ilp) = {{.Rf}, {©, <8>}), где е = —оо, Rf = яи{е}, R — множество действительных чисел, о©Ь = тах(а,Ь), а® Ь = а + 6 Распространение этих операций на матрицы определяются

следующим образом17

1) если А, В <Е Ä™xn, то

(Л ф В)гз = ау ® btj,,г = = I~ñ,

2) если Л € iíf хр, В € Щ*п, то

р _ _____

(Л ® = ф а1к <8) it, = max{a,í; + bkj}, г = 1, т, j = 1, n fc=l *=i¿>

Рассматривается модель сети общественного транспорта18

x(k + l) = A{k)®x(k)®d{k + l), (5)

где

х(к) = (xi(k),x2(k), ,хп{к))т,

d(k) = (*(*), ,dn(k))T,

А(к) — (п х п)-матрица (тг — количество путей) Здесь хг(к) означает (астрономическое) время отправления к-го поезда по пути т„ dl{k) - время отправления к-го поезда по пути тг согласно расписанию, й1]{к) - время движения по пути г, к-го поезда, который продолжит затем движение по пути т„ причем в это время входит время, необходимое пассажирам для пересадки При этом atJ(k) > 0, если к-ый поезд по пути г, продолжает при к + 1 движение по пути т„ и atJ(k) = е в противном случае, г, j = 1,тг Если расписание регулярно, то

d(k + 1) = 7г ® d(k), к = 1,2,3, ,

где 7г — период расписания, который в диссертации выбран единым для всех поездов Расписание называется выполнимым, если справедливо неравенство

А(к) ® d(fc) < d{k + 1) (6)

В п 3 4 эта модель сети общественного транспорта представлена в форме ДСС со шкалой значений счетчика событий N = {1,2,3, } Пусть X = Щ (векторы х = (xi, , хп)т с неотрицательными компонентами) При этом состояние системы х определено парой (к,х) Е NхX, те X = NxX

17Cunnmgham-Green R.A Minimax algebra // Lecture Notes in Economics and Mathematical Systems — Vol 166 - Berlin Springer-Verlag, 1979

18Heidergott В , de Vnes R Towards a (Max, +) control theory for public transportation networks // Discrete Event Dynamic Systems Theory and Applications — 2001 — N 11 — P 371-398

События в ДСС-модели С транспортной сети связываются с продолжи-тельностями движения поездов по всем путям С каждым событием ассоциируется множество соответствующих величин аг](к) Таким образом, множество событий £ С Щхп, те каждое событие е € £ является некото-рои (п х п)-матрицей Л, и в дальнейшем вместо е будем писать А

Функция возможностей д вводится как отображение, которое для каждой пары (к,х) € X определяет множество допустимых матриц, состоящих из значений величин ач(к), которые, в частности, зависят от скорости движения поезда по пути т3, имеющей физические ограничения Тогда д, например, может задаваться следующим образом д(к, х) = {А € £ а3{к,х) < оу < Ь^к, х) или аг] = е} для (к, х) £ X Здесь а3(к,х) и Ь}(к,х) — время движения по пути т3 с минимально и максимально возможной скоростью соответственно

Операторы событий /д для А € д(к, х) определяются уравнениями движения транспортной сети (5), т е /д(к, х) = (к + 1, А ® х ® ¿{к + 1))

В качестве множества Е„ действительных событийных траекторий выбирается множество последовательностей (Л(1),Л(2), } таких, что для всех А(к) выполняется неравенство (6), к = 1,2,3, Вводится множество

Хт = {{к,хк) Е N х X х,* = ад,г = Т7й},

содержащее фазовые состояния, которые отвечают отправлению /с-ых поездов для каждого к в соответствии с расписанием (те без опозданий) Множество Хт инвариантно относительно Еи (те для любой событийной траектории еЕ£,и соответствующей ей траектории состояний х = {21,22, ,хг, }, если хг е хт, то х3 € Хт, 2 > г)

Предложение 1. Для модели сети общественного транспорта (5) замкнутое инвариантное множество Хт устойчиво по Ляпунову относительно Еу

Предложение 2 Для модели сети общественного транспорта (5) замкнутое инвариантное множество Хт может не быть асимптотически устойчивым в целом относительно Е„

Обозначим + 1) = ¿г(к + 1) — аг]{к) — ^(к), г,] = 1,п, к — 2,3, Предложение 3 Если множество Еа состоит из последовательностей матриц {Л(1), Л(2), } € Еу, таких, что ряд

оо

тт_{51:)(/с)} к=2 47=1."

расходится, то для модели сети общественного транспорта (5) замкнутое инвариантное множество Хт асимптотически устойчиво в целом относительно Еа

Для анализа свойств рассматриваемой модели транспортной сети использованы предложенные алгоритмы Рассматривается свойство достижимости множества Хт из некоторого множества начальных позиций Хц при фазовых ограничениях Хг При этом ДСС С? рассматривается как общая трехосновная алгебраическая система конечного типа 21 = {А, 0.р, ПР, ПЕ), где Л = Пр = {/г}, ПР = {Х^Х^Х^Ё^,^, ПЕ = 0,

причем Хт = X \ Хт, Х1 = X \ Хх Считается, что Х0 = {1} х Х0, Х0 С X Заметим, что ДоС^хХДтС^хХД^^хХ Здесь N — унарный предикат, тождественно совпадающий с множеством N моментов "времени" (счетчиком состояний), N = {1,2,3, } Функция /г Х0 х £м х N —► X определяет состояние Н(хо, е, /с), в которое система перешла из начальной позиции хо = (1,хо) после того, как произошло к событий, принадлежащих действительной событийной траектории е € Е„(хо) Для бинарного предиката Е„ пара (хо, е) принадлежит Е„ тогда и только тогда, когда е € £„(хо), те е является действительной траекторией, начинающейся из состояния хо (в интерпретации Ё„ € 2х"у£Ы)

Изучаемое свойство достижимости при фазовых ограничениях примет вид

Р = Ух0 Х0{х0)\/е Д,(ж0,е) ЗА* N(4*) ( .

(Хт{к*,Цх0,е,к*)) & УЛх кг<к* ЩкиКхо^к!))) ( )

Теорема 5. Если ДСС С обладает свойством (7) и <р = (ср\, <^2, </?з)> где фх X —> X', <Р2 £ —► £', N —► ./V, есть гомоморфизм соответствующих системам С и С' ОМАСК^А и однотипной ей ОМ АС К 21', то ДСС С также обладает свойством (7)

Полученная теорема имеет, например, следующее приложение Свойство (7) интерпретируется как способность системы (5) прийти к движению по расписанию при любых начальных опозданиях поездов по р путям тУг (равным 2„,(1)), г = 1 ,р, причем для любого к все поезда в сети опаздывают не более, чем на время, равное тахг=1^{2„1(1)} Ставится задача найти условия, при которых в транспортную сеть (5) можно включить новый путь т„+1 так, чтобы это не помешало расширенной транспортной сети приходить к движению по расписанию Для расширенной системы снова рассматривается свойство (7) в указанной интерпретации

Пусть = {11,12, ,гР}, Р > 1, обозначает множество номеров путей, поезда по которым должны ждать прибытия поезда по пути тг, а </, =

Оь.72, ,3ч}, Ч > 1, — множество номеров путей, прибытия поездов по которым ждут, чтобы отправиться, поезда, следующие по пути г,

Рассмотрим условие

<1п+х{к) > й1гп(к),гт € 1}1,л € Л+1 (8)

Если период расписания тг постоянен, оно эквивалентно условию

^+1(1) > ),1т £ 1)1,31 6 Л+1

При выполнении условия (8) существует гомоморфизм из ОМАСК, описывающей транспортную сеть с новым путем, в ОМАСК, описывающую транспортную сеть (5) Поэтому из теоремы 5 следует

Теорема 6 При выполнении условия (8) включение в модель транспортной сети (5) нового пути тп+\ не меняет момент к выхода системы на реоким движения по расписанию (без опозданий поездов)

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1 Выполнена алгоритмизация синтеза критериев сохранения свойств общих многоосновных алгебраических систем конечного типа относительно семейства отображений основных множеств в однотипные ОМАСК Предложенный метод решения логико-алгебраических уравнений открывает новые возможности гибкого формирования условий сохранения свойств алгебраических систем при морфизмах с учетом специфики конкретного изучаемого свойства

2 Построен модифицированный алгоритм, обеспечивающий синтез критериев сохранения свойств ОМАСК в направлении, противоположном направлению отображений

3 С помощью указанных алгоритмов впервые получены критерии сохранения динамических свойств дискретно-событийных систем, представленных в виде ОМАСК, и на этой основе исследована модель сети общественного транспорта сформулированы утверждения об устойчивости и некоторых других свойствах Исследована динамика автоматных моделей некоторого класса Продемонстрирована применимость предложенного аппарата к исследованию общих динамических систем (в смысле В В Немыцкого)

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1 Нагул Н В К вопросу сохранения свойств многоосновных алгебраических систем / Нагул Н В // Вестник СамГУ Естественнонаучная серия - 2007 - N 6 (56) - С 223-241

2 Нагул Н В Модель сети общественного транспорта как дискретно-событийная система / Нагул Н В // Материалы Всероссийской конференции с международным участием "Знания — Онтологии — Теории" (ЗОНТ-07) Новосибирск, 14-16 сентября 2007 г — Новосибирск, 2007 - Т 2 - С 155-159

3 Нагул Н В Новый подход к исследованию дискретно-событийных систем / Нагул Н В // Труды СВМО - 2007 - Т 9 - N 1 - С 221-225

4 Нагул Н В Дискретно-событийные системы в исследовании сложных искусственных систем / Нагул Н В // Труды XII Байкальской Всероссийской конференции "Информационные и математические технологии в науке и управлении" 4 1— Иркутск ИСЭМ СО РАН, 2007 — С 91-96

5 Нагул Н В О сохранении свойств многоосновных алгебраических систем / Нагул Н В // Вестник ТГУ - 2006 - N 293 - С 158-164

6 Нагул Н В Устойчивость свойств многоосновных алгебраических систем / Нагул Н В // Материалы VIII Школы-семинара молодых ученых "Математическое моделирование и информационные технологии" (ММИТ'06) 8-12 июля 2006 г, пос Энхалук - Иркутск РИО ИГУ, 2006 - С 122-126

7 Нагул Н В Алгоритмизация получения критериев устойчивости свойств многоосновных алгебраических систем при отображениях типа мор-физмов, I / Нагул Н В // Оптимизация, управление, интеллект — 2005 - N 3 (11) - С 268-281

Редакционно-издательский отдел Института динамики систем и теории управления СО РАН 664033, Иркутск, ул Лермонтова, д 134 Подписано к печати 12 03 08 Формат бумаги 60 х 84 1/16, объем 0,8 п л Заказ 3 Тираж 100 экз

Отпечатано в ИДСТУ СО РАН

Введение

Глава 1. Обзор литературы и вспомогательные сведения

1.1. Логические и логико-алгебраические уравнения

1.2. Многоосновные алгебраические системы.

1.3. Дискретно-событийные системы как класс систем

1.4. Формализм дискретно-событийных систем.

1.5. Модель сети общественного транспорта.

Глава 2. ОМАСК и алгоритмизация синтеза критериев сохранения их свойств на основе решения логико-алгебраических уравнений

2.1. Понятие общей многоосновной алгебраической системы конечного типа

2.2. Алгоритмы синтеза критериев сохранения свойств ^ ОМАСК

2.3. Переносимость свойств в направлении, обратном направлению отображений ОМАСК

2.4. Алгоритм преобразования критериев в более эффективные

Глава 3. Примеры использования алгоритмов синтеза критериев сохранения свойств ОМАСК

3.1. Устойчивость движения общей динамической системы

3.2. Динамика автоматной сети

3.3. Некоторые свойства ДСС

3.4. ДСС-модель сети общественного транспорта и ее свойства

Данная диссертационная работа посвящена разработке на стыке динамики систем, алгебры и логики такого метода математической теории систем, который позволяет алгоритмически синтезировать критерии сохранения свойств систем при некоторых связывающих их отображениях типа морфизмов. Предлагаемый метод является развитием известных в математической теориии систем результатов: метода сравнения, последовавшего за ним более общего метода сравнения — метода логических уравнений (ЛУ), имеющих структуру ХМШ&^З' —» ф (где ШТ, ф', ф — известные члены уравнения, X подлежит отысканию, ф — свойство, рассматриваемое в одной системе, ф' — свойство второй системы, WI — условие связи), и еще более общего метода решения логических уравнений — метода редукции, оперирующего с уравнениями вида;£&(&;{(£; : г = 1, 2,., п}) ф, где п > 1.

Для получения критериев сохранения, состоящих из условий, имеющих смысл условий типа сохранения операций или отношений (т.е. формулируемых в духе традиционных морфизмов), в развитие известных в теории алгебраических систем результатов, а также в развитие так называемых критериев переносимости термов и соотношений в теории структур Н. Бурбаки, С.Н. Васильевым и С.В. Афанасьевой был разработан метод представимости. Его особенностью является то, что каждый критерий, в отличие от критериев, получаемых методом ЛУ, обслуживает сразу целый класс свойств (например, все позитивные свойства сохраняются при гомоморфизме). К сожалению, задача представимости (эквивалентными преобразованиями) формулы изучаемого свойства в требуемом классе является, вообще говоря, алгоритмически неразрешимой. Путем развития метода ЛУ удалось избежать этой задачи представимости (С.Н. Васильев, 1988), а также совместить гибкость формирования критерия сохранения по конкретному виду изучаемого свойства с получением всех условий в духе традиционных морфизмов. Логические уравнения при этом имеют вид Х&ф' —» ф, т.е. априорно никаких условий связи не задается, что полезно, так как тем самым повышается уровень алгоритмичности развиваемого аппарата.

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

Автором представлен алгоритм автоматического формирования условий сохранения свойств многоосновных алгебраических систем, а именно, введенных в диссертации общих многоосновных алгебраических систем конечного типа. Особенностью предлагаемого метода является также тот факт, что рассматриваются такие многоосновные алгебраические системы, функции и отношения которых определены не просто на базисных множествах или их декартовых произведениях, а на произвольных ступенях в смысле Н. Бурбаки. Более того, в диссертации введены некоторые дополнительные расширения ступеней. Это позволяет охватить такие динамические системы, как дискретно-событийные, главной отличительной особенностью которых является моделирование эволюции системы путем учета наступления каких-либо событий. Потребность в ДСС обуславливается стремительным развитием производственных систем и сетей связи, транспортных сетей и других, в первую очередь антропогенных, систем. Кроме того, ДСС широко применимы в технике. Любопытным примером ДСС является модель сети общественного транспорта.

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

Исходя из вышеизложенного, в диссертации были поставлены следующие задачи:

1) разработка метода алгоритмического синтеза критериев сохранения свойств многоосновных алгебраических систем;

2) получение с помощью этого метода критериев сохранения свойств динамических систем, в частности, представление дискретно-событийных систем в виде многоосновных алгебраических систем и получение критериев сохранения различных динамических свойств ДСС в их собственных терминах;

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

Заключение

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

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

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

1. Анапольский Л.Ю., Матросов В.М. Метод сравнения в анализе возмущаемых процессов // Рефераты докладов Международного симпозиума ИФАК по проблемам организационного управления и иерархическим системам, Баку, 1971. — 1972. — М., Ч. I. — С. 43 -46.

2. Аитсаклис П.И., Мишель Э.Н., Пассино К.М. Устойчивость по Ляпунову класса систем дискретных событий // АиТ. — 1992. — N 8. С. 3-18.

3. Артамонов В. А., Ященко В.В. Многоосповные алгебры в системах открытого шифрования // Успехи математических наук. — 1994. Т. 49, N 4. - С. 149-150.

4. Афанасьева С.В., Васильев С.Н. Теорема о сохранении свойств многоосновных алгебраических систем // Оптимизация, управление, интеллект. 2005. — N 3 (11). - С. 235 247.

5. Бурбаки Н. Теория множеств. — М.: Мир, 1965. — 455 с.

6. Васильев С.Н. Достижимость и связность в автоматной сети с общим правилом переключения состояний // Диф. уравнения. 2002. - Т. 38, N 11. - С. 1533-1539.

7. Васильев С.Н. Метод представимости в логико-алгебраическом подходе к качественному анализу динамических систем j j Оптимизация, управление, интеллект. — 2005.- N 3 (11). — С. 248254.

8. Васильев С.Н. Метод редукции и качественный анализ динамических систем. I, II // Изв. РАН, ТиСУ. 2006. - N 1; N 2.

9. Васильев С.Н. Метод сравнения в анализе систем. I—IV // Диф. уравнения. 1981. - Т. 17, N 9; Т. 17, N И; 1982. - Т. 18, N 2; Т. 18, N 6.

10. Васильев С.Н. : Синтез теорем с ВФЛ в математической теории систем. дис.док.физ.-мат.наук. — Иркутск: СО РАН СССР, 1988.

11. Васильев С.Н. Сохранение некоторых динамических свойств при морфизмах // Тезисы докладов III Всесоюзной Четаевской конференции по устойчивости движения, аналитической меха-пике и управлению движением. — Иркутск. — 1977. — С.99.

12. Горчинский Ю.Н. О гомоморфизмах многоосновных универсальных алгебр в связи с криптографическим применением // Труды по дискретной математике. — 1997. — Т. 1. — С. 67-84.

13. Горчинский Ю.Н. О 7г-гомоморфизмах конечных многоосновных универсальных алгебр // Дискретная математика. — 1999. Т. 11, N 2. — С. 3-19.

14. Ершов Ю.Л. Инволюторные группы // Алгебра и логика. — 1983. Т. 22, N 3. - С. 260-275.

15. Журавлев В.Ф. Основы теоретической механики. — М.: Физ-матлит, 2001. 320 с.

16. Зиглер Б.П. Представление динамических систем на основе дискретно-событийных описаний: интеллектуальное управление на базе событий // ТИИЭР. 1989. - Т. 77, N 1. — С. 68J77.

17. Зубов В.И. Методы A.M. Ляпунова и их применения. — JL: Изд-во ЛГУ, 1957. 241 с.

18. Кавинов А.В., Крищенко А.П. Устойчивость решений в разных переменных // Диф.уравнения. — 2007. — Т. 43, N 11. — С. 14701473.

19. Карпуиин Г.А., Шапошников И.Г. Скрещенные гомоморфизмы конечных многоосновных универсальных алгебр с бинарными операциями // Дискретная математика. — 2000. — Т. 12, N 2. — С. 66-84.

20. Коэн Г., Моллер П., Кадра Ж.-П., Вьо М. Алгебраические средства оценивания характеристик дискретно-событийных систем // ТИИЭР. 1989. - Т. 77, N 1. — С. 30-53.21| Мальцев А.И. Алгебраические системы. — М.: Наука, 1970. — 329 с.

21. Мальцев А.И. Модельные соответствия // Изв. АН СССР, сер. мат. 1959. - Т. 23, N 3. - С. 313-336.

22. Мальцев А.И. О представлениях моделей // ДАН. — 1956. — Т. 108, N 1. С. 27-29.

23. Матросов В.М. Метод сравнения в динамике систем. I, II // Диф. уравнения. 1974. - Т. 10, N 9; 1975. - Т. 11, N 3.

24. Матросов В.М., Анапольский Л.Ю., Васильев С.Н. Метод сравнения в математической теории систем. — Н.: Наука, 1980. 480 с.

25. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971. 320 с.27| Михалев А.В. Ортогонально полные многосортные системы // Доклады АН СССР. 1986. - Т. 289, N 6. — С. 1304-1038.

26. Нагул Н.В. Алгоритмизация получения критериев устойчивости свойств многоосновных алгебраических систем при отображениях типа морфизмов, I // Оптимизация, управление, интеллект. 2005. - N 3 (11). - С. 268-281.

27. Нагул Н.В. Дискретно-событийные системы в исследовании сложных искусственных систем // Труды XII Байкальской Всероссийской конференции "Информационные и математические технологии в науке и управлении". Ч. I. — Иркутск: ИСЭМ СО РАН, 2007. С. 91-96.

28. Нагул Н.В. К вопросу сохранения свойств многоосновных алгебраических систем // Вестник СамГУ. Естественнонаучная серия. 2007. — N 6 (56). - С. 223-241.

29. Нагул Н.В. Новый подход к исследованию дискретно-событийных систем // Труды СВМО. 2007. — Т. 9. — N 1. — С. 221-225.

30. Нагул Н.В. О сохранении свойств многоосновных алгебраических систем // Вестник ТГУ. 2006. - N 293. - С. 158-164.

31. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. — М.: Наука. Гл. ред. физ.-мат. лит., 1991. — 448 с.

32. Рамадж П.Дж., Уонэм У.М. Управление дискретно-событийными системами // ТИИЭР. — 1989. — Т. 77, N 1. — С. 78-98.

33. Романко В.К. Разностные уравнения. — БИНОМ. Лаборатория знаний, 2006. 112 с.

34. Сибирский К. С. Введение в топологическую динамику. — Кишинев: РИО АН МССР, 1970. 221 с.

35. Ульянов С.А.: Алгоритмы и программный комплекс для анализа логико-динамических моделей автоматного типа. дис.:канд.тех.наук. Иркутск: ИДСТУ СО РАН, 2005.

36. Шапошников И.Г. Гомоморфные отношения многоосновных универсальных алгебр // Дискретная математика. — 2004. — Т. 16, N 4. — С. 138-148.

37. Шапошников И. Г. О конгруэнциях конечных мпогоосповпых универсальных алгебр // Дискретная математика. — 1999. — Т. 11, N 3. С. 48-62.

38. Benabou J. Structures algebriques dans les categories // Cahiers de Topologie et Geometric Differentiel. 1968. - N 10. - P. 1-126.

39. Braker J.G. Max-Algebra Modeling and Analysis of Time-Dependent Transportation Network // Proc. of the 1st European Control Conference Grenoble, France, 1991. — 1991. — P. 18311836.

40. Bushaw D.D. Dynamical Polysystems and Optimisation // Contr. Diff. Equations. 1963. - Vol. 2. - P. 351-365.

41. Caillaud В., Darondeau P., Lavagno L., Xi X. Synthesis and Control of Discrete Event Systems. — Springer, 2002. — 238 p.

42. Cassandras C.G., Lafortune S. Introduction to Discrete Event Systems. — Springer Science+Business Media, Inc., 1999. — 776 p.

43. Ershov Yu.L. Two Theorems on Regularly R-Closed Fields j j Journ.reine angew.Math. — 1984. — Bd. 347. — P. 164-167.

44. Feferman S. Applications of Many-Sorted Interpolation Theorems // Proc. of the Tarski Symposium. Provudence, R.I.: Amer. Math. Soc. 1974. - P. 205-224.

45. Feferman S. Lectures on Proof Theory // Proceedings of the Summer School in Logic, Leeds (M. Lob, editor), Lecture Notes in Mathematics. — Springer-Verlag, 1968. — Vol. 70. — P. 1-107.5559 6061

46. Goverde R.M.P. Railway Timetable Stability Analysis Using Max-Plus System Theory // Transpartation research, Part B. — 2007. — N 41. P. 179-201.

47. Heidergott Вde Vries R. Towards a (Max, +) Control Theory for Public Transportation Networks // Discrete Event Dynamic Systems: Theory and Applications. 2001. — N 11. — P. 371-398.

48. Michel A.N., Raining W.K., Bo H. Qualitative Theory of Dynamical Systems. — N.Y.: Marcel Dekker, Inc., 2001. — 706 p.

49. Moody J.0., Antsaklis P.J. Supervisory Control of Discrete Event Systems Using Petri Nets. — Kluwer Academic Publishers, 1998. — 208 p.

50. Overkamp A., van Schuppen J.II. Control of Discrete Event Systems — Research at the Interface of Control Theory and Computer Science. — In "From Universal Morphisms to Megabytes a Baayen Space Odyssey". CWI, Amsterdam, 1994. - P. 453-467.

51. Passino K.M., Burgess K.L. Stability Analysis of Discrete Event Systems (Adaptive and Learning Systems for Signal Processing, Communications and Control Series). — Wiley-Interscience, 1998. — 202 p.

52. Ramadge P.J., Wonham W.M. Supervisory Control of Class of Discrete Event Processes // SIAM J. Control and Optimisation. — 1987. N 25 (1). - P. 206-230.

53. Ramadge P.J., Wonham W.M. On the Supremal Controllable Sublanguage of a Given Language // SIAM J. Control and Optimisation. 1987. - N 25 (3). - P. 637-659.

54. Ramadge P.J., Wonham W.M. Modular Feedback Logic for Discrete Event Systems // SIAM J. Control and Optimisation. — 1987. N 25 (5). P. 1202 1218.

55. Rossman B. Existential Positive Types and Preservation Homomorphisms // IEEE Symp. Logic In Comput. Sci. — 2005. P. 467-476.

56. Sreenivas R.S. On the Implications of the Solvability of the Supervisory Control Problem for Certain Infinite-state Discrete Event Systems Электронный ресурс]. — Режим доступа: http://www.citeseer.ist.psu.edu /138861 .html

57. Stiver J.A., Antsaklis P.J., Lemmon M.D. A Logical DES Approach to the Design of Hybrid Control Systems // Math. Comput. Modelling. 1996. - N 23 (11/12). - P. 55-76.

58. Vassilyev S.N. Machine Synthesis of Mathematical Theorems // J. of Logic Programming. 1990. - Vol. 9, N 2, 3. - P. 235-266.

59. Walther C. Many-sorted Inferences in Automated Theorem Proving //In Sorts and Types in Artificial Intelligence. — Lecture Notes in Artificial Intelligence. Springer, 1990. - Vol. 418. - P. 18-48.

60. Whitehead A.N. A Treatise on Universal Algebra, with Applications. — I. Cambridge, 1898. Reprinted 1960. — 614 p.