Материал: Дискретная математика. методические указания к выполнению лабораторных работ для студентов направления подготовки «Информатика и вычислительная техника». Собенина О.В., Пак А.А

2.Даны два множества, заданные перечислением своих элементов. Определить декартовое произведение этих множеств.

3.Получить семейство множества, заданного, перечислением своих элементов.

4.Выяснить является ли данное множество подмножеством множества.

5.Выяснить является ли множество собственным подмножеством.

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

Примеры решения задач

1. Задача 1. Определить свойства отношения R={(x,y)| x,y R и x+2=y+1}. Отношение задано на множестве действительных чисел R.

Решение.

1. Проверим отношение на рефлексивность.

Условие (x,x) R для данного отношения принимает вид x+2=x+1. Полученное соотношение не выполняется ни для одного значения x R. Поэтому данное отношение является антирефлексивным.

2. Проверим отношение на симметричность. Условие (x,y) R для данного отношения принимает вид x+2=y+1. Условие (y,x) R для данного отношения принимает вид y+2=x+1.

Получаем систему уравнений и исследуем ее на совместность.

6

Из первого уравнения x+2=y+1 получим x+2+1=y+1+1, x+3=y+2. Из второго уравнения системы y+2=x+1, т. е. получаем x+3=x+1, что не является верным ни для одного значения x R. Таким образом, отношение является антирефлексивным.

Опровергнуть свойство можно используя прием контрпримера. Для этого возьмем, например, пару (3,4). Она принадлежит рассматриваемому отношению, так как выполняется условие 3+2=4+1. Проверим принадлежит ли отношению пара (4,3). Так как 4+2 3+1, то отношение не является симметричным.

3. Проверим отношение на транзитивность. Составим систему уравнений, соответствующую определению транзитивности:

x 2 y 1,

y 2 z 1,

x 2 z 1.

Из первого и второго уравнений системы исключим y: y+2=z+1, y=z-1, x+2=z-1+1, x+2=z.

Полученное соотношение не совпадает с третьим уравнением системы. Следовательно, отношение не является транзитивным.

Задача 2.

Отношение R задано матрицей, которая имеет вид.

Является ли данное отношение эквивалентностью. Для отношения эквивалентности определить классы эквивалентности.

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

Переставляя строки и столбцы, попробуем привести матрицу отношения R к блочно-диагональному виду. Поменяем местами столбцы b, d и строки b, d, получим

7

Поменяем местами столбцы с, b и строки с, b, получим

Матрицу отношения привели к блочно-диагональному виду, значит, R является эквивалентностью, и по полученной матрице можно определить классы эквивалентности К1 ,К 2 ,К 3 .

Таким образом К1 = {а, d}, К 2 = {b}, К 3 = {с, е, f}.

Практическая часть Задание 1

Определите свойства отношения. Отношение задано на множестве действительных чисел R.

Варианты

1.R={(x,y)| x,y R и x - y<0}.

2.R={(x,y)| x,y R и x+y 0}.

3.R={(x,y)| x,y R и x = y}.

4.R={(x,y)| x,y R и x = y2}.

5.R={(x,y)| x,y R и x 2 =y}.

6.R={(x,y)| x,y R и |x –y| 3}.

8

7.R={(x,y)| x,y R и x3 = y}.

8.R={(x,y)| x,y R и x = y3}.

9.R={(x,y)| x,y R и x +5>3 – y}.

10.R={(x,y)| x,y R и |x| | y|}.

11.R={(x,y)| x,y R и x2 = y2}.

12.R={(x,y)| x,y R и x >y2}.

13.R={(x,y)| x,y R и x3 = y3}.

14.R={(x,y)| x,y R и x y+1}.

15.R={(x,y)| x,y R и x2 +y2=1}.

16.R={(x,y)| x,y R и x y }.

17.R={(x,y)| x,y R и x 2y }.

18.R={(x,y)| x,y R и x+2 y+1}.

19.R={(x,y)| x,y R и x-5 y+3}.

20.R={(x,y)| x,y R и 2x 3y}.

Задание 2

Для отношения, заданного матрицей, определить является ли оно отношением эквивалентности. Если является, то определить классы эквивалентности.

9

10