Методическое пособие по математике по теме: «Отношение на множестве»

МИНИСТЕРСТВО ПРОСВЕЩЕНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего образования

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОСВЕЩЕНИЯ»

Методическая разработка по «Математике  и информатике»

Тема: «Отношение на множестве»

Выполнили студентки

Группы:НОсДП( РЯ/ИЯ/СпВиВсДОО)

Быстрова Виолетта

Никитина Ирина 

Руководитель:

Филатова Ольга Петровна

Доцент кафедры начального образования,

кандидат педагогических наук в ГУТ.

г.Мытищи,2025

СОДЕРЖАНИЕ

1.Введение…………………………………………………………………………3

Глава 2. Теоретические основы теории множеств и бинарных отношений…..4

 2.1. Понятие и виды отношений…………………………………………………4

 2.2. Бинарные отношения и их свойства………………………………………..5

 2.3. Представление бинарных отношений………………………………..……9

 2.4. Операции над бинарными отношениями………………………………….10

 2.5. Отношение порядка…………………………………………………………15

 2.6. Принцип разбиения множества на классы………………………………..16

Глава 3. Практическая часть…………………………………..……….………18

     3.1. Понятие и виды отношений……………………………………………18

     3.2. Бинарные отношения и их свойства……………………………………20

     3.3. Представление бинарных отношений…………………………….…….22

     3.4. Операции над бинарными отношениями……………………………….23

     3.5. Отношение порядка…………………………………………….………..29

   3.1.1 Задачи для самостоятельного решения………………………..………..31

4.Заключение……………………………………………………………………..37

5.Список литературы…………………………………………….………………38

 

1. ВВЕДЕНИЕ

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

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

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

• раскрыть сущность и математическое определение отношения на множестве;
• рассмотреть основные свойства и виды отношений;
• исследовать примеры использования отношений в различных областях математики и информатики.

 

Глава 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ МНОЖЕСТВ И БИНАРНЫХ ОТНОШЕНИЙ

2.1. Понятие и виды отношений

 

Отношение — это связь между элементами двух (или одного) множеств. Это математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи.

Различают разные виды отношений: 

Бинарное отношение — это отношение между двумя элементами. Примеры: отношение равенства между двумя или несколькими числами, фигурами, множествами, старшинства между людьми по возрасту или воинскому званию. 

Тернарное отношение — это отношение между тремя элементами. Пример: отношение «между» для тройки точек (A, B, C) на прямой: точка A расположена между точками B и C. 

N-арное отношение — это отношение между n элементами. Число n называется арностью, или местностью отношения. 

Таким образом, бинарное отношение — двуместное, тернарное — трёхместное, а n-арное — в общем случае n-местное

Бинарное отношение на множестве Х — это подмножество декартова произведения Х × Х. 

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

Утверждение о том, что элементы х и у находятся в отношении , можно записывать: (х, у)  или ху.

Последняя запись читается: «Элемент х находится в отношении  с элементом у». 

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

Тождественное (единичное) отношение на множестве X — это отношение, которое содержит только пары вида (x, x) для любого элемента x ∈ X.

Тождественное отношение на конечном множестве можно задать единичной матрицей Е, граф отношения содержит только петли в каждой из вершин.

Полное (универсальное) множество — в математике множество, содержащее все объекты и все множества. 

Такое множество обычно обозначается символом U (от англ. universe, universal set), реже E

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

 

2.2 Бинарные отношения и их свойства.

 

1. Рефлексивное отношение — это бинарное отношение на множестве, при котором каждый элемент связан с самим собой. Иными словами, для каждого элемента a из множества A пара (a, a) включена в отношение. 

Математически это можно выразить так: отношение R на множестве A рефлексивно, если (a, a) ∈ R ∀ a ∈ A. 

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

Определение

Формально отношение R на множе  стве A рефлексивно, если ∀a ∈ A, (a, a) ∈ R. Это означает, что если элемент a присутствует в множестве A, то отношение «a» к «a» (aRa) должно присутствовать в отношении R. Если какой-либо такой aRa отсутствует в R, то R не является рефлексивным отношением. 

Примеры:

• Отношение «равно» (обозначаемое «=») на множестве действительных чисел — рефлексивно, так как каждое действительное число равно самому себе. 
• Отношение «является родителем» в наборе людей — рефлексивно, потому что каждый человек — свой собственный родитель (в биологическом смысле). 
• Отношение «ровесник», определённое на области пар людей, — рефлексивно, потому что любой человек — ровесник самого себя. 

2. Антирефлексивное отношение (также известно как нерефлексивное отношение) — это бинарное отношение на множестве, в котором ни один элемент не связан сам с собой. Другими словами, для всех элементов a в наборе пара (a, a) не находится в отношении. 

Определение

Формально антирефлексивность отношения R на множестве A определяется как ∀a ∈ A, (a, a) ∉ R. 

Примеры

Некоторые примеры антирефлексивных отношений:

• отношение неравенства (≠);
• отношения строгого порядка: отношение строгого неравенства (<);
• отношение строгого подмножества (⊂);
• отношение перпендикулярности прямых (или ортогональности ненулевых векторов) в евклидовом пространстве.

Также антирефлексивно отношение «быть сыном», так как никто не приходится сыном самому себе

3. Симметричное отношение множеств — это бинарное (двухместное) отношение, определённое на некотором множестве, которое характеризуется тем, что для любых элементов х и у этого множества из того, что х находится в отношении R с элементом у, следует, что и у находится в том же отношении к х. Проще говоря, если «a связано с b», то «b связано с a» справедливо для всех элементов, включённых в отношение

Определение

Формально симметричное отношение R на множестве A записывается так: для всех a, b ∈ A, если (a, b) ∈ R, то (b, a) ∈ R. 

Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к х

Примеры

• Отношение «равно» на множестве чисел. Если число 3 равно 3, то это будет верно даже при изменении порядка, что делает «равно» симметричным отношением.
• Отношение «является братом» в группе людей. Если Алиса — брат Боба, то Боб — брат Алисы — отношение симметрично, потому что порядок имён можно изменить, и оно останется истинным.
• Отношение дружбы между людьми — симметрично, так как если человек a дружит с человеком b, то и человек b дружит с человеком a.

4. Антисимметричное отношение множеств — это тип бинарного отношения, при котором любые два различных элемента, связанные друг с другом в одном направлении, не могут быть связаны в противоположном направлении

Определение

Бинарное отношение R на множестве X называется антисимметричным, если для любых элементов a и b множества X из выполнения отношений aRb и bRa следует равенство a и b. 

Или эквивалентное определение: для любых неравных элементов a и b множества X из выполнения отношения aRb следует невыполнение отношения bRa. 

Важно: антисимметричность отношения не исключает симметричность — существуют бинарные отношения, которые одновременно симметричные и антисимметричные (например, отношение равенства).

Примеры

• Отношение «меньше или равно» (≤) на множестве целых чисел. Если a ≤ b и b ≤ a, то a должно быть равно b. 
• Отношение делимости на натуральных числах. Если a делит b и b делит a, то a = b. 
• Отношение включения на множестве всех подмножеств некоторого множества. Если A подмножество B и B подмножество A, то A = B

5. Транзитивное отношение множеств (от лат. transitivus — «переходный») — свойство бинарных отношений, выражающее их «переносимость» с одних пар объектов на другие. Это означает, что если один элемент упорядоченной пары соотносится со вторым, а второй элемент другой упорядоченной пары — с третьим, то и первый элемент соотносится с третьим. 

Определение

Пусть на множестве X задано бинарное отношение R. Отношение называется транзитивным, если для любых элементов x, y, z ∈ X из того, что x находится в отношении R с элементом y, и элемент y находится в отношении R с элементом z, следует, что x находится в отношении R с элементом z. 

Формально это записывается так: ∀x, y, z ∈ X, (x R y) ∧ (y R z) ⇒ (x R z). 

 Примеры

• Отношение «меньше или равно» на натуральных числах — транзитивно, так как если a ≤ b и b ≤ c, то a ≤ c.
• Отношение «является подмножеством» (включение множества, отношение к множествам) — транзитивно.
• Отношение «делит» (делимость, отношение к натуральным числам) — транзитивно.

 

2.3. Представление бинарных отношений

 

Признаки матрицы отношения , характеризующие его свойства:

1. О рефлексивно, если главная диагональ его матрицы содержит только единицы.
2. О антирефлексивно, если главная диагональ его матрицы содержит только нули.
3. О симметрично, если его матрица симметрична относительно главной диагонали.
4. О антисимметрично, если в его матрице отсутствуют единицы, симметричные относительно главной диагонали.
5. О транзитивно, если в его матрице выполняется следующее условие: если в i-й строке стоит единица, например, в j-м столбце строки, то всем единицам j-й строки  должны соответствовать  единицы в i-й строке в тех же столбцах и, может быть, еще и в других столбцах.

Признаки графа отношения , характеризующие его свойства:

1. рефлексивного о содержит петли во всех узлах.
2. антирефлексивного о не содержит ни одной петли.
3. В графе симметричного отношения для каждой стрелки, соединяющей два узла, существует также стрелка, соединяющая эти узлы в обратном направлении.
4. В графе антисимметричного отношения не существует двух различных узлов, связанных парой разнонаправленных стрелок.
5. В графе транзитивного отношения для любых двух стрелок таких, что одна направлена от x к y, а другая — от y к z, существует стрелка, соединяющая x и z в направлении от x к z.

 

2.4. Операции над бинарными отношениями

 

Операции над бинарными отношениями: 

1. Пересечение множеств — это новое множество, содержащее те и только те элементы, которые входят одновременно и в множество A, и в множество B. 

Пересечение множеств обозначается: A ∩ B. 

Примеры пересечения множеств:

• Если H — множество упражнений, укрепляющих руки, и L — множество упражнений, укрепляющих ноги, то H ∩ L — множество упражнений, укрепляющих руки и ноги.
• Если A — множество яблок и G — множество зелёных предметов, то A ∩ G — множество зелёных яблок.
• Если E — множество песен на английском языке и J — множество песен Дженнифер Лопес, то E ∩ J — множество песен Дженнифер Лопес на английском языке.
• Если нет элементов, которые принадлежат обоим множествам сразу, то пересечение множеств будет пустым: A ∩ B = ∅
• Пустое множество — множество, не содержащее ни одного элемента. Обычно обозначается ∅

2. Объединение — это множество, содержащее все элементы, которые принадлежат хотя бы одному из множеств A или B. Объединение множеств обозначается: A ∪ B.

Примеры объединения множеств:  

• Если H — множество упражнений, укрепляющих руки, и L — множество упражнений, укрепляющих ноги, то H ∪ L — множество упражнений, укрепляющих руки или ноги (или и то, и другое).  
• Если A — множество яблок и G — множество зелёных предметов, то A ∪ G — множество всех яблок и зелёных предметов вместе.  
• Если E — множество песен на английском языке и J — множество песен Дженнифер Лопес, то E ∪ J — множество всех песен либо на английском языке, либо Дженнифер Лопес (или оба условия).  
• Если одно из множеств пусто, например B = ∅, то A ∪ B = A.

 

3. Разность — это множество элементов, которые принадлежат множеству A, но не принадлежат множеству B. Обозначается: A \ B.

Примеры разности:  

• Если H — множество упражнений для рук, а L — для ног, то H \ L — упражнения, укрепляющие руки, но не ноги.  
• Если A — множество яблок, а G — множество зелёных предметов, то A \ G — все яблоки, которые не зелёные.  
• Если E — множество песен на английском, а J — песни Дженнифер Лопес, то E \ J — все английские песни, кроме песен Дженнифер Лопес.  
• Если A = B, то A \ B = ∅.

4. Симметрическая разность — это множество элементов, которые входят либо в A, либо в B, но не в оба одновременно. Обозначается: A △ B.

Примеры симметрической разности:  

• Если H — упражнения для рук, L — для ног, то H △ L — упражнения, которые укрепляют либо только руки, либо только ноги, но не одновременно руки и ноги.  
• Если A — яблоки, G — зелёные предметы, то A △ G — элементы, которые либо яблоки без зелёного цвета, либо зелёные предметы, которые не являются яблоками.  
• Если E — песни на английском, J — песни Дженнифер Лопес, то E △ J — песни либо на английском, но не Дженнифер Лопес, либо Дженнифер Лопес, но не на английском языке.  
• Если A = B, то A △ B = ∅.

 

5. Дополнение множества A относительно универсального множества U — это множество всех элементов универсального множества, которые не входят в A. Обозначается: Aᶜ или U \ A.

Примеры дополнения:  

• Если U — множество всех упражнений, а H — упражнения для рук, то Hᶜ — упражнения, которые не укрепляют руки.  
• Если U — все предметы, A — яблоки, то Aᶜ — все предметы, кроме яблок.  
• Если U — все песни, E — английские песни, то Eᶜ — все песни на других языках.  
• Дополнение пустого множества ∅ — это всё универсальное множество: ∅ᶜ = U.

6. Обратное отношение R⁻¹ к отношению R — это множество пар (b, a), таких что (a, b) принадлежит R. Иначе, это отношение, в котором все пары исходного отношения «перевернуты».

Примеры обратного отношения:  

• Если R — отношение «быть родителем», то R⁻¹ — отношение «быть ребёнком».  
• Если R — отношение «учитель — ученик», то R⁻¹ — отношение «ученик — учитель».  
• Если R — отношение «владеет», то R⁻¹ — отношение «находится во владении».  
• Если пары в R — (x, y), то в R⁻¹ — соответствующие пары (y, x).

 

7. Произведение отношений R и S, обозначаемое как S ∘ R, — это отношение, состоящее из пар (a, c), для которых существует элемент b, такой что (a, b) ∈ R и (b, c) ∈ S.

Примеры произведения отношений:  

• Если R — отношение «живёт в городе», а S — «расположен в стране», то S ∘ R — отношение «житель страны».  
• Если R — отношение «учитель — студент», а S — «студент — курс», то S ∘ R — отношение «учитель — курс» (то есть учитель читает курс через студента).  
• Если R и S — отношения «связи» между объектами, то их произведение — цепочка связей, проходящая через посредника.  
• Чтобы пара (a, c) была в S ∘ R, должен существовать b, связывающий через R и затем через S.

Правила построения некоторых матриц отношений по известной матрице отношения R:

1. Матрица дополнения R. В матрице исходного отношения R заменить единицы нулями, а нули — единицами.
2. Матрица обратного отношения R-1. Проставить в ней единицы, симметричные (относительно главной диагонали) соответствующим единицам исходной матрицы.
3. Матрица составного отношения R(2). Для каждой единицы исходной матрицы отношения R, принадлежащей i-й строке, например единицы в j-й компоненте, в i-й строке вычисляемой матрицы проставить единицы в тех k-х компонентах, в которых имеются единицы в j-й строке исходной матрицы.
4. Матрица транзитивного замыкания R0 нетранзитивного отношения R. Для её построения проделать ряд итераций: в матрицу составного отношения R(2) занести все единицы исходной матрицы, которые отсутствуют в R(2), полученную матрицу принять за исходную и повторить для неё процедуру. Выполнять это до тех пор, пока матрица не перестанет изменяться.
5. Матрица рефлексивного замыкания R. Построить матрицу транзитивного замыкания, а затем в полученной матрице заменить нули на главной диагонали на единицы.

 

2.5. Отношение порядка

 

Отношение порядка — это бинарное отношение между элементами данного множества, по своим свойствам сходное со свойствами отношения неравенства. 

Некоторые виды отношений порядка:

• Отношение нестрогого порядка. Рефлексивное антисимметричное транзитивное отношение. Обозначается символом ⩽. Пример: на множестве вещественных чисел отношения «больше или равно» и «меньше или равно» — нестрогого линейного порядка. 
• Отношение строгого порядка. Антирефлексивное транзитивное отношение. Обозначается символом <. Пример: на множестве вещественных чисел отношения «больше» и «меньше» — отношения строгого порядка. 
• Отношение линейного порядка. Является отношением частичного порядка и обладает свойством: для любых элементов множества либо один элемент меньше другого, либо наоборот. Множество, на котором введено такое отношение, называется линейно упорядоченным. 
• Отношение полного порядка. Является отношением линейного порядка и обладает свойством: для любого подмножества множества есть элемент, для которого верно отношение порядка для всех элементов подмножества. Множество, на котором введено такое отношение, называется полностью упорядоченным. 

Примеры отношений порядка:

• Отношение «является делителем» на множестве натуральных чисел — отношение частичного порядка.
• Отношение «меньше или равно» — отношение полного порядка на множестве натуральных чисел.
• Отношение «лексикографически не меньше» на множестве всех возможных слов, составленных из букв русского алфавита, — отношение полного порядка.
• Отношение «состоит в подчинении» на множестве работников компании — отношение нестрогого порядка.

Множество Х, на котором задано отношение порядка, может быть:

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

Например, отношение «быть не старше» задает полный порядок на множестве людей;

б) частично упорядоченным — в противном случае. При этом говорят, что отношение задает на множестве Х частичный порядок. Например, отношение «быть начальником» задает на множестве сотрудников организации частичный порядок, так как, например, для пары сотрудников одного отдела данное отношение не выполняется: они несравнимы по данному отношению.

 

2.6. Принцип разбиения множества на классы

 

Принцип разбиения множества на классы 

Принцип разбиения множества на классы заключается в том, что множество считается разбитым на классы, если подмножества попарно не пересекаются

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

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

Также классификацию можно выполнять при помощи свойств элементов множеств. Например, если на множестве задано одно свойство, то это множество разбивается на два класса: первый — класс объектов, обладающих данным свойством, а второй — класс объектов, не обладающих этим свойством

 

3. ПРАКТИЧЕСКАЯ ЧАСТЬ

3.1.Понятие и виды отношений

 

Задача 1: Определите, является ли следующее отношение  R  на множестве  A = {1, 2, 3}  рефлексивным:  R = {(1, 1), (2, 2), (1, 2)} .

Решение: Отношение рефлексивно, если для каждого элемента  a ∈ A  выполняется  (a, a) ∈ R . В данном случае отсутствует пара  (3, 3) , следовательно, отношение не рефлексивно.

Ответ: Не рефлексивно.

 

Задача 2: Приведите пример симметричного отношения на множестве  B = {a, b} .

Решение: Отношение  S = {(a, b), (b, a)}  является симметричным, так как если  (x, y) ∈ S , то  (y, x) ∈ S .

Ответ:  S = {(a, b), (b, a)} .

 

Задача 3: Является ли отношение  T = {(1, 2), (2, 3), (1, 3)}  транзитивным на множестве  C = {1, 2, 3} ?

Решение: Определение: транзитивно, если (a,b) ∈ T и (b,c) ∈ T ⇒ (a,c) ∈ T для любых a,b,c.

— Проверка: имеются (1,2) и (2,3) ⇒ проверяем, есть ли (1,3). Да, (1,3) ∈ T. Других цепочек вида (a,b) и (b,c) нет.

— Вывод: T транзитивно.

Ответ: Транзитивно.

 

Задача 4: Найдите антиссимметричное отношение на множестве  D = {x, y} .

Решение: Определение: антиссимметрично, если при (u,v) и (v,u) ∈ R следует u = v (то есть для различных элементов нельзя иметь обе обратные пары).

— Пример: A = {(x,y),(y,y)}. Здесь есть (x,y), но нет (y,x), поэтому условие антиссимметричности не нарушается.

Ответ:  A = {(x, y), (y, y)} .

 

Задача 5: Определите вид отношения  M = {(a, a), (b, b), (c, c)}  на множестве  E = {a, b, c} .

Решение: Это тождественное (identity) отношение: все диагональные пары есть, других пар нет.

— Свойства: рефлексивно (все (a,a) ∈ M), антиссимметрично (нет пар (x,y),(y,x) с x≠y), симметрично (для диагональных пар (x,x)⇔(x,x)), транзитивно.

— Вывод: M — рефлексивное; дополнительно: это тождественное отношение, оно одновременно транзитивно, симметрично и антиссимметрично.

Ответ: Рефлексивное и антиссимметричное.

 

Задача 6: Приведите пример отношения на множестве  F = {1, 2, 3} , которое не является ни симметричным, ни транзитивным.

Решение: — Пример: G = {(1,2),(2,3)}.

— Симметрия: (1,2) ∈ G, но (2,1) ∉ G ⇒ не симметрично.

— Транзитивность: (1,2) и (2,3) ∈ G, но (1,3) ∉ G ⇒ не транзитивно.

Ответ:  G = {(1, 2), (2, 3)} .

 

Задача 7: Определите рефлексивность отношения  H = {(1, 1), (2, 2), (3, 4)}  на множестве  J = {1, 2, 3, 4} .

Решение: Отношение не рефлексивно из-за отсутствия пар  (3, 3)  и  (4, 4) .Ответ: Не рефлексивно.

 

3.2. Бинарные отношения и их свойства

 

Задача 1: Дано множество  K = {1, 2} . Определите все возможные бинарные отношения на этом множестве.

Решение: Возможные бинарные отношения:

1. R₁ = ∅ 
2. R₂ = {(1, 1)} 
3. R₃ = {(1, 2)} 
4. R₄ = {(2, 1)} 
5. R₅ = {(2, 2)} 
6. R₆ = {(1, 1), (1, 2)} 
7. и так далее до полного множества пар.

Ответ: Всего 16 бинарных отношений.

 

Задача 2: Проверьте рефлексивность отношения  R = {(a,a), (b,b)}  на множестве  L = {a,b,c} .

Решение: — Для рефлексивности нужно также (c,c) ∈ R, но его нет.

— Вывод: R не рефлексивно.

Ответ: Не рефлексивно.

 

Задача 3: Найдите все антиссимметричные отношения на множестве  M = {1, 2} .

Решение: Возможные антиссимметричные отношения:

1. A₁ = ∅ 
2. A₂ = {(1,1), (2,2)} 
3. A₃ = {(1,2)} 

Ответ: Три антиссимметричных отношения.

 

Задача 4: Определите транзитивность отношения  P = {(1, 2), (2, 3), (1, 3)} 

Решение: Проверка: пары (1,2) и (2,3) дают (1,3) — оно есть; других комбинаций с посредником нет. Никаких нарушений.

 Вывод: P транзитивно

Ответ: Транзитивно.

 

Задача 5: Дайте пример бинарного отношения на множестве  N = x,y,z , которое является симметричным и транзитивным.

Решение: Отношение  S = (x,y),(y,x),(y,z),(z,y),(x,z),(z,x).

Ответ: Симметрично и транзитивно.

 

Задача 6: Определите свойства отношения  T = (1,2),(2,3),(3,4).

Решение: — Симметрия: для (1,2) нет (2,1) ⇒ не симметрично.

— Рефлексивность: отсутствуют диагональные пары (1,1),(2,2),(3,3),(4,4) ⇒ не рефлексивно.

— Транзитивность: (1,2) и (2,3) ⇒ надо (1,3), которого нет ⇒ не транзитивно.

— Антиссимметричность: нет обратных пар вида (2,1),(3,2),(4,3) ⇒ услов антиссимметричности не нарушен (т.е. оно антиссимметрично).

Ответ: Не симметрично и не рефлексивно.

 

Задача 7: Найдите все рефлексивные бинарные отношения на множестве {a,b,c,d}.

Решение: Существует множество рефлексивных отношений: например,

• {a,a}, {b,b}, {c,c}, {d,d}, а также любые сочетания с другими парами.
• Всего будет 15 различных рефлексивных отношений.

Ответ: Более 15 различных рефлексивных отношений.

 

3.3. Представление бинарных отношений

 

Задача 1: Запишите матрицу смежности для бинарного отношения  R = (1,2),(2,3),(1,3) на множестве {1,2,3}.

Решение:

0 | 1 | 1

0 | 0 | 1

0 | 0 | 0

Ответ:

0 | 1 | 1

0 | 0 | 1

0 | 0 | 0

 

Задача 2: Запишите список пар для бинарного отношения заданного матрицей смежности:

0 | 1 | 0

0 | 0 | 1

0 | 0 | 0

Решение: Из матрицы видно пары: 

 R = (1,2),(2,3).

Ответ:

 R = (1,2),(2,3).

 

Задача 3: Найдите количество различных бинарных отношений на множестве {a,b,c,d}, представленных в виде матрицы смежности.

Решение: На множестве из n элементов существует  n² пар. Для {a,b,c,d} это будет:

16 различных бинарных отношений.

Ответ:16.

 

Задача 4: Определите количество строк в матрице смежности для бинарного отношения на множестве {x,y,z,w}.

Решение: Количество строк равно количеству элементов в множестве — в данном случае это будет:

4.

Ответ:

4.

 

Задача 5: Запишите матрицу смежности для отношения  R = (x,y),(y,x),(y,z) на множестве {x,y,z}.

Решение:

0 | 1 | 0

1 | 0 | 1

0 | 0 | 0

Ответ:

0 | 1 | 0

1 | 0 | 1

0 | 0 | 0

 

Задача 6: Какой вид имеет матрица смежности для полного бинарного отношения на множестве {a,b,c}?

Решение:

Полное бинарное отношение будет иметь вид:

0 | 1 | 1

1 | 0 | 1

1 | 1 | 0

Ответ:

Полная матрица смежности:

0 | 1 | 1

1 | 0 | 1

1 | 1 | 0

 

3.4. Операции над бинарными отношениями

 

Задача 1: Даны два бинарных отношения: 

 R₁ = (1,2),(2,3) и 

 R₂ = (2,3),(3,4). Найдите их объединение.

Решение:- Объединение R1 ∪ R2 содержит все пары, которые есть в хотя бы одном из множеств.

— R1 ∪ R2 = {(1,2),(2,3),(3,4)}.

Объединение:

 R₃ = R₁ ∪ R₂ = (1,2),(2,3),(3,4).

Ответ:

 R₃ = (1,2),(2,3),(3,4).

 

Задача 2: Найдите пересечение отношений 

 R₄ = (a,b),(b,c) и 

 R₅ = (b,c),(c,d).

Решение:- Пересечение R4 ∩ R5 — пары, которые присутствуют и в R4, и в R5.

— Общая пара: (b,c).

— R4 ∩ R5 = {(b,c)}.

Ответ:

 R₆ = (b,c).

 

Задача 3: Найдите разность отношений 

 R₇ = (x,y),(y,z) и 

 R₈ = (y,z).

Решение:- Разность R7 \ R8 — пары из R7, которых нет в R8.

— В R7 пары (x,y) и (y,z); (y,z) удаляем — остаётся (x,y).

— R7 \ R8 = {(x,y)}.

Ответ:

 R₉ = (x,y).

 

Задача 4: Найдите обратное отношение к 

 R₁₃ = (m,n),(n,o).

Решение:- Обратное (инверсное) отношение R^{-1} — это множество пар (y,x) для каждой пары (x,y) ∈ R.

— Для (m,n) даёт (n,m); для (n,o) даёт (o,n).

— R13^{-1} = {(n,m),(o,n)}.

Ответ:. {(n,m),(o,n)}

 

Задача 5: Найдите симметричное дополнение к отношению 

 R₁₅ = (p,q),(q,r).

Решение:

— Обратное R15^{-1} = {(q,p),(r,q)}.

— Симметрическая замыкание (симметричное дополнение) = R15 ∪ R15^{-1} = {(p,q),(q,r),(q,p),(r,q)}.

Ответ:

— Обратное отношение: {(q,p),(r,q)}.

— Симметрическая замыкание (симметричное дополнение): {(p,q),(q,r),(q,p),(r,q)}.

 

3.5. Отношение порядка

 

Задача 1: Определите является ли отношение 

 P = (a,a),(a,b),(b,b),(b,c),(c,c) частичным порядком на множестве {a,b,c}.

Решение:Проверяем по трём свойствам (рефлексивность, антисимметричность, транзитивность).

1) Рефлексивность:

— Для всех элементов a,b,c нужны (a,a),(b,b),(c,c). В P они есть. → Рефлексивно.

2) Антисимметричность:

— Условие: если (x,y) ∈ P и (y,x) ∈ P, то x = y.

— В P есть (a,b), но нет (b,a); есть (b,c), но нет (c,b). Нет обратных пар между различными элементами, значит антисимметричность выполняется.

3) Транзитивность:

— Условие: если (x,y) ∈ P и (y,z) ∈ P ⇒ (x,z) ∈ P.

— В P есть (a,b) и (b,c) ⇒ должно быть (a,c). Но (a,c) в P отсутствует.

— Значит транзитивность нарушена.

Вывод: P не является частичным порядком (нарушена транзитивность).

 Ответ: Не является частичным порядком.

 

Задача 2: Приведите пример линейного порядка на множестве {x,y,z}.

Решение:Требования для линейного порядка:

— Рефлексивность: (x,x),(y,y),(z,z) ∈ R.

— Антисимметричность.

— Транзитивность.

— Полнота (тогость): для любых разных u≠v либо (u,v) ∈ R, либо (v,u) ∈ R.

Пример и проверка:

Возьмём L = {(x,x),(y,y),(z,z),(x,y),(y,z),(x,z)} — порядок x < y < z.

— Рефлексивность: диагонали есть.

— Антисимметричность: между различными элементами присутствует только один направленный порядок (например (x,y) есть, (y,x) нет).

— Транзитивность: (x,y) и (y,z) ⇒ (x,z) есть.

— Полнота: для каждой пары разных элементов одно из направлений есть — (x,y) есть, (y,x) нет; (x,z) есть; (y,z) есть.

Значит L — линейный порядок.

Ответ:L = {(x,x),(y,y),(z,z),(x,y),(y,z),(x,z)} — пример линейного порядка (x < y < z).

Задача 3. На множестве {1,2,3,4} R = {(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,4)}. Является ли R частичным порядком? Если нет — найдите транзитивное замыкание.

Решение:

— Рефлексивность: есть.

— Антисимметричность: обратных пар нет → ок.

— Транзитивность: (1,2) и (2,4) ⇒ нужно (1,4) (его нет) → нарушено. Также возможна цепочка (1,3) с чем-то? нет.

— Транзитивное замыкание R = R ∪ {(1,4)} (т.к. единственная недостающая пара для транзитивности — (1,4)). Проверяем: после добавления новые цепочки не создают новых недостающих пар.

Ответ: R не является частичным порядком; транзитивное замыкание R = R ∪ {(1,4)}.

 

3.1.1.Задачи для самостоятельного решения.

Задача №1. 

Найти все подмножества следующих множеств: ∅, {∅}, {1, 2, 3}, {a, {1, 2}, ∅}. 

Ответ:

P(∅) = {∅}, P({∅}) = {∅, {∅}}, P({ 1, 2, 3 }) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, P({a, {1, 2}, ∅}) = {∅, {a}, {{1, 2}}, {∅}, {a, {1, 2}}, {a, ∅}, {{1, 2}, ∅}, {a, {1, 2}, ∅}}.

 

Задача №2. 

Даны множества: A = {a,b,{∅},{a,c,d}}, B = {a,c,e,{a},{b}} и C = {a, b, c, d, {e}, ∅}. Найти множество D = (A ∪ B) \ C. Какова его мощность?

Ответ: 

2. (A ∪ B) \ C = {{∅}, {a, c, d}, e, {a}, {b}}, |(A ∪ B) \ C| = 5.

 

Задача №3

Пусть A = {0,1}, B = {a,b,c}. Найти множества A×B и B×A

Ответ:

3. A × B = {(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}, B × A = {(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)}.

Задача№4

Даны четыре множества: A = {0,1,2}, B = {2,3}, C = {a,b,c} и D = {a, c, e}. Определить, чему равны следующие множества: 

(а) F1 =(A\B)×(C∩D); 

(б) F2 = (A∩B)×(C ∩D);

(в) F3 =(B\A)×(C\D). 

Ответ:

4.(а)A\B={0,1},C∩D={a,c},F1 ={(0,a),(0,c),(1,a),(1,c)},

(б)A∩B={2},C∩D={a,c},F2 ={(2,a),(2,c)},

(в)B\A={3},C\D={b},F3 ={(3,b)}.

 

Задача №5 

Доказать следующие тождества для любых множеств A, B, C:

(а) A∩(B∪C)=(A∩B)∪(A∩C);

(б) A\(B∪C)=(A\B)∩(A\C)

(в) A\(B\C)=(A\B)∪(A∩C)

Ответ:

5. (а) Докажем, что A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C). Пусть x ∈ A ∩ (B ∪ C). По определению пересечения множеств это значит, что x ∈ A и x ∈ B ∪ C. По определению объединения x ∈ B или x ∈ C. Если x ∈ B, то x ∈ A ∩ B, а значит, x ∈ (A ∩ B) ∪ (A ∩ C). Если же x ∈ C, то x ∈ A ∩ C и снова x ∈ (A ∩ B) ∪ (A ∩ C). Докажем, что (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C). Пусть x ∈ (A ∩ B) ∪ (A ∩ C). По определению объединения множеств это значит, что x ∈ A ∩ B или x ∈ A ∩ C. Если x ∈ A ∩ B, то x ∈ A и x ∈ B. Тогда x ∈ B ∪ C, и следовательно, x ∈ A ∩ (B ∪ C). Если же x ∈ A ∩ C, то x ∈ A и x ∈ C. Значит, x ∈ B ∪ C, и следовательно, x ∈ A ∩ (B ∪ C).

 

(б) Докажем A \ (B ∪ C) ⊆ (A \ B) ∩ (A \ C). Если x ∈ A \ (B ∪ C), то x ∈ A и x ∈/ B ∪ C, то есть x ∈/ B и x ∈/ C. Следовательно, x ∈ A \ B и x ∈ A \ C, что означает x ∈ (A \ B) ∩ (A \ C). Докажем A \ (B ∪ C) ⊇ (A \ B) ∩ (A \ C). Если x ∈ (A\B)∩(A\C), то x ∈ A\B и x ∈ A\C. Следовательно, x ∈ A, но x ∈/ B и x ∈/ C. Получаем x ∈/ B ∪ C и x ∈ A \ (B ∪ C).

(е) Докажем (A\B)∩C ⊆ (A∩C)\B. Если x ∈ (A\B)∩C, то x ∈ A\B и x ∈ C. Следовательно, x ∈ A и x ∈/ B. Таким образом, x ∈ A ∩ C и x ∈ (A∩C)\B. Докажем (A\B)∩C ⊇ (A∩C)\B. Если x ∈ (A∩C)\B, то x ∈ A ∩ C и x ∈/ B. Получаем, что x ∈ A и x ∈ C. Следовательно, x ∈ A \ B и x ∈ (A \ B) ∩ C.

(в) Докажем A \ (B \ C) ⊆ (A \ B) ∪ (A ∩ C). Если x ∈ A \ (B \ C), то x ∈ A и x ∈/ B \ C. Последнее означает, что x ∈/ B или x ∈ C. В случае x ∈/ B получаем x ∈ A\B и, следовательно, x ∈ (A\B)∪(A∩C). В случае x ∈ B получаем x ∈ A∩C и, следовательно, x ∈ (A\B)∪(A∩C). Докажем A \ (B \ C) ⊇ (A \ B) ∪ (A ∩ C). Если x ∈ (A \ B) ∪ (A ∩ C), то x ∈ A \ B или x ∈ A∩C. В случае x ∈ A\B получаем x ∈ A, но x ∈/ B. Следовательно, x ∈/ B \ C и x ∈ A \ (B \ C). В случае x ∈ A ∩ C получаем x ∈ A и x ∈ C. Следовательно,x∈/B\C иx∈A\(B\C).

 

Задача№6

Доказать следующие равенства и включения:

(а) P(A∩B)=P(A)∩P(B);

(б) P(A∪B)⊇P(A)∪P(B);

(в) P(A\B)⊆(P(A)\P(B))∪{∅}.

Ответ: 

6. (а) Пусть x ∈ P(A∩B), значит, x ⊆ A∩B, следовательно, x ⊆ A и x ⊆ B, поэтому x ∈ P(A) и x ∈ P(B), то есть x ∈ P(A) ∩ P(B). Пусть x ∈ P(A)∩P(B), тогда x ∈ P(A) и x ∈ P(B), значит, x ⊆ A и x ⊆ B, поэтому x ⊆ A ∩ B и x ∈ P(A ∩ B).

(б) Если x ∈ P(A) ∪ P(B), то x ∈ P(A) или x ∈ P(B), значит, x ⊆ A или x ⊆ B, поэтому x ⊆ A ∪ B и x ∈ P(A ∪ B). Пусть A = {a}, B = {b}, где a ̸= b. Тогда P(A ∪ B) = {∅, {a}, {b}, {a, b}}, но P(A) ∪ P(B) = {∅, {a}, {b}}.

(в) Пусть x ∈ P(A\B), значит, x ⊆ A\B, следовательно, x ⊆ A и x∩B = ∅. Получаем x ∈ P(A), а если x ∈ P(B), то x = ∅. Тогда x ∈ (P(A)\P(B))∪{∅}. Пусть A = {a,b}, B = {b}, где a ̸= b. Тогда P(A\B) = {∅,{a}}, но

(P(A) \ P(B)) ∪ {∅} = {∅, {a}, {a, b}}.

 

Задача №7

Для каждого из следующих бинарных отношений на множестве A = {a, b, c} определить, является ли оно рефлексивным, симметрич- ным, антисимметричным, транзитивным:

(а) R1 = {(a, a), (a, b), (b, a), (b, b), (c, c)};

(б) R2 = {(a, a), (a, c), (c, b), (a, b), (b, b), (c, c)};

(в) R3 = {(a, a), (a, c), (c, b), (a, b)}.

7. (а) R1 рефлексивно, симметрично, транзитивно;

(б) R2 рефлексивно, антисимметрично, транзитивно;

(в) R3 антисимметрично, транзитивно.

 

4. ЗАКЛЮЧЕНИЕ

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

 

5. СПИСОК ЛИТЕРАТУРЫ

1. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа.
2. Розен К. Дискретная математика и её применения.
3. Демидович Б.П., Марон И.А. Основы высшей математики.
4. Гусев В.Е. Математическая логика и теория множеств.
5. Учебные материалы по дискретной математике, лекции кафедры информатики.