Лабораторная работа: Отношения на множествах

Дисциплина

ДИСКРЕТНАЯ МАТЕМАТИКА

Лабораторная работа № 2

Отношения на множествах. Отношения, связывающие элементы множеств

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

Теоретические сведения

Прямое (декартово) произведение множеств Х и Y - множество упорядоченных пар, таких что:

Х x Y = {(x,y)| xX, yY}.

При X = Y множество X х X называется декартовой степенью

множества X и обозначается X².

Отношением на множествах X и Y называется произвольное

подмножество прямого произведения этих множеств

Х x Y = {(x,y)| xX, yY}.

Если Х², то отношение задано на множестве Х.

Если (x,y), то (x,y) находятся в отношении или связаны отношением х y или y = (х) .

Область определения D бинарного отношения - множество первых элементов каждой упорядоченной пары D = {x | (x,y) }.

Область значений J бинарного отношения - множество

вторых элементов каждой упорядоченной пары

J = {y | (x, y) }.

Способы задания бинарных отношений

Список пар

= {(1,5), (2,4), (3,6), (6,2)} на Х², Х = {1,2,3,4,5,6}

Характеристическая функция

= {(n,m)| n = 2*m}

Графическое изображение отношения

={(1,5), (2,4), (3,6), (6,2)} на Х², Х = {1,2,3,4,5,6}

Матрица отношения для:

={(1,5), (2,4), (3,6), (6,2)} на Х², Х = {1,2,3,4,5,6}

Свойства бинарных отношений

Пусть задано на множестве X, Х²

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

Антирефлексивность: х Х х х.

Нерефлексивность: х Х (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).

Отрезок натурального ряда N₄={1,2,3,4}.

Отношение сравнения по модулю 2 на N₄ :

= { (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:

Отношения и заданы на множестве N_{4 .}

={ (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) R² | y² + x² = 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

отношение множество бинарный эквивалентность

Для ниже приведенных вариантов задания считать, что все отношения и заданы на множестве N₆={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) | m²=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 ² 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 ² n }

= { (m, n) | m / n - нечетно}

= { (m, n) | m n, m - четно }

= { (m, n) | m и n имеют общий делитель, отличный от 1 }

Задание№4

Определить является ли заданное отношение f:

Ш функциональным,

Ш всюду определенным,

Ш инъективным,

Ш сюръективным,

Ш биекцией.

Построить график отношения f, определить область определения и область его значений.