Алгебраические системы и некоторые их приложения в теории информации и автоматизации проектирования

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕПИАЛЬНОГО ОБРАЗОВАНИЯ СССР МОСКОВСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮПИИ АВИАПИОННЫЙ ИНСТИТУТ имени СЕРГО ОРДЖОНИКИДЗЕ В,А, ОСИПОВА В,В РЫВИН АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ И НЕКОТОРЫЕ ИХ ПРИЛОЖЕНИЯ В ТЕОРИИ ИНФОРМАПИИ И АВТОМАТИЗА11ИИ ПРОЕКТИРОВАНИЯ Учебное пособие Утверждено иа заседании редсовета 29 анрепа 1987 г. МОСКВА 1988 519 (О75) 0-7 41 УДК 512.8+512,5~(075.8) Осипова В,А„Рыбвн В,В, Алгебренческне системы н некоторые нх приложения в теории ннформапнн н автометнэеднн проектвровення: Учебное пособие, — Мгп МАИ, 1988.

-59 с.;нл, В пособии дается краткое взложенне основных понятвй теории елгебранческю систем. Провллюстрнровено прнмененвя елгебраическвх в топологвческнх методов к эадечем кодирования в теорвя информепнн н для опвсеяяя н нсследовення структу)юых свойств систем упраелення Пособяе предназначено для студентов факультета "Првкледнея метемлтнка" н попвчно студентем внженерных фекультетов прн поучения курса Дискретная математике . Рецензенты; В.С. Зарубвн, А.В. Пестуховсквй, В.В, Подяновсквй С Московскнй евашяонный ннствтут, 1988 О ПРЕЛИС ЛОВ ИЕ Ра~ятвэ мкогвх современных оч'раслей каукн в техники потребовало обьэдвкнть творческве усялня спепвалкстов в са- мых разных областях првхладкой математнкв, Работа в этвх областях в ряде случаев требует довольно глубокого званая со- временной алгебры. В этом пособвя дается краткое наложение о<ионных жжятвй теорпв алгебравческвх свсгем н провллюстрвровано прв- мекепне алгебранческях в топологвческвх методов к задачам кодяровання в теорнн внформапнк в опясаякв к нсследовавяя сгруктуркых свойств скстем управления, В разделе 1 рассматрнваются псжяткя полугруппы, группы, колька, коля, Подробно освешыогся вопросы, связанные с тео- рвей групп Раздел 2 посэюпеп взложепвю элементов алгебракческой теорвя кодвроваяня, В разделе 3 рассматривается алгебраический метод описа- ния к ясследоваквя разлкчвых твпов графов метод структур- ных чисел.

В разделе 4 опнсывается методвка расчета системных ха- рактэрвстях лвнейкых систем управленвя в свмвольком вндэ, э основе которой лежат соедвяепне топологкческкх к алгебракчео кнх методов.. Она позволяет рещать задачу автоматнзвроваяного расчета снстемных харахтернстхп в общем контексте решекнк задачи ав оматнзапня проектнрованяя скстем управлеввя, Пособне базируется на материале лехпвй по курсам "Лнс хретяая математкка, Основы построения првкладного программ- ного обеспечения САПР УК ЛЛ, чнтаемых авторамн на факуль- тете Пряклел~ая математнка, Его првкладные аспекты исполь- зуются прв выполпеевв курсовых работ по укаэанным курсам.

1, АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ В этом рездвде ва элементарном уровне рассматрвваются о~лепные, фундшаентальиые для всей алгебры понятия полугрупцы, группы, кольца и поля, 1,1, Ацгебравческве опе адни В различных разделах курса математики Вы уже встреча- лись с понятием алгебраической операции, определенной на неко- тором множестве. Пусть дано множество М, Говорят, что иа М определена бинарная алгебраическая операция, если всякой упо- рядоченной паре элементов множества М по некоторому закову ставится в соответствяе вполне определенный элемент этого же множестве, Примерами бинарных оверапий на множестве целых чисел явлшотся сложение и умножение, однако нашему определеншо не удовлетворшот, например, множество отрицательных нелых чнсеп относительно умножения, множество действвтельных чисел отно- сительно деления ввиду невыполнвмости деления иа нуль.

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

Его удобно описать с помощью так называемой таблипы Кэпи. Слева и сверху квадрат- ной таблипы выцксываются все элементы множества, На пересе- чении строки, соответствующей элементу й ° и столбца, соот- ветствующего элементу д, пишут результат операции над с2 в Ь, Из двух приведенных примеров таблиц Кэпи (табл.

1,1 и 1,2) вторая есть таблица для операции конъюнкции на множест- ве 1И,Л). Мы будем употреблять спедуюшую терминологию и свмволи- ку: операцию называть умножением, а результат применения опе- рации к элементам й и Ь обозначать ИЬ . Это мультиплика- тивная терминология, В некоторых случаях естественнее и удоб- нее испольэовать аддитивную терминологию и символику: опера- зюо называть сложением и результат ее выполнения называть =уммой Д~ Ь элементов м и Ь ч Таблипа 1,1 Таблнпа 1.2 Если для любых элементов О нЬ множестваМ спревед пяво равенство Одежд, то оперэдня называется коммута- т явнойй, Првмерами пекоммугатввных операпвй являются век- торное произведение векторов, провзведенве матрвп порядка п. прп УюэЯ.

.Еспп для пвбых элементов О,Ь,ь ьпиожестааМ справед- ляво равенство О~ЬгРайФС, то операпвп называется а соо- ппатпвной, Сложение в умпакенве пммх чисел, умножение матрнп, композвпяя отображенвй ассодватввны. Првмером неао- соппатнвпой операпкп спужпт векторное умвожепю векторов пространства, Оперэпнн, определеяные табпвпамв Кэлв (табл.1.1 и 1.2), ассопватввны.

В ряде случаев множеством, ва котором определена алга брапческая операдвя, об~адает едннячпым элементом, т.е. т пм е енто с, чтоО~=жал д в О вэМ . Епн- нвчный элемент эдяпственеп, так кэх чспн Г' эые однн элемент с тя же с йтв м, т сс=с вхзс=к', откудаЕ а", В слу- чае апдитввной эапнск единпчпый элемыгг будет называться ку- левым н обозначаться О . Нэ множестве квадратных матрвп порядка гт едвввчкым элементом относительно операпвк умножения является едпнвчпая матрвпа, яа множестве отображений множества Х в себя едв- пкчным элементом относвтельно композиппп отображенвй явля- ется тождественное отображеяне, Чпсло Ф есть едяввчный эле- мент иножесгва пелых чисел' относятэльно операппк умпоженпд, а множество четных чисел ве обладает единичным элементом отяоснтельно этой оперални, Еслх оперения ассоциативна, то мы можем одкозпачпо гово- рить о провзведении тобого копечиого числа элементов, взятых э определенном порядке.

Пусть дана упоряцочжчпая система вз и элементов множества М:Ог,й~,..., й~з, в которой неко торым образом расставлены скобкп, указыэатощве иа порядок,в ко- тором должна выполняться оперэпяя. 5 Теорема 1 Еслн операнда, определшпюаа наМ, ассопнатва- на, то результат ее последовательного прамэневна к Рк элемен- там мкожества ве завнсвт от расстановкн скобок, Воказательство проведем ввдукпвей по чвслу множвтелей Рт, ))ла Р$ * 3 утверждение следует кз заксша ассопнатнвво- ств, Всквжем это дпк случая П мпожвгепей, предполэгээ, что длк мвкьшего чнсла множителей упзэрждэпве нерво. Достаточно показать, что дпя любмк Ф н 6, где Ул4 ~ б Р8 — 1 йг,.

„., Й„)~Й,„...Й„)=(а,...а, ) ~а...„. а„), так как внутри скобок пк расстановка весупшствевва по ндпу~- тканому преддоложевню. Юла этого покажем, что обе часта ра- вевстеа совпадают с провэаедевнем элемевтов Йб...,Й гх взатых в следующем фвксвроваввом порндке [, [(Й йл)Йл~ . )Й~ ( во аа ааетса левовормнро пным прон аед п м а...,а~). Д й, р Ь -~ (Й, Й „~ )Й~ (...(Й йд ) Й )Й,, левапормврованаое произ- ведевнэ, Прая , и-4 ввиду ассопватвэностн (а,... Йд)(ай„...а ) =~а,... ай)((ай., а„,)а„) = -Яа,.„ай)СЙ„, а„,))Й„=(...((...(а,а )...а~]ай„)„.а„,)а„ т.е. снова получаем левсвсрмнроаанвоэ провэведэвне, К этому же ввду прнводнтса а правам часть доказываемого раввиства, В свау доказанной теоремы прв запаса а вмчвсленвв произ- ведеввкЙ Й „,Й мы должны заботатьсн лишь о порндке мко жвтелей, в то лншь в случае, когда оперэлнп нексммутатювоа В частности, пРн Ф лйР .эйли л 4 пРокзведеввед а „.

Й обоатачшот самвелом а ° который плзываетсв Рэ -й степенью элемшгге Бом г .Р'" М ав М обладает едвкнчвмм элементом, то полагают Йэ""Ю, Иэ теоремы 1 вытекают ссочношеввп Й а~за';('а~) ла, пг,Па 4'. (1,х) В адднтваной снмаолнке имеем ооответстзеавоРУЙ эЙ+Й~„.+ Й и вмполнаотсп соотношепвн РУ~Й т и Й =(т+ гг)Й, П ~гпту) = з'йугттРЙ.

)..а. и н мсвонды Множество /7 с заданной в пем баваркой ассоднатавной оаерапией называется полугруппой, Полугруппа с едвннчпмм элементом называется м оп о ад ом (ввв просто полугруппой с единицей). Дрймер 1„Пусть Х - произвольное множество,/Ч (Х )— множество всех отображепвй Я а себя Тогда относительно опе ракии композвцин отображений М (Х )- мспонд,оп не коммутативеп. Будем обозначать его (Ю (Х,д,Р ), В носительно оперении: если ьх и Ь обратимы, то а й - элемент, обратный к /2Ь.

1.3. Полугр ь и проблема тождества слов Пусть м х ~Яю „,, Л/ь ) — подмножество элементов полугруп- пы П, такое, что любой элемент нз П может быть предстэв- лен кэк пронзведенве элементов вз .у . Тогда множество ю на- зывается системой образуюшюс П . Например, для свободной полугруппы /7, порождешьой алфэввтомЯ=(/7 „„,,2„), семо множесгвоЯ есть системе обрэзуюших; для йолугрудпы пелых чисел относительно сложения (Е, +,ь7) множество (-/,/, О) является системой образующих, для полугрулпы пелых чисел от- носительно уыноженвя (2,', / ) образующими явльпотся все про- стые числе и едвинпа, Отметим, что дэлеко не все произведения элементовЛ бу- дут различными алемеитвми полугруппы П .