В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 22
Текст из файла (страница 22)
1. Пусть Х вЂ” произвольное множество, М(Х) — множестве всех отображений Х в себя. Тогда относите.тьво операции кои; позиции отображении М (Х) — моиоид, оп иекоммутгтивныйОбозначпм сто 21(Х О, ет). 2. Множество квадратных матриц порядка и отноз:тельно умножения матриц в некоимутатиеный моноид с сдюпжиыи элементом — сдеипчиой матрицей, а относительно сложения матриц — комиутативвый мононд с единичным злсмектои — ну левой матрицей. Обозначим ит соответственно (М„(К], , Е) (М,(й), +,О).
3. Множество целых чисел — камиутативиый монопд хе«ог носительно сложения, так п умножения. Обозначим пх ссответ отвеине (2, +, О), (2. °, 1). Множество целых чисел, зеляжнх ся на п(п ° 1),— коммутатнвпая полугруппа без еднснсы итие сительно умножению Обозначим ее (пХ, ° ). 4. Пусть А=(аь ..., а,) — конечное множество ю:кислое алфавит. Конечная последовательность символов называетгй слоном в алфавгпе А. На множестве П слов в алфавите А вве. Гея дем бпнарную операппю — «приписывание», т, е.если а=аг аел Ь=а,...а)о то аЬ=аг, аь а . ад Тогда П вЂ” полугрупйа д)иа называется саоболной полугруппой, порожденной множест. аон А. 5. Множество (Хь Х,.
Хг. Х,) откоснтельно операдин, задан. пой таблнцей Кэлн (см. табл. О.!), — конмутатнаный мононд, едпнпчный элемент которого Хй Полнножество П' полугруппы П называется лодлолугруллой, есзз абеаП' для всех а, ЬсаПС В этом случае говорнт также. что подмножество П' замкнуто относительно рассматриваемой операцпн. Очевндно, подцолугруппа П' сама нвлаетсн полугруп. пой относительно операцнн в П. Если М вЂ” моноид н подмноже. ство М' не только замкнуто относительно операция, но н содер.
жнт еднннчный элемент, то М' называется лодлоиопдал М. Например, множество чнсел. нратных л, — нодпалугрупоа в позугруппе целых гнсел относительно умножении (Х, , 1) н поднопанд в (Х, +, О). В полугруппе П слов в алфавите А под.
множество слов в алфавите А'ЫА также подполугруппа. Элемент а мононда М с единичным элементом е называетсн обрагпаыл, если для некоторою элемента Ь выполняется равенство аЬ=Ва=е. Элемент Ь называется обраглмл а н обозначается а '. Обратны!г элемент едпнственен. Действительно, еслн еще п аЬ'=Ь'а=с, то Ь'=еЬ' (Ьа)Ь'=Ь(аЬ')=Ье=Ь.
Нетрудно вндпгь, что (а-')-'=а. Кроме того, если а, Ь обратимы. то (аЬ)-'=Ь-'а-', так как (аЬ)(Ь-'а-')=а(ЬЬ-')ам= =ага-' аа-'=е, н апалогпчно (Ь-'а-') (ад)=е, т, е. злеыент аЬ тоже обратим. Множество всех обратнмык элементов монопда образует подмоноид, так как содержит единичный элемент н замкнуто отпсснтельно операцнп: если а н Ь обратимы, то Ь-'а-' — элемент. обратный аЬ. Расснотрнм проблему тождества слов в полугруппах. Пусть 5= (гь ..., з,) — подмножество элементов полугруппы П таксе, что любой элемент пэ П мохгет быть представ.тен как пронзаеденне элементов нз 5. Тогда множества 5 называется системой образукчцих полугруппы П.
Например. лля свободной полтРУппы П, поРождевной алфавитом А=(аь ..., а ), само множество А является системой образующих; для полугруппы целых чисел относительно сложения (Х, +, О) системой абразщощнк явлнетсн множество ( — 1, 1, О), а лля полугруппы пе.чых чисел относнтельно умножения (Х, °, 1) образующими яв.
лаются все простые числа н едпннца. Следует заметить, что далека ве все пронзведеннн элеменюв Множества 5 будут разлнчнымп элемевтамн полугруппы П. В общем счучае вопрос о равенстве таких пронзведеннй довольао сложен. 1ОЗ Будем рассматривать полугруппы, порожденные нонечиыьз множеством своих элементов. Они назызаютси конечно.пораж денными. Можно укааать некоторый способ задания полугрупп без ис пользования индивидуальных свойств элементов множества, в коюром определена полугрупповая операция, а именно задание полугруппы образующими и определяющими соотнощепнями. Каждая полугруппа П может быть задана образующими аи аз, ..., а, (2.1) (алфавит полугруппы) п опрезслнюшими соотношенггями А~=вг (г=1, 2, ...), (2.2) где Я~ и Вг — слова в алфавите (2.!). Элемент полугруппы, т.
е. стоэо в алфавите 12.1), незывакм словом полугруппы П. Элементарным преобразованием нолугруппы П называется переход от слова вида ХА,У к слову ХВ,У (илп обратно), где Х, У в произвольные слова полугруппы П, а А.=З. — одно пз определнющих соотношений (2.2). Элементарные нреобразозання представляются з виде схем ХЛ;У ХВгу; ХВ;У ХЛ,У. К схемам элементарнык преобразований относятсв также тавтологнческве переходы энда Л Х. Графическое созпэденае лвух слов Х и У обозначают Хо У, Соотношения (2.2) определяют равенство слов в полугруппе П, которое связано с элсмснтарнымн преобрвзовангжмя полу- группы П следующим образом.
Два слова Х в У полугруппы П равны в П тогда н только тогда, котла можно указать последо- вательность элементарных преобразований полугруппы П Хбхе-ьхгч-..г-ьхг-ьх;ы ... Х,бу, переводящую слово Х в слово У. Для своболной палугруппы с алфавитом (2.1) миохюство оп- ределяанцих соотноюений пусто: два слова разин тогда и толь- ко тогда, когда онн графически совпадают. Полугруппу (Е, +, 0) целых чисел относительно сложения можно задать обраэующини ( — 1. 1, 0) н определяющими (в адг дитивиой записи) соотношенаями: 1+( — 1)=0; ( — 1)+1=0. Проблема:голгдесгаа слое в полугруппе заключаетсч в сле- дующем: указать алгоритм, который по. любым двум словам ус: танавливал бы, равны они в полугруппе П илн нет. Докаэанф что эта проблема елгоритмнчески неразрешима.
Простым прн мером полугруппы с неразрешимой проблемой тождества слов !04 ввляетс1г позугруппз с образующиыи а. Ь, с, б, е н опрелеляю- ягкми сооглощеииямн ос=со, айр йа. ос=со, ЬИ='бЬ, еса=се, а1Ь =с)з, сса=ссае. 2.12. Группы: опрелеление и примеры Кепустое множество С с пдной бинарной алщбранческой операцией называется зрущюй, ецтв выполняются следующие условия; ! ) осерзаня в б ассоциативна: 2) в О существует единнчный элемент е: еа аз=а для всех ащб; 3) лля «зжзого элемент» а существует обратный ему элеиент а-Н ва-'=а-'а=с. Иными словамн, мононд б.
все эзеыеиты кото!ого обрати. Мы, назыазется группой. Если озерацпя в б комнутатввпа. то группа иаэынается коллугагизнол нлн абглезол. Подмножество Нщб называется лодгруююй в б, если еиу прквздлежкт единичный элемент е, для любых элементов Ьь Ь,щН выполняется Ь,йгщН, т. е. Н замкнуто относительно операции. н дзя любого ащН выполняется 1юцщН, Подгруппа Нщ! кззыааегса собственной. если Н вЂ” е н Нчьб.
Пример 2:г. !. )дпожссгво целых чисел образует групву целих чисел относитеааю операции сложения (2. +. О). Эта групп» коммугагизпа. Ляззогично множество рзщюпальных и действ~пеньках чисел образует сгютветствеино группы относительно сложения,'гй, тч О) и (2, +, О). Подмножество четных чисел образует подгругзу. Полчножество аечегвых чисел не образует подгруппу, таа ггзк операции сложения выводит нз этого ыножесгв а. 2. Меожгсгво целых чисел не обрззует группу отноагтельво умкожензя.
так кзп может не существовать обратного Ьленеытз. Все атласные от нуля рациональные числа н действительиые числа образуют группы относите.тьно умножения, причем комчугвтизаые. 1!оложительные рзппонзльиые п ооложнтельные лейсгантельеые числа образуют позгртнаы этих групп. 3. Пусть Х вЂ” щюнзвольное нножество, 8 (Х) — множество всех бвеятханых отображений Х е себя.
Тогда 5(Х) — группа отиосительао операция компознник С. Опа наэыеается группой преобразований. 4. Рзссмотрни множество Л пвазрвтнык матриц порядки в с оиредеактелем. отличным от пула. Это пекоммутативиая группа (24„... Е) опюсительно операции умножения ыатрвц, поскольку каждый элемент имеет обэзтный — обратную матущу. Подмножество матриц с опрсцелктелен, равным 1, образует подгруппу, так как бе1Е=1: бс!А=!; бе!В=!ьбе!АВ=1! бе!А=)4ь ~бе! А-'= 1. б.
Множество элементов (хь ль к,, хг) относительно операции, определенной таблицей Кэпи (см. табл. О.! ),— группа. Длв элемент» к,, например, обратным являетси элемент л, !см. введенне, равд. ОА). б. Рассмотрим множество классов вычетов по модулю л. т.е классов.эквивалентности по отноюеншо р сравнкмости по моду. лю чвсла л иа множестве целых чисел (арЬ тогда и только тот. да, когда азгзЬ (глоб л) ). Обозначим зти классы через Сз,. „С„в где аспсз тогда и только тогла, когда азий(вобл), 0<А<в (см. введение, рззж 0.2).
множество илассов вычетов образует группу отиосптевьио ооерацви спожения классов, определяемой по следующему эвггону4 Сз-(-Сг=С„где й+(=г(пюбл), 0( щг цл, и «=Сч, С 'ь=С -з. Например, прв л=З зту группу можно задать таблицей Кэпи (см. табл. 2.1). 7. Рассмотрим свободную волугруппу с алфавитом (аь ..., и,). Сопоставим символам а4, ., а символы л4-', ..., а.,-! Пустое слово обозначим символом 1.
Тогда сеобоблой груллой с образующими аь ..., а„называется полугруппа с елиияцей 1. которая задается определиющимп соотношениями о4а 4=1, аг-'а4= =1, 4=1... л. Тзазивэ 21 С ) С Сг С» Сг 8. Рассмотрим правильный л-угольник с центром в иачзле. коорлинет О. Тогда множество преобразований плоскости, переволвщее многоугольник в себи, образует некоммутатнвнум группу, называемую группой самосовмещеннй мпагоугольнвка. Можно показать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
