Федоров В.Н. - Введение в теорию множеств, страница 8
Описание файла
Документ из архива "Федоров В.Н. - Введение в теорию множеств", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Федоров В.Н. - Введение в теорию множеств"
Текст 8 страницы из документа "Федоров В.Н. - Введение в теорию множеств"
Пусть заданы множества М1, М2, М3 и отношения 
и 
. Составное отношение действует из М1 в М2 посредством R1, а затем из М2 в М3 посредством R2, т.е. 
Rl○R2, если существует такое с
М2, что (а, с) R1 и (с, b) R2. На рис. 3.6 показаны множества М1, М2, М3, в них – области определений D(R1), D(R2) и области значений Q(R1) и Q(R2), заштрихованные в разных направлениях для R1 и R2. Сегменты с двойной штриховкой на М1, М2, М3 представляют собой D(R1○R2), 
и Q(R1○R2) соответственно.
Р
исунок 3.6
В частности, если отношение R определено на множестве М, R
М2, то составное отношение
R○R={(a,b):(a,c),(c,b) R}.
Например, если R – "быть сыном", то R○R – "быть внуком".
Обозначим R○R = R 2. Используя это обозначение, можно определить Rn для любого п N, п > 1 следующим образом:
Rn = {(a,b):(a,c), R и (с, b) Rn–1}.
7. Транзитивное замыкание R°.
Транзитивное замыкание R° состоит из таких и только таких пар элементов а, b из М, т.е. (a, b) R°, для которых в M существует цепочка из (k+2) элементов М, k
0: а, с1, с2,..., сk, b, между соседними элементами которой выполняется R: aRc1, c1Rc2,..., ckRb, т.е.:
R° = {(a, b): (a, c1), (c1 ,c2),..., (сk , b) R} (определение I).
Унарная операция транзитивного замыкания Ro может быть также определена как бесконечное объединение:
R° = 
(определение II).
Например, для отношения R – "быть сыном" составное отношение (композиция) R○R = R2 – "быть внуком", R○R○R = R3 –"быть правнуком" и т.д. Тогда объединение всех этих отношений есть транзитивное замыкание R° – "быть прямым потомком".
Если отношение R транзитивно, то R° = R. Например, транзитивное замыкание отношения R – "быть больше" совпадает с этим отношением, т.е. R° = R.
8. Рефлексивное замыкание R*.
Пусть тождественное отношение Е= {(а, а): а М}. Тогда
R* = R° 
E.
Если R транзитивно и рефлексивно, то R* = R.
Пример 1. Пусть отношение R – "быть руководителем", определенное на множестве сотрудников организации М. Назовите отношения: 
, R–1, R°, R*. Каковы свойства отношений?
-
![]()
=(M x M) \ R – "не быть руководителем".
R–1 = {(b, a): (a, b) R} – "быть подчиненным".
R° = R – "быть руководителем" (так как R – транзитивно).
R*=
– трудно назвать такое отношение, возможно – "быть руководителем, в том числе по отношению к самому себе".
Отношение R – "быть руководителем":
а) не является рефлексивным, так как выражение "быть руководителем по отношению к самому себе" вряд ли имеет смысл (с точки зрения должностных инструкций, должностной организационной структуры);
б) антирефлексивно, так как ни для какого члена организации А не выполняется "А – руководитель А";
в) не симметрично, так как если А – руководитель В, то В не является руководителем А (В– подчиненный для А);
г) антисимметрично, так как ни для каких членов организации А, В не выполняется одновременно "А – руководитель В" и "В – руководитель А" (считаем, что речь не идет о разных сферах деятельности внутри одной организации, например об участии А, В в разных проектах);
д) транзитивно, так как если А – руководитель В и В – руководитель С, то А– руководитель С.
Итак, отношение R – "быть руководителем" антирефлексивно, антисимметрично и транзитивно, т.е. является отношением строгого порядка на множестве М сотрудников организации. Очевидно, что R задает на множестве М частичный порядок, поскольку в любой организации существуют сотрудники (например, работники одного отдела), которые не являются руководителями по отношению к другим.
Отношение – "не быть руководителем":
а) рефлексивно, так как любой член организации А – не руководитель самому себе (по должностной структуре);
б) не антирефлексивно, поскольку неверно, что ни для какого А не выполняется: "А – не руководитель А";
в) не симметрично, ибо в организации существуют сотрудники, для которых не выполняется одновременно "А – не руководитель В" и "В – не руководитель А" (в случаях, когда, например, "А – руководитель В");
г) не антисимметрично, так как в организации существуют сотрудники А, В, никто из которых не является руководителем для другого: для них справедливо одновременно "А – не руководитель B" и "В – не руководитель А";
д) не транзитивно, так как если, например, А – руководитель для С, а сотрудник В работает в другом отделе, то имеет место: "А – не руководитель В", а "B – не руководитель С", но неверно, что"A – не руководитель С”. Очевидно, что отношение R не является ни эквивалентностью, ни порядком.
Рассуждая аналогично, нетрудно определить свойства отношений R–1, R°, R*. Результаты сведены в табл. 3.1.
Таблица 3.1
| Отношение | Рефлексивно | Антирефлексивно | Симметрично | Антисимметрично | Транзитивно |
| R | – | + | – | + | + |
| | + | – | – | – | – |
| R–1 | – | + | – | + | + |
| R° | – | + | – | + | + |
| R* | + | – | – | + | + |
Пример 2. Пусть на множестве М= {2, 4, 6} определено отношение R — "быть меньше". Задать характеристическим свойством и списком отношение R, обратное отношение R–1 и дополнение . Сравнить отношения. Определить их свойства.
-
R = {(а,b):а<b} – "быть меньше".
R ={(2,4), (2, 6), (4, 6)}.
R–1 = {(а, b): (b, a) R} = {(a, b): a>b} – "быть больше".
R–1 = {(4,2), (6, 2), (6,4)}.
= (
)\R= {(а, b): (а, b) 
R} = {(а, b): а b} – "быть не меньше".
= {(2, 2), (4,2), (4,4), (6, 2), (6, 4), (6, 6)}.
Между R, R–1 и имеют место соотношения:
• 
, где Е = {(a, b): a = b} – тождественное отношение;
• 
где U= ;
• 
Диаграмма Эйлера–Венна представлена на рис. 3.7, где заштрихованное множество соответствует дополнению .
Отношения R и R–1 – антирефлексивны, антисимметричны, транзитивны, т.е. являются отношениями строгого порядка.
Р
исунок 3.7
Эти отношения задают полный порядок на множестве М.
Отношение — рефлексивно, антисимметрично, транзитивно, т.е. является отношением нестрогого порядка; оно также задает полный порядок на множестве М.
Пример 3. Пусть R — отношение на N: R = {(а, b): а > b} — "быть больше".
Выполнить операции над R.
R–1 = {(a,b): a<b} – "быть меньше";
R = U \ R = {(a, b)\ a 
b} = 
– "быть не больше", где Е – тождественное отношение, Е = {(а, b): а = b};
R○R = R2= {(a, b): a–1 >b}– "быть больше по крайней мере на 2";
R° = R (так как R транзитивно);
R*=R° E= {(a, b):a>b или а = b} = {(а, b): а b} – "быть не меньше".
Пример 4. Пусть на множестве чисел М= {1, 2, 3, 4, 5, 6} определено отношение R.
Задать матрицами отношения R, , R–1, R°, R*, если R означает – "быть меньше".
Сформулировать правила получения матриц соответствующих отношений по исходной матрице отношения R.
-
1. Отношение R – "быть меньше <": антирефлексивно, антисимметрично, транзитивно. Воспользуемся результатами выполнения унарных операций над указанным отношением, полученными в примере 2:
R1 = {(а, b): а< b} – "быть меньше";
= {(а,b): а >= b} — "быть не меньше";
={(а, b): а>b} –"быть больше".
Если R1 означает, по существу, – "быть меньше, по крайней мере, на 1", то составное отношение:
R1○R1 = R12 = {{a, b): (a –1) < b} – "быть меньше по крайней мере на 2".
Наконец, в силу транзитивности отношения R1,:
R1° =R1= {(a, b): a< b} – "быть меньше";
