Дискретная математика (стр. 2 )

Обратное отношение не надо путать с инверсным отношением (–), которое состоит из пар, не принадлежащих , но принадлежащих DR. Для конечных отношений матрица инверсного отношения получается из матрицы исходного отношения инвертированием, т. е. нули матрицы становятся единицами, а единицы – нулями. Очевидно, что ()=.

Композицией отношений и называется множество упорядоченных пар <x, z> таких, что существует y такое что, <x, y> и <y, z>. Для конечных отношений матрица их композиции будет произведением матриц исходных отношений.

Докажем, что ()=. Для этого возьмём любую пару из левой части равенства и приведём её в правую часть. Доказательство: пусть <x, y>()<y, x> z : <y, z> и <z, x><z, y> и <x, z><x, y>. Здесь над стрелками указаны применяемые операции. Поскольку все стрелки двусторонние, то можно по ним пройти и из правой части равенства в левую. Не всегда стрелки бывают двусторонние. Равенство доказано.

Отношение f будет функцией, если из того, что <x, y>f <x, z>f следует, что y=z. Другими словами, для каждого x существует ровно одно y, такое что <x, y>f. Отношение не будет функцией, если у какого-то x существует два или несколько y, или у какого-то x нет совсем никакого y. Функция осуществляет отображение множества X на множество Y или устанавливает соответствие между X и Y. Мощность функции равна мощности множества X.

Функция f инъективна (однозначна), если у каждого x своё собственное y, не совпадающее с другими y. Функция сюръективна, если все y имеют свои x. Функция биективна, если она и инъективна и сюръективна одновременно. Биекция (биективная функция) осуществляет взаимно однозначное соответствие между множествами X и Y.

Примеры: экспонента (y=e) инъективна, но не сюръективна, так как нет отрицательных значений y; y=(x*x*x – x) – сюръективна, но не инъективна, так как y в интервале от 2/(3*) до -2/(3*) имеют по два x; y=2*x+1 – биекция.

Теорема: композиция двух функций есть функция. Доказательство: пусть функция f отображает X на Y, а функция g – Y на Z, докажем, что gf отображает X на Z. Для доказательства берём две пары из композиции: <x, y> gf и <x, z> gf и докажем, что y=z. По определению композиции для <x, y> u : <x, u>f и <u, y>g, а для пары <x, z> v : <x, v>f и <v, z>g. Поскольку f – функция, то u=v, а так как g – тоже функция, то y=z. Теорема доказана.

Композиция двух биекций тоже биекция. Без доказательства. Единичная функция e отображает множество X на себя так, что каждое x переходит само в себя. Если функция f отображает X на Y, то f e= f = ef. При конечном множестве X матрица единичной функции имеет единицы только на главной диагонали (так называемая единичная матрица).

Поскольку функция f – это и отношение тоже, то существует и обратное отношение f. Обратное отношение будет функцией тогда и только тогда, когда f – биекция. Без доказательства. Если f биекция, то f тоже биекция.

Глава 3. Специальные бинарные отношения

Для отношений эквивалентности и порядка (специальных бинарных отношений) область определения отношений совпадает с областью их значения. Матрица конечного специального бинарного отношения (далее просто отношения) будет квадратной. Для таких отношений, определённых на одном множестве, существуют понятия рефлексивности, симметричности и транзитивности.

Отношение на множестве X рефлексивно, если xX пара <x, x>. Для конечного рефлексивного отношения на главной диагонали его матрицы отношения находятся одни единицы. Отношение «быть больше и равно» - рефлексивно, а отношение «быть меньше» - антирефлексивно. Для конечного антирефлексивного отношения на главной диагонали его матрицы отношения находятся одни нули. Не рефлексивное и не антирефлексивное отношение является арефлексивным. Для конечного арефлексивного отношения на главной диагонали его матрицы отношения находятся и единицы (хотя бы одна) и нули (хотя бы один). Для понятия рефлексивности конечного отношения важны только данные на главной диагонали его матрицы.

Отношение на множестве X симметрично, если x, yX из того, что пара <x, y> следует, что и пара <y, x> . Матрица конечного симметричного отношения будет симметричной. Симметричным является отношение «совпадать по чётности» (или «иметь одинаковый остаток при целочисленном делении на два» или «совпадать по модулю два») на множестве {1, 2, 3, 4}. Пара <1,3> и пара <4,2> принадлежат этому отношению, а пара <4,1> - нет. Матрица этого отношения имеет вид:

Равенство чисел по модулю два является частным случаем равенства чисел по модулю n. Отношение «равенство по модулю n» является симметричным для каждого n>1.

У понятия антисимметричности есть два определения. Применяется то из них, которое в данном случае более удобно. Отношение антисимметрично, если из того, что пара <x, y> и пара <y, x> следует, что x = y. Отношение на множестве X антисимметрично, если x, yX из того, что пара <x, y> следует, что пара <y, x>.

У антисимметричного конечного отношения в его матрице её элементы, симметричные относительно главной диагонали, могут быть или оба равными нулю, или один равен единице, а другой нулю, но оба одновременно не могут быть равными единице. Для понятия симметричности конечного отношения данные на главной диагонали его матрицы отношения не важны. Отношения «быть меньше» и «быть больше или равно» являются антисимметричными.

Не симметричное и не антисимметричное отношения называется асимметричным. В матрице конечного асимметричного отношения есть по крайней мере два элемента, симметричных относительно главной диагонали и равных единице, и по крайней мере два элемента, симметричных относительно главной диагонали, один из которых равен единице, а второй – нулю.

Отношение на множестве X транзитивно, если x, y, zX из того, что пара <x, y> и пара <y, z> следует, что и пара <x, z> (транзит через y). Отношения «быть равным по модулю n», «быть меньше», «быть больше», «быть больше или равно» - транзитивны. Если у элементов x и y одинаковые остатки при целочисленном делении на n, и у элементов z и y тоже одинаковые остатки при целочисленном делении на n, то и у элементов x и z одинаковые остатки при целочисленном делении на целое число n. Если x<y и y<z, то x<z.

Не транзитивным является отношение на целых числах «не равно». Если x y и y z, то из этого не следует, что x обязательно не равен z (x может и совпасть с z). Для доказательства не транзитивности отношения достаточно найти хотя бы две бинарных пары <x, y> и <y, z> из отношения такие, что пара <x, z> не входит в это отношение. Для отношения «не равно» это, например, пары <1,3> и <3,1> и пара <1,1> не входит в отношение «не равно». Для транзитивности отношения надо доказать, что для всех пар <x, y> и <y, z> из отношения и пара <x, z> входит в это отношение.

Для проверки транзитивности конечного бинарного отношения надо возвести матрицу отношения в квадрат и провести операцию sign (знак) над этим квадратом. Операция sign на целых не отрицательных числах возвращает в качестве результата 1 для положительных чисел и ноль для нуля. Если у полученной после операции sign матрицы не будет единиц там, где они есть у матрицы самого отношения, то это отношение транзитивно. Например, матрица и sign квадрата этой матрицы для отношения «не равно» на множестве {1, 2, 3, 4}:

Здесь у матрицы знака квадрата на главной диагонали имеются 1, тогда как у самой матрицы отношения нулевая главная диагональ. Это значит, что отношение «не равно» не транзитивно. Матрица и sign квадрата этой матрицы для отношения «быть меньше» на множестве {1, 2, 3, 4}:

Здесь у матрицы знака квадрата нет 1 там, где у самой матрицы отношения 0. Это значит, что отношение «быть меньше» транзитивно. Матрица знака квадрата отношения «быть меньше» соответствует отношению «быть меньше как минимум на 2».

Рефлексивное, симметричное и транзитивное отношение на множестве X называется отношением эквивалентности на множестве X. Примером эквивалентности на целых числах является отношение «быть равным по модулю n», оно иначе называется сравнением по модулю n. Оно рефлексивно, так как число само с собой имеет одинаковый остаток при целочисленном делении на n. Симметричность сравнения по модулю следует из того, что если x имеет одинаковый остаток с y, то и y имеет одинаковый остаток с x. Аналогично доказывается и транзитивность.

Если имеется эквивалентность, то [x] – это класс эквивалентности, где x – это элемент множества, на котором определена эквивалентность (множества – носителя эквивалентности). [x] ={y: yX и <x, y>эквивалентности}. Класс эквивалентности пустым никогда не бывает, так как по рефлексивности отношения эквивалентности сам элемент x принадлежит своему классу эквивалентности.

У эквивалентности на целых числах «совпадать по чётности» - два класса эквивалентности – чётные (C) и нечётные числа (C). В общем случае, у отношения на натуральных числах «быть равным по модулю n» при n > 1 имеется n классов эквивалентности: C, C, …, C. В C все числа имеют остаток 0, в C все числа имеют остаток 1, … , в C все числа имеют остаток n – 1.

Здесь каждый из n классов эквивалентности (классов вычетов по модулю n) содержит бесконечное число элементов, хотя самих классов n. Например, при n = 3 C ={0, 3, 6, …}, C= {1, 4, 7, …} и C={2, 5, 8, …}.

Единичное отношение (единичная функция) – тоже эквивалентность. Оно рефлексивно по самому определению единичного отношения. Оно симметрично и антисимметрично одновременно, так как не содержит пар<x, y>, таких что, x не равно y, а только такие пары и влияют на симметричность отношения. Оно транзитивно, так как если пары <x, y> и <y, z> принадлежат единичному отношению, то x = y и y = z, отсюда x = z и пара <x, z> принадлежит единичному отношению. У единичного отношения мощности n имеется ровно n классов эквивалентности, каждый из которых содержит по одному элементу: [x] = {x}.

У отношения на множестве {1 2, 3, 4}, содержащего пары <x, y> такие что x+y<10 ровно один класс эквивалентности ({1 2, 3, 4}), так как любые x<5 и y<5 в сумме дадут не более 8.

Теорема: класс эквивалентности порождается любым своим элементом. Доказательство: возьмём любой элемент y из [x], и любой z из [y]. Докажем, что и z принадлежит [x]. Если пары <x, y> и <y, z> принадлежат эквивалентности, то по транзитивности и пара <x, z> тоже принадлежит эквивалентности. Отсюда элемент z принадлежит [x]. Доказали, что [y] подмножество [x]. Аналогично докажем, что и [x] подмножество [y]. Значит [x] = [y]. Теорема доказана.

Разбиение множества X – это совокупность не пересекающихся подмножеств таких, что их объединение равно X, и каждый элемент x из множества X принадлежит к одному и только одному подмножеству этого разбиения.

Теорема: Всякое разбиение множества X определяет на нём отношение эквивалентности : <x, y> принадлежит тогда и только тогда, когда x и y находятся в одном подмножестве этого разбиения. Доказательство: рефлексивность и симметричность очевидны. Для доказательства транзитивности берём пары <x, y> и <y, z> из . По определению элементы x и y находятся в одном подмножестве разбиения X, и элементы y и z находятся в одном подмножестве. Так как по определению разбиения элемент y не может находиться одновременно в двух подмножествах разбиения, то элементы x и z находятся в одном подмножестве разбиения (где и элемент y). По определению пара <x, z> принадлежит . Теорема доказана.

Теорема: всякое отношение эквивалентности определяет на множестве – носителе эквивалентности разбиения на подмножества. Доказательство: этими подмножествами являются классы эквивалентности. Так как каждый элемент x принадлежит [x], то каждый элемент входит в подмножество. Так как класс эквивалентности порождается любым своим элементом, получаем, что классы эквивалентности либо совпадают, либо не пересекаются. Теорема доказана.

Антисимметричное и транзитивное отношение на множестве X называется отношением порядка на X. Если эквивалентность одна, то порядков – четыре. Порядок может быть строгим (антирефлексивным) и не строгим (рефлексивным). Если x, yX либо <x, y>, либо <y, x> (все элементы множества X сравнимы), то порядок будет полным, а если нет – то частичным.

Примером порядка являются служебные отношения. Существуют начальники и подчинённые, и всё это можно описать отношением порядка.

Рассмотрены все транзитивные бинарные отношения, так как не пустого транзитивного, симметричного и антирефлексивного отношения не существует. Если отношение не пусто, то существует по крайней мере одна пара <x, y> из него. Если x = y, то отношение не антирефлексивно. Если x не равно y, то по симметричности и пара <y, x> принадлежит отношению, но тогда по транзитивности и пары <x, x> и <y, y> тоже принадлежат отношению. Следовательно, отношение не антирефлесивно.

Можно рассмотреть и четыре не транзитивных отношения: рефлексивное, симметричное или антисимметричное; или антирефлексивное, симметричное или антисимметричное. Отношения эквивалентности и порядка наиболее часто используются по сравнению с другими отношениями.

Примером полного строгого (линейного) порядка является отношение « быть меньше» на целых числах, а примером полного не строгого порядка является отношение «быть меньше и равно» на целых числах.

Примером строгого частичного порядка на множестве - степени является отношение включения подмножеств друг в друга без совпадения подмножеств (), а примером не строгого частичного порядка является отношение включения подмножеств друг в друга с возможным совпадением подмножеств ().

Два подмножества x и y одного и того же множества X могут быть такими, что ни x не является подмножеством y (x y), ни yx. Например, X={1, 2, 3, 4}, а два его подмножества x={1,2} и y={3,4}. Тогда ни x y, ни yx. Таблица примеров различных порядков:

порядки	полные	частичные
не строгие
строгие	<

Множество с заданным на нём частичным порядком называется частично упорядоченным. Например, множество – степень частично упорядочено по отношению включения его подмножеств друг в друга.

Если на множестве X существует порядок , то на множестве X*X можно определить отношение частичного порядка П (отношение Парето): <<a, b>,<c, d>>П тогда и только тогда, когда <a, c> и <b, d>. Например, на множестве X={1, 2, 3} возьмём отношение «быть меньше». Тогда отношение Парето на X*X состоит из семи пар: П={<<1,1>,<2,2>>, <<1,1>,<3,3>>, <<1,1>,<2,3>>, <<1,1>,<3,2>>, <<2,2>,<3,3>>, <<2,1>,<3,3>>, <<1,2>,<3,3>>}. Остальные пары состоят из не сравнимых элементов. Например, элементы X*X <1,2> и <2,1> не сравнимы, так как 1<2, но 2 не меньше 1. Отношение Парето – это упорядоченные двойки пар чисел.

Конечный порядок можно изобразить диаграммой Хассе. В диаграмме Хассе выше любого элемента x находятся все такие элементы y, что пара <x, y> принадлежит порядку. Диаграммой Хассе линейного порядка является линия, поэтому этот порядок и называется линейным. Например, линейный порядок «быть меньше» на множестве {2, 3, 4} изображается так:

Диаграмма Хассе для приведённого выше отношения Парето имеет вид:

Мощность линейно упорядоченного множества – ординальное (порядковое) число.

Алгебраические структуры

Глава 4. Алгебраические операции. Алгебры, решётки

На множестве M определена бинарная алгебраическая операция (далее операция), если каждой упорядоченной паре элементов множества ставится в соответствие вполне определённый элемент этого же множества M. Примерами операций являются операции сложения и умножения на множестве целых чисел. Деление не является операцией на множестве целых чисел, так как результат деления одного целого числа на другое может и не быть целым. Деление будет операцией на множестве действительных чисел, или на множестве рациональных чисел.

Для конечного множества операцию можно задать квадратной таблицей Кэли, в которой на пересечении строк и столбов, соответствующих элементам множества, находятся соответствующие им результаты операции. Рассмотрим множество целых чисел от нуля до трёх включительно. На этом множестве определим операцию сложения по модулю четыре: два числа складываются, эта сумма целочисленно делится на четыре и в качестве результата операции берётся остаток от целочисленного деления. Таким образом, результат сложения по модулю 4 на множестве {0, 1, 2, 3} тоже принадлежит этому множеству. Таблицы Кэли для этой операции:

В этой таблице операнды и операция взяты в кавычки, а результат операции – нет. На этом множестве можно и умножать по модулю четыре. Таблица Кэли для умножения по модулю четыре на множестве {0, 1, 2, 3}:

Операция может быть любой, например – наложение поворотов (“o”) на плоскости. На множестве из четырёх поворотов на 0, 90, 180 и 270 градусов определена операция наложения поворотов, причём 360 градусов – это 0 градусов. Таблица Кэли для этой операции:

При использовании мультипликативной терминологии операция называется умножением, а результат операции – произведением. При использовании аддитивной терминологии (как в двух примерах для множества {0, 1, 2, 3}) – сложением и суммой соответственно.

Операция коммутативна, если a, b M a*b=b*a (мультипликативная терминология). Для коммутативных операций на конечных множествах таблица Кэли симметрична, как в двух примерах для множества {0, 1, 2, 3}. Умножение и сложение на действительных числах коммутативны, а вот деление – нет.

Операция ассоциативна, если a, b, c M a*(b*c)=(a*b)*c (мультипликативная терминология). Умножение и сложение на действительных числах ассоциативны, а вот деление – нет, так как в общем случае a/(b/c)=(a*c)/b(a/b)/c=a/(b*c).

Множество M, на котором определена операция, обладает единичным элементом e (операционная единица), если a M a*e=e*a=a. При аддитивной записи единичный элемент называется операционным нулём. На множестве {0, 1, 2, 3} операционным нулём по операции сложения является 0, а операционной единицей по операции умножения - 1. На множестве из четырёх поворотов на 0, 90, 180 и 270 градусов операционным нулём по операции наложения поворотов является 0 градусов.