elem_mat_copy

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

Самостоятельная работа по теме «Множества и элементы комбинаторики»

1.В конкурсе красоты участвуют 20 девушек. Сколько может быть вариантов распределения пяти призовых мест в этом конкурсе?

2.Сколькими способами 10 человек могут встать в очередь друг за другом?

3.Найти:

а) шестой член разложения бинома			(3+	;
б) два средних члена разложения	бинома			)	.
		(1 −2 )

4.Записать разложение бинома (2− с) .

5.В селении проживают 2000 жителей. Доказать, что по крайней мере двое имеют одинаковые инициалы.

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

Бинарные соответствия и операции над ними

§3. Соответствия и отношения

Основные знания, умения и навыки, которыми должны овла-

деть студенты в процессе изучения этой темы:

понимать смысл неопределяемых понятий «соответствие», «отношение»;

знать свойства соответствий и отношений, уметь их определять и приводить конкретные примеры;

знать основные типы соответствий и отношений.

Основные понятия темы: соответствие, отношение.

51

Пусть даны два произвольных множества X, Y.

Y

X

x

y

Тройка множеств

, где

, будем назы-

вать бинарным

соответствием между множеством X и Y, мно-

=

,

,

×

жество A ― его графиком, множество X ― областью отправле-

ния, Y ― областью прибытия.

Если

, то говорят, что элемент x находится с эле-

ментом y в

соответствии f и пишут x f y, то есть

,

,

.

З а м е ч а н и е:

Часто понятие бинарного соответствия

определяют как любое( )

подмножество А множества

×

,

то

есть отождествляют его с графиком соответствия.

определения

(

)

{

|

:

}

называют

областью

Множество

|

:

}

соответствия f.

Множество

называют

областью

значения соответствия( )f. {

жествП р и м е р ,

1.

Пусть

=

,

=

. Тогда тройка мно-

где

и

будет

задавать=соответствие, ,

между множествами R и R, графиком

×

=+

{ ,

|

}

которого будет.

парабола. D(f)=R, E(f)=R

. ,

=

R

,

R

52

,

.

=

,

=

.

= { , | ≥ }

.

П р и м е р

2: Пусть

×

≥

График

этого

соответствия

пред-

ставляет собой полуплоскость.

R

A

Множество					называют полным об-
разом элемента x при( )соответствии{ |			f.	,	}
Множество						полным
			,	}	называют
прообразом элемента у	(при)	соответствии{ |			f.	( ) ,
Из определения.	(	) и	(	) следует, что

( )

П р и м е р 3: Пусть X ― множество студентов в аудитории, У ― множество столов, за которым они сидят. Зададим соответствие х f у «студент x сидит за столом y». Тогда:

1.Областью отправления этого соответствия будет множество всех студентов в аудитории;

2.Областью определения ― множество студентов, которые сидят за столами;

3.Областью прибытия ― множество столов в аудитории.

4.Областью значений ― множество столов, за которыми сидит хотя бы один студент;

5.Графиком соответствия будет множество пар «студентстол»

6.Полным прообразом студента х будет стол, за которым он сидит;

53

7.Полным прообразом стола у будут все студенты, которые за нимсидят.

П р и м е р 4:

		2	Y
	X a		5
			4

b с1 3

Этот рисунок задает соответствиемеждумножествами:
График этого= { а,		,с }	и	= {1,2,3,4,5}.
	соответствия			=, {	,2 , ,2,,		,1 }	.	( ) =,
= { , , }, ,	( ) = 2,	(,	) = 2			,(с ) = 1	(,	) = {1,2}
(.1) =	(2) = { ,	}		(3) = Ø		(4) = Ø			(5) =
= Ø

Из рассмотренных выше примеров видно, что соответствие может быть задано:

а) путем указания подмножества A X Y (графически); б) аналитически; х f у у = f (х);

в) с помощью графов или таблиц.

Графом называют множество точек, некоторые пары из которых соединены линиями с направлениями (см. пример 4).

Операции над соответствиями

Понятие бинарного соответствия тесно связано с понятием двухместного предиката. Если Р(х,у) ― двухместный предикат, в котором переменная х пробегает множество X, переменная у ― множество У, а Т ― множество истинности этого предиката, то тройка множеств Т, ,У будет задавать соответствие между X и

У.

54

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

предыдущем параграфе для предикатов.
Пусть даны два соответствия:		,			.
	противоположными, если их гра-
Эти соответствия называются		= , ,У	=	, ,
фики взаимно дополняют друг друга в множестве Х			У,	или	на

«языке» предикатов ― соответствующие им предикаты Р(х,у) и Q (х,у), взаимно отрицают друг друга.

Например, для соответствия «х f у х < у» противополож-

ным будет соответствие	«х f у			».
			х у
Действительно, графики		этих соответствий ― взаимно до-
			≥
полняющие множества	R R ― и отрицание предиката «x<y»
есть предикат «x≥y».				R
R

R

Объединением соответствий f и g называют соответствие,

графиком

которого

является объединение графиков А и В

и

которому

соответствует

дизъюнкция предикатов

(Р(х,у))и Q(x,y): (Р(х,у) Q(x, у)).

Аналогично

определяется пересечение соответствий.

«хfу х у» и «хfу

Например,

для

соответствий

х

у»

их

объединением будет

соответствие «хhу

((х

у)

(x

у)) с графиком R

―

≥

(х

R, а пересечением

«х S у

х R}.

≤

у) & (х

у)» с графиком А ={{х, х} /

55

Для каждого соответствия

можно опреде-

лить обратное-1

соответствие f

1 между У и X следующим обра-

=

,

,У

зом: у f x

x f у, иначе ― пара

,

принадлежит графику со-

ответствия f -1 тогда и только тогда

, когда

пара

-1

.

Можно сказать, что граф соответствия f ,

получается из

графа соответствия f изменением направления всех стрелок.

Например, если х f у «прямая х касается окружности у»,

то у f -1

x

«окружность у

касается прямой х».

Определим операцию композиции

двух

соответствий

= , ,У ,

= , , :

X	f	Y	g	Z
x		y		z

Обозначим через С график композиции соответствий f и g. Тогда

x,z C df y Y :x, y A& y,z B.

На «языке» графов это означает, что точки (х) и (z) соединяются стрелками в том случае, если соединены стрелками

точки (х) и (у), (у) и (z).			x( f g)
Короче ― x X								.
П р и м е р: Пусть хfу					«у=х2	», y g z				z=y+2».
Тогда х(fg)z		«z = х2		+ 2». (			)		«

Упражнения

1.Даны два множества: N и R. Задать различные бинарные соответствия между этими множествами различными способами.

56

2.	Дано соответствие						. Изобразить
	график соответствия:.			Определить область отправления,
					→	, :	+1
	область прибытия, область значений, область опреде-
	ления.			,	:
3.	Даны два соответствия
	Найти	:	→				и .
		:	→ ,		:	3	+5
		композицию			и построить ее график.

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

Свойства и типы соответствий

Виды соответствий

Соответствие

если:

,У

называется всюду определен-

ным на множестве X,

= А,

а)

=

( )

, то есть:

: у=f(x), или на «языке»

полного образа элемента;

в)

( ) ≠

б)

, или на «языке» графов;

из каждого элемента множества X выходит стрелка и прихо-

дитвY.

называют сюръективным, если:

Соответствие

а)

=

( )

,

то есть

: хfу

у=f(x), или на

языке полного прообраза;

-1

в)

в

( ) ≠

б)

, или на «языке» графов;

каждый элемент множества Y приходит стрелка из X.

Если f

― всюду определенно на X, то f

― сюръективное

соответствие Y на X, если f ― сюрьективно, то f -1 всюду определенно на Y.

Соответствие f называют функциональным, если:

а) x X R(x) содержит не более одного элемента, то есть x X y1, y2 Y (xfy1)&(xfy2 ) (y1 y2 );

б) на языке графов это означает, что из каждого элемента множества X не выходит две стрелки и более.

57

Соответствие f называется инъективным, если:

а) y Y R 1 (y) содержит не более одного элемента, то есть y Y x1,x2 X (x1 fy) &(x2 fy) (x1 x2 );

б) на «языке» графов это означает, что в каждый элемент множества Y приходит неболее одной стрелки.

Из этих определений следует, что соответствие, обратное функциональному, ― инъективно, а обратное инъективному ― функционально.

Если f и g ― всюду определенные, функциональные, инъ-

ективные и сюръективные соответствия, то		― тоже будет
обладать всеми этими свойствами.

П р и м е р 1: Соответствие на рисунке

а) не всюду определено; б) функционально; в) инъективно; г) сюръективно.

П р и м е р 2: Пусть X ― множество студентов в аудитории.

Y ― множество стульев. Зададим соответствие x f y «студент x

сидит на стулеy».

Это соответствие будет:

X Y

x y

58

а) всюду определенным, если каждый студент будет сидеть; б) сюрьективным, если все стулья заняты;

в) функциональным, если каждый студент не сидит на двух стульях; г) инъективным, если на каждом стуле не сидят два студента.

П р и м е р 3: Пусть х f у (у = sin х), X = R, Y = R. То-

гда графиком этого соответствия будет синусоида:

Соответствие это будет:

а) всюду определено, так как : (у = sin х) (любая прямая, параллельная оси ОY, пересекает график функции хотя бы в одной точке).

б) функционально, так как							состоит из одного элемента
(любая прямая,	параллельная оси ОУ, пересекает график
					( )
функции в единственной точке).
в) не инъективно, так как						, для которых R -1(у) состоит
более чем из одного		элемента (существуют прямые, парал-
лельные оси ОХ, которые пересекают график множество раз).
г) не сюръективно, так как						, для которых не существует
х: у=sinx (существуют
		прямые, параллельные оси ОХ, которые

не пересекают график ни в одной точке).

Рассмотренные выше свойства соответствий (инъективность, сюръективностъ и т.п.) позволяют классифицировать все соответствия на определенные типы. Приведем классификацию соответствий по свойствам в виде таблицы:

59

Функ-

Всюду оп-

Инъек-

Сюръек-

Название

циональ-

ределен-

тивность

тивность

ность

ность

+

Функция

типа

X Y

+

+

Отображение

из X в Y

Вложение

+

+

+

(инъекция)

X в Y

Наложение

+

+

+

(сюръекция)

X на Y

+

+

+

+

Биекция

X на Y

Из этой таблицы видно, например, что отображение ― это

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

П р и м е р 4:

3

: →3

, :

сюръек-

Отображение

тивно и инъективно, так как:

из того,

что

(x1) (x2 ) ,(x1 x2 ) (x1 x2 )

и

:

= √

. Следовательно, соответствие

:

―

3

биекция.

Упражнения

1.Доказать, что композиция двух инъекций является инъекцией.

2.Доказать, что композиция двух сюръекций является сюръекцией.

3.Доказать, что композиция двух биекций ― биекция.

60