Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 21
Текст из файла (страница 21)
Пусть А— указатель. Предположим, что имеется только одпа операция 9, определенная па А. Следовательно, более точно зто ьюжет быть записано как (А. О+), т. е. указатель состоит из множества А с операцией ®. Теперь, если В гк А и (В, ®) также является уиазателеы, в частности ® ыожет быть замкнута яа В, то (В, йр) называется иодуказателелп Возьыеы другую структуру, состоящую пз множества С и операции ю. (ю и ® должны иметь одпп и тот же порядок.
Например, если одна из нпх является бинарной, то и другая должна быть такой же. Можно ввести и другие операции на С, однако в настоящее время ыы их ие рассматриваем). Если существует отображение ф: А - С такое, что ф(кар)-ф(к) В ф(у) для любых и и у из А, то ф называют гоыоиорфигмок. Если существует гоыоморфпэм между Л и С, то в некотором смысле образ (ф(Л), ~) гомоморфпзма из (А, ®) ведет себя подобно прообразу, тая как мы можем выполнить операцию ® на А, а затеы отобравпть в С (посредством ф) или сначала отобразить в С, а затем выполнить операцию ю. В обоих случаях результат будет один и тот же.
Поэтому мы можеьс делать так, как яам удобнее. Эту ситуацию можно пояснить с помощью иомыутативных диаграмм, изображеииых па рис. 5Л. Диаграмма па рпс. 5.1,а указывает включаемые мвожества или структуры, а диаграмма на рис. 5 1, Ь связывает отдельные элеыеиты. На рпс. 5.1, Ь справа изображены две различные формы одпого и того же результата.
Коммутатявиость диаграммы вытекает из определения оце. раций. 134 На самом деле мы получаем ц ° ® = 9 ° %, что не является в строгом смысле коммутатпвностью, так как ® п 6 существенно различны. Однако обе части равенства м,у1 — ~ — ~ Еу А~А — ® — е А ст — Е- с а Ряс. 5Л означают комбинации операций одного и того же порядка и, следовательно, подходят под общее определение отображение э операция операция а отображение. Рассмотрим пример. Пример 1.1. Пусть отображение О, О: Е- Ею — ос- таток от деления на 10.
Тогда 6(го)-о, 8(17) 7, ... Если мы рассзютркм простейшие системы (Е, +) и (Е~е, +) с операцией +, определенной естественным образом на Е я на «единичном столбцее лля Еиь то легко видеть, что 6 является гомоморфизмом. Напрпмер, 8(24+ 38) ° 6(62) 2, 8(24)+ 8(36) 4+ 8 2 (в Ею). В этом случае диаграмма будет выглядеть так, как зто изображено на рис. 5.2. е \Ж, > 5~,б) [2 ) Рее. 5.2 Таким образом, гомоморфязм одной структуры в другую является отображением, которое сохраняет структуру. Можно вводить ограниченпя ва ранг отображения, чтобы получить, например, сюръектпвяость пли пньективность, Поэтому, если отображение является гомомор- $55 фпзмом, можно надеяться, что это обеспечит механизм перехода от структуры к структуре (и обратно!) без какой-либо потери информации. О п р е д е л е н и е.
Го»1о»шрфизм, который является кпъекцпей, называют мономорфизмом, гомоморфизм, который является сюръекцпей, пазыва»от впиморфизмом, а гомоморфпзм, который является бпекцпей, пазывают изоморфизмом. Если существует пзоморфпзм между двумя структурамп, то говорят, что онп изоморфиы. г" Слово «пзоморфно» означает етой же самой формы», и поэтому, кажется, разумпо ожвдать, что пзоморфпзм должен быть в состоянии разделить множество всех алгебраических структур на классы вквпвалептиости (см.
упражнение 5.1, 2). Пример 1.2. Структуры (Ф, В'), П, В) п ((О, 1) Д, Ч)(см. определевпе в т 4 гл. 4) пзоморфны. Доказательство. Пусть ср(Ж) 0 и ~р(3) 1. Яспо, что <р — бпекцпя. Тогда д(!2!и !2!) = р(аЦ=О=ОЛО= р(а)Л р(а), ч(апй)= р(~)-о-од1- р(а)Л р(~), г (Ю П 8) = т (8) - () - 1Л О = ч Ф) Л ч (8). <ГФП~)=т(п) 1 1Л1 Ф(~)Л'р(й) ц(~!() а)- р(~!) = о-оЧ о- р(вИ р(8), г(8()й')= р(Ю)=1-О~1- р(аИгФ), г(~() 8) = р(~) -1=1~О= р(йИр(а), р(К() Ю) = р(й) -1-1Ч1= рая р(й).
Таки»г образом, «р является гомо»юрфпзмом п, следовательно, изоморфпзмом. Ф В заключение отметим, что структура может быть пзоморфка самой себе (пмеется в виду изоморфлзм, отлкчиый от тривиального) и может также быть изоморфна одной из своих подструктур (это возможно лишь для бескопечяых множеств). Определение. Если область определения и область зпачеппй отображения совпадают, гомоморфизм называют зндол»орфи»хо,з, а пзоморфпзм называют автоморфизмом. г 11 ример 1.3. Для заданного множества А структура (У(А), Г!, В) пзоморфпа (э»(А), й, П) с отображением ~р: Х- Х', 136 Д о к а з а т е л ь с т в о. Очевидно, что у ппъектпвпо и сюръектпзпо. Нслп В, С ю д>(»1), то <р (В й С) = (В П С) ' В' О С' ц (В) 0 <р (С), ~(ВйС)=(ВйС)'-В'йС'=~(В)П р(С), Позднее мы увидпм, что зтн соотношення явно показывают самодвойственность булевой алгебры множеств н <р является автоморфпз>юм.
у Упражнение 5Л. 1. Показать, что дзе структуры (Е«, »), полученные прп решении задачи пз упражнения 4Л, 2 изоморфны. 2. Пусть (А, ®), (В, Ю) и (С, б>) — указатели, а ця А - В п 8: В- С вЂ” изоморфпзмы. Показать, что О ° ~р: А- С, <р >: В- А также являются пзоморфизмамп. й 2. Простейшие операционные структуры Начнеы детальное изучение алгеораическнх структур с рассмотрения тех пз нпх, которые имеют только одну бинарную операцию. Где аго возможно, будем в атом и последующих параграфах представлять структуры в (приблизительно) возрастающем порядке «свлы». (Говорят, что структура А слабее структуры В, если А можно рассматривать как В «с отброшенной структурой». Как мы увидим позже, некоторые структуры получают путем «слияния» двух более слабых структур, и, следовательно, строгий порядок здесь невозможен.) Обычно каждую структуру можно определить в терминах основных свойств, а не только в терминах простейших структур.
Определение. Волугрунной называется мно>кество Я с бинарной операцией ®, которая удовлетворяет только требованию ассоциативности х(й>(у®з) =(х®у)®з, х, у, зев Я.,р Определение. Р>!оноидом называют множество М вместе с бинарной операцией ® такой, что ()) ® ассоциативна; (П) существует и >н М такое, что и®х=х=хцри для всех хенМ; и называют единицей но отношению к ®. е 137 Полугруппы и моноиды име»от особов значение прн обработке строк символов и теории языков. Пример 2А. Пусть А -(х, р, г).
Рассматривая х, р н г просто как символы, а не как имена объектов или «переменных», получаем, что А является аа4авитом. Оп- ределим А» как множество всех строк символов, принад- лежащих А. Тогда А» включает х, р, г, хх, ху, ух, ххуг, грх и т. д.; А» бесконечно. Па А» можно определить операцию конкатенации О следующим образом: если а, р ю А», то а О р а!), т.
е. результатом является строка а и сразу же за ней за. писанная строка р. Таким образом, имеем хуг О г хргг, хг О ух хгрх и т, д. Каждая строка а имеет конечную длину, которая обо- значается через !а! и равна числу символов в а (при етом разрешаютсл повторения). Таким образом, !х! ° 1, !ху! 2, !хххгу! ° 5. Это несколько похоже на обозначение мощности множа.
ства. Заметим, в частности, что !х! 1, !(хН 1, (ху! 2, !(х уН = 2, !ух! 2, !(у, хН 2, но (хрх! 3, ((х, р, хН ° !(х, рН 2. Позтому нет полной аналогии, хотя существует аналогия с пустым множеством. Для обозначения строки, аналогичной пустому множеству, будем использовать специальный символ Л, Л«вА*. Таким образом, !Л! 0 и ЛОа аОЛ а для всех строк а. Следовательно, для любого алфавита А структура (А», О) является моноидом, а Л вЂ” единица по отноше. пиюкО. в (Может показаться, что символ ° неверно употреб ляется в обозначении А*, однако зто не так: А» ° В»(Л), где Я ((а, р): (1 аОа, ашА).) Приведенный выше пример чрезвычайно важен.
Для заданного, достаточно большого алфавита А, содержащего, например, все символы, доступные периферийным уст- 438 ройствам какого-либо компьютера, все языки, испольвуемые в компьютерныл системах, являются подмножеством А». Это понятие является основным прп формальном изучении языков (см. гл. 8). Третьей (н последней) операционной структурой является непосредственное и естественное расширение монопда. Определение. Группой С называют множество с бинарной олерацней ® такой, что а) 9 ассоциативна; б) сутцествует элемент ию С (единица по отношению к 9) такой, что и®х х х®и для всех хыС; в) каждому элементу хыС соответствует элемент уж ю С такой, что х9у=и=у9х; у называется обратным элементом к х по отношению к ® 0 В случаях, когда групповая операция обозначается символом 9, единичный элемент обозначается 1, а обратный к элементу х элемент записывается в виде х '.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
