Дискретная математика (998286), страница 10
Текст из файла (страница 10)
[Х) 0 [у] с [Х 0 у). 2.1.3. Алгебра термов Пусть заданы сигнатура Е = (р„,..., р ) типа АГ = (иы...,и ) и множество переменных У = (хмхю...). Определим множество термез Т в сигнатуре Е следующим образом: 1. УсТ; 2. 1ы..., 8„,. н Т зг ~р; ц Е =ь ~р(1г ° °, 8т) Е Т, Алгебра (Т; Е) называется свободной алгеброй термов, или Е-алгеброй. ОТСТУПЛЕНИЕ Носителем Е-алгебры является множество термов, то есть формальных выражений, построенных с помощью знаков операций сигнатуры Е. Таким образом, с Е-алгеброй не связано никакое конкретное множество, являющееся носителем. Поэтому Е-алгебры используются в программировании для определения абстрактных типов данных. 2.1.4.
Система образующих Множество М' с М называется системой образующих алгебры (М;Е), если [М']и = М. Если алгебра имеет конечную систему образующих, то она называется конечно-порождвнной. Бесконечные алгебры могут иметь конечные системы . образующих. Пример Алгебра натуральных чисел — (Р1;+) — имеет конечную систему образующих 1 ей. 54 Глава 2. Алгебраические структуры 2.1.5. Свойства операций Некоторые часто встречающиеся свойства операций имеют специальные названия.
Пусть задана алгебра (М; Е) и а, Ь, с е М; о, о ц Е; о, о: М х М -+ М. Тогда (аоЬ) ос = ао(Ьос); аоЬ=Ьоа; ао(Ьо с) = (аоЬ) о (аос); (а о Ь) о с = (а о с) о (Ь о с); (а оЬ) оа = а; 1. Ассоциативностгс 2. Коммугпативность: 3, Дистрибутивность слева; 4. Дистрибутивность справа: 5. Поглощение. 6. Идвмпотентносгпгк а о а = а. Пример 2.2.
Морфизмы Понятие изоморфизма, введенное в этом разделе, является одним из ключевых. Поэтому следует обратить особое внимание на посвященный изоморфизму под- раздел 2.2.2. 2.2.1. Гомоморфизм Алгебры с различными типами имеют различное строение. Пусть А = (А' Ютг..., У,„) н З = (З тут ° ° ф ) две алгебры одинакового типа.
Если существует функция У: А -+ В, такая что т 1 е 1,т У(рг(ат,..., а )) = ф; Яат),..., г (а„)), то говорят, что У вЂ” голгоморфизм из А в З. 1. Ассоциативные операции: сложение н умножение чисел, объединение и пересечение множеств, композиция отношений. Неассоциативные операции: возведение чисел в степень, вычитание множеств. 2. Коммутативные операции: сложение и умножение чисел, объединение и пересечение множеств.
Некоммутативные операции: умножение матриц, композиция отношений. 3. Дистрибутивные операции: умножение относительно сложения чисел, Недистрибутивные операции: возведение в степень дистрибутивно относительно умножения справа, но не слева: ((аЬ)' = а'Ь', аь' ~ аьа'). 4. Пересечение поглощает объединение, объединение поглощает пересечение.' Сложение и умножение не поглощают друг друга.
5. Идемпотентные операции: наибольший общий делитель натуральных чисел', объединение и пересечение множеств. Неидемпотентные операции: сложение и умножение чисел. 2.2. Морфизыы Пусть А = (А; р), З = (В; ф), тип = (1) и 7: А -+ В. Действие этих функций можно изобразить с помощью следующей диаграммы: А — "— + А  — + В Пусть у — гомоморфнзм.
Тогда если взять конкретное значение а Е А и двигаться по двум различным путям на диаграмме, то получится один и тот же элемент ь е В (так как г( р(а)) = 4 Ща))). В таком случае диаграмма называется коммутативной Коммутатнвной диаграмма называется потому, что условие гомоморфизма (2.1) можно переписать так: ~роз = з о 4~. Прииер Пусть Я = (р(;+), З = (г(1о,+го), где Х,о — — (0,1,2,3,4,5,6,7,8,9), а +гав сложение по модулю 10. Тогда Г: =а щос(10 — гомоморфизм из А в З Гомоморфизмы, обладающие дополнительными свойствами, имеют специальные названия: ° Гомоморфизм, который является инъекцней, называется мономорфизмом.
Р Гомоморфизм, который является сюръекцией, называется эпиморфизмом (или эпиоморфизмом). Р Гомоморфизм, который является биекцией, называется изоморфизмом. Р Если А = В, то гомоморфизм называется эндоморфизмом, а изоморфизм называется аетоморфизмом, 2.2.2. Изоморфизм Пусть Я = (А; ~ры..., ~о ) и З = (В; ф„..., ть ) — две алгебры одного типа, и У: А -+  — изоморфизм. ТЕОРЕМА Если ~: А -+  — изоморфизм, то у ': В + А тоже изоморфизм. Доказательство Рассмотрим произвольную операцию р из сигнатуры А и соответствующую ей операцию ф из сигнатуры З.Имеем: у(у(аы".,а.)) =Ф(у(а1) ". У(а )) кроме того, у — бнекция. Обозначим Ь1 .
= г(аг),..., Ь„: = До„), при этом а1 = з' '(Ь,),...,а„= У (Ьл) Глава 2. Алгебраические структуры Тогда у т(тЬ(Ьт,...,Ь„)) =~ '(тр(Г(ат),...,1(а„))) = У ~(У(ттт(ат,...,а„))) = .=тр(ат,...,а„) = у(~ ~(Ьт),...,~ '(Ь„)). Если ~: А +  — изоморфнзм, то алгебры А и З называют изоморфными и обозначают так: Я З, У ТЕОРЕМА Отношение изоморфизма на множестве однотияных алэебр является эквивалентностью. Доказательство 1.
Рефлексивносття А А, У:=Е Х 2. Симметричность: Я З =ь З 4. У у 1 3. Транзитивносттк Я ЗЬгЗ 9 =в А 9. У э год Пример 1. Пусть Я = (Р(;+), З = ((н ~ и = 2Ь, Ь и 1Ч) т р) — четные числа, Тогда А З. 2. А = (2м; и, и) ~ З = (2м; ц Гт), у(Х) = 2('. З. А = ()й,;.) '-" З = ()й;+), Понятие изоморфизма является одним из центральных понятий, обеспечивающих применимость алгебраических методов в различных областях. Действительно, пусть А = (А; Е ), З = (В; Ее) и А З. Пусть в алгебре Я уста- У новлено свойство Ф, = Фю где Фт и Фз — некоторые формулы в сигнатуре Е„. Поскольку алгебры А и З изоморфны, отсюда немедленно следует, что в алгебре З справедливо свойство Ф, = Фю где Ф, н Фз — формулы, полученные нз формул Ф т н Фз заменой операций из сигнатуры Е„, на соответствующие операции из сигнатуры Ее.
Таким образом, достаточно установить некоторое свойство в одной алгебре, и оно автоматически распространяется на все изоморфные алгебры. Алгебраические структуры принято рассматривать с точностью до изоморфизма, то есть рассматривать классы эквивалентности по отношению изоморфизма. 2.3. Алгебры с одной операцией Естественно начать изучение алгебраических структур с наиболее простых. Самой простой структурой является алгебра с одной унарной опердцией, но этот 2.3.
Алгебры с одной операцией случай настолько тривиален, что про него нечего сказать, Следующим по порядку является случай алгебры с одной бинарной операцией о: М х М -~ М, который рассматривается в этом разделе. 2.3.1. Полугруппы Палулруппа — это алгебра с одной ассоциативной бинарной операцией; а о (Ь о с) = (а о Ь) о с. Пример 1. Множество слов А+ в алфавите А образует полугруппу относительно операции конкатенации. 2. Всякое множество функций, замкнутое относительно суперпозиции, является полутрупной.
Если в полугруппе существует система образующих, состоящая из одного эле- мента, то такая полугруппа называется циклической. Пример (1Ч; +) является циклической полутрупной, поскольку (Ц является системой образующих. Пусть Р = (М; о) — полугруппа с конечной системой образующих А = (аи...,а„). Тогда т'з е М Луп...,уь и А з = у1 о" о уь. Если опустить обозначение операции о, то всякий элемент а е М можно представить как слово а в алфавите А, то есть М с А'. Обозначим через а элемент, определяемый словом о. Слова а и 33 могут быть различны, но соответствующие им элементы а н 13 могут быть равны: а = 33, а, 13 ~ А*, а, 13 н М. Такие равенства называются определяющими соотногаенияии.
Если в полугруппе нет определяющих соотношений, н все различные слова, составленные из образующих, суть различные элементы носителя, то полугруппа называется свободной. Всякая полугруппа может быть получена из свободной введением определяющих соотношений. Отношение раненства слов в полугруппе с определяющими соотношениями является отношением эквивалентности. Пример В полугруппе (Р1;+) имеется конечная система образующих (Ц. Другими словамн, каждое натуральное число можно представить, как последовательность знаков 1.
Очевидно, что различные слова в алфавите (Ц суть различные элементы носителя, то есть эта полугруппа свободна. 58 Глава 2. Алгебраические структуры ТЕОРЕМА (Марковт — Пост) Сутцестпвувт полугруппа, в которой проблема распознавания равенства слов алгориемичвски нвразрвтиима. Доказательство Без доказательства. 2.3.2.
Моноиды Моноид зто полугруппа с единицей; Зе Уа а ое = ео а = а. Пример 1. Множество слов А в алфавите А вместе с пустым словом А образует моноид. 2. Пусть Т вЂ” множество термов над множеством переменных тг и сигнатурой г.. Подстпановкой, или заменой переменных, называется множество пар (~г //тгг Ье 7 ~ где тг — термы, а пг — переменные, причем пг )г тт. Результатом применения подстановки о к терму 1 (обозначается йт) называется терм, который получается заменой всех вхождений переменных пт на соответствуютцие термы Ер Композицией подстановок а,' = (1г//оттгег и аз = тг //пу1уез называется подстановка а: = ат о ог: =(1ь//рьтьел, где К = 1 0.1, а 1 ггаз, если й е1, те= если )т к 1.
Множество подстановок образует моноид относительно композиции, причем тождественная подстановка (от//911 является единицей. ТЕОРЕМА Единица единственна. Доказательство Пусть 3 е1, ез ту а а о ег = ет с а = а ог а о ез — — ез с а = а. Тогда ет с ез = ег й ет о ез = ез =ь ет = ез.
ТЕОРЕМА Всякий моноид над гк1 изоиорфен некоторому моноиду преобразований над гк1. тА. А, Марков (1903-1979) 2.3. Алгебры с одной операцией ДОКАЗЯТИЛ ьство Пусть,ц = (М; ° ) — моноид над М = (е, и, Ь, с,... ). Построим У = (К; о) — моноид преобразований над М, где Р;=(~: М -+ М ~ ~ (х):=х ° пь) а о — СуПЕрПОЗИцИя фуНКцИй, Ь: М -+ Г, Ь(ГП): = Г . ТОГда: 1, У вЂ” моноид, поскольку суперпозиция функций ассоциативна, У, — тождественная функция (так как ~,(х) = х ° е = х), и с замкнуто относительно о (так как Д,о,(ь =Х ь: У ь(х) =хе(а ° Ь) =(х ° а) ° Ь= У (х) ° Ь= Я (х)). 2.
Ь вЂ” гомоморфизм (так как Ь(а ° Ь) = г„ь =,Г, о ~ь = Ь(а) о Ь(6)). 3. Ь вЂ” биекция, поскольку Ь вЂ” сюръекция по построению, и Ь вЂ” ииьекция (так как (Яе) = е ° а = а Вс Гь(е) = е ° Ь = Ь) =ь (а ф Ь =ь Д эв Я). П 2.3.3. Группы Группа — это моноид, в котором Чада ~аоа ~=а гоа=е. Элемент а ' называется обратным. Пример 1. Множество невырожденных квадратных матриц порядка п образует группу относительно операции умножения матриц.
Единицей группы является единичная матрица. Обратным элементом является обратная матрица. 2. Множество подстановок на множестве М, то есть множество взаимно однозначных функций У: М -+ М является группой относительно операции суперпозиции. Единицей группы является тождественная функция, а обратным элементом — обратная функция. ТЕОРЕМА Обратный элемент единственен. Доказательство Пусть оса ' = а г о а = е4гаоЬ=Ьоа =е. Тогда а =а 'се=а ~о(аоЬ)=(а 'оа)оЬ=еоЬ=Ь. ТЕОРЕМА В группе выполняются следующие соотношения: 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
