Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 4

1.2, в — частично опредедеппой фупвппей. Количество аргументов определяет местность функции. Выше были рассмотрены одноместные функции. Аналогично понятию декартова произведения двух множеств определим декартово произведение и множеств. Декартовым произведением состоит из и элементов, причем первый элемент принадлежит множеству Мы второй — множеству Мз и т. д., и-й элемент принадлежит множеству М„. Если множество М в определении функции у = Г(х/ является декартовым произведением множеств М „М „..., ~ „, то получим определение пместной функции: у = Г(хы хз,..., х„).

Частным случаем и-местной функции у = Г(хг, хт,..., х„) является и-местная операция. Под и-мссткой операцией О„в множестве М понимается и-местная функция у = Г(хь,хз,...,х„), у которой области определения аргументов и область значений функции совпадают: Таким образом, и-местная операция по и элементам множества М определяет (и+ 1)-й элемент этого же множества. Рассмотрим пространство 1 и определим в нем четыре операции над множествами: объединение, пересечение, разность, дополнение. Объединением М, !.1 Мь двух множеств М, и Мь является множество Ме состоящее из элементов множества М, и из элементов множества Мь: М=М 0Мь=(т;/ т;бМ и/плит!бМь).

Пересечением М, ! !Мь двух множеств М, и Мь является множество М, состоящее нз элементов, которые принадлежат как множеству М„так и мнод!еству Мь.' М = Мо й Мь = (тз/ т! б М» н т! б Мь) ! часто союз "иа заменяют знаком Й: М = М, Г! Мь = (т;/ т; б М, Й т; б Мь). Разностью М, 1 Мь множеств М, и Мь является множество М, состоящее из элементов, принадлежащих множеству М, и не принадлежащих множеству Мь.' М Ма!!Мь = (т'/ т' б М Йт' ~ Мь). Введенные операции являются двуместными. Рассмотрим операцию дополнения, являющуюся одноместной. Доиолнекием М множества М является множество М = (т;/ уи; 1с М).

Операции объединения, пересечения, разности и дополнения проиллюстрированы на рис. 1.3; результирующее множество каждой операции выделено штриховкой. Используя эти операции, можно выражать одни множества через другие, при эхом сначала выполняется одноместная операция дополнения, затем пересече- 18 Гл. 1. Основы многосортвных мяожес>пв 11.2. Понятие алгебры. Фундамеи>ппльяые алгебры 19 ния и только затем операция объединения и разности.

Для изме- нения этого порядка в выражении используют скобки. М, М, м,гьм, М.ЦМь МаГ>Мь Майа М31 Мь М Рпс. 1.3 Ярь ЯУ,32вгь Рпс. 1.4 Э1.2. Понятие алгебры. Фундаментальные алгебры Алгеброй А называется совокупность множества М с заданными в нем операциями о = 1>2311> Л2» " Лк» У21> 122> > вяз» Ут1> Уеьэ» Уюкэ> У> обозначается А = (М, Я)," здесь множество М вЂ” носитель, Я— сигяатура алгебры.

Первый нижний индекс у идентификатора операции указывает ее местность. Замечание. Для идентификации единого целого, содержащего объекты, которые имеют различное математическое строение (например, множества и операций в нем), было предложено использовать термин многосортнос множество или совокупность и обозначать его угловыми скобками. Рассмотрим фундаментальные алгебры. Алгебра вида (М, ут) называется группоидом. Если уэ — операция типа умножения, то группоид называют мультипликативкым, если у2 — операция хипа сложения, то ад'- дитивяым. Таким образом, множество можно задать выражением, в которое входят идентификаторы (указатели) множеств, операции и, быть может, скобки. Такой способ задания называется аналитическим.

Пример 1.2. Рвссмотрпм эпервпшо дополнения мпэяествэ, яэдяющегвся пересе>вянем мпояеств М, и Мь Ее ревукьтвт сввпэдвет с эбьедппзнпем дэповкеппй этих мпов>еств: М = ММ>»>ть = >я, ц Мь; в этом мвяпэ убедяться с помощью дяэгрзмм Эйперв (рпс. 1.4).

Пусть А = (М, 12) — группоид; обозначим операцию Л как о. Тогда элемент е б М называется правым кейгяральиым элементом группоида А, если для всякого элемента гп б М выполняется равенство то е = т, и левым нейтральным элементом, если ЕО ГП = Пь. Если элемент е б М группоида А = (М, о) является одновременно и левым, и правым нейтральным элементом, то его называют двусторонним нейтральным элементом или просто нейтральным элементом. Никакой группоид не может иметь более одного нейтрального элемента. Действительно, если гп о с = = е о т = тп и гп о е' = е' о пь = т справедливо для всех т б М, то е'=е'оехзе.

Если группоид (М, о) мультипликативный, то нейтральный элемент называется единицей и обозначается 1; если группоид (М, о) аддитивный, то нейтральный элемент называется кулем и обозначается О. Группоид А = (М, о) называется идемпотсяткым, если его сигнатура удовлетворяет закону идемпотентности (Ут б М) (гп о т = т). Группоид А = (М, о), сигнатура которого удовлетворяет закону коммутативности (эх> у б М)(х о у = у о х) > называется яолсиутативяым или абслевым.

Группоид (М, о), в котором выполняется закон ассоциативности (1>'х> у, х б М) (х о (у о х) = (х о у) о х) > называется ассоциативным или полугруппой. Полугруппа (М, о), в которой выполнимы обратные операции, т. е. для любых а; 6 б М каждое из уравнений а о х = 6, у о а = 6 обладает единственным решением, называется группой. Проплпюстрпруэм понятие группы пэ примере группы падстэповок, сэдеряэшей шесть элементов. Группу пэдстэновов псследэвэк зыдвющкйся фрэппуэскпй мзтемэтпк Эвэрнст Гвпув в связи с решением уравнений в радикалах. Пэ>>сп>а нов кое я-а с>пепем к нвэыввэтся взаимно одповпэчяое отэбрвяеяпе мпояествв яз я элементов пэ себя.

Рассмотрим трп элемента: х>, хз, хз. Существует шесть перестэиэвок пэ трех элементом х>хзхз, хзхзх>, х>хзхз, хзх>хз, хзх>хз> хзхзх>. Эвппшем две перествяовкя пз трех элсмеятов друг под другам: (х> хз хз) Этв ээвпсь ээпэчэет, чтэ х> перэхэдпт э хз,хз — в хз,хз — в х>. Числа воэмояяых кодстэпэвэк резко числу перестэпэвэк. Введем спелую. щяе обозкэчзякя ддя шесп> воэмэяпых подствнэвок: (х> хз хз) 6 (х> хз хз) (х> хз хз) 1 (х> хз хз) (х> хз хз) у (х> хз хз) Гл. 1. Основы мноаосортных множесте 20 11,2. Понангие алгебры.

Фундаментальные алгеб ы 21 Введем операцию умножения х иад подстановками. Ироозаедемкел ноосюоноаок называется подстановка, получаемая в результате последовательного выполнеиин сначала первой, а затем второй па перемиожаемып подстаиовок. Например, (х1 хз хз) (хг хз хз) (хг хз хз) Значения выражения а х л, где а, 16 = о, Ь, с, а, е, у, представлены в табл. 1.1. Таблица 1.1 В рассматриваемой алгебре (М, х) выполняется закон ассодиатявиости, ио не выполняется закон коммутативиостя.

Рассматриваемая алгебра (М, х) ие является абелевой, так, а х 13 ф 11 х а, например, при значениях и = с, 11 = Ь; с х Ь = е, Ь х с' = о*. В алгебре выполняется ааксн ассоциативности (а хф) х у=ах(8х у), (1.1) следовательно, она является полугруппой (рис. 1.5). хь л Зе г» ге о Рис.

1.6 )(иаграмма выполнения подсгаиовов согласие левой (о) и правой (6) частям выражения (1.1) х, хс Каждое уравнение а х х = й и р х а = 11 имеет одноапачное решение (рис. 1.б). Следовательно, зта алгебра является группой. АЬ пе (В(1), О, П, ), носителем которой является булеан универсального множества 1, сигнатурой — операции объединения О, пересечения Г1 н дополне- ния . Для операций алгебры Кантора выполняются следуюшие законы: закон кольиутативности объединения и пересечения Ме 0 МЬ = МЬ 0 Ма, Ме Г) МЬ = М6 Г1 Ма) эакон ассоциативности объединения и пересечения М.0(МЬОМ,) = (М,ОМЬ) 0М„ М, П (МЬ Г1 М,) = (М, П МЬ) П М,; эакон дистрибутивности пересечения относитлельно объе- динения и объединения относитпельно пересечения Ма П (М6 0 Мс) ™е й МЬ 0 Ма П Ме| М,0М6 ПМ, = (М,0МЬ) Г3(М,0М,); эаконы поглоибенил М.

0 М. Г1 МЬ = М., М, Г1 (М. 0 МЬ) = М.; эаконы склеивания Ма Г6 МЬ 0 Ма П ИЬ вЂ” Мо ~ (Ма 0 МЬ) П (Ме 0~~6) Ма) законы Лореикого Ма 0~ Ма Г1 М6 — Ма 0~ МЬ| Ма Г1 (Ма 0 МЬ) — Ма Г1 МЬ) эакон идемпотенглносгпи объединения и пересечения М,0М, озМ„М,ПМ,=М,; закон действия с универсальным (1) и пустым (й1) множе- ствами М0Ыаз М, МПЯ~= Ы) М01 = 1, МГ31=М, М0М=1, МПМ=а; Алгебра (М, х, +), которан по умножению является мультипликативным группоидом, а по сложению — абелевой группой, причем умножение связано со сложением законами дистрибутив- ности а х (Ь+ с) = а х Ь+ а х с, (Ь+ с) х а = Ь х а+ с х а, называется кольцом. Кольцо, в котором все отличные от нуля злементы составляют группу йо умножению, называется телом.

Тело, у которого мультипликативная группа абелева, называется полем. Рассмотрим алгебру множеств (алгебру Кантора, алгебру классов) Гл. 1. Основы миогосортиых множеств законы де Моргана М,ПМЬ=М,иМь, М,ОМЬ=М;ПМь, закон двойного дополненид М=М. Алгебра Кантора по аддитивной операции объединения и мультипликативной операции пересечения является абелевой полугруппой (так как для этих операций выполняются законы коммутативности и ассоциативности), но она не являетсн группой (поскольку уравнения М, 0Х = Мь, МаПХ = Мь не имеют решения, например, для случая когда множества не пересекаются: М, ПМь = Я). Следовательно, алгебра Кантора по двуместным операциям 11 и П не является кольцом.

Эта алгебра принадлежит к другому классу фундаментальных алгебр — к классу решеток, который рассмотрен ниже. 3 1.3. Бинарные отношения, способы нх задания и свойства Фундаментальным понятием дискретной математики является понятие отношенил, которое используют для обозначенин связи между объектами или понятиями. .Квадратом множества М иазываетсн декартово произведение двух равных между собой множеств: М х М = Мт. Бинарным отношением Т в множестве М называется подмножество его квадрата: Т С Мт. Говорят, что элементы т; и т находлтсл в отношении Т, если (т„т.) б Т. Совокупность множества М с заданным в нем бинарным отношением Т С Мт называется графом С: ст=(М, Т), где М вЂ” носитель графа (множество вершин), Т вЂ” сигнатура графа (множество дуг).