Декартово произведение множеств.

Национальная горная академия Украины

Кафедра управления в технических системах

К О Н С П Е К Т

Лекций по дисциплине

«Основы дискретной математики»

 

Для студентов специальностей

И 7.080203

 

 

Днепропетровск

 

Содержание

Стр.

Введение.....................................

Раздел 1. Основы теории множеств...............

1.1. Основные определения...................

1.2. Операции с множествами................

Декартово произведение множеств...........

Отношения.........................

Свойства отношений...................

Соответствие, отображения и функции........

Раздел 2. Основы теории графов..................

Основные положения....................

Неориентированные графы..................

Изоморфизм графов......................

Отношение порядка и отношение эквивалентности

На графе............................

Характеристики графов...................

Эйлеровы графы и гамильтоновы циклы..........

2.7. Расчет сетевого графика..................

Оптимизация на сетях...................

 

 

Введение

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

Выход из этой ситуации заключается в переходе к дискретным представлениям измеряемых параметров, что позволяет выполнять измерения только в некоторые фиксированные моменты времени. Это неизбежно снижает точность представления объекта исследования и одновременно упрощает его модель. Правомерность перехода к дискретным представлениям должна быть тщательно обоснована. Именно такое обоснование дает дискретная математика.

Основные объекты дискретной математики – множества, графы, логические функции и автоматы, формальные системы, алгебры и комбинаторика.

Раздел, посвященный множествам, служит основой для остальных разделов дискретной математики. Рассматриваются основные операции с множествами, понятие декартова произведения, отношения и их свойства, а также соответствия отображения и функции. Большинство понятий, излагаемых в разделе о графах, имеют самостоятельное теоретическое и прикладное значение. Графы, благодаря своей наглядности и универсальности стали одним из наиболее распространенных языков для задач управления. Именно исследования по теории графов привели к понятию объективно сложных задач, т.е. таких задач, сложность которых не устраняется никаким увеличением мощности вычислительных систем.

Логика и автоматы являются традиционными разделами курса дискретной математики. Рассматриваются основные законы математической логики и методики работы с логическими выражениями. Основы теории автоматов представлены для класса конечных автоматов. Подробно рассмотрены вопросы синтеза и минимизации автоматов. Алгебры и формальные системы являются центральным разделом курса дискретной математики. Знание принципов организации формальных систем, связанных с вычислениями, становится важным элементом математической культуры любого исследователя, имеющего отношение к алгоритмизации процессов управления. По существу оно дает понимание того, что можно и чего нельзя сделать с помощью вычислительных машин. Элементы комбинаторики представлены как необходимый элемент систем управления, связанных с генерированием вариантов принятия решений.

 

 

Раздел 1. Основы теории множеств.

 

Основные определения

 

Множество – это некоторый набор объектов, называемых элементами. Оно обозначается следующим образом

А={a₁,a₂,…,a_n},

где А – множество, a₁, a₂,…, a_n - его элементы. Например, множество А может состоять из натуральных чисел 1, 2,…,6 при этом его элементами будут a₁=1, a₂=2, …, a₆=6.

Любой набор, каждый элемент которого принадлежит множеству А, является его подмножеством, так В={1, 2, 3} – подмножество А={1, 2, 3, 4, 5, 6} обозначается ВÌА. Любое множество по этому определению является собственным подмножеством.

Все рассматриваемые в дискретной математике множества содержат элементы, принадлежащие наибольшему множеству S, называемому пространством элементов. Следовательно, все рассматриваемые множества являются подмножествами S.

Пример. Пусть S={1, 2, …, 6}. Рассмотрим формирование подмножеств множества S. С учетом пустого подмножества Æ в рассматриваемом множестве S может быть выделено в общей сложности 2⁶=64 подмножества:

Æ, {1}, …, {6}, {1, 2},……,{1,2,6},…, S.

В общем случае если множество S содержит n элементов, в нем можно выделить 2ⁿ подмножеств.

Одной из причин применения теории множеств в дискретной математике является то, что для множеств определены важные преобразования, которые имеют простое геометрическое представление. Это представление носит название диаграммы Эйлера-Венна и в ней пространство S изображается в виде квадрата, а различные множества в виде плоских фигур, ограниченных замкнутыми линиями. Использование таких диаграмм рассмотрим на примере описания подмножеств

С Ì В Ì А

S

А

С

В

 

 

Обычно каждое натуральное число воспринимается как то общее, что присуще любой совокупности М, состоящей из m предметов; об этом делают запись вида m = |М|. Если все m предметов из совокупности М попарно различны, то совокупность эту именуют множеством, а также m- элементным множеством, при этом число m называют кардинальным числом, а также мощностью множества М.

Если |М| = 0, то говорят, что М - пустое множество, и пишут М = Æ. Если среди предметов, входящих в совокупность М, имеются одинаковые, то такую совокупность называют мультимножеством.

Говоря о множестве М, подразумевают, что М состоит из элементов. Множество, состоящие из конечного числа элементов, т.е. имеющие конечную мощность называют конечным. Множество, не являющееся конечным, называют бесконечным. Если x есть элемент множества М, то этот факт записывают в виде x М и говорят «принадлежит М». Запись означает, что рассматривается множество, состоящее из элементов, обладающим свойством Р, а запись М₁ =íx ÎМ: P(x) ý и аналогичная запись М₁ = íx Î М | P(x)ý означают, что рассматривается часть множества М, причем x Î М₁ Û (x Î М & Р(x)). (Обозначения: АÞВ - из утверждения А следует утверждение В; АÛВ - из А следует В и наоборот).

Возможно, что М₁ = 0, либо М₁ = М. В любом случае о множестве М₁ говорят, что оно суть подмножествомножества М, и пишут М₁ Í М. Если М₁ Í М и М Í М₁, то пишут М₁ = М и называют М₁ и М равными множествами. Если М₁ Í М, но М₁ ¹ М, то пишут М₁ Ì М, т.е. М₁ строго включено в М. Если же просто М₁ Í М, то говорят о включении М₁ в М.

Пусть А Í R. Тогда в дальнейшем А⁺ = í x Î А: x > 0 ý, так что R⁺ = í x Î R: x > 0ý, Z⁺ = íx Î Z: x > 0ý = í1,2,...,ý = N⁺.

Если хотя бы одним способом можно пронумеровать (пересчитать) с помощью всех натуральных чисел n Î N все элементы бесконечного множества М, то говорят, что М имеет счетную мощность или является счетным множеством, и пишут |М| = |N|. Вместо |N| пишут иногда одну букву a (готическое а). Например, множество Z счетно, ибо это легко усматривается в следующей записи чисел друг под другом:

Z = í...,-3,-2,-1,0,1,2,3,...ý,

N = í...,6,4,2,0,1,3,5,...ý.

В общем случае если между элементами множеств X и Y можно установить взаимно однозначное соответствие (т.е. каждому элементу x Î X поставить в соответствие один и только один элемент y Î Y, но так, чтобы при этом каждому y Î Y также будет поставлен в соответствие некоторый элемент x Î X), то говорят, что множества X и Y имеют одно и то же кардинальное число, или имеют одинаковую мощность, или равномощны, и пишут |X| = |Y|. Запись |X| < |Y| означает, что |X| ¹ |Y|, но для некоторого подмножества Y₁ Ì Y выполнятся |X| = =|Y₁|. Например, множество Q имеет счетную мощность, а множество R имеет более высокую мощность (континуальную мощность c), так что а = |N| = |Q| < |R| = c, где c - готическое С. Итак, 0,1,2,... - все конечные кардинальные числа, а, с - два бесконечных кардинальных числа; отметим, что бесконечных кардинальных чисел существует сколь угодно много.

 

Операции с множествами

Равенство множеств. Множества А и В равны тогда и только тогда, когда каждый элемент множества А является элементом множества В, и наоборот, каждый элемент множества В является элементом множества А, т. е.

А Ì В и В Ì А

Объединение множеств. Объединением или суммой двух множеств А и В называется множество, состоящее из всех элементов, каждый из которых принадлежит хотя бы одному из данных множеств.

Выполняются законы:

S 1)Ассоциативный.

(АÈВ)ÈС=АÈ(ВÈС)=АÈВÈС.

А В 2) Коммутативный.

АÈВ=ВÈА; АÈА=А;

АÈÆ=А;

АÈS=S; АÈВ=А если В Ì А.

 

Пересечение множеств. Пересечением или произведением двух множеств называется множество, состоящие, из всех тех элементов, которые принадлежат обеим множествам.

 

S Справедлив коммутативный и

ассоциативный закон в частности:

А АÇ(ВÈС)=(АÇВ)È(АÇС).

В

 

Два множества А и В являются взаимоисключающими, или несовместимыми, если АÇВ=Æ.

Дополнение множеств. Дополнение множества А называется множество, в котором содержатся все элементы пространства S^’, кроме принадлежащих множеству А. Оно обозначается через `А.

Справедливыми будут следующие

выражения

=

`А А `Æ=S; `S=Æ; (A)=A; AÈ`A=S;

AÇ`A=Æ;

`AÌ`B при ВÌА;

`A=`B если А=В.

 

Кроме того, справедливы законы де Моргана:

(АÈВ)=`А Ç`В; (АÇВ)=`А È`В.

 

Разность множеств. Разность А-В множеств А и В есть множество, состоящие из элементов множества А, не принадлежащих множеству В.

A - B=A \ B=A Ç`B=A - (AÇB).

A S (читаем “A без B”)

А-В

В

 

В-А

 

Из последней диаграммы выведены следующие соотношения:

А - Æ = А, А - S = Æ, S - A =`A.

Выражения, где присутствует разность, необходимо записывать со скобками.

Описанные выше операции со множествами проиллюстрируем примером. Предположим, что элементами пространства S – натуральные числа от 1 до 6. S={1, 2, 3, 4, 5, 6} и определим следующие подмножества:

А={2, 4, 6}; B={1, 2, 3, 4}; C={1, 3, 5}.

Учитывая приведенные соотношения можно записать:

(АÈВ)={1, 2, 3, 4, 6}, (BÈC)={1, 2, 3, 4, 5}

(AÈBÈC)={1, 2, 3, 4, 5, 6}=S=AÇC,

AÇB={2, 4}, BÇC={1, 3}, AÇC=Æ,

AÇBÇC=Æ,`A={1, 3, 5}=C, `B={5, 6},

`C={2, 4, 6}=A, A-B={6}, B-A={1, 3},

A-C={2, 4, 6}=A, C-A={1, 2, 5}=C,

B-C={2, 4}, C-B={5}.

 

Разбиение множеств

Понятие разбиения множества. Пусть А - множество учеников некой школы. Обозначим А₁ множество учеников первого класса, А₂ -множество учеников второго класса и т. д., А₁₀-множество учеников десятого класса этой школы. Ясно, что А₁А_2¼А₁₀- подмножество множества А, причем каждое из них не пусто (в каждом классе, конечно, есть ученики), они попарно не имеют общих элементов (не может же один и тот же человек учиться одновременно в двух разных классах) и объединение всех равно А.

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

Таким образом, в примере рассмотренном выше, совокупность подмножеств А₁,А₂¼А₁₀ образует разбиение множества А.

Если, например, А={1, 2, 3, 4, 5, 6}, то совокупность подмножеств {1, 3}, {2, 4, 6}, {5} множества А образует его разбиение, а его совокупность таких подмножеств {1,2,3},{4,5},{3,6} разбиения не образует, ибо два из них имеют общий элемент.

Итак, выражаясь образно, под разбиением множества мы будем понимать "разбиение" его на части, подмножества. Ясно,что одно и тоже множество "разбить" на части можно по-разному. Так, например, если В={a, b, c, d, e, f},то совокупности его подмножеств {a, b, c},{d, e, f, g},и{a, b},{c, d},{e, f, g}образуют его разбиения, но различные т.е. В " разбито" на подмножества по-разному.

Разбиения будем обозначать строчными буквами греческого алфавита:r,s,d и т.д.

Классы разбиения. Пусть М-множество и r-некоторое его разбиение. Каждое из подмножеств совокупности, образующей разбиениеr, называется классом разбиения.

Так, например, если В={a, b, c, d, e, f, g} и r-разбиение множества В, образованное совокупностью его подмножеств {a, b}, {e, d, f}, {c}, {g},то каждое из этих подмножеств является классом данного разбиения r.

Если теперь изобразить множество с помощью диаграммы Эйлера-Венна, то его разбиение можно представить наглядно, в виде разорванного на части круга. Каждая такая часть и является классом данного разбиения.

 

В одном и том же классе разбиения r множества М может содержаться несколько (и даже бесконечно много) элементов из М. Если элементы x, yÎМ принадлежат одному и тому же классу данного разбиения r, то этот факт мы будем обозначать следующим образом: x~y(r). Например, для рассмотренного выше разбиения s множества В можно записать a~b(s), d~e(s),¼, а запись c~d(s) неверна, ибо c и dпринадлежат различным классам разбиения s. Так как, элементы a и а, конечно, лежат в одном и том же классе разбиения, ибо это один и тот же элемент, то можно записать a~a(s). Аналогично b~b(s),c~c(s) и т. д.

Пусть далее для разбиения r множества М и некоторых x, y, zÎМ

имеет место x~y(r) и y~z(r). Запись x~y(r) означает, что элементы x и y принадлежат одному и тому же классу нашего разбиения. Аналогично y и z содержаться в одном и том же классе. Если теперь предположить, что x и z лежат в различных классах разбиения r, то получим, что эти классы имеют общий элемент y, а это невозможно. Значит, x~z(r).

Таким образом, мы доказали, что если x~y(r)и y~z(r), то x~z(r).

Каждый класс данного разбиения r множества М, по определению, не пуст, т.е. в каждом классе содержатся элементы из М.

Например, для разбиения и s множества В, рассмотренных выше, класс разбиения {a, b} можно обозначить `a, ибо он содержит элемент a. Но этот же класс содержит и элемент b, значит, его можно обозначить `b. Таким образом, {a, b}=`a=`b. Аналогично {e, d, f}=`e=`d=`f.

У нас получилось, что один и тот же класс разбиения обозначается по-разному. Это не должно вас удивить. И в математике, и в жизни вы не раз встречались с такой ситуацией. Например, дроби 1/2, 2/4, 3/6,¼-это одно и то же число, обозначаемое по-разному.

Вернемся теперь к общему случаю разбиения r множества М. Если некоторый класс разбиения содержит элементы x и y множества М, то, с одной стороны, он обозначается `x, а с другой- `y, т. е. `x=`y. Таким образом, мы доказали, что из x~y(r) следует `x=`y.

Пусть теперь, наоборот, `x =`y. Но `x - это класс, содержащий элемент y, и эти классы равны, т. е. это один и тот же класс. Значит, x и y содержатся в одном и том же классе разбиения, т. е. x~y(r).

Из приведенных выше рассуждений мы можем сделать следующий вывод:`x =`y тогда и только тогда, когда x~y(r).

Фактор множества. Рассмотрим построенное выше разбиение s множества В. Подмножества {a,b},{e,d,f},{c},{g} являются классами этого разбиения. Согласно нашей договоренности, их можно обозначить, например, `a,`e,`c, `g соответственно. Таким образом, с разбиением s связана совокупность его классов разбиения, т. е. множество {`a,`e, `c,`g}.

И в общем случае, если r-некоторое разбиение произвольного множества М, то с этим разбиением связана совокупность его классов.

Совокупность всех классов данного разбиения r множества М называется фактор- множеством множества М по разбиению r и обозначается М/r.

Таким образом, элементами множества М/r являются классы данного разбиения rи других элементов в нем нет.

Если мы вернемся к разбиению r множества М, изображенному на рис. 10, то множество М/r состоит из кусков (рис. 1.8), на которые мы разрезали круг, изображающий множество М. Далее, для нашего разбиения s множество В имеем В/s = {`a, `e, `c, `g}. Конечно же, элементы множества В/s можно обозначить и по-другому, и тогда, например, В/s={b, f, c, g}.

 

М/r =,,,,

 

Пусть теперь d - разбиение множества В, классами которого являются подмножества {a, b, c, d}, {e, f, g}.Тогда В/d={a, `e}.Обращаем ваше внимание на то, что `a в В/d и `a в В/d - это разные элементы, Например, кинотеатр "Мир" в Минске и кинотеатр "Мир" в Москве - это разные кинотеатры, и хотя они называются одинаково, это не вызывает недоразумений. Не будет их и в нашем случае с разбиениями, так как всегда ясно о каком разбиении идет речь.

Заметим. Что М/r - это совокупность лишь некоторых (не всех) подмножеств множества М, а 2^М-совокупность всех их. Значит, М/rÌ2^М, более того, М/r - собственное подмножество множества 2^М.

Ясно, что если множество М конечно, то и всякое его фактор -множество в зависимости от разбиения может быть как конечным, так и бесконечным. Вы без труда приведете соответствующие параметры.

 

Декартово произведение множеств.

Рассмотрим некоторые дополнительные термины, характерные для операций над множествами.

Вектор – это упорядоченный набор элементов, другой синоним этого термина – “кортеж”.

Элементы, образующие вектор, называются координатами или компонентами вектора. Координаты нумеруются слева направо. Число координат называется длинной или размерностью вектора. Вектор будем заключать в круглые скобки, например (0, 5, 4, 5) иногда скобки и даже запятые опускаются.

Векторы длинны 2 часто называются упорядоченными парами.

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны иначе говорят, векторы (а₁, …..,а_m) и (b₁,…..,b_n) равны, если m=n и a₁=b₁, a₂=b₂,……., a_m=b_m.

Прямым (декартовым) произведением множеств А и В (обозначают А х В) называется множество всех пар (а, в), таких что аÎА и вÎВ. В частности, если А=В, то обе координаты принадлежат А. Такое произведение обозначается А². Аналогично прямым произведением множеств А₁, ….,А_n (обозначение А₁ х ….х А_n) называется множество всех векторов (а₁, …,а_n) длины n, таких, что а₁ÎА₁….а_nÎА_n.А х А х…х А обозначается Аⁿ.

Пример 1. Множество R x R=R² – это множество точек плоскости, точнее пар (а, в), где а, вÎR и являются координатами точек плоскости.

Пример 2. А={а, в, c, d, e, f, g, h}, B={1, 2,….,8}тогда А х В ={a₁, a₂, a₃, …,h₇, h₈} – множество, содержащие обозначения всех 64 клеток шахматной доски.

Пример 3. Рассмотрим множество числовых матриц 3 х 4, т. е. матриц вида

а₁₁ а₁₂ а₁₃ а₁₄

а₂₁ а₂₂ а₂₃ а₂₄

а₃₁ а₃₂ а₃₃ а₃₄ ,

где а_ij принадлежит множеству R действительных чисел. Строки матрицы – это элементы множества R⁴ (векторы длинны 4). Сама матрица, рассматриваемая как упорядоченный набор (т. е. вектор) строк – это элемент множества (R⁴)³=R⁴ x R⁴ x R⁴. Компоненты матрицы, заданной таким образом – строки, а не числа. Поэтому (R⁴)³¹R¹². Содержательный смысл этого неравенства в том что в векторе R¹² не содержится никакой информации о строении матрицы, тот же вектор мог бы перечислять элементы 4 х 3 или 2 х 6, которые как математические объекты не совпадают с матрицами 3 х 4.

 

Отношения

Подмножество RÍ Mⁿ называется n- местным отношением на множество М. Говорят, что а₁, …., а_n находится в отношении R, если (а₁,…..,а_n)ÎR. Одноместное отношение это просто подмножество М. Такие отношения называют признаками: а обладает признаком R, если аÎR и RÍМ. Свойства одноместных отношений это свойства подмножеств М; поэтому для случая n=1 термин отношение употребляется редко. Примером трехместного отношения является множество троек нападающих в хоккейной команде. Каждый из нападающих находится в этом отношении со всеми теми игроками, с которыми он играет в тройке.

Наиболее часто встречаются и лучше всего изучены двухмерные или бинарные отношения. Записывают, что если а и в находятся в бинарном отношении R ® а R в.

Пример. Отношение на N (где N – множество положительных чисел):

1) отношение £ выполняется для пар (7, 9) и (7, 7), но не выполняется для пар (9, 7).

2) отношение “иметь общий делитель, отличный от единицы” выполняется для пар (6, 9), (4, 2), (2, 4), (4, 4), но не выполняется для пар (7, 9) и (9, 7).

3) Отношение “быть делителем” а R в - а- делитель- в – выполняется для пар (2, 4) и (4, 4), но не выполняется для пар (4, 2) и(7, 9).

Пример. Отношения на множестве точек действительной плоскости:

1) отношение “находиться на одинаковом расстоянии от начала координат” выполняется для пар точек находящихся на одной и той же окружности с центром в начале координат.

2) отношение “находиться на разном расстоянии от начала координат” выполняется для тех и только тех пар точек, для которых не выполняется предыдущее отношение.

3) отношение “быть симметричным относительно оси Х” выполняется для всех пар точек (х₁y₁) и (x₂y₂), удовлетворяющих условию х₁ = х₂ и y₁ = -y₂.

Пример. Отношения на множестве людей “жить в одном городе”, “быть моложе”, “быть сыном”, “быть знаменитым”.

Пусть дано отношение R и М. Для любого подмножества М₁ Í М естественно определяется отношение R^’, называемое сужением R на М₁, которое получается из R удалением всех пар, содержащих элементы, не принадлежащие множеству М₁. Другими словами, R’=R Ç M₁². Строго говоря, R и R’ - это разные отношения с разными областями определения. Однако, если не возникает разночтений этот педантизм не соблюдается; например, вполне можно говорить “быть делителем” не уточняя, задано оно на N или каком-либо его подмножестве.

Для задания бинарных отношений можно использовать любые способы, задания множеств, например, список пар, для которых данное отношение выполняется. Отношение на конечных множествах обычно задаются списком или матрицей. Матрица, задающая бинарные отношения на множестве M={a₁, ….,a_m} – это квадратная матрица с порядком m, в которой элемент c_ij, стоящий на пересечении i-й строки и j-го столбца определяется следующим образом:

 

i j

ì 1, если a_i R a_j;

c_ij = í

î 0 – в противном случае.

Например, для конечного множества {1, 2, …,6} матрицы отношений £, “имеет общий делитель”, “быть делителем” имеют вид:

 

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1

2 0 1 1 1 1 1 2 0 1 0 1 0 1 2 0 1 0 1 0 1

3 0 0 1 1 1 1 3 0 0 1 0 0 1 3 0 0 1 0 0 1

4 0 0 0 1 1 1 4 0 1 0 1 0 1 4 0 0 0 1 0 0

5 0 0 0 0 1 1 5 0 0 0 0 1 0 5 0 0 0 0 1 0

6 0 0 0 0 0 1 6 0 1 1 1 0 1 6 0 0 0 0 0 1

 

 

Для любого множества М отношение Е, заданное матрицей, в которой по главной диагонали стоят единицы, а в остальных местах – нули, называется отношением равенства на М.

Поскольку отношение на М задаются подмножествами М², для них можно определить те же операции, что и над множествами.

Определим еще одну операцию над отношениями. Отношение является обратным к R (обозначается R^-1), если a_i R^-1 a_j тогда и только тогда когда a_j R a_i. Так например, для отношения £ обратным является ³.

 

Свойства отношений

Отношение R называется рефлексивным, если для любого аÎМ имеет место аRа. Главная диагональ его матрицы содержит только единицы. Отношение R называется антирефлексивным, если ни для одного из аÎМ не выполняется аRа. Главная диагональ его матрицы содержит только нули.

Так например, отношения £ и “имеет общий делитель” - рефлексивны, отношения < и “быть сыном” – антирефлексивны.

Отношение R называется симметричным, если для пар (а, в)ÎМ² из аRв следует вRа. (Иначе говоря, для любой пары R выполняется либо в обе стороны либо не выполняется вообще матрица симметричного отношения, симметрична относительно главной диагонали: a_ij = a_ji.

Пример. – Быть симметричным относительно оси Х.

Отношение R называется антисимметричным, если из a_iRa_j и a_jRa_i следует, что a_i=a_j. Отношение ”быть симметричным: если первая точка симметрична второй, то и вторая симметрична первой.

Пример антисимметричного отношения – отношение £: действительно, если а £ в и в£ а, то а=в. Нетрудно убедится в том, что отношение R симметрично тогда и только тогда, когда R=R^-1.

Отношение R называется транзитивным, если для любых а, в, с из аRв и вRс следует аRс. Отношения “равенство”, £, “жить в одном городе” транзитивны; отношение “быть сыном” не транзитивно.

Для любого отношения R отношение называемое транзитивным замыкани ем R, определяется следующим образом: а в, если, в М существует цепочка из n элементов а=а₁, а₂, …, а_n-1, а_n=в, в которой между соседними элементами выполнено R: а₁Rа₂, а₂Rа₃, ……, а_n1Rв. Если R транзитивно, то = R. Действительно, если аRв, то а в (цепочка состоит из двух элементов а, в), поэтому RÍ . Если же а в, то существует цепочка а₁Rа₂, а₂Rа₃,…,а_n-1Rв. Но так как R транзитивно, то аRв, поэтому Í R. Из включения в обе стороны следует R= .

Транзитивным замыканием отношения “быть сыном” является отношение “быть прямым потомком”, являющееся объединением отношений “быть сыном”, “быть внуком”, “быть правнуком” и т. д

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

Пример 1. Отношение равенства Е на любом множестве является отношением эквивалентности. Равенство – это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из Е (т. е. любой единицы на диагонали матрицы Е) оно перестает быть рефлексивным, и, следовательно, уже не является эквивалентностью.

Пример 2. Рассмотрим множество треугольников на плоскости, считая, что треугольник задан, если заданы координаты его вершин. Два треугольника называются равными, если при наложении они совпадают, т. е. могут быть переведены друг в друга путем некоторого перемещения. Отношение равенства (конгруэнтности) является отношением эквивалентности на множестве D.

Пример 3. Отношение “иметь один и тот же остаток отделения на 7” является эквивалентностью на множестве целых положительных чисел N. Это отношение выполняется, например, для пар (11, 46), (14, 70) и не выполняется для пар (12, 13), (14, 71).

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

Пример 4. Отношение £ и ³ для чисел являются отношениями нестрогого порядка, отношения < и > - отношениями строгого порядка. Оба отношения полностью упорядочивают множества N и R.

Пример 5. На системе подмножеств множества М отношение включения Í задает нестрогий частичный порядок, а отношение строгого порядка включения Ì задает строгий порядок. Например

{1, 2}Ì{1, 2, 3}, a {1, 2} и {1, 3, 4} не сравнимы.

Пример 6. Отношения подчиненности на предприятии задает строгий частичный порядок. В нем несравнимыми будут сотрудники разных отделов.

Пример 7. Пусть в списке конечного алфавита А порядок букв зафиксирован, т. е. всегда один и тот же. Тогда этот список определяет полное упорядочение букв, которое назовем отношением предшествования и обозначим aiíaj (если ai предшествует aj в списке букв). На отношение предшествования букв строится отношение предшествования слов. Это отношение задает полное упорядочение множества всех конечных слов в алфавите А, которое называется лексикографическим упорядочением слов. Примером такого упорядочения является словарь.

Пример 8. Если рассматривать числа в позиционных системах счисления (напр. десятичной), как слова в алфавите цифр, то их лексикографическое упорядочение совпадает с обычным, если все сравнимые числа имеют одинаковое число разрядов.

20 < 1073;

20 1073;

0020 1073.

 

12Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: