- •Е.Д. Стрельцова, в.С. Стрельцов моделирование дискретных систем Учебно-методическое пособие по дисциплине «Дискретная математика»
- •2. Теория множеств и отношений………………………………….20
- •Введение
- •1. Функции алгебры логики
- •1.1. Основные понятия
- •Пример функции алгебры логики , заданной таблицей
- •1.2. Алгоритм нахождения фиктивных аргументов.
- •1.3. Элементарные функции алгебры логики
- •Функции алгебры логики, зависящие от одного аргумента
- •Вопросы к разделу 1
- •2. Теория множеств и отношений
- •2.1. Множества. Способы задания множеств
- •2.2. Основные операции над множествами
- •2.2.1. Объединение множеств
- •2 .2.2. Пересечение множеств
- •2.2.3. Разность множеств
- •2.2.4. Дополнение множеств
- •2.4. Свойства операций над множествами
- •2.5. Упорядоченные множества
- •2.6. Прямое (декартово) произведение множеств
- •2.7. Степень множеств
- •2.8. Сечение и проекция
- •Декартово произведение
- •2.9. Соответствия
- •2.10. Композиция соответствий.
- •2.11. Отображения
- •2.12. Виды отображений. Функциональное отображение (функция)
- •2.13. Функционалы
- •2.14. Операторы
- •2.15. Линейные операторы
- •Отношение «Читает лекции по…»
- •Отношение «Посещать лекции»
- •2.20. Бинарные отношения
- •2.20.1. Матричный способ задания отношений
- •2.20.2. Задание отношений в виде графа
- •2.20.3. Задание отношений с помощью фактор множества
- •2.21. Свойства бинарных отношений
- •2.22. Отношение эквивалентности
- •2.23. Отношение порядка
- •2.24. Изоморфизм отношений
- •2.26. Операции над бинарными отношениями
- •2.26.1. Объединение отношений
- •2.26.2. Пересечение отношений
- •2.26.3. Разность отношений
- •2.26.4. Включение отношений
- •2.26.5. Переход к обратному отношению
- •2.26.6. Произведение отношений
- •2.26.7. Транзитивное замыкание
- •Вопросы к разделу № 2
- •3. Алгебраические системы
- •3.1. Понятие алгебраической системы
- •3.1. Морфизм алгебраических систем
- •3.3. Автоморфизмы
- •3.4. Виды универсальных алгебр
- •3.4.1. Полугруппы. Моноиды
- •3.4.2. Морфизм групп
- •3.4.3. Свойства морфизма групп
- •3.4.4. Кольцо
- •Вопросы к разделу №3
- •4. Практикум к решению задач Основные обозначения
- •4.1. Операции над множествами
- •Разностью множеств а и в называется множество
- •Симметрической разностью множеств а и в называется множество
- •Пустым множеством называется множество, не имеющее ни одного элемента.
- •Задачи и упражнения
- •На основании (14) можно записать
- •По определению объединения
- •Пусть теперь у (ав) (ас) у (ав) у (ас) (у а у в) (у а у с) у а (у в у с)
- •Задачи для самостоятельного решения
- •4.2. Векторное произведение
- •4.3. Соответствие
- •Свойства отношений
- •Список литературы
- •Моделирование дискретных систем
- •3 46428, Г. Новочеркасск, ул. Просвещения, 132
2.20.2. Задание отношений в виде графа
Существует ещё и другой важный способ задания бинарных отношений, заданных на конечных множествах. Изобразим элементы конечного множества точками на плоскости. Если выполнено соотношение (или ), то проведём стрелку от к . Если выполняется (или ), то нарисуем петлю, выходящую из и входящую в эту же точку. Такая фигура называется ориентированным графом, а сами точки – вершинами графа (рис. 2.19.).
При графическом способе задания бинарных отношений пустому отношению соответствует граф без стрелок и петель. Диагональное отношение изображается графом, в котором присутствуют только петли. Полное отношение изображается полным графом, где каждая его вершина соединена со всеми другими вершинами, в том числе и сама с собой. Граф есть геометрическое изображение бинарного отношения аналогично тому, как график есть геометрическое изображение функции. Геометрический язык полезен лишь тогда, когда граф достаточно прост. Изучать же сложные графы с большим числом вершин удобнее в терминах отношений.
2.20.3. Задание отношений с помощью фактор множества
Прежде, чем изложить способ задания бинарных отношений с помощью фактор множества, введём понятие окрестности единичного радиуса. Рассмотрим множество с заданным на нём бинарным отношением .
Определение
Окрестностью единичного радиуса элемента называется множество , задаваемое следующей высказывательной формой:
.
Является бесспорным, что окрестность единичного радиуса представляет собой не что иное, как образ элемента носителя бинарного отношений.
Определение
Множество окрестностей единичного радиуса, взятых для всех элементов носителя бинарного отношения , называется фактор множеством множества по отношению и обозначается .
Таким образом, фактор множество можно представить как объединение окрестностей единичного радиуса, взятых для всех элементов множества : . Фактор множество полностью определяет отношение .
2.21. Свойства бинарных отношений
Рассмотрим свойства, которыми могут обладать бинарные отношения. Допустим, что на некотором множестве как на носителе задано бинарное отношение , . Произвольное бинарное отношение может обладать следующими свойствами.
1. Свойство рефлексивности , т.е. любой элемент из множества находится сам с собой в отношении . Свойство рефлексивности можно записать в форме соотношений: в инфиксной форме , в префиксной форме , в постфиксной форме .
2. Свойство антирефлексивности т.е. любой элемент из множества не может находиться сам с собой в отношении . Или в форме соотношений:
в инфиксной форме ,
в префиксной форме ,
в постфиксной форме .
2. Свойство симметричности
, т.е. если элемент носителя находится в отношении с элементом носителя , то и элемент находится в отношении с элементом . В форме соотношений это свойство можно записать:
в инфиксной форме ,
в префиксной форме ,
в постфиксной форме .
3. Свойство антисимметричности
, т.е. если элемент находится в отношении с элементом и одновременно элемент находится в отношении с элементом , то эти элементы совпадают. В форме соотношений это свойство выглядит следующим образом:
в инфиксной форме ,
в префиксной форме ,
в постфиксной форме .
4. Свойство несимметричности
, т.е. если элемент находится в отношении с элементом , то элемент не находится в отношении с элементом . В форме соотношений это свойство можно записать:
в инфиксной форме ,
в префиксной форме ,
в постфиксной форме .
5. Свойство транзитивности
, т.е. для любых элементов , и из множества если элемент находится в отношении с элементом , а элемент находится в отношении с элементом , то элемент находится в отношении с элементом . В форме соотношений это свойство выглядит следующим образом:
в инфиксной форме ,
в префиксной форме ,
в постфиксной форме .
6. Свойство антитранзитивности
,
или в форме соотношений:
в инфиксной форме ,
в префиксной форме .
Перечисление свойств бинарных отношений совсем не означает, что все бинарные отношения ими обладают. В зависимости от присущих бинарным отношениям свойств они подразделяются на виды, которые будут рассмотрены далее.
Отношение толерантности
Рассмотрим бинарное отношение , . Это отношение носит название отношения толерантности (или сходства), если оно рефлексивно и симметрично, т.е. если выпорняются свойства:
– или ;
– или
.
Отношение толерантности не обладает свойством транзитивности, поэтому его нельзя принимать за отношение эквивалентности. Пренебрежение к отсутствию свойства транзитивности и ошибочное принятие отношения толерантности за отношение эквивалентности может привести к неприятностям.
Пример 2.19
Множество состоит из четырёхбуквенных слов – нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более чем на одну букву. Известная задача превращения мухи в слона формулируется следующим образом. Найти такую последовательность слов, начинающуюся словом «муха» и оканчивающуюся словом «слон», любые два соседних слова в которой сходны.
Изобразим эту последовательность.
Муха→мура→тура→тара→кара→каре→кафе→кафр→каюр→
каюк→крюк→крок→срок→сток→стон→слон.
Множество с заданным на нём отношением толерантности называется пространство толерантности.