Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§ 1.2. Понятие алгебры. Фундаментальные алгебры

Алгебра (М, х,+), которая по умножению является мульти

пликативным группоидом, а по сложению — абелевой группой,

причем умножение связано со сложением законами дистрибутив

ности

а х (Ь +с) = a xb + a x с, (Ь+с) ха = Ьха + сх а,

называется кольцом. Кольцо, в котором все отличные от нуля

элементы составляют группу по умножению, называется телом.

Тело, у которого мультипликативная группа абелева, называется

полем.

Рассмотрим алгебру множеств (алгебру Кантора, алгебру

классов)

Ak = (В( 1), U, П, ” ),

носителем которой является булеан универсального множества 1 ,

сигнатурой — операции объединения U, пересечения П и дополне

ния . Для операций алгебры Кантора выполняются следующие

законы:

закон коммутативности объединения и пересечения

Ма U Mb = Mb U М а, , М а П Mfc = Mb П Ма\

закон ассоциативности объединения и пересечения

М а U (МЬ U Мс) ~ (Ма У М Ь) U Мс,

Ма П (Mb П Мс) = (М0 П Mb) П Мс\

закон дистрибутивности пересечения относительно объе

динения и объединения относительно пересечения

Ма П (Mb U М с) = М а П Мь U Ма П Мс,

МаиМьПМс = (Ма и Мь) П (Ма U Мс);

законы поглощения

М а U Ма П Мь = Ма, М а П (Ма U Mb) = М а]

законы склеивания

Ма П Mb U Ма П Mb = Ма, (Ма U М(,) П (Ма U Mfc) = Ма;

законы Порецкого

Ма U Ма П Мь = Ма U Мь, Ма Л (Щ и М Ь) = Ма П Мь;

закон идемпотентности объединения и пересечения

M a U Ма = М а, Ма П М а = М а]

закон действия с универсальным (1 ) и пустым (0 ) множе

ствами

M U 0 = M, М ГШ = 0, М Ul = l,

М П 1 = М, М и М = 1, М П М = 0;

Гл. 1. Основы многосортных множеств

законы де Моргана

М„ П Мь = Ма и Мь, М0 и Мь = М а П Мь,

закон двойного дополнения

М = М.

Алгебра Канхора по аддитивной операции объединения и муль

типликативной операции пересечения является абелевой полугруп

пой (так как для этих операций выполняются законы коммутатив

ности и ассоциативности), но она не является группой (поскольку

уравнения М„ U X = Мь, М0ПХ = Мь не имеют решения, напри

мер, для случая когда множества не пересекаются: МаПМь = 0 ).

Следовательно, алгебра Кантора по двуместным операциям U и П

не является кольцом. Эта алгебра принадлежит к другому классу

фундаментальных алгебр — к классу решеток, который рассмо

трен ниже.

§ 1.3. Бинарные отношения,

способы их задания и свойства

Фундаментальным понятием дискретной математики является

понятие отношения, которое используют для обозначения связи

между объектами или понятиями.

Квадратом множества М называется декартово произведе

ние двух равных между собой множеств: М х М = М 2. Бинар

ным отношением Т в множестве М называется подмножество его

квадрата: Т С М 2. Говорят, что элементы т,- и mj находятся в

отношении Т, если (т,-, rrij) £ Т. Совокупность множества М с

заданным в нем бинарным отношением Т С М 2 называется гра

фом G:

G = (М, Т),

где М — носитель графа (множество вершин), Т — сигнатура

графа (множество дуг).

Пример графа был использован при рассмотрении группы Га

луа (рис. 1 .6 ).

Рассмотрим задание бинарного отношения с помощью матри

цы смежности и фактормножества.

При матричном задании используют двумерную таблицу — ма

трицу смежности, каждой строке (столбцу) которой взаимно одно

значно сопоставляют элемент множества М . Тогда каждая клетка

(г, j) взаимно однозначно соответствует элементам множества М 2.

Клетку (г, j), которая соответствует элементу, принадлежащему

Т е м 2, каким либо образом помечают, например, зачерняют или

помещают в нее единицу; остальные клетки оставляют незачер-

ненными или в них записывают нули.

§1.3. Бинарные отношения, способы их задания и свойства 23

Рассмотрим предложенную фон Нейманом блок-схему ЭВМ, которая состоит

из множества устройств

М = {а, Ъ, с, d, е},

где а — устройство ввода, 6 — арифметическое устройство (процессор), с —

устройство управления, d — аапоминающее устройство, е — устройство вывода.

Рассмотрим информационный обмен между устройствами ш, и ту, кото

рые находятся в отношении Т, если из устройства т , поступает информация в

устройство ту. Это отношение можно задать в виде матрицы смежности сле

дующим образом:

В =

1 '

Граф G, задаваемый рассмотренным отношением Т, изобра

жен на рис. 1.7. Здесь (и в дальнейшем) вершины графа изобра

жаются в виде кружков (иногда в виде точек),

дуги — в виде стрелок, исходящих из тп,- и

входящих в rrij, если (m,-, rrij) 6 Г; при этом

вершина тп; — начало дуги, а вершина rrij —

ее конец.

Рассмотрим задание бинарного отношения

с помощью фактормножества.

Окрестностью единичного радиуса эле

мента тп,- € М называется множество элемен

тов rrij € М таких, что (m,-, rrij) € Т, Т С М 2.

Часто вместо термина окрестность единич

ного радиуса используют термин сечение.

Множество окрестностей единичного радиу

са, взятых для всех элементов множества М

при задании в нем отношения Т С М 2, называется фактормно

жеством М /Т множества М по отношению Т. Фактормножество

М /Т полностью определяет отношение Т.

Зададим фактормножество для рассматриваемого примера в виде двух строи,

в первой из которых поместим элементы множества М, во второй под каждым

элементом запишем окрестность единичного радиуса этого элемента:

Рис. 1.7

<*}

{с, d, е}

{a A d, е}

{Ь, с, е}

{с}

Тогда вторая строка аадает фактормножество М по Т.

Бинарное отношение, задаваемое графом G = (М, Т) (рнс. 1.7), можно за

дать и перечислением его дуг: М ={о, 6, с, d, е}, Т = {(о, 6), (а, с), (о, rf), (6, с),

(Ь,е), (b,d), (с, о), (с, 6), (c,d), (с,е), (d,c), (d,b), (d,e), (е,с)}.

Рассмотрим наиболее важные свойства бинарных отношений.

Отношение Т в множестве М называется рефлексивным, если

для каждого элемента тп € М справедливо (тп, тп) € Т. Свойст

во рефлексивности при задании отношения матрицей смежности

Гл. 1. Основы многосортных множеств

Рнс. 1.8

характеризуется тем, что все элементы, лежащие на главной диаго

нали, отмечены (равны 1 или зачернены); при задании отношения

графом каждый элемент имеет

петлю — дугу вида (т, т)

(рис. 1 .8 , а).

Отношение Т в множестве

М называется симметричным,

если из (m,-, rrij) 6 Т следует

(m*, m,j) 6 М, mi ф mj.

Матрица смежности симме

тричного отношения являет

ся симметричной относительно

главной диагонали, а при за

дании отношения в виде графа

следствием симметричности является наличие между всякой па

рой вершин, находящихся в отношении Т, двух противоположно

направленных дуг (рис. 1 .8 , 6).

Отношение Т в множестве М называется транзитивным, ес

ли из (mi, mj) € Т и (mj, тк) € Т следует (mi, m*) € Т, где mi,

mj, m k е М; mi ф mj, mi ф m k, mj ф m k.

В графе, задающем транзитивное отношение Т, для всякой

пары дуг таких, что конец первой совпадает с началом второй,

существует третья дуга, имеющая общее начало с первой и общий

конец со второй (рис. 1 .8 , в), — транзитивно замыкающая дуга.

Отношение Т', задаваемое частичным графом G' графа G (см.

рис. 1.7), после удаления дуг (а, 6), (а, d), (b, е) и (d, е) становится

симметричным.

Частичным графом G' графа G — (1^, U) называется граф

вида G' — (^, U'), U' С U, т. е. граф G', G' С G, получается путем

удаления дуг из графа G.

Дуга называется инцидентной вершине и, если эта вершина

является началом или концом дуги.

При удалении, вершин и инцидентных с ними дуг получаем

подграф G' графа G: G' С G. Если в подграфе G', G' С G, удалены

некоторые дуги, то получаем частичный подграф G", G" С G' С

С G, графа G.

Отношение Т ", задаваемое частичным подграфом G" графа G

(см. рис. 1.7), полученным после удаления всех дуг, кроме (а, Ь),

(а, d), (6 , е) и (d, е) и вершины с (рис. 1.9, а), не обладает ни

свойством симметричности (<т), ни рефлексивности (р), ни тран

зитивности (г)). Оценим, к какому из этих свойств отношение Т"

наиболее близко. Близость А(Т", а) отношения Т" к свойству

будем оценивать минимальным числом дуг, которые нужно уда

лить или добавить к графу, задающему это отношение, для того,

чтобы граф задавал отношение Т, которое обладает свойством а,

а = (Т, р, 77. Для рассматриваемого примера (рис. 1.9,6)

Д(Г,«т) = 4, А(Т", р) = 4, Д (Г")7?) = 1 .

Используя эти свойства, определим бинарное отношение упоря

доченности, имеющее большое теоретическое и практическое зна

чение.

§1.3. Бинарные отношения, способы их задания и свойства 25

Рис. 1.9

Бинарное отношение R в множестве М , обладающее свойст

вами:

рефлексивности

(Va € М ) ((а, а) € Д);

антисимметричности 4

(Va, 6 G М ) (((а, Ь) € R (Ъ, а) € R) а = Ъ);

транзитивности

(Va, Ь, с € М ) (((а, 6) € R (6 , с) € R) -»• (а, с) е R)]

называется отношением упорядоченности и обозначается <.

Бинарное отношение в множестве М, обладающее свойствами

антирефлексивности, антисимметричности и транзитивности, на

зывается

отношением строгой упорядоченности

и обозначается

<. Отношение R в множестве М, обладающее свойствами ре

флексивности и транзитивности, называется отношением пред-

порядка.

Рассмотрим отношение включения С . Это отношение рефлек

сивно: Mi С Mi (множество М,- включает самое себя); если М,- С

С Mj и Mj С Mi, то Mi — Mj и, следовательно, оно антисимме

трично; если Mi С M j и Mj С Mk, то М' С Mjfc, значит, отношение

С транзитивно.

Отношение включения С является отношением упорядоченно

сти <. Множество М с заданным в нем отношением упорядочен

ности < называется упорядоченным этим отношением.

Если любые два элемента т,- и ту упорядоченного множества

находятся в отношении упорядоченности т,- < ту или ту < т,-,

Гл. 1. Основы многосортных множеств

то это множество называется линейно упорядоченным (цепью); в

противном случае множество называется частично упорядочен

ным.

Пример частично упорядоченного множества приведен на

рис. 1 .1 0 (в качестве отношения < рассмотрено отношение вклю

чения множеств с).

Часто частично упорядоченное множество изображают в виде

графов Я = (V, < ), у которых удалены все петли и все транзи-

тивно замыкающие дуги. Граф Я = (V, <), задающий частично

упорядоченное множество с удаленными петлями и транзитивно

Рис. 1.10

замыкающими дугами, называется диаграммой Хассе Я . Диа

грамма Хассе Я , задающая частично упорядоченное множество,

которое показано на рис. 1 .1 0 , а, изображена на рис. 1.10,6.

Диаграмма Хассе известна с конца XIX века, и в течение мно

гих лет ее применяли в генеалогии для указания родства. Понятие

непосредственного старшего легко задается в частично упорядочен

ном множестве следующим определением: тп,-

покрывает ту; это

означает, что m j < mi и не найдется такого элемента т х, что

mj < тх < mi.

Рассмотрим подмножество М ' упорядоченного множества М .

Если найдется элемент та € М такой, что т,- < та для любого

элемента т,- подмножества М ', то элемент т а называется

мажорантой подмножества М '. Аналогично, если найдется эле

мент тр € М ' такой, что тр < т,- для любого элемента т,- под

множества М ', то элемент тр называется минорантой подмно

жества М '. На диаграмме Хассе Я (рис. 1.10, б) элемент {г} яв

ляется минорантой подмножества {{у, г}, {а, х}, {у, х, о}}, эле

мент {а, г} — мажорантой подмножества {{г}, {а}, 0 }.

§ 1.3. Бинарные отношения, способы их задания и свойства 27

Если мажоранта т а подмножества М ' принадлежит М '. т а (Е

€ М ', то она называется максимальным элементом ( т макс) этого

подмножества. Аналогично, если миноранта тр подмножества

М ' принадлежит М ', тр 6 М ', то она называется минималь

ным элементом ( т мии) подмножества М '. В диаграмме Хассе Н

(рис. 1 .1 0 , б) минимальным и максимальным элементами подмно

жества {{г}, {у, г}, {а, х}, {у, х, а}} являются соответственно

{ж}, {у, х, а}. Для пары элементов линейно упорядоченного мно

жества всегда существуют максимальный (равный одному из них)

и минимальный (равный другому) элементы. Пару элементов ли

нейно упорядоченного множества m,-, rrij, для которых тп; < rrij

или rrij < тп,-, называют сравнимыми.

Если множество мажорант (минорант) в свою очередь имеет

максимальный (минимальный) элемент, то его называют верхней

(нижней) гранью подмножества М'. Верхнюю (нижнюю) грань

множества М ' обозначают supМ ' (infM').

Верхняя (нижняя) грань подмножества М ', принадлежащая

М ', называется наибольшим (наименьшим) элементом подмно

жества М '.

Теорема 1 .1 . Упорядоченное множество М содержит не

более одного наибольшего (наименьшего) элемента.

Докажем теорему для случая наибольшего элемента. Действи

тельно, если т а, тр — два наибольших элемента, то т а < тр и

тр < т а, откуда в силу антисимметричности отношения < сле

дует т а = тр. Доказательство для наименьшего элемента анало

гично.

Наибольший элемент упорядоченного множества М , если он

существует, назовем единичным и будем обозначать 1. Наимень

ший элемент упорядоченного множества М , если он существует,

назовем нулевым и будем обозначать 0 .

В упорядоченном семействе множества 1 пустое множество со

ответствует нулевому элементу, 1 — единичному элементу.

Элемент, покрывающий 0 в частично упорядоченном множе

стве М , т. е. минимальный элемент в подмножестве множества

М , полученном исключением 0, называется атомом или точ

кой. При задании с помощью графа семейства множества М точке

(атому) соответствует элемент универсума.

Под изоморфизмом между двумя упорядоченными множества

ми М и М* будем понимать взаимно однозначное соответствие rj

между М и М* такое, что из mi < mj следует Т)(m,) < Tj(mj) и из

т?(т,-) < тl(mj) следует т,- < т,-.

Два упорядоченных множества, М и М*, называются изо

морфными тогда и только тогда, когда между ними существует

изоморфизм.

Гл. 1. Основы многосортных множеств

Под отношением R, обратным R, понимают такое отношение,

при котором (mi, rrij) € R тогда и только тогда, когда (rrij, тп,-) €

€ R.

Принцип двойственности. Отношение, обратное от

ношению упорядоченности, также является отношением упо

рядоченности.

Двойственным к частично упорядоченному множеству М на

зывается частично упорядоченное множество М , определенное на

том же носителе с помощью обратного отношения. На рис. 1.10, в

изображена диаграмма, являющаяся двойственной к диаграмме

Хассе (рис. 1 .1 0 , 6). Часто принцип двойственности формулируют

следующим образом: если теорема справедлива для частично

упорядоченных множеств, то справедлива и двойственная ей

теорема.

Очевидно, что подмножество М ' упорядоченного множества М

является упорядоченным множеством, и если это упорядоченное-

множество М ' является линейным, то подмножество М ' является

цепью М ' в М . Одной из важных числовых характеристик цепи

М ' является ее длина I, равная |М '| — 1 , где \М'\ — мощность

носителя линейно упорядоченного подмножества М '. Каждая цепь

длины I изоморфна цепи целых чисел 1 , 2 , ...,/ + 1 . „

Высотой d(mi) элемента тп,- упорядоченного множества М на

зывается максимум длины (/Макс) цепей m0 < mi < ... < т,- в

М , для которых mi — наибольший элемент, то — минимальный

элемент множества М.

Длиной d(M) упорядоченного множества М называется макси

мум длин цепей в М. Другими словами, длиной d(M) упорядочен

ного множества называется максимум высот с?,(т,) его элементов

d(M) = maxd,(m,), m, € М.

Наименьшей верхней гранью называется верхняя грань, мень

шая всякой другой верхней грани. Наибольшая нижняя грань

определяется аналогично. Очевидно, что подмножество упорядо

ченного множества имеет не более одной наименьшей верхней и

не более одной наибольшей нижней грани.

Другим важным бинарным отношением является отношение

эквивалентности (^>). Бинарное отношение эквивалентности, об

ладающее свойствами рефлексивности, симметричности и тран

зитивности, называется отношением эквивалентности.

Назовем классом эквивалентности К (т а) элемента т а мно

жество всех элементов т,-, каждый из которых находится с этим

элементом в отношении эквивалентности (множество эквивалент

ных элементов):

К(та) = {m i/ т{ ~ т а}.

§1.4. Решетка 29

Согласно свойству рефлексивности отношения ^ имеем т а €

€ К(та). Из свойства транзитивности отношения эквивалентно

сти

(та * ть) к (гпь * тпс) т „ ^ т с

следует K(ma) Э К(тпь), а из свойства симметричности —

тпа ^ ть - К(та) = К(ть).

Два различных класса эквивалентности, К(тх) и К(ту),

тпх / ту, не пересекаются: К(тпх) П К(тпу) = 0, так как в про

тивном случае они бы совпали. Действительно, пусть найдется

элемент тпг, принадлежащий этим классам: mz € K(mx), К(ту)\

тогда согласно приведенным выше свойствам К(тх) = К(тг) =

= К(ту). Иначе говоря, если найдется элемент mz, принадлежа

щий двум классам эквивалентности, К(тпх) и К(ту), то К(тпх) =

= К(тпу), что можно записать (используя вместо слова “найдется”

обозначение 3)

(3 тпг е К(тпх), К(тпу)) -¥ (к{тпх) = К(тпу)).

Представление множества М в виде попарно непересекающих-

ся подмножеств {М,} будем называть разбиением этого множе

ства:

U Mi = М, Mia П М,ь = 0 , ia ф ib-

Таким образом, классы эквивалентности

образуют разбиение множества. Тестом

распознавания отношения эквивалентно

сти, заданного матрицей смежности,

может быть приведение с помощью пере

становки строк (столбцов) матрицы смеж

ности к виду, изображенному на рис. 1 .1 1 ,

где около главной диагонали расположены

подматрицы, состоящие из единиц (они

заштрихованы), остальные элементы матрицы равны нулю. Каж

дая заштрихованная подматрица соответствует классу эквивалент

ности.

§ 1.4. Решетка

Используя понятие частичного упорядоченного множества, оп

ределим понятие решетки. Решеткой называется упорядоченное

множество (М, <), любые два элемента m,-, rrij которого имеют

наибольшую нижнюю грань, или пересечение т,- П ту, и наи

меньшую верхнюю грань, или объединение т,- U rrij. Очевидно,

Рис. 1.11

Гл. 1. Основы многосортных множеств

что упорядоченное множество М , двойственное решетке М, явля

ется решеткой, в которой пересечение и объединение меняются

местами.

Упорядоченное множество, в котором любое подмножество име

ет наибольшую нижнюю и наименьшую верхнюю грани, называ

ется полной решеткой. Очевидно, что если все цепи в решетке

конечны, то всякое подмножество в решетке имеет наименьшую

верхнюю и наибольшую нижнюю грани.

Найдем в качестве упражнения пересечение и объединение некоторых эле

ментов решетки, определенной диаграммой Хассе Н (см. рнс. 1.10,6):

{у} U {*} = {у, *}, 1 U 0 = 1,

{у} П {о, у} = {у}, {у, х}П {а} = 0 ,

{у, х} П {а, х} = {*}, {у} U {а, х} = 1.

Решетку можно определить и как алгебру А = (М, U, П), сиг

натура которой обладает следующими свойствами:

коммутатив ности

ТП{ U T71y = rtlj U 771;, т ; П mj = rrij П m,-; (1.2)

ассоциативности

(m; U mj) U тк = т ; U (my U тк),

(т ; П ту) П т* = т,-П (ту П т*); ‘

поглощения

771; и т , П mj = т ;, 771; П (т ; U mj) — ТП{. (1.4)

На основе закона поглощения можно доказать свойство идем

потентности (дедекиндовости) этой алгебры:

771; = ТП; U Ш; П (т71; U 771 j) = 771; U 771;,

771; = ТГЦ П (m; U Ш; П mj) = mi П ТП;

(этот результат получен Дедекиндом).

В любой алгебре, удовлетворяющей свойствам (1.2)—(1.4),

т,- П ту = ту тогда и только тогда, когда

771; U my = т,- U т,- П ту = т ;.

При введении отношения упорядоченности <:

тп,- > ту <-> т ; П ту = ту,

получаем определение решетки, в которой т , Пту и m, Umy явля

ются соответственно наибольшей нижней и наименьшей верхней

гранями.

Свойство рефлексивности отношения <:

771; < т ;,

вытекает из справедливости закона идемпотентности

тп,- П т ; = т,-;