Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 7

Пусть даны слова а1 =ам ... а1 и сс~=ам ...оз . Тогда а1(аз, если и только если либо 1) а~=ра,у, к»=5а,б и аг (а~ (Р у 5 — некоторые слова, возможно, пустые, а~ и а; — буквы), либо 2) и» вЂ” — а,)), где р — непустое слово, Это отношение задает полное упорядочение множества всех конечных слов в алфавите А, которое называется лексико-графическим упорядочением слов. Пример 1.15.

а. Нас,о, сс . звестным примером лексико- графического упорядочения является упорядочение слов в словарях. Например, лес ( лето 1случай 1 определения: лес,с(т, у пусто, о=о), поэтому слово «лес» расположено в словаре раньше слова «лето», лес (лесть (случай 2 определения: ))=ть). б. Если рассматривать числа в позиционных системах счисления 1например, в двоичной или десятичной) как слова в алфавите цифр, то их лексико-графическое упорядочение совпадает с обычным, если все сравнимые числа имеют одинаковое число разрядов.

В общем же случае эти два вида упорядочения могут не совпадать: например, 10(1073 н 20«1073, но 10 (1073, а 20)1073. Для того чтобы опи совпадали, нужно выравнять число разрядов у всех сравниваемых чисел, приписывая слева нули. В данном примере при этом получим 0020(1073. Такое выравнивание автоматически происходит при записи целых чисел в ЭВМ. в. Лексико-графическое упорядочение цифровых представлений дат вида 05.08.86 1пятое августа 1986 года) ие совпадает с естественным упорядочением дат от ранних к поздним: например, 05.08.86 лексико-графически «старше» третьего числа любого года. Чтобы возрастание дат совпадало с лексико-графическим упорядочением, обычное представление надо «перевернуть», т.

е. годы поместить слева: 86.08.05. Так обычно делают при представлении дат в памяти ЭВМ. ГЛАВА ВТОРАЯ ЭЛЕМЕНТЫ ОБЩЕЙ АЛГЕБРЫ ЗД. ОПЕРАЦИИ НА МНОЖЕСТВАХ И ИХ СВОИСТВА Алгебры. Функцию типа цс М" М будем называть и-арной операцией на множестве М; и называется арностью операции ~р. Множество М вместе с заданной на нем сова купностью операций П =(~р~...., ~р, ), т. е. система А= (М; ць..., ~р,...), называется алгеброй; М называется основным, или несущим, множеством (или просто носителем) алгебры А. Вектор арностей операций алгебры называется ее типом, совокупность операций (г — сигнатурой. Множество Л4'с:М называется замкнутым относительно п-арной операции <р на М, если ~р(М'и) с:-М', т.е.

если значения ~р на аргументах из М' принадлежат М'. Если М' замкнуто относительно всех операций ~рь ...,ц ... алгебрыА, то система Л'=(М',ць...,ц ...) называется подалгебройА (при этом ~,, ..., ц~ ... рассматриваются как операции на М'), Пример 2.1. а. Алгебра (К; +, ) называется полем действительных чисел.

Обе операции — бинарные, поэтому тип этой алгебры (2, 2). Все конечные подмножества )7, кроме (О), не замкнуты относительно обеих операций. Подалгеброй этой алгебры является, например, поле рациональных чисел. б. Пусть А',=(О, 1, 2, ...,р — 1). Определим на А'„операции о+ («сложение по модулю р») и Я («умножение по модулю р») следующим образом; а ЯЬ=с, аОЬ=й, где с й й — остатки от деления на р чисел а+Ь и а Ь соответственно. Например, если р=7, то Ур-— (О, 1,..., б), З,~п4= =О, ЗО4=5,4®б=З. Часто операции9 и 8 обозначают как а+Ь=— с (щоб р), а Ь=й(птоо р), Если р — простое число, то алгебра (У„, Я, (.)) называется конечным полем характеристики р. в.

Пусть задано множество У. Множество всех его подмножеств называется булеаном (7 и обозначается через х1((7). Алгебра В=(В(У); (), П, — ) называется булевой алгеброй множеств над У, ее тип (2, 2, 1). Элементами основного множества этой алгебры являются множества (подмногкества У), Для любого У'~У В'=(5(У'); (), ) является подалгеброй В. Например, если ()=(а, Ь, с, й), то основное множество алгебры В содержит 16 элементов; алгебра В'=(о((а, с)); (), Г1, ) — подалгебра В; ее основное множество содержит четыре элемента.

37 г. Множество /з одноместных функций на Я, т.е. функций /Я- /з', вместе с операцией дифференцирования является алгеброй. Элементы основного множества — функции типа Я-~й!, единственной операцией этой алгебры служит дифференцирование — унарная операция типа г-+-г (производной функции па Д является спора функция на /т). Множество элементарных функций (см.

пример 1.10, г) замкнуто относительно дифференцирования, поскольку производные элементарных функций элементарны и,следовательно, образует подалгебру данной алгебры. д. Рассмотрим квадрат с вершинами в точках аь аз,. аз, а4, пронумерованных против часовой стрелки, и повороты квадрата вокруг центра в том же направлении, переводящие вершины в вершины. Таких поворотов бесконечное множество: на углы О, и/2, я, Зп/2, 2п, бп/2..., однако они задают всего четыре различных отображения множества вершин в себя, сооответствующих первым четырем поворотам.

Таким образом, получаем алгебру с основным множеством (аь аз, аз, а4) и четырьмя унарными операциями а, р, у, б. Их можно задать табл. 2.1, в которой на пересечении, например, строки аз и столбца у написано значение функции у(аз). Таблица 22 Таблица 2.2 а (1 у б у 6 я у б а 6 я 6 у а аз аз ал а, аз а, аз аз аз а4 аз аз аз а~ аз а а, аз аз 38 Операция а, отображающая любой элемент в себя, называется тождественной операцией. Она соответствует нулевому повороту.

Подалгебр в этой алгебре нет. е. Множество О=(а, р, у, б) отображений вершин в себя из предыдущего примера вместе с бинарной операцией композиции отображений (см, 5 1.2) образует алгебру (О; .), Элементами множества О являются отображения (повороты), Композиция отображений — это последовательное выполнение двух поворотов. Она задается табл. 2.2 (в ней на пересечении строки а и столбца у написан резуль* тат композиции я иу). Такая таблица, задающая бинарную операцию, называ ется таблицей Кали.

Множество (а, у), т, е, повороты иа углы О, и, образует подалгебру алгебры (О, Свойства бинарных алгебраических операций. Для того чтобы последующие соотношения выглядели более привычно, условимся результат применения бинарной операции ф к элементам а, Ь записывать пе в функциональном виде ф(а, Ь), а в ниде афЬ, так, как это принято для арифметических операций. Операция ф называется ассоциативной, если для любых элементов а, Ь, с (афЬ) фс =- аф (Ьфс). Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении афуфс можно не расставлять, Сложение и умножение чисел ассоциативны, что и позволяет не ставить скобки в выражениях а+Ь+с и аЬс. Пример неассоциативной операции — возведение ь'> ес в степень аь:(аь)'Фам .

Правда, запись а~ считается допустимой, но служит сокращением выражения ам >, а не (аь)', которое равно более компактному выражению аь"'. Важным примером ассоциативной операции является композиция отображений. Операция ф называется номмутативной, если для любых элементов а, Ь афЬ = Ьфа. Сложение коммутативно («от перемены мест слагаемых сумма не меняется»), так же как и умножение; вычитание и деление некоммутативны.

Некоммутативным является умножение матриц, например () ~) х(й й) = (и З), но (й й)х() )) .= (й 4). Операция ф называется дистрибутивной слева относительно операции ф, если для любых а, Ь, с аф(Ьфс) = — (афЬ) ф(афс), и дистрибутивной справа относительно ф, если (афЬ) срс =- (ач с) ф (Ьфс). Дистрибутивность разрешает раскрывать скобки. Например, умножение дистрибутивно относительно сложения слева и справа. Возведение в степень дистрибутивно относительно умножения справа: (аЬ)'=а'Ь', но не слева: 39 а"'чьа"а'. Сложение недистрибутивно относительно умножения: а+Ьсчь(а+Ь) (а+с).

Как будет показано позднее (5 3.2), операции пересечения н объединения множеств дистрибутивны относительно друг друга слева и справа (см. (3.9) и(3.10)). Гомоморфизм и изоморфизм. Алгебры с разными типами, очевидно, имеют существенно различное строение. Если же алгебры имеют одинаковый тип, то наличие у них сходства характеризуется с помощью вводимых ниже понятий гомоморфизма и изоморфизма. Пусть даны две алгебры А = (К; ~рь..., <рр) и В = (М; фь ..., фг) одинакового типа, Гомоморфизмом алгебры А в алгебру В называется отображение Г: К-~М, удовлетворяющее условию Г(ч (йт " "лс )) =Ч>~(Г(йн) "° Г("л~ )) (2.1) для всех 1=1,..., р(1(() — арность операций ф~ и фь кото- рая у них по условию одинакова) и всех йь~ К Смысл ус- вия (2.1) в том, что независимо от того, выполнена ли сна- чала операция ~; в А и затем произведено отображение Г, либо сначала произведено отображение Г, а затем в В вы- полнена соответствующая операция фь результат будет одинаков, Изоморфизмом алгебры А на алгебру В называется взаимно однозначный гомоморфизм.

В этом случае суще- ствует обратное отображение Г ': М-+.К, также взаимно однозначное. Пусть Г(я,) =ть т~ ~вМ. Тогда йг=Г '(т;). Заменим в условии (2.1) левые части этих равенств на пра- вые и применим Г ' к обеим частям получившегося равен- ства. Так как Г ' Г является тождественным отображением Г гГ(а) =а, то получим: ~р;(Г '(ип), ..., à — '(пгцп) =à — 'ф,(пьп ..., топо)). (22) Равенство (2.2) — это то же равенство (2.1) с заменой Г на Г ', элементов К на элементы М и перемендй местами Чч н ф; иначе говоря, Г ' — это изоморфизм В на А.

Итак, если существует изоморфизм А на В, то существует изоморфизм В на А; при этом алгебры А и В называются изоморфными. Мощности основных множеств изоморфных алгебр равны (при гомоморфизме это равенство может не выполняться). Если А=В, то изоморфизм называется изоморфизмом на себя, или автоморфизмом; если В~А, то изоморфнзм называется изоморфизмом в себя. 40 Таблица 2.3 Ь! Ьг Ье Ье й! й2 йе Ьз Ьз Ьг Ьз Ьз 2 Ь, 62 Ьз ь, Ь Ь, Ь, Ь, ь, ь, Ьз Ь, аз йг аз а, ае а, йе аг йг а! а! аз й! аг йз ае а аг а, ае б) Отображение Г: ае-е-Ьз, аг-е-Ь|, аз-+62, ае-|-Ье изоморфизмом. является 41 ПРимеР 2.2.

а, ПУсть Яи — множество всех целых чисел, (.12и — множество всех четных чисел. Алгебры (Яа', +) и (с?гн1 +) изоморфны; нзоморфнзмом является отображение Гг,. п-э2п, причем условие (2.1) здесь имеет вид 2(а+6) =2а+2Ь. ПосколькУ Я!и~?~ю то Гг„— изомоР- физм (сбн; +) в себя. Отображение Г-:и- ( — и) является для алгебры (Язе, +) автоморфизмом; условие (2.1) имеет вид ( — а)+ ( — Ь) = — (а+Ь).

Для алгебры Яи; ° ) Г л не является автоморфизмом, так как ( — а) ( — 6) чь — (йЬ). б. Рассмотрим алгебры (А|„+, ) и (№, Я, О) (см. пример 2.1) н определим отображение Г!.Ле-~№ следующим образом: Гз(п) равно остатку от деления и на 7; иначе говоря, если п=7а+Ь(Ь(7), то Гг(п) =Ь. Пусть а!= =7а|+Ь,; пг=7аг+62, Проверим условие (2.1). Для сложения имеем Г2(п,+п,) =Ге(6|+62) =ЬеЯ62=Г2(п!)Я-;.Гз(гзг). Для умножения имеем Гг(пепг) -Гг(6!62) =Ь! В62= =Гт(п!)ОГ2(пг). Таким образом, условие (2.1) выполнено и Г! — гомоморфнзм. Очевидно, Г, не является нзоморфнзмом, так как нет взаимной однозначности.

Этот пример показывает, что возможен гомоморфизм бесконечной алгебры (т.е. алгебры с бесконечным основным множеством) в конечную алгебру. При этом Ае разбивается на семь классов эквивалентности по отношению Е!. аЕ,Ь, если и только если Гт(а) =Гг(6) (см. пример 1.12,г) а. Изоморфизмом между алгебрами Я+, ° ) и (12', +), где ет+ — положительное подмножество 1с, является отображение а-е-?оц а, Условие (2.1) имеет вид равенства ?оц аЬ=?оп а+?од Ь. г.

Рассмотрим алгебры (??, |р) и (М, |р), где ??=(а! аь йз, пе); М=(Ь!, Ьг, Ьз, 6е), а бинарные операции |р и ер заданы следуюшими таблицами (табл. 2.3„а, б). Буквальная проверка условия (2.1) состоит в следующем: в клетках (во внутренней части) таблицы ~р заменяем а; на Ь„в соответствии с Г и получаем левую часть (2.1), т. е, таблицу функции Гч (аь а~); во внешней части таблицы ф заменяем Ь, на а; и получаем правую часть (2.1); сравнением полученных двух таблиц убеждаемся, что они задают одну и ту же функцию, В действительности достаточно в таблице ~р переименовать все ьп в Ь; и сравнить полученную таблицу с ф.