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

В общем случае вопрос о равенстве твквх произведений труден Мы будем рассььатрввэть полугруппы, порожденные конеч- ным множеством своих элементов. Они нвзываются конечно по- рож денным в, Можно уквэать некоторый способ задания полугрупп без ио пользовлния вндивидуэльиых свойств элементов этого множества, в котором определена полугрупповая операдня, в именно ведение полугруппы образующими и определшошими соотношениями, Кэж- пая полугруппа П может быть зедэна образующими (1.2) (алфаввт полугруппм) и определшошими соотношениями 7,.кД,. ~;х/„,„, ) (1.З) гдеЯ и В ° - слове в елфавите (1'.2). Элемент полугруппы,т.е.

слово в елфэвите (1.2), нэзывеют словом полугруппы П Элементарным преобразовэнием полугруппы /7 нвзывается переход от слова видвХЯ Х к слову ХВ/Х или обрэтно, где Х,Х - произвольные слова полугруппы П, аЯ.=В - одно аз определяющих соотношений (1.2). Элемеитарнйе преобрезова- зия предстевляются в виде схем ХЯ;У ХВ;Х' ХВ;Х ХЯ;Х . К схемэм элементарных преобрезовений прясоедииим также тэв- пологическве переходы видеХ Х .

Графическое совпадение двух ,".лов Х и ~' обозначаем К ° Х . Соотношения (1.3) определяют рввеяство слов в польгруп- ье П, которое связеио с элементарными пр оервзоэпнпямп полу- группы /7 следующим образом. ч Лва слова А' и У полугрупшя /7 равны в П тогда и только тогда, когда можно указать последовательность элементарных преобразований подгруппы П х —,)( я '..

л. х ° ... к — х переволяшую слово М в слово у Юля свободной полугруппы с алфавнтом (1,2) множество определяюпшх соотношений пусто; два слова равны то да и толь- ко тогда, когда оня графически совпадают, Полугруппу (8', +, О ) палых чисел относительно сложення можно задать образукхд33ми 1 ~р lр 01 и определяюшимн сост%О шеннямн (в адаптивной ~аннан): Г (-у) =17' (-1) у= О.

Проблема тождества слов в полугруппе заключается в сле- дуюшем: указать алгорятм, который по любым двум словам устенавлнвал бы, равны сши в полугруппе /7 илн нет, Показано, что эта проблема елгорнтмическн неразрешима, Простым првме- ром полугруппы с неразрешимой проблемой тождества слов явля- ется полугруппа с образуюшпми ~2,Ь,С,Ы, ~ н определяюшнмн соотношениями ас=са, г2С~йа, ЬС=с~, М=ЫЬ, л.а = се, едЬ= Йс, сси = сса е, 1 4 Гранты Непустое множество С с одной бпла~кой алгебраической опв рацией-называется г р уп п ой, если выдолншотся следуюшне условяр: 1) операция в С ассоцнатнвна; 2) в~ су с ву елин ч й Е:Еаааг=а~~ все Й,еС; / 3) для каждого элемента Я сушествует обратный й; дд = й 2 =Г, Иными словамн, мсжонд С, все элементы которо- го обратимы, называется группой.

Если операция вб' коммутатнвиа, то группа незывается коммутатнвной нлн абелевой. Подмножество //сС называется подгруппой в б', еслн ему принадпежнг единичный элемент с, для любых элементов /у~,Ь сФ вьшолняется Ь,Ахею, т.е, Ч замкнуто огносвтельно операции и для любогоЬеУ Ь еФ . Подгруппа/~сС называется собственной, если ~ «фн ~У х" бь~ ~. ~~,~р у,р, (г,+,у). о... „... л логячно множество рациональных и действительных чисел обра- зует группы по сложенпю (4~;~,0 ), (й',+ О ). Подмножество чет- ных чисел образует подгруппу. Подмножество нечетных чисел не 9 будет подгруппой, так как опередил сложения выводит за пределы этого множества. м ар умнохсению, так как может не сушествовать обратного элемента. Все отличные от нуля рдпиональпые числе н действительные числа образуют группы по умножению, причем коммутативные, Положительные рапионельные и положительные действительные числе образуют подгруппы этих групп.

пзр з. и с †.р ° .зМ- жество всех биективных отобреженнй Х в себя. Тогда з(Х) группа относительно оперении композипии ", Оиа называется группой преобразовзннй. р~~** *Р сс «р р порядка сх с определителем, отличным от нуля, Это некоммутативная группе (М,,~, С ) относительно оперкпии умножения матрзш, поскольку кзждый элемент имеет обретший - обратную матрипу. Подмножество матрип с определителем, равным 1, образует подгруппу, так как Х~ИГлК, а~Е1 яху С~Е~Ьху ~С~Е1ЯВс~, дИ~.р 5 м с,х,х,х определенной таблвпей Кэли (табл.

1 1), - группа ссля элементе (я, например, обратным является .Г пя в 6 аоРг, т,е классов эквивалентности по отношениюЯ сравнимостн по модулю числе гС на множестве пелых чисел (сХфЬ тогда и только тогда, когда газо (стспсс гс). Обозначим зти классы черезС,, „.,С~, где схимов ваап~(сттсзс~гх), 0 сФ" т . Множество классов вычетов образует группу с оперзпней сложения классов, определяемой по следуюшему законуссй "~~ =С, гдел~сх~ (гстссссст),Сснпл 'ссиР=Со, Сй~=Ссг-й . для п=.у, непример, зту группу можно задеть таблицей Кэлн (табл, 1.З). Твблипв 1.З ш з7 Р б ную подгруппу с елфавитом ( ст с ... ... сс,с ~ .

Сопоставим симвогвм СО ~( ~Й й,, ...,й„симьолыС7.',., а„' . Пустое слово обозначим снмволом 1. Тогда свободной группой с м С( С( С~ Ссз образуюшими П,...„сс нвзывз- ется палугруппа с еднпнпей 1, коС2 С2 Со С( торая задается определшопппш сооткошеннями сс . й . с = с' сс . й с с' с с' Пример 8. Рассмотрим правильный зг -угольник с пелтром в начале координат сс . Тогда множество преобразований плоско- 10 стя, переводящее многоугольник в себя, — некоммутатввная группа, Можно показать, что любое такое преобрзаованне есть композицвя врашелий вокруг точки 0 и осевых свмметрий, Для ут 3, напрвмер, группа самосовмешенвй правильного треугольнвка состоят пз врашенвй 6 Фг ф протвв ! часовой стрелки на углы О, 120, 1 о 240, котоРые переводят треуголь- Ь2 () 5,( вкк в себя, в трех свмметрвй Ф~, ~~,фу стносвтелъно осей свммет'- рвв У,, У~,,бу (рвс, 1.1)„йз геометрвческвх соображений понятно, (д,у -е-ч„Ф,' -е ° ((д Ф, )-е.

5 а элементы (Р~, Ф~, Фд выражаются 3 через (Дх н ф~ ". (РК = (Д х ФК = Ф~ Ф~ х Рвс. 1.1 Фв;Ф~К . 'Еслв группа состоят яо конечного чксла элементов, то сна называется конечной, а чвсло ее элементов порядкрм группы, В противном случае группе называется бесконечной. Упражнения. 1. Напвсать таблнпу Кэлв в выяснить, явлшотся лн группой; а) врзшвпня квадрата„б) свмметрнв квадратн, в) свмметрнв ромба) г) свмметрвв прямоугольнвка.

2. Пусты2 в Б - пронзволъные элементы группы б'. Повевать, что каждое нз уравнчниййк' о в ра =Б вмеет, в прв том еджствепвое, решение в данной группе. 3, Пустьаахп для любого элемента д группы С, )1оюмзать, что б" каммутатввна, 1.5. Системы об Пусть С - группа, Ф вг' - ее подгруппы. Тогда пересечение,РлЮуР непусто, так как содержит едвввчный эаемент в являетса подгруппой грудными: еспн элементы ~2 вБ прихадлежат .Р, то вх нронзведенве в обратные к ввм элементы содержатся как в Ф, так н в ~ в поэтому првкадлежат также.Р Аналогично доказывается следуюшее утвешкденве: Тео ема 2. Пересечение любого множества подгрупп грут~- пы само является подгруппой этой группы.

Пусть у - пронзэольное непустое подмножество группы С . Рассмотрим всевозможные подгруппы 0 которые содержат.Я в качестве подмножества. Одной вз них будет, в частностн, сама группа б . Пересечение всех таких 11 подгрупп будет, в сиду тсорел«ы 2, подгруппой С , которая называется подгруппой, порожденной множсством5 ° и обозно- чается "> > . Еспи множество > состоит нз одного эд«-мента И, то порожпенная нм подгруппа ~г«> цезывастся пикнической подгруппон, цор««жденной элементом «2 т,~,З,««,,„„«„п а элементом «."с, состоит из всех степеней «оп«мента «2.

11оказат«дь«чво, Все степени эдом нте «е принадлежат подгруппе с ««> . С другой стороны, этн с!пени сами составляют ,т! и «г подгруппу, так как «х «««>г) ',г« =с, а обратным к эдеменгугг >!явпяется «1 ", где по опрсдеденвн «2 ™>(>1 )'г. Лейс!.— витедьно, нетрудно показать, что дпя дюбых цс««ых:тг и гг ггг гт пг г, ггг ! гг, . ггг. г гг' й =й г (г.г г =гг ~()лн натурадмп«х ' ' г и ' г э «\ спедуст нз ссотно«ценил! ( 1 1 ), Еснн,-гг гг 'г< Сэ то «2 ~„г >г >г,г «) г«г('и --г.-«>.«'и) .',.;-!-.-- Если гтт47,гг >гг, тогг Й >««>(й ) ге -г г>а) гг'д', )!'а )~ есди 'г ' -ггг = а ) Апаногично прн ггг», ггггг .

Второе равенств«вытекает нз предыдушгга н предоставля«-.тся читатед»! ь кач«цтве упражнения. Группа, совппдьч«шая с одной из своих цнк.«!»«еских подгрупп, т,е. состояшая из ст«п«н«й одного из сгюих эд«мгнтов, называется циклической группой, а элемент, н! степеней которого состоит пикническая группа, - ее обр«лэую«ьпл!. Всякая цикднчос*«я группа колгмутативца. «««щ~ ! Г„р «Х, +, Р«, ., „С„Г. «~ «гр «д«мент - чисчо 1, Это бесконечная группз. В !.ачегт! е образу»- ного можно взять и числа - 1. «> я 2. Р, „«, „..., ., «, 2 порядка с целыми элементами н опредедитецем, равным 1. Это -руина относитедьно операции умножения матриц (показать самим), Тогда матрица 9> !о ! «порождает бесконечиу», с.жги е«.- хуго подгрупгу, .«дес! ~, гг — (г ггг г/ Гр!« .е! =, Е! я груздь! сга«осоцл сшецнй ср«ш»пьногогг — гс ! -.

п!»п и- примо).а В (сл«,разг,1г!) !«одгрупгч про иеч!«Р отис;чт! - 2.7 "очки О сост«п«т пз ц«,поротое на угды ~Р ед $Р = =' о г ! (' ° " г ) гг против ч' сгной 'т 'е!'кп Эт~ д»«.с«чесь Р ! рхддз „р дло Рг, по)с-«д«нн н«э к>«эи:ом С . ))з г-с ° нт! и- гг ь скал соэ5ргк нвй ясно, что (р = ф, (р =(Р и СР = ф н единичное прео5разовавие.

Теопема й. Всякая подгруппа пиклической группы сама п иклическая, дэказательство. Действительно, пуатье'= 4 э есть пикличес кэя группа с образующим элементом г2 и пусть И вЂ” подгруппа С, отличная от единичной. Предположим, что наимеиьпшя по- дожлггельиая степень элемента ~2, содержащаяся в И, ссгь лл . Тогда ~д~эсгг' Лопустим, что в т' содержится элементлт г ,гтО и 1 ие делятся на Ф . Тогда, осли Ы ость наибольший об- пый целитель чисел А и г, то существуют такие пелыс числа и в, чтоХГС~'Ы'чан, сла~овательио, в И должен содержать- ся элемент (м ) (лл ) =Гл . Но так как г1г~4, то мы прина ги ходюэ к шютнворечшо с выбором элемзита ~2 . Следовательно, М уу= а Пусть б' — произвольная группа, 2 - некоторый ее элемент, Если все степени злемента Я. различны, то говорят, что эле- мент 2 имеет бесконечный порядок.

Если для некоторых ртг ж /гл- е ~ Ртг н гг ямеемЫ гд, той гГ, т.е. сушествуюг положи- тельные степени элемента й., равпыо сдиаичному элементу, Пусть $ — наименьшее полглкятельиос ~испо, для которого д 'л Тогда говорят, что ~ — элемант конечного порядка Упражнения, 1. Пусть лл - элем нт конечного порядка $ Тогда поря- док пиклической подгрупчы ' ьд э равен 2, Н,.йти все образуощне в грлше врашеншу правильного 12-угольника.