Рефлексивным замыканием	R1	отношения	R2	называется
R2 U , где U – отношение тождества.
Симметричным замыканием R1 отношения			R2	называется
R I = I .
Транзитивным замыканием	R1	отношения	R2	называется
R2 R2 [R2 ] R2 [R2 [R2 ]] .

Используя свойства бинарных отношений, можно доказать следующую теорему [2].

Теорема 1.6. Пусть R бинарное отношение на М, R M × M . Тогда:

1)R рефлексивно тогда и только тогда, когда U R ;

2)R симметрично тогда и только тогда, когда R= R−1 ;

3)R транзитивно тогда и только тогда, когда R[R] R ;

4) R антисимметрично тогда и только тогда, когда

R ∩ R−1 U ;
5)	R антирефлексивно тогда и только	тогда, когда
R ∩U ;
6)	R линейно тогда и только тогда, когда	R U R−1 = I ,
где U – отношение тождества, а I – универсум.

Контрольные вопросы и задания

1.1. Даны множества А, В и С. Определить по кругам Эйлера – Венна результат применения операций над ними в указанных трех случаях (рис. 1.19).

A	A		A		A
		B		B		B
	C		C		C
	a		б			в
			Рис. 1.19

33

1.2. Даны множества I = {a, b, c, d, e, f}, A ={a, c, e}, B={b, d, f}, C={a, b, e, f}. Вычислить результат операций:

A B C ;

A B C ;

A B C ;

(A B) C .

1.3. Даны множества А (треугольник), В (квадрат) и С (овал). Определите через операции объединения, пересечения, дополнения, разности и симметрической разности, чему равна заштрихованная область в указанных четырех случаях (рис. 1.20).

C	A	C	A
	B		B
	а		б

A	A
C	C
B	B
в	г
	Рис. 1.20

1.4.Дано множество M={a, b, c, d, e}. Найти все его подмноже-

ства.

1.5.Дано множество M={a, b, c, d, e}. Найти все его собственные подмножества.

1.6.Определить мощность булеана для M = {a, b, c, d, e}.

34

1.7.Определить мощность декартова произведения для M и N,

если |M| = 10, а |N| = 25.

1.8.Построить декартово произведение M и N, если M = {a, b, c}

иN = {a, d, e}.

1.9. Нарисовать круги Эйлера – Венна для A (B / C) ,

A /(B / A) .

1.10. Для заданных множеств I={1,2,3,4,5,6,7,8,9}, A={1,3,5,7,9}, B={1,2,3,8,9} и C={2,3,5,6,9} вычислить множества:

•A ∩ B C ;

•A ∩ B C ;

•A ∩ B C ;

•A ∩ B C .

1.11. Дополните следующие определения.

а) Бинарное отношение T(M), заданное на множестве М, называется отношением эквивалентности тогда и только тогда, когда оно...

б) Бинарное отношение T(M), заданное на множестве М, называется классом эквивалентности тогда и только тогда, когда оно...

в) Бинарное отношение T(M), заданное на множестве М, называется отношением упорядоченности тогда и только тогда, когда оно...

г) Бинарное отношение T(M) заданное на множестве М, называ-

ется отношением строгой упорядоченности тогда и только тогда,

когда оно...

д) Бинарное отношение T(M) заданное на множестве М, называется линейно упорядоченным тогда и только тогда, когда оно…

е) Бинарное отношение T(M) заданное на множестве M, называется отношением толерантности тогда и только тогда, когда оно…

1.12.Построить бинарное отношение R(M) и определить его свойства. M = {1,2,..,10}, R = {(a, b)/ res(b, a) = 0}

1.13.Построить бинарное отношение R и определить его свой-

ства. M = {1,2,..,10}, R = {(a, b)/ res(b, a) = 1}

1.14.Построить бинарное отношение R(M) и определить его свойства. M = {1,2,..,10}, R= {(a, b)/ res(a+1, b) = 0}.

35

1.15.На множестве M1 = {a, b, c, d, e, f} построить бинарное отношение толерантности R, при условии, что (a, b) R; (a, c) R .

1.16.На множестве M1={a, b, c, d, e, f} построить бинарное отношение эквивалентности R, при условии, что (a, b) R; (a, c) R .

1.17.На множестве M1 = {a, b, c, d, e, f} построить бинарное отношение частичного порядка R, при условии, что (а, b) R, (a, c) R.

1.18.На множестве M1 = {a, b, c, d, e, f} построить бинарное от-

ношение линейного порядка R, при условии, что (а, b) R, (a, c) R. 1.19. Дана диаграмма Хассе частично упорядоченного множест-

ва ≤ M (рис. 1.21).

Установите соответствие между экстремальными характеристиками и элементами для выделенного подмножества {c, f, m} и заполните таблицу.

		b	c
a	n	m	d	е
		g	f	Рис. 1.21
Минимальные эле-			Миноранты
менты
Максимальные эле-			Мажоранты
менты
Наибольший эле-			Точная нижняя
мент			грань
Наименьший эле-			Точная верхняя
мент			грань

1.20.Дано множество натуральных чисел. Укажите, какие из арифметических действий (сложение, вычитание, умножение, деление) всегда выполнимы на этом множестве?

1.21.Дано множество четных натуральных чисел. Укажите, какие из арифметических действий (сложение, вычитание, умножение, деление) всегда выполнимы на этом множестве?

36

1.22.На множестве натуральных чисел задано отношение равенства (а=b). Какими свойствами (рефлексивность, симметричность, транзитивность) обладает это отношение?

1.23.На множестве натуральных чисел задано отношение больше или равно (а≥b). Какими свойствами (рефлексивность, симметричность, транзитивность) обладает это отношение?

1.24.На множестве нечетных натуральных чисел задано отношение меньше (а<b). Какими свойствами (рефлексивность, симметричность, транзитивность) обладает это отношение?

1.25.Задано множество X={a,{b,c}}. Выделите все элементы и все подмножества для этого множества.

1.26.Задано множество X = {a,{a,b}}. Выделите все элементы и все собственные подмножества для этого множества.

1.27.Задано множество X = { ,{ }}. Выделите все элементы и все подмножества для этого множества.

1.28.Определить свойства бинарного отношения T, заданного на множестве M2 = {a, b, c, d, e, f} (рис. 1.22).

b f

a

е

c d

Рис. 1.22

1.29. Определить свойства бинарного отношения T, заданного на множестве M2 = {a, b, c, d, e, f} (рис. 1.23).

b f

a

е

c d

Рис. 1.23

37

1.30. Определить свойства бинарного отношения T, заданного на множестве M2 = {a, b, c, d, e, f} (рис. 1.24).

b	f
a	е
c	d

Рис. 1.24

1.31. Даны бинарные отношения А и В, заданные на множестве

M={a,b,c}. Найти: A ∩ B ; A B ; A[B] ; B[A] ; A−1 ; B ; A × B (рис. 1.25).

a	a
A
b	b
c	c
	Рис. 1.25

B

1.32. На множестве натуральных чисел задана операция . Какой может быть эта операция?

а) a	b = ab;
б) a b = a + b;
в) a b = a – b;
г) a	b = a b;
д) a b = a / b;
е) a b = a2 + b2;
ж) a	b = NOD(a,b);

з) a b = a2 – b2;

38

и) a b = –2 (a2 + 2b).
1.33. На множестве рациональных чисел задана операция	.

Какой может быть эта операция?

а) a	b = ab;
б) a b = a + b;
в) a b = a – b;
г) a	b = a b;
д) a b = a / b;
е) a b = a2 + b2;
ж) a	b = NOD(a,b);
з) a	b = MOD(a,b);

и) a b = -2 (a2 + 2b).

1.34. Дано множество, равное пересечению A ∩ B следующих множеств (рис. 1.26):

A ={(x, y) R2 : x ≥ 0, y ≥ 0, x + y ≤ a} ; B ={(x, y) R2 : 0 ≤ x ≤ a,0 ≤ y ≤ a}.

Укажите, какой графический вид оно имеет?

Рис. 1.26

39