Файл: Дискретная мат-ка_Ч.1_УП.pdf

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

16 

1.4 

Экстремальные

 

элементы

 

множеств

 

В соответствии с отношением порядка говорят, что при x

≤ x

2

 

элемент x

предшествует элементу

 

x

или x

следует за

  

x

1

Пусть  имеется  подмножество    X

′  ⊂ X, где X упорядоченное 

множество,  т.е.  множество,  для  элементов  которого определено от-
ношение порядка. Тогда мажорантой множества X

′ называется эле-

мент  x

max

 

∈ X, следующий  за  всеми  элементами  множества  X′,              

x

max

  

≥x  (x

max

 

∈ X). При этом мажоранта может и не принадлежать 

множеству  X

′.  Если  же  x

max

 

∈  X′,  то  x

max

  называется  наибольшим 

элементом, или максимумом множества X

′. 

Минорантой множества X

′ называется элемент x

min

 

∈ X, пред-

шествующий всем элементам множества X

′. Если элемент     x

min

 

∈ 

X

′,  то  он  называется  наименьшим  элементом,  или  минимумом 

множества X

′. 

1.5 

Отображения

 

множеств

 

Пусть X и Y - два непустых множества. Закон G, согласно ко-

торому  любому  элементу x 

∈ X  ставится  в  соответствие  элемент            

∈ Y, называется однозначным отображением X в Y, или функци-

ей, определенной на X и принимающей значения на Y.  

Используются следующие формы записи: 

G: X 

→ Y или  y = G(x),  x ∈ X, y ∈ Y. 

В  случае  однозначного  отображения  элемент y = G(x) называ-

ется образом элемента x. 

Возможна ситуация, когда каждому x 

∈ X отображение G ста-

вит  в  соответствие  некоторое  подмножество G(x) 

⊂ Y. Тогда обра-

зом  элемента x будет  подмножество G(x), а  отображение G, будет 
называться  многозначным  отображением.  Отображение  является, 
таким  образом,  всюду  определенным  соответствием,  т.е.  частным 
случаем соответствия и определяется тройкой множеств (X, Y, G). 

Интересным является случай, когда множества X и Y совпада-

ют. При этом отображение G: X 

→ X представляет собой отображе-

ние  множества X самого  в  себя  и  определяется  парой (X, G), где              

⊂ X × X. Подробным  изучением  таких  отображений  занимается 

теория графов. Коснемся лишь нескольких операций над ними. 


background image

 

17 

Пусть G и H – отображения  множества X в X. Композицией 

этих  отображений  назовем  отображение GH, которое  определяется 
следующим образом: GH(x) = G(H(x)). 

В  частном  случае  при H = G получим  отображения                     

G

2

(x) = G(G(x)), G

3

(x) = G(G

2

(x)) и т.д. 

Для произвольного S 

≥ 2: G

S

(x) = G(G

S-1

(x)). 

Введем для общности рассуждений соотношение G

0

(x) = x. То-

гда можно записать: G

0

(x) = G(G

-1

(x)) = GG

-1

(x) = x. 

Это  означает,  что  G

-1

(x)  представляет  собой  обратное  отобра-

жение. Тогда G

-2

(x) = G

-1

(G

-1

(x)) и т.д. 

Пусть, например, X - множество людей. Для каждого человека 

∈ X обозначим  через G(x)  множество  его  детей.  Тогда  G

2

(x) - 

множество внуков x, G

3

(x) - множество правнуков x, G

-1

(x) - множе-

ство родителей x  и т.д. Изображая людей точками и рисуя стрелки, 
идущие из x в G(x), получим родословное, или генеалогическое де-
рево (рис. 1.7.) 

                    

 

Рис. 1.7 – Генеалогическое дерево 

1.6 

Задачи

 

и

 

упражнения

 

1.

 

Даны  множества X = {1, 2, 3, 4, 5}, Y = {2, 4, 6, 7}, найдите          

∪ Y, X ∩Y, X \ Y, Y \ X. 

2.

 

Пусть X 

− множество отличников в группе, Y − множество сту-

дентов группы, проживающих в общежитии. Найдите множества:    

∪ Y, X ∩ Y, X \ Y, Y \ X. 

3.

 

Что  представляет  собой  пересечение  множества  всех  прямо-
угольников с множеством всех ромбов? 

4.

 

Пусть I = {x

1

, x

2

, x

3

− универсальное множество, а X = {x

1

, x

2

},   

Y = {x

2

, x

3

}, Z = {x

3

− его подмножества. Определите перечис-


background image

 

18 

лением множества: X 

× X, Z × Z, X × Y, Y × X, X × Y ∩ Y × X,           

× Y ∪ Y × X. 

5.

 

Проиллюстрируйте графически тождества 

      X 

∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z), 

      X 

∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪ Z). 

6.

 

Пусть R 

−  множество  вещественных  чисел, X = {x ∈  R  /                     

≤ x ≤ 1}, Y = {y ∈ R / 0 ≤ y ≤ 2}. Что представляют собой мно-

жества X 

∪ Y, X ∩ Y, X \ Y? 

7.

 

Начертите фигуры, изображающие множества A = {(x, y) 

∈ R

2

 /  

x

2

 + y

2

 

≤ 1}, B = {(x, y) ∈ R

2

 / x

2

 + (y-1)

2

  

≤ 1}, где R

2

 

− вещест-

венная плоскость. Какие фигуры изображают множества A 

∪ B,          

∩ B, R

\ A? 

8.

 

Пусть X, Y, Z 

−  подмножества  множества  R

2

,  равные:                     

X = {(x, y) 

∈ R

2

 / x 

≥ 0}, Y = {(x, y) ∈ R

2

 / y 

≥ 0}, Z = {(x, y) ∈ R

2

 / 

x + y 

≥ 1}. Представьте  геометрически  множества 

,

,

,

Z

Y

X

 

,

Y

X

 

,

Y

X

 

,

Y

X

 

,

Y

X

 

,

Z

X

 

,

Z

X

 

∩ ∩

,

Z

Y

X

 

.

∩ ∩

Z

Y

X

 

9.

 

Пусть X = {-1, -2, -3, 1, 2, 3, 0} и Y 

− множество всех натураль-

ных  чисел.  Каждому  числу x 

∈ X ставится  в  соответствие  его 

квадрат.  Выпишите  все  пары,  принадлежащие  этому  соответст-
вию. 

10.

 

Пусть X = {«атом», «стол», «море», «мера»}, Y = {а, м, о, р, е}. 
Составьте декартово  произведение X 

× Y. Отметьте в нем пары, 

связанные соответствием «в слово x входит буква y». 

11.

 

Пусть V 

− множество положительных целых чисел от 1 до 20, на 

котором задано отношение R: «число x делится на число y», при-
чем x 

∈ V, y ∈ V. Выпишите все пары из V, находящиеся в от-

ношении R. 

12.

 

Дано  множество B = {1, 3, 5, 7, 9}. Элементы  этого  множества 
связаны отношением S: «число x на 2 больше числа y». Запишите 
множество пар, принадлежащих этому отношению. 

13.

 

Определите свойства следующих  отношений: 

а) «прямая x пересекает прямую y» (на множестве прямых); 
б) «число x больше  числа y на 2» (на  множестве  натуральных 

чисел); 


background image

 

19 

в) «число x делится на число y без остатка» (на множестве на-

туральных чисел); 

г) «x 

− сестра y» (на множестве людей). 

14.

 

На множестве X = {x / x 

∈ N, x < 12} задано отношение R:  «x и y 

имеют один и тот же остаток при делении на 5» (x 

∈ X, y ∈ X). 

Покажите,  что R 

−  отношение  эквивалентности.  Запишите  все 

классы    эквивалентности,  на  которые  разбивается  множество 
данным  отношением. 

15.

 

Рассмотрите на множестве людей следующие отношения, укажи-
те среди них  отношения эквивалентности:  

а) «x похож на y»; 
б) «x и y живут в одном доме»; 
в) «x и y 

− друзья»; 

г) «x живет этажом выше, чем y». 

16.

 

Отношение S на  множестве X = {1, 2, 3} состоит  из  пар:  (1, 2),    
(1, 1), (2, 2), (2, 1), (3, 1), (3, 3). Является ли S отношением экви-
валентности на множестве X? 

17.

 

Какие из нижеперечисленных отношений являются отношениями 
квазипорядка, порядка, строгого порядка? 

а) «отрезок x длиннее отрезка y»; 
б) «отрезок x короче отрезка y в 2 раза» 

− на множестве отрез-

ков; 

в) «x старше по возрасту, чем y»; 
г) «x является сестрой y»; 
д) «x живет в одном доме с y»; 
е) «x 

− друг y» − на множестве людей; 

ж) «число x не меньше числа y» 

− на множестве R; 

з) «окружность x лежит внутри окружности y» 

− на множестве 

окружностей плоскости. 

18.

 

Докажите тождества: A 

∩ (B \ A) = ∅,  A \ (B ∪ C) = (A \ B) \ C. 

19.

 

Решите систему уравнений 

                   A \ X = B, 
                   A 

∪ X = C, 

 

где A, B, C - заданные множества и B 

⊂ A ⊂ C. 

20.

 

Докажите, что A = B 

⇔ (A \ B) ∪ (B \ A) = ∅. 

21.

 

Докажите, что если отношения R

1

 и R

2

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

сивны и отношения R

1

 

∪ R

2

, R

1

 

∩ R

2


background image

 

20 

22.

 

Докажите, что если отношения R

1

 и R

2

 симметричны, то симмет-

ричны и отношения R

1

 

∪ R

2

, R

1

 

∩ R

2

23.

 

Докажите, что два множества равны тогда и только тогда, когда 
результаты их пересечения и объединения совпадают. 

24.

 

Известно, что из 100 студентов живописью увлекается 28, спор-
том 

− 42, музыкой − 30, живописью и спортом − 10, живописью 

и  музыкой 

− 8, спортом  и  музыкой  − 5, живописью,  спортом  и 

музыкой 

− 3. Определите количество студентов: 

а) увлекающихся только спортом; 
б) ничем не увлекающихся. 

ОСНОВЫ

 

ТЕОРИИ

 

ГРАФОВ

 

На  практике  часто  бывает  полезно  изобразить  некоторую  си-

туацию в виде рисунков, составленных из точек (вершин), представ-
ляющих основные ситуации, и линий (ребер), соединяющих опреде-
ленные  пары  этих  вершин  и  представляющих  связи  между  ними. 
Таким способом удобно представлять структуру системы (вершины 
– блоки, ребра – связи между блоками). Удобны графы при исследо-
вании  систем  методом  пространства  состояний.  В  этом  случае  вер-
шины – состояния  системы,  процесса,  ребра – действия,  которые 
могут  изменить  состояние.  При  решении  оптимизационных  задач 
вершинами могут быть предполагаемые решения, ребрами – прави-
ла для их нахождения. 

Такие  рисунки  известны  под общим названием графов. Графы 

встречаются в разных областях под разными названиями: “структу-
ры” в гражд-анском строительстве, “сети” в электротехнике, “социо-
граммы”  в  социологии  и  экономике, “молекулярные  структуры”  в 
химии, и т. д. 

Начало  теории  графов  как  математической  дисциплины  было 

положено  Эйлером  в  знаменитом  рассуждении  о  Кенигсбергских 
мостах. Однако эта статья, написанная в1736 г, была единственной в 
течение почти ста лет. Интерес к этой науке возродился около сере-
дины  ХIХ  в.  в  связи  с  развитием  естественных  наук  (исследования 
электрических  сетей,  моделей  кристаллов  и  структур  молекул), 
формальной  логики  (бинарные  отношения  можно  изучать  в  форме 
графов). Кроме того, оказалось, что многие математические голово-
ломки могут быть сформулированы в терминах теории графов. Это