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

Лекции по предмету «Математика»
Информация о работе
  • Тема: Отношения эквивалентности и порядка
  • Количество скачиваний: 7
  • Тип: Лекции
  • Предмет: Математика
  • Количество страниц: 5
  • Язык работы: Русский язык
  • Дата загрузки: 2018-07-29 18:41:56
  • Размер файла: 85.79 кб
Помогла работа? Поделись ссылкой
Узнать стоимость учебной работы online!
  • Тип работы
  • Часть диплома
  • Дипломная работа
  • Курсовая работа
  • Контрольная работа
  • Решение задач
  • Реферат
  • Научно - исследовательская работа
  • Отчет по практике
  • Ответы на билеты
  • Тест/экзамен online
  • Монография
  • Эссе
  • Доклад
  • Компьютерный набор текста
  • Компьютерный чертеж
  • Рецензия
  • Перевод
  • Репетитор
  • Бизнес-план
  • Конспекты
  • Проверка качества
  • Экзамен на сайте
  • Аспирантский реферат
  • Магистерская работа
  • Научная статья
  • Научный труд
  • Техническая редакция текста
  • Чертеж от руки
  • Диаграммы, таблицы
  • Презентация к защите
  • Тезисный план
  • Речь к диплому
  • Доработка заказа клиента
  • Отзыв на диплом
  • Публикация статьи в ВАК
  • Публикация статьи в Scopus
  • Дипломная работа MBA
  • Повышение оригинальности
  • Копирайтинг
  • Другое
Узнать стоимость
Информация о документе

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

Если Вы являетесь автором текста представленного на данной странице и не хотите чтобы он был размешён на нашем сайте напишите об этом перейдя по ссылке: «Правообладателям»

Можно ли скачать документ с работой

Да, скачать документ можно бесплатно, без регистрации перейдя по ссылке:

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

План

  1. Покрытие и разбиение множества.

  2. Отношение эквивалентности.

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

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


1.Покрытие и разбиение множества

Пусть – некоторое семейство (совокупность) множеств.

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


.


Если покрытие таково, что его элементы попарно не пересекаются (), и все , то такое покрытие называется разбиением множества А.

Пример. . Тогда - покрытие, но не разбиение, - разбиение и покрытие, - не является ни покрытием, ни разбиением.

Разбиение множества А всегда является его покрытием; покрытие не всегда является разбиением.

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


Рис.1.


2.Отношение эквивалентности

Определение. Пусть задано бинарное отношение . Если это отношение является одновременно рефлексивным, симметричным и транзитивным, то оно называется отношением эквивалентности.

Пример. Пусть - это множество таких вещественных чисел, что . Отношение имеет место между двумя элементами тогда и только тогда, когда их разность является рациональным числом, т.е. когда . Такое отношение является рефлексивным, поскольку для (); является симметричным, поскольку, если , то , т.е. если , то и ; транзитивным, поскольку, если и , то , т.е. из того, что и ,следует, что . Таким образом, рассмотренное отношение является отношением эквивалентности.

Пример. Отношение равносильности, заданное на множестве формул, является отношением эквивалентности.

Пример. Отношение «проживания в одном доме» на множестве жителей города Одесса является отношением эквивалентности.

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

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


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

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

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

Отношения нестрогого и строгого порядка вместе называются отношениями порядка.

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

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

Пусть - отношение порядка. Элементы называются сравнимыми по отношению порядка на множестве , если выполняется или .

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

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

  • Частично упорядоченным множеством, если существуют , которые не сравнимы по отношению порядка . В таком случае говорят, что отношение задает частичный порядок на множестве . Например, отношение «быть начальником» задает строгий частичный порядок на множестве сотрудников некоторой организации.


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

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

  1. Объединением бинарных отношений и называется такое бинарное отношение , для которого имеет место соотношение:





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





  1. Разностью бинарных отношений и называется такое бинарное отношение , для которого имеет место соотношение:





  1. Дополнением бинарного отношения называется такое бинарное отношение , для которого имеет место соотношение:



, где (если ) или (если )



  1. Обратным отношением к бинарному отношению называется такое бинарное отношение , для которого имеет место соотношение:



.



Пример. Пусть - бинарное отношение «быть руководителем», определенное на множестве сотрудников некоторой организации. Тогда бинарные отношения имеют следующий смысл:

- «не быть руководителем»

- «быть подчиненным».

Перечисленные отношения имеют свойства, отраженные в таблице 1.


Таблица 1.

Отношение

Рефлексивно

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

Симметрично

Антисимметрично

Транзитивно

-

+

-

+

+

+

-

-

-

-

-

+

-

+

+


Вопросы

  1. Что такое покрытие множества? Привести примеры.

  2. Для любого ли множества можно построить покрытие? Ответ обосновать.

  3. Чем покрытие множества отличается от разбиения этого множества? Привести примеры.

  4. Всегда ли покрытие множества является его разбиением?

  5. Может ли покрытие множества быть его разбиением?

  6. Всегда ли разбиение множества является его покрытием?

  7. Какое бинарное отношение называется отношением эквивалентности? Привести примеры отношений эквивалентности.

  8. Какое бинарное отношение называется отношение нестрогого/строгого порядка? Привести примеры.

  9. Какое множество называется полностью упорядоченным? Привести примеры.

  10. Какое множество называется частично упорядоченным? Привести примеры.

  11. Какие операции над бинарными отношениями можно определить?