elem_mat_copy

4.Какими свойствами обладают соответствия:

б)	:	→	,	:				;
a)	:	→	,	:				;
в)			,					;
г)	:	→	,	:				;
д)	:	→	,	:	|	|			;
е)	:	→	,	:	√		;
	:	→		:	3

Практическое занятие №13

Бинарные отношения и их свойства

		Отношения
Если дано соответствие				и X = Y, то f называют
отношением во множестве X.			Примерами отношений в R могут
			= А, ,У		( > );
служить:	и т.п(.	= );	( ≠ );
( )	и т.д.				( || )
Если X = М, где М ― множество прямых, то					;

( )

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

Отношение f на множестве X называют рефлексивным, если

, хfx.

R

,

x X

R

61

П р и м е р

1: Пусть

,

. Это отно-

шение рефлексивно, т.к.

каждое действительное число, отлич-

=

\{0}

(

)

ное от нуля, делится само на себя, т.е.

.

Отношение f на множестве X

называют антирефлексив-

(

)

ным, если

, то есть график этого отношения не со-

одной пары вида

, или ни один элемент не имеет

держит ни

, х

,

«петли».

П р и м е р

2: Пусть

,

. Это отношение

антирефлексивно,

так как

любое действительное число не больше

=

у

>

самогосебя.

Отношение f на множестве X называют симметричным, если

,

.

x

y

,

,

График симметричного отношения вместе с парой

содержит и пару

, или же: если есть стрелка из х в у, то, и

есть стрелка и из y в,x.

П р и м е р 3:

Если X = М,

, то это отноше-

прямая x параллельна пря-

ние будет симметричным, так как если ( ||

)

мой y, тои прямая y параллельна прямой x.

Отношение f на множестве X называют асимметричным,

этого

,

:(

)& (

)

одновременно, то есть если график

если

отношения содержит пару

,

то не содержит пару

,

или, если из x в y приходит стрелка,, то

из y в x ее нет.

П р и м е р 4:

Пусть

,

. Это отноше-

у.

может быть больше

ние асимметрично, так как если=х < у, то x не(

<

)

62

Отношение f на множестве X называют антисимметрич-

ным, если

из того, что

Этоотношение

П р и м ,е р 5:

Пусть

(,

)& (

=

) .( = ).

антисимметрично.

(

≤

)

отношение является и ан-

Ясно, что всякое асимметричное

тисимметричным, но не наоборот.

,

Отношение на множестве X называют транзитивным, если

,

из того, что (

)&(

) f(

).

f

y

x

f

z

П р и м е р 6:

Отношения х< у, х = у, х > у, х || у — тран-

зитивны.

f

X называют связным, если

Отношение

на множестве

,

(

) (

) ( = ).

П р и м е р 7:

Пусть X = N,

. Это отношение

рефлексивно,

так как

)&

(

)

, антисимметрично( ) , так как

,

,

если

(

( = ),

транзитивно, так как

(

)

если

,

не

связно,

так как

,

:

,

&

.

&(

≠

)

(например)

,

7,12

:

7 12

&

,

(

)&(

)

,

&

12 7

&(7 ≠ 12)

Упражнения

1.Какимисвойствами обладаютотношениянамножествеR?

ба))

(

=

);;

в)

(|

| = |

|);

г)

(

>

;)

д)

(

= 3 ) ;

e)

(

+

) 2

;

ж)

(

=

;

)

(√

=

√ )

63

и) ( = − ).

2.Привести пример антирефлексивного, антисимметричного и транзитивного отношения на множестве R .

3.Какими свойствами обладают отношения: х у, х||у на множестве прямых?

Практическое занятие №14

Отношения эквивалентности и порядка. Фактор-множество

Приведем таблицу классификации отношений по их свойствам:

Реф-	Сим-	Антисим-	Асим-	Транз-	Связ-	Название
ть	ть	ть	ть	ть	ть
						Отноше-
+	+			+		ние экви-
						валентно-
						сти
						Отноше-
			+	+		ние стро-
						гого по-
						рядка
						Отноше-
+		+		+		ние не-
						строгого
						порядка
						Отноше-
			+	+	+	ние линей-
						ного по-
						рядка

64

П р и м е р ы:		Отношение			на множестве R ― нестро-
гого порядка,		― строгого	порядка, х = у ― отношение эквива-
	<			≥
лентности.

Систему S непустых подмножеств заданного множества A будем называть разбиением множества А, если каждый элемент множества А принадлежит одному и только одному подмножеству из системы S. Подмножество из S называются смежными классами разбиения S.

С каждым разбиением S мы свяжем бинарное отношение φ на множестве А, полагая, по определению, тогда и только тогда, когда x и y принадлежат одному и тому же смежному клас-

су множества А.

Изобразим множество А в виде квад-

рата, а смежные классы ― в виде прямо-

угольников, на которые разбивается квад-

рат. Имеем, что

тогда и только тогда,

когда x и y принадлежат одному и тому же

x

y

прямоугольнику.

Ясно,

что отношение

является отношением

эквивалентности.

Оно называется отношением эквивалент-

ности, отвечающим разбиению S.

Совокупность всех смежных классов множества А по от-

ношению эквивалентности

обозначается через

/

и называет-

ся фактор-множеством от А по .

Однозначное отображение

, при котором каждый

элемент

переходит в

содержащий его смежный класс

,

→

/

/ .

[

]

называется каноническим отображением А на

Упражнения

1.Доказать, что всякое симметричное, транзитивное, всюду определенное отношение является отношением эквивалентности.

2.Построить отношение эквивалентности на множестве Z.

65

3.	Доказать, что отношение										на множестве
	Z есть отношение				эквивалентности. Построить фактор-
									(	− ) 5
	множество по этому					отношению.
4.	аНайти)	фактор-множество,					/ , если;			:
	б)	(«sinx и y= sin				)	=
5.			= {	имеют одинаковые остатки при делении
				|		≤ 10}		.
	на 7»,
	Доказать, что любые два смежных класса из фактор-
	множества		/	общих элементов не имеют.

Практическое занятие №15

Самостоятельная работа по теме «Соответствия и отношения»

1.	Докажите, что бинарное отношение									(	)
						:	→	найдите
	задает отображение						= lg (,				.
									+1)
2.				, где			.		{0,−1}	при отображении
	Найдите прообраз множества								{0,−1}
3.		:	→	, где	( ) =			.		при отображении
	Найдите прообраз множества
4.	а)	:	→	, где	= cos +1;
	Определите тип( отображения)							:
	б)	:	→	, где	( ) =		+1	;
	в)	:	→	, где	( ) =		.+3
		:	→		( ) =

5.Найдите обратные соответствия для следующих функций:

	ба))	= 3 − 5,		; ;
	в)	= 3 ,						.
				−2 ;			2
		= sin	,					66

Практическое занятие №16 n-арные операции на множествах. Бинарные операции и их свойства

§4. Операции на множествах и их свойства

Основные знания, умения, и навыки, которыми должны овладеть студенты в процессе изучения данной темы:

знать основные операции на множествах;

знать определение бинарной операции на множестве;

знать и понимать свойства бинарных операций.

Основные понятия темы: n-арная операция, бинарная

операция.

О п р е д е л е н и е 1: Отображение :А → А множества

Аn в множество А называется n-арной (n-местной) операцией f,

заданной на множестве А. Число n называется рангом операции. Из этого определения следует, что n-арная операция является

всюду определенным, функциональным соответствием, т.е. всю-

ду определенной функцией n переменных со значением из множества А.

Действие этой функции на элементы множества А обозначают так:

Элементы		( , ,…, )
	, ,…,		называют операндами, а значение
функции			― результатом операции f.
В частности( , ,,…при,		= 0 операцию f называют нуль-арной, ее
		n) =

смысл состоит в том, что на множестве А выделяется (фиксируется) некоторый элемент. При n = 1 операцию f называют унарной, она является отображением f: А А. При n = 2 ― бинарной, она является отображением f: А2 А. При n = 3 ― тернарной, она представляет собой отображение f: А3 А.

Например, нуль-арными операциями будут: операция фиксации 1 на множестве N натуральных чисел, или операция фиксации 0 на множестве Z целых чисел; унарными операциями являются операция возведения в целую степень, а аn на множестве Q ра-

67

циональных чисел, или операция взятия противоположного элемента а (-а) на множествеZ целых чисел.

В математике чаще всего рассматриваются бинарные операции. Результат бинарной операции f(a,b) обычно записывают в виде a f b . Вместо буквы f в конкретных случаях используют специальные знаки и символы:

	+, –,				, : ― для операций над числами;
							― для операций над множествами;
			,	∙	, \			― для операций над высказываниями;
	&,―,для ,композиции отображений.
2	Из определения n-арной									операции следует, что соответствие
f: А А является бинарной операцией тогда и только тогда, когда
истинныследующиеусловия:
1. (а,b) А2									с А | a f b = с ― условие выполнимости
		операции на множестве (всюду определенности).
2.		(а,b) А2							с, d A | (a f b = с) & (a f b = d) (с =
		=d) ― условие однозначности операции (функционально-
		сти).
	З а м е ч а н и е. Если условие 2) не соблюдается, т.е.
3.		(а,b) А2							с, d A | (a f b = с) & (a f b = d)&(с d) ,
		то соответствие f не является операцией, более того ―
		отображением.
	Если не соблюдается условие 1), соответствие f не явля-
ется всюду определенным, т.е.											(а,b) А2 | с A, (a f b c)
или		(а,b)				А	2	| (a f b = с) &(с
											A), то мы приходим к следую-
щему определению:										Функцию f: А2 А называют час-
	О п р е д е л е н и е 2:

тичной бинарной операцией на множестве А (частично выполни-

мой на множестве А операцией), если она не является всюду определенной.

П р и м е р 1: Арифметическая операция вычитания целых чисел на множестве натуральных чисел N не всегда выполнима,

так как		(а,b)		N	2	|
							(a-b) N, то есть эта операция ― частична.
В то же время она ― однозначна, так как
(а,b) N2			с, d N | (a – b = с) & (a – b = d) (с = d)
							68

П р и м е р 2: Арифметическая операция деления рациональных чисел на множестве Z целых чисел также частично выполнима. Например, результат деления целых чисел 3 и 5 не является целым числом.

О п р е д е л е н и е 3: Если на множестве А задана бинарная операция * и непустое подмножество В множества А таково, что а, b В, а * b В, т.е операция *, заданная на А, выполнима на его подмножестве В, то такое подмножество В называется замкнутым относительно операции *. В этом случае говорят так-

же, что операция * не выводит за пределы множества В.

П р и м е р 3. Относительно операции умножения целых чисел множество всех положительных целых чисел замкнуто, а множество всех отрицательных целых чисел незамкнуто.

Иногда свойство замкнутости множества относительно операции считают эквивалентным свойству выполнимости операции на множестве.

Упражнения

1.Являются ли операциями и какого ранга следующие действия:

а)вычисление десятичных логарифмов на множестве R;

б) вычисление среднего геометрического двух чисел на множестве положительных действительных чисел;

в) вычисление среднего арифметического трех чисел на множестве Q;

г) вычисление наибольшего общего делителя 2-х чисел на множестве N;

д) скалярное умножение на множестве векторов плоскости

.

2.Какие из арифметических операций +, –, ∙, : являются выполнимыми:

а)на множестве {-1, 0, 1 };

б) на множестве N натуральных чисел; в)на множестве Z целых чисел;

г) на множестве Q рациональных чисел;

69

д) на множестве R действительных чисел, е) на множестве I иррациональных чисел.

Практическое занятие №17

Исследование свойств бинарных операций на числовых множествах

Важными свойствами бинарной операции являются свойст-

ва ассоциативности, коммутативности, существования нейтрального элемента (левого, правого, двухстороннего), существования обратного элемента (левого, правого, двухстороннего), наличие нулей и идемпотентов. Сформулируем основные свойства бинарных операций в виде условий, называемых также аксиомами:

А1. Аксиома ассоциативности:

а, b,с А, (а * b) * с = а * (b * c);

А2. Аксиома коммутативности:

а, b А, а * b = b * a;

A3. Аксиома существования левого нейтрального элемента:

e' A | a A, e' * a = a;

A4. Аксиома существования правого нейтрального элемента:

e'' A | a A, a * e''= a;

А5. Аксиома существования нейтрального элемента (двухстороннего):

е А | а А, е *а= а*е =а;

А6. Аксиома левого симметричного элемента:

a A а' А | а'*а= e;

А7. Аксиома правого симметричного элемента:

a A а'' А | а*а''=e;

А8. Аксиома существования симметричного элемента (двухстороннего):

a A ′ А | ′ * а = а * ′= е.

70