Отношения на множествах
Отношения, связывающие элементы множеств. Свойства бинарных отношений. Функциональные отношения. Отношения на заданном двухэлементном множестве. Выделение отношений эквивалентности и построение классов эквивалентности. Классификация отношений порядка.
Рубрика | Математика |
Вид | лабораторная работа |
Язык | русский |
Дата добавления | 17.09.2019 |
Размер файла | 54,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Дисциплина
ДИСКРЕТНАЯ МАТЕМАТИКА
Лабораторная работа № 2
Отношения на множествах. Отношения, связывающие элементы множеств
Цель работы: изучение способов задания отношений, приобретение практических навыков в проверке свойств отношений, классификация отношений.
Теоретические сведения
Прямое (декартово) произведение множеств Х и Y - множество упорядоченных пар, таких что:
Х x Y = {(x,y)| xX, yY}.
При X = Y множество X х X называется декартовой степенью
множества X и обозначается X2.
Отношением на множествах X и Y называется произвольное
подмножество прямого произведения этих множеств
Х x Y = {(x,y)| xX, yY}.
Если Х2, то отношение задано на множестве Х.
Если (x,y), то (x,y) находятся в отношении или связаны отношением х y или y = (х) .
Область определения D бинарного отношения - множество первых элементов каждой упорядоченной пары D = {x | (x,y) }.
Область значений J бинарного отношения - множество
вторых элементов каждой упорядоченной пары
J = {y | (x, y) }.
Способы задания бинарных отношений
Список пар
= {(1,5), (2,4), (3,6), (6,2)} на Х2, Х = {1,2,3,4,5,6}
Характеристическая функция
= {(n,m)| n = 2*m}
Графическое изображение отношения
={(1,5), (2,4), (3,6), (6,2)} на Х2, Х = {1,2,3,4,5,6}
Матрица отношения для:
={(1,5), (2,4), (3,6), (6,2)} на Х2, Х = {1,2,3,4,5,6}
Свойства бинарных отношений
Пусть задано на множестве X, Х2
Рефлексивность: х Х х х .
Антирефлексивность: х Х х х.
Нерефлексивность: х Х (x, x) .
Симметричность: х, y Х х y => y х.
Антисимметричность: х, y Х х y, y х ?x = y.
Транзитивность: х, y, z Х х y, y z => x z.
Отношение порядка - антисимметрично, транзитивно.
Отношение нестрого порядка - рефлексивно, антисимметрично, транзитивно.
Отношение строгого порядка - антирефлексивно, антисимметрично, транзитивно.
В отношениях полного порядка все элементы сравнимы между собой, а в отношениях частичного порядка не все элементы сравнимы между собой.
Отношение эквивалентности ( ) - рефлексивно, симметрично, транзитивно .
Класс эквивалентности для х : [ x ] = { y Х | x y }
Обратное отношение получается путём перестановки значений в парах исходного отношения.
Композиция отношений и - отношение, состоящее из пар
_ = {(x, z)| х у, y z }
Пример1:
Отношения и заданы на множестве Х = {1, 2, 3, 4, 5, 6,}.
= {(1,4), (2,5), (3,6), (4,1), (6,3)},
= {(1,1), (2,3), (3,4), (4,5), (5,6), (6,6)}.
Область определения D = {1, 2, 3, 4, 6}.
Область значений J = {1, 3, 4, 5, 6}.
Обратное отношение -1 = {(4,1), (5,2), (6,3), (1,4), (3,6)}.
Отношение - антирефлексивно, не симметрично, не транзитивно.
Область определения D = {1, 2, 3, 4, 5, 6}.
Область значений J = {1, 3, 4, 5, 6}.
Отношение - не рефлексивно, антисимметрично, не транзитивно.
Композиция _ = {(1,5), (2,6), (3,6), (4,1), (6,4)}.
Пример2:
Отношение = { (x, y) | сравнение по модулю m, x,y N }.
Отношение сравнения по модулю m на множестве натуральных чисел:
x = y mod m,
что означает x и y имеют одинаковый остаток при делении на m (классы вычетов по модулю m).
Отрезок натурального ряда N4={1,2,3,4}.
Отношение сравнения по модулю 2 на N4 :
= { (1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2) ,(4,4)}.
Область определения D = {1, 2, 3, 4}.
Область значений J = {1, 2, 3, 4}.
Отношение - рефлексивно, симметрично, транзитивно.
Отношение - отношение эквивалентности.
Классы эквивалентности:
[ 1 ]={ 1,3 }=[ 3 ]
[ 2 ]={ 2,4 }=[ 4 ].
Пример3:
Отношения и заданы на множестве N4 .
={ (1,2), (2,3), (1,3), (3,4), (2,4), (1,4) }
={ (1,1),(2,2),(3,3),(4,4) }.
Область определения D = { 1, 2, 3 }.
Область значений J = { 2, 3, 4 }.
Отношение - антирефлексивно,антисимметрично,транзитивно.
Отношение - отношение строгого порядка.
Область определения D = { 1, 2, 3 ,4 }.
Область значений J = { 1, 2, 3, 4 }.
Отношение - рефлексивно, симметрично, антисимметрично, транзитивно.
Отношение - отношение нестрогого частичного порядка.
Отношение - отношение эквивалентности.
Классы эквивалентности:
[ 1 ]={ 1 }
[ 2 ]={ 2 }
[ 3 ]={ 3 }
[ 4 ]={ 4 }.
Функциональные отношения
Пусть Х х Y.
Функциональное отношение - бинарное отношение
х D y Y: х y .
Всюду определённое отношение - отношение, у которого D = Х ("нет одиноких х").
Сюръективное отношение - отношение, у которого J = Y ("нет одиноких y").
Инъективное отношение - отношение, в котором разным х соответствуют разные у.
Биекция - функциональное, всюду определённое, инъективное, сюръективное отношение. Оно задаёт взаимно однозначное соответствие множеств.
Пример:
Пусть = { (x, y) R2 | y2 + x2 = 1, y > 0 }.
Отношение :
· функционально,
· не всюду определено ("есть одинокие х "),
· не инъективно (есть разные х, которым соответствуют одинаковые у),
· не сюръективно ("есть одинокие у "),
· не биекция.
Задания к лабораторной работе №2
по теме: Отношения на множествах
Задание№1
Заданы множества N1 и N2. Вычислить множества:
(N1 х N2) (N2 х N1);
(N1 х N2) (N2 х N1);
(N1 N2) x (N1 N2);
(N1 N2) x (N1 N2),
где N1 = {цифры номера зачетной книжки};
N2 = {цифры даты и номера месяца рождения}.
Задание№2
Найти все отношения на двухэлементном множестве A = {a, b}. Среди них указать:
все рефлексивные;
все антирефлексивные;
все симметричные;
все антисимметричные;
все транзитивные.
Результат свести в таблицу.
Выделить отношения эквивалентности и построить классы эквивалентности.
Выделить отношения порядка и классифицировать их.
Задание№3
отношение множество бинарный эквивалентность
Для ниже приведенных вариантов задания считать, что все отношения и заданы на множестве N6={1,2,3,4,5,6}. Студенту необходимо:
· Описать отношения , , -1, _ , -1 _ списком пар.
· Найти матрицы отношений и .
· Для каждого отношения определить область определения и область значений.
· Определить свойства отношений .
· Выделить отношения эквивалентности и построить классы эквивалентности.
· Выделить отношения порядка и классифицировать их.
Варианты для выполнения задания№3:
= { (m, n) | m > n }
= { (m, n) | сравнение по модулю 2}
= { (m, n) | (m - n) делится на 2}
= { (m, n) | m делитель n }
= { (m, n) | m < n }
= { (m, n) | сравнение по модулю 3}
= { (m, n) | (m + n) - четно}
= { (m, n) | m2=n }
= { (m, n) | m / n - степень 2 }
= { (m, n) | m = n }
= { (m, n) | m / n - четно}
= { (m, n) | m n }
= { (m, n) | m / n - нечетно }
= { (m, n) | сравнение по модулю 4}
= { (m, n) | m n - четно }
= { (m, n) | m n }
= { (m, n) | сравнение по модулю 5 }
= { (m, n) | m делится на n }
= { (m, n) | m - четно, n - четно }
= { (m, n) | m делитель n }
= { (m, n) | m = n }
= { (m, n) | (m + n) 5 }
= { (m, n) | m и n имеют одинаковый остаток от деления на 3 }
= { (m, n) | (m - n) 2 }
= { (m, n) | (m + n) делится нацело на 2 }
= { (m, n) | 2 (m - n) 4 }
= { (m, n) | (m + n) делится нацело на 3 }
= { (m, n) | m n }
= { (m, n) | m и n имеют общий делитель }
= { (m, n) | m 2 n }
= { (m, n) | (m - n) делится нацело на 2 }
= { (m, n) | m < n +2 }
= { (m, n) | сравнение по модулю 4 }
= { (m, n) | m n }
= { (m, n) | m делится нацело на n }
= { (m, n) | m n , m- четно}
= { (m, n) | сравнение по модулю 3 }
= { (m, n) | 1 (m - n) 3 }
= { (m, n) | (m - n) делится нацело на 4 }
= { (m, n) | m n }
= { (m, n) | m - нечетно, n - нечетно }
= { (m, n) | m n , n-четно }
= { (m, n) | m и n имеют нечетный остаток от деления на 3 }
= { (m, n) | (m - n) 1 }
= { (m, n) | m n - нечетно }
= { (m, n) | сравнение по модулю 2 }
= { (m, n) | m n - четно }
= { (m, n) | 1 (m - n) 3 }
= { (m, n) | (m + n) - четно }
= { (m, n) | m не делится нацело на n }
= { (m, n) | m = n }
= { (m, n) | m делится нацело на n }
= { (m, n) | (m - n )-четно }
= { (m, n) | m делитель n }
= { (m, n) | (m - n) 2 }
= { (m, n) | m делится нацело на n }
= { (m, n) | m 2 n }
= { (m, n) | m / n - нечетно}
= { (m, n) | m n, m - четно }
= { (m, n) | m и n имеют общий делитель, отличный от 1 }
Задание№4
Определить является ли заданное отношение f:
Ш функциональным,
Ш всюду определенным,
Ш инъективным,
Ш сюръективным,
Ш биекцией.
Построить график отношения f, определить область определения и область его значений.
Варианты для выполнения задания№4:
f={ (x, y) R2 | y=1/x +7x }
f={ (x, y) R2 | x y }
f={ (x, y) R2 | y x }
f={ (x, y) R2 | y x, x 0 }
f={ (x, y) R2 | y2 + x2 = 1 }
f={ (x, y) R2 | 2| y | + | x | = 1 }
f={ (x, y) R2 | x + y 1 }
f={ (x, y) R2 | x = y2 }
f={ (x, y) R2 | y = x3 + 1}
f={ (x, y) R2 | y = -x2 }
f={ (x, y) R2 | | y | + | x | = 1 }
f={ (x, y) R2 | x = y -2 }
f={ (x, y) R2 | y2 + x2 1, y > 0 }
f={ (x, y) R2 | y2 + x2 = 1, x > 0 }
f={ (x, y) R2 | y2 + x2 1, x > 0 }
f={ (x, y) R2 | x = y2 , x 0 }
f={ (x, y) R2 | y = sin(3x + ) }
f={ (x, y) R2 | y = 1 /cos x }
f={ (x, y) R2 | y = 2| x | + 3 }
f={ (x, y) R2 | y = | 2x + 1| }
f={ (x, y) R2 | y = 3x }
f={ (x, y) R2 | y = e-x }
f ={ (x, y) R2 | y = e| x | }
f={ (x, y) R2 | y = cos(3x) - 2 }
f={ (x, y) R2 | y = 3x2 - 2 }
f={ (x, y) R2 | y = 1 / (x + 2) }
f={ (x, y) R2 | y = ln(2x) - 2 }
f={ (x, y) R2 | y = | 4x -1| + 2 }
f={ (x, y) R2 | y = 1 / (x2+2x-5)}
30) f={ (x, y) R2 | x = y3, y - 2 }.
Контрольные вопросы
1. Декартово или прямое произведение множеств.
2. Определение бинарного отношения.
3. Способы описания бинарных отношений.
4. Область определения и область значений.
5. Свойства бинарных отношений.
6. Отношение эквивалентности и классы эквивалентности.
7. Отношения порядка: строгого и нестрого, полного и частичного.
8. Классы вычетов по модулю m.
9. Функциональные отношения. Инъекция, сюръекция, биекция.
Размещено на Allbest.ru
Подобные документы
Типичные примеры рефлексивных бинарных отношений. Понятие множества и его элементов. Операции над множествами: объединение, пересечение и разность. Декартово произведение множеств. Отношения функциональные, эквивалентности, порядка. Отношения степени n.
контрольная работа [163,2 K], добавлен 08.11.2009Определение, типы и примеры отношений, способы их задания; алгебраическая и геометрическая интерпретации. Разбиение на классы и фактор-множество. Смысл отношения эквивалентности. Теорема о равносильности определений. Отношения в школьной математике.
курсовая работа [1,0 M], добавлен 01.10.2011Эквивалентность, ее формальные свойства и операции над отношениями. Доказательство основных теорем, лемм. Отношения эквивалентности на числовой прямой. Характерные свойства толерантности. Применение эквивалентности и толерантности в сферах различных наук.
курсовая работа [496,5 K], добавлен 20.09.2009Типы бинарных отношений. Изображение графов в виде схемы. Цикл в графе, совпадение его начальной и конечной вершины. Понятие достижимости в теории графов, их математические свойства. Частично упорядоченное множество как один из типов бинарного отношения.
контрольная работа [116,5 K], добавлен 04.09.2010Проведение исследования на уроках обобщающего повторения курса математики в контексте ведущего понятия "порядковая структура". Примеры алгебраических и геометрических бинарных отношений. Включение учащихся в исследовательскую и проектную деятельность.
курсовая работа [1,6 M], добавлен 01.12.2014Бинарные отношения на множестве. Рефлективность, примеры рефлективности. Симметричность, транзитивность, отношение порядка. Примеры дестрибутивных и недестребутивных решеток. Основные определения и свойства теории структур. Операции над множествами.
курсовая работа [64,0 K], добавлен 04.06.2015Понятие множества, его трактование Георгом Кантором. Условные обозначения множеств. Виды множеств, способы их задания. Операции над множествами (пересечение, объединение, разность и дополнение), условия их равенства и основные свойства, отношения.
презентация [1,2 M], добавлен 12.12.2012Математическая теория нечетких множеств, история развития. Функции принадлежности нечетких бинарных отношений. Формирование и оценка перспективного роста предприятия оптовой торговли. Порог разделения ассортимента, главные особенности его определения.
контрольная работа [22,3 K], добавлен 08.11.2011Основополагающие понятия теории графов и теории групп. Определение эквивалентности, порождаемой группой подстановок, и доказательство леммы Бернсайда о числе классов такой эквивалентности. Сущность перечня конфигурации, доказательство теоремы Пойа.
курсовая работа [682,9 K], добавлен 20.05.2013Определение корня первого и второго многочлена, вычисление предела функции. Применение правила Лопиталя (предел отношения функций равен пределу отношения их производных). Пример использования замечательного предела, который применяется в виде равенства.
контрольная работа [95,5 K], добавлен 19.03.2015