Множества и бинарные отношения (Учебное пособие)


Министерство образования и науки Краснодарского края
ГБОУ СПО «АМТ» КК
Учебное пособие
Множества и бинарные отношения
для обучающихся специальности 09.02.03
«Программирование в компьютерных системах»
Автор: Беляева Татьяна Юрьевна

Содержание
1. Множества, их виды. Способы задания множеств 3
1.1. Понятия множества и его элементов. Виды множеств 3
1.2. Подмножества. Универсальное множество 4
1.3. Способы задания множеств 4
2. Операции над множествами и их свойства 6
2.1. Объединение множеств (сложение) 6
2.2. Пересечение множеств (произведение) 6
2.3. Разность множеств 7
2.4. Дополнение множества 8
2.5. Дизъюнктивная сумма множеств (симметрическая разность) 8
2.6. Тождества алгебры множеств, связывающие несколько операций 9
3. Декартово произведение множеств и его свойства 10
4. Бинарные отношения 11
4.1. Понятие бинарных отношений 11
4.2. Области определения и значений бинарного отношения 12
4.3. Типы бинарных отношений 12
4.4. Матрица отношения 13
4.5. Операции над бинарными отношениями и их свойства 14
4.6. Основные свойства бинарных отношений во множестве А 16
4.7. Виды бинарных отношений во множестве 17
5. Функции и отображения 19
5.1. Функциональные отношения 19
5.2. Отображения и их типы 20
5.3. Подстановки как отображения 21
Задания для самостоятельного решения 23
Контрольные вопросы 26
Тест для самоконтроля 28
1. Множества, их виды. Способы задания множеств
1.1. Понятия множества и его элементов. Виды множеств
Опр. А) «Множество есть многое, мыслимое нами как единое целое» (Г. Кантор)
Б) Множество – это совокупность объектов, объединенных по какому-либо признаку.
Обозначение: А, В, С, … (возможно, с индексами)
Опр. Объекты, из которых состоит множество, называются его элементами.
Обозначение: а, в, с, … (возможно, с индексами)
При этом говорят, что элемент принадлежит множеству, и пишут: а ∈ А.
Опр. Множество называется конечным, если оно содержит конечное число элементов, и бесконечным, если в нем бесконечно много элементов.
Напр.: 1) Множество дней недели – конечное
2) Множество натуральных чисел – бесконечное
Опр. Число элементов множества называется мощностью этого множества.
Обозначение: QUOTE
Опр. Множество, которое не содержит ни одного элемента, называется пустым.
Обозначение: Ø.
(!!) Очевидно, что QUOTE .
Опр. Два множества, имеющие одинаковую мощность, называются равномощными.
Напр.: А – множество цветов радуги, В – множество нот
А= В=7Опр. Два множества называются равными, если они содержат одни и те же элементы.
Обозначение: А = В
(!!) Если А = В, то |А| = |В|.
1.2. Подмножества. Универсальное множество
Опр. Множество В называется подмножеством множества А, если всякий элемент множества В является элементом множества А.
Обозначение: В ⊂ А
Напр.: N ⊂ Z ⊂ Q ⊂ R ⊂ C.
(!!) 1) Если А ⊂ В и В ⊂ А, то А = В.
2) Если А – некоторое множество, то Ø ⊂ А и А ⊂ А.
Опр. Подмножества А и Ø множества А называются несобственными подмножествами множества А. Любое другое подмножество называется собственным подмножеством этого множества.
Напр.: А = {1; 2; 3}
{1}, {2}, {3}, {1; 2}, {1; 3}, {2; 3} – собственные подмножества
Опр. Множество всех подмножеств некоторого множества А называется его булеаном.
Обозначение: В(А)
Напр.: А = {a; b}
B(A) = { Ø; {a}; {b}; {a; b}}
(!!) |B(A)| = 2|A|, т.е. множество, содержащее п элементов, имеет 2п подмножеств.
Опр. Воображаемое множество, содержащее в себе все другие множества, называется универсальным.
Обозначение: U.
1.3. Способы задания множеств
Перечислением (списком) его элементов
Этот способ используется только для конечных множеств.
Напр.: Д = {понедельник, вторник, среда, четверг, пятница, суббота, воскресенье}
Порождающей процедурой
Порождающая процедура описывает способ получения элементов множества из уже полученных элементов, либо из других объектов.
Этот способ используется для бесконечных множеств.
Напр.: а) M = {1, 1, 2, 3, 5, 8, 13, 21,…}
m1 = 1, m2 = 1, mn+2 = mn + mn+1 – порождающая процедура
б) А = {2, 4, 6, 8, 10,…}
an = 2n – порождающая процедура
Указанием характеристического свойства
Характеристическое свойство – это такое свойство, что элементы множества им обладают, а все остальное на свете не обладает.
Этот способ применим как к конечным, так и бесконечным множествам.
Напр.: а) Герои романа Л. Н. Толстого «Война и мир».
Такое описание множества вполне понятно. Очевидно, что А. Болконский принадлежит этому множеству, а А. Каренина не принадлежит.
б) М = { x| 0 ≤ x ≤ 1} – множество всех действительных чисел таких, что они заключены между 0 и 1 включительно.
4) Графически (с помощью диаграмм Эйлера-Венна)
Универсальное множество обозначается в виде прямоугольника. Любое множество А, являющееся подмножеством U, изображают в виде круга.
205740172085
424815139065 U
A
729615234315205740193675
A B B ⊂ A
ПР. Прочитайте запись М = х∈ Z x2+4х<0. Задайте это множество перечислением элементов. Запишите все подмножества множества М.
/ М – множество целых чисел, удовлетворяющих неравенству x2+4х<0.
Решим неравенство: x(x+4)<0
+ - +
1653540171450090551017145004533903429000
- 4 0 х
М = -3;-2; -1В(М) = Ø; -3; -2; -1; -3;-2; -2; -1; -3; -1; -3;-2; -1 /
2. Операции над множествами и их свойства
2.1. Объединение множеств (сложение)
Опр. Объединением 2-х множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из данных множеств.
Обозначение: А ∪ В
124396526606600Т. о.: А ∪ В = {x | x ∊ A или x ∊ В}
145351564135001910715641350014535156413500 U
157734013335А
00А
232029013335В
00В

Напр.: 1) {1; 2; 3} ∪ {2; 3; 4} = {1: 2; 3; 4}
2) А = {1, 3, 5, 7,…}, B = {2, 4, 6, 8,…} A ∪ B = N
(!!) 1) Если А – произвольное множество, то
А ∪ А = А А ∪ Ø = А А ∪ U = U
2) Если А и В – произвольные множества, то А ∪ В = В ∪ А
3) Если В ⊂ А, то В ∪ А = А
2.2. Пересечение множеств (произведение)
Опр. Пересечением 2-х множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат каждому из данных множеств.
Обозначение: А ∩ В
Т. о.: А ∩ В = {x | x ∊ A и x ∊ B}
18345151016000 U
Напр.: 1) {1; 2; 3} ∩ {2; 3; 4} = {2; 3}
2) А = { x | x = 2n, n ∊ Z}, B = {x | x = 3n, n ∊ Z}
A ∩ B = { x | x = 6n, n ∊ Z}
(!!) 1) Если А – произвольное множество, то
А ∩ А = А А ∩ Ø = Ø А ∩ U = А
2) Если А и В – произвольные множества, то А ∩ В = В ∩ А
3) Если В ⊂ А, то В ∩ А = В
Совершенно аналогично определяются объединение и пересечение 3-х, 4-х, …, бесконечного числа множеств.
(!!) Имеют место равенства:
А QUOTE (В QUOTE С) = (А QUOTE В) QUOTE С А ∩ (В ∩ С) = (А ∩ В) ∩ С
2.3. Разность множеств
Опр. Разностью 2-х множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат множеству А, но не принадлежат множеству В.
Обозначение: А \ В
1329690273685Т. о.: А \ В = { x | x ∊ A и x ∊ B}
1453515641350019107156413500145351564135002329815156210В
00В
1605915108585А
00А
U

Напр.: 1) {1; 2; 3} \ {2; 3; 4} = { 1 }
(!!) Если А – произвольное множество, то
А \ А = Ø А \ Ø = А А \ U = Ø
В отличие от объединения и пересечения, разность – строго двуместна.

2.4. Дополнение множества
Опр. Если В ⊂ А, то разность А \ В называется дополнением множества В до множества А.
Обозначение: ВА172021511112500
2674620102235002139315102235А
00А

27584406985В
00В

Опр. Дополнением множества А до универсального множества U, или просто дополнением, называется множество всех элементов множества U, не принадлежащих А.
Обозначение: Ā
По определению: Ā = U \ А
(!!) Очевидно:
∅ = U U = Ø А = А А ∪ Ā = U А ∩ Ā = Ø
Дополнение – одноместная операция.
2.5. Дизъюнктивная сумма множеств (симметрическая разность)
Опр. Дизъюнктивной суммой 2-х множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат или множеству А, или множеству В, но не обоим вместе.
Обозначение: А ⊕ В
Т. о.: А⊕В = { x | x ∊ A и х ∉ В или х ∉ А и x ∊ B}
2053591698500U
Напр: 1) { 1; 2; 3 } ⊕ { 2; 3; 4 } = { 1; 4 }
(!!) Если А – произвольное множество, то
А⊕ А = Ø А⊕ Ø = А А⊕ U = Ā

2.6. Тождества алгебры множеств, связывающие несколько операций
1. Законы поглощения:
А ∪ (А ∩ В) = А А ∩ (А ∪ В) = А
2. Дистрибутивность:
А ∪ (В ∩ С) = (А ∪ В) ∩ (А ∪ С) А ∩ (В ∪ С) = (А ∩ В) QUOTE ∪ (А ∩ С)
3. Законы де Моргана:
А∪В=А∩ВА∩В=А∪В4. А \ В = А ∩В
5. А ⊕ В = (А ∩ QUOTE
Все эти формулы легко доказать с использованием кругов Эйлера. Для этого достаточно построить области, соответствующие правой и левой частям тождества, и установить их совпадение.
ПР. Упростите:
1) (А ∩ В ∩ С) U (Ā ∩ В ∩ С)
/ (А U Ā) ∩ (В ∩ С) = U ∩ (В ∩ С) = В ∩ С/
2) (А ∩ В ∩ С) ∪ (Ā ∩ С) ∪ (В ∩ С)
/ ((А ∩ В) ∩ С) ∪ ((Ā ∪ В) ∩ С) = ((А ∩ В) ∪ (Ā ∪ В)) ∩ С = ((А ∩ В) ∪ А∩В ) ∩ С = U ∩ С = С/
3) Х\У∩Х∪У
/ Х∩У∩Х∩У = Х∩У ∪ Х∩У = (Х ∩ У) ∪ (Х ∩ У) = Х ∩(У ∪У) = Х ∩U = Х/
ПР. Докажите с помощью тождественных преобразований:
А \ (А \ В) = А ∩ В
/ Л.ч. А \ (А ∩ В) = А ∩ А ∩ В = А ∩ (Ā ∪В) = (А ∩ Ā) ∪А ∩В= Ø ∪ А ∩В = А ∩ В, ч.т.д./
3. Декартово произведение множеств и его свойства.
Декартова степень множества
Опр. Прямым (декартовым) произведением 2-х множеств А и В называется множество, элементами которого являются все упорядоченные пары (a; b), первые компоненты которых принадлежат множеству А, а вторые – множеству В.
218567025146000Обозначение: А × В
А × В = {(a; b) | a ∊ A и b ∊ B}
ПР. А = {1; 2; 3}, B = {2; 4}
А × В = {(1; 2), (1; 4), (2; 2), (2; 4), (3; 2), (3; 4)}
B × A = {(2; 1), (2; 2), (2; 4), (4; 1), (4; 2), (4; 3)}
(!!) 1) Прямое произведение множеств не коммутативно, т.е.
А × В ≠ B × A
2) Число элементов прямого произведения равно произведению числа элементов множеств А и В, т.е. | А × В | = | А | × | В |
Опр. Если А = В, то А × В = А × А – декартовый квадрат.
Обозначение: А2
Напр.: R2 = R × R – множество точек плоскости (х; у)
ПР. А2 = {(1; 1), (1; 2), (1; 3), (2; 1), (2; 2), (2; 3), (3; 1), (3; 2), (3; 3)}
Опр. Прямым произведением множеств А1, А2, …, Ап называется множество, состоящее из упорядоченных п-ок.
Обозначение: А1 × А2 × … × Ап

814070-14668500 А1 × А2 × … × Ап= { (a1; a2; …; an) | ai ∊ Ai, где i = 1, …,n}
(!!) Если все Аi = А, то А × А × … × А = Аn и | Аn | = | A |n.
ПР. В3 = {(2; 2; 2), (2; 2; 4), (2; 4; 2), (2; 4; 4), (4; 2; 2), (4; 2; 4), (4; 4; 2), (4; 4; 4)}
Опр. Упорядоченную п-ку называют п-мерным вектором или кортежем, а элементы, составляющие п-ку, – ее координатами.
Опр. Две п-ки называются равными, если они имеют одинаковую длину, и соответствующие координаты их равны.
4. Бинарные отношения
Многие задачи математики, техники и других областей человеческой деятельности получают удобную интерпретацию на языке теории отношений. Все арифметические операции – это, по существу, некоторые отношения между числовыми множествами. Множество деталей остается складским имуществом до тех пор, пока между ними не реализуются определенные отношения, превращающие эти детали в какой-нибудь механизм или устройство (телевизор, станок, ПК, здание, мост, …). Разнообразные отношения складываются между людьми: родители и дети, начальники и подчиненные, учителя и учащиеся.
Отношения между элементами двух множеств, т.е. бинарные отношения, устанавливают соответствие элементов одного множества А элементам другого множества В.
4.1. Понятие бинарных отношений
Опр. Подмножество R прямого произведения множеств А и В называется бинарным отношением.
Обозначение: R ⊂ А × В
Если (а; в) ∈R, то говорят, что элементы а и в находятся в отношении R и пишут аRв.
ПР. Пусть даны два множества А = {2; 3}, B = {3; 4; 5; 6}.
Тогда А × В = {(2; 3), (2; 4), (2; 5), (2; 6), (3; 3), (3; 4); (3; 5); (3; 6)}
Пусть R1 – отношение «быть делителем», т.е. запись аRв означает, что а – делитель в.
Тогда R1 = 2;4;2;6;3;3;(3;6).
R2 – отношение «быть равным» R2 = 3;3
R3 – отношение «быть ≤» R3 = А × В
R4 – отношение «быть >» R4 = Ø
ПР. Пусть М – множество людей. Тогда можно задать на этом множестве следующие бинарные отношения: «быть моложе», «быть сыном», «жить в одном городе», «быть знакомым»,…
4.2. Области определения и значений бинарного отношения
Опр. Областью определения бинарного отношения R ⊂ А × В называется подмножество множества А, для элементов которого найдутся такие элементы из В, что аRв.
Обозначение: Dom R
Опр. Областью значений бинарного отношения R ⊂ А × В называется подмножество множества В, для элементов которого найдутся такие элементы из А, что аRв.
Обозначение: Im R
Иначе говоря, множество первых координат в упорядоченных парах, составляющих бинарное отношение R, образует область определения, а множество вторых координат – область значений этого отношения.
Так, Dom R1 = {2; 3} = A, Im R1 = {3; 4; 6} ⊂ В
Dom R2 = {3} ⊂ A, Im R2 = {3} ⊂ В
Dom R3 = A, Im R3 = В
Dom R4 = Im R4 = Ø
4.3. Типы бинарных отношений
1) Если Dom R ⊂ А, Im R ⊂ В, то говорят, что R есть отношение от А к В. Его называют также соответствием.
2) Если Dom R = А, то говорят, что отношение определено на А.
3) Если В = А, то отношение R ⊂ А × А называют отношением в А. При этом различают три частных случая:
а) Полное (универсальное) отношение Р, которое имеет место для каждой пары (а1; а2) элементов из А.
Напр.: Отношение «учиться в одной группе» во множестве студентов этой группы.
б) Тождественное (диагональное) отношение Е - такое, что каждый элемент множества А находится в этом отношении только с самим собой.
Напр.: Отношение «равенства» во множестве R.
в) Пустое отношение Ø, которому не удовлетворяет ни одна пара элементов из А.
Напр.: Отношение «быть братом» во множестве женщин.
(!!) Для любого отношения R в А справедливы включения: Ø ⊂ Е ⊂ Р.

4.4. Матрица отношения
Для задания бинарных отношений можно использовать любой способ задания множеств. Но существует специальный способ задания отношения – табличный (с помощью матрицы).
Опр. Матрица бинарного отношения R – это прямоугольная таблица, строки которой соответствуют первым координатам, а столбцы – вторым координатам. На пересечении i-й строки и j-ого столбца ставится 1, если выполняется соотношение аiRаj, и 0, если оно не выполняется (нулевые клетки можно оставлять пустыми).
Напр.: Для отношений R1 и R2, приведенных выше, матрицы будут выглядеть так:
R1 R2
3 4 5 6 3 4 5 6
2 0 1 0 1 2 0 0 0 0
3 1 0 0 1 3 1 0 0 0
(!!) Очевидно, что полному бинарному отношению соответствует квадратная матрица, все клетки которой заполнены единицей, тождественному – единичная матрица (квадратная матрица, у которой только на главной диагонали стоят единицы); пустому – нулевая квадратная матрица.
ПР. На множестве N определим бинарное отношение
R = х;у х+у<5.
Очевидно, что (1; 3) ∈ R, (4;1) ∉ R.
Зададим это бинарное отношение перечислением его элементов R = 1;1;1;2;1;3;2;1;2;2;3;1Матрица этого отношения имеет вид:
1 2 3
1 1 1 1
2 1 1 0
3 1 0 0
4.5. Операции над бинарными отношениями и их свойства
Опр. Обращением бинарного отношения называется переход от некоторого отношения R ⊂ А × В к симметричному (обратному) ему отношению R-1 ⊂ В × А, образованному теми парами (b; a), для которых (a; b) ∈ R.
Переход от R к R-1 осуществляется взаимной перестановкой координат каждой упорядоченной пары. При этом область определения становится областью значений и наоборот. Матрица обратного отношения получается транспонированием исходной матрицы, т.е. заменой строк матрицы ее столбцами при сохранении нумерации.
ПР. Пусть R1 – « а – делитель b» (R1 = 2;4;2;6;3;3;(3;6)). Тогда R1-1 – «b делится на а» (R1-1 = 4;2;6;2;3;3;(6;3)).
Матрица отношения R1-1 будет иметь вид:
2 3
3 0 1
4 1 0
5 0 0
6 1 1
(!!) Операция обращения обладает следующими свойствами:
1) (R ∪ S)-1 = R-1 ∪ S-1 2) (R ∩ S)-1 = R-1 ∩ S-1 3) (R-1)-1 = R
Пусть даны три множества А, В и С и два бинарных отношения R ⊂ А × В и S ⊂ В × С.
Опр. Композицией отношений R и S называется отношение, состоящее из всех тех пар (а; с) ∈А×С, для которых существует такой элемент b ∈В, что (а; b) ∈R, (b; с) ∈S.
Обозначение: R ○ S ПР. Пусть А = 2;3, В = 3;4;5;6, С = 6;7;8 и
R = 2;4, 2;6, 3;3, 3;6, S = 3;6, 4;8,6;6.
Тогда R ○ S = 2;8,2;6,3;6.
(!!) Матрица композиции R ○ S получается как произведение матриц отношений R и S (в порядке их следования), которое выполняется по обычному правилу умножения прямоугольных матриц с последующей заменой отличного от нуля элемента результирующей матрицы единицей.
В предыдущем примере:
R: S:
3 4 5 6
2 0 1 0 1
3 1 0 0 1
6 7 8
3 1 0 0
4 0 0 1
5 0 0 0
6 1 0 0

R ○ S = 01011001 ·100001010000 = 101200 →
R ○ S:
6 7 8
2 1 0 1
3 1 0 0
(!!) Композиция отношений обладает следующими свойствами:
1) R ○ S ≠ S ○ R 2) (R ○ S) ○ Т = R ○ (S ○ Т) 3) (S ○ R)-1 = R-1 ○ S-1
4.7. Основные свойства бинарных отношений во множестве А
Пусть R – бинарное отношение в А, т.е. R ⊂ А2.
1) Отношение R называется рефлексивным, если для любого элемента а ∈А выполняется отношение аRа.
Напр.: отношение «быть =»
2) Отношение R называется антирефлексивным, если для любого элемента а ∈А не выполняется соотношение аRа.
Напр.: отношение «быть >»
3) Отношение R называется симметричным, если для любых двух элементов ai;aj ∈А из того, что ai Raj , следует, что aj Rai.
Напр.: «параллельность прямых»
4) Отношение R называется антисимметричным, если из соотношений ai Raj и aj Rai следует, что ai = aj.
Напр.: отношение «быть ≤»
5) Отношение R называется асимметричным, если ни для одной пары ai;aj∈А не выполняются одновременно соотношения ai Raj и aj Rai.
Напр.: отношение «быть моложе»
6) Отношение R называется транзитивным, если из того, что ai Raj и aj Raк, следует, что ai Raк.
Напр.: отношение «быть делителем»
7) Отношение R называется антитранзитивным, если оно не обладает свойством 6.
Напр.: «перпендикулярность прямых»
(!!) Для рефлексивного отношения все элементы матрицы на главной диагонали – единицы, а для антирефлексивного – нули. Симметричность отношения влечет и симметричность матрицы относительно главной диагонали.
4.8. Виды бинарных отношений во множестве
Опр. Отношение R в А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Напр.: отношения «равенства», «параллельности прямых», «подобия фигур»,…
Отношения эквивалентности представляют особый интерес, т.к. именно они определяют признак, который допускает разбиение множества А на непересекающиеся подмножества, называемые классами эквивалентности. Все элементы, принадлежащие некоторому классу Аi такого разбиения, связаны отношением эквивалентности. Каждый из них определяет данный класс и может служить его представителем.
В качестве примера рассмотрим классы вычетов по модулю т.
Пусть т – любое натуральное число.
Опр. Целые числа а и в называются сравнимыми по модулю т, если при делении на т они дают один и тот же остаток.
Обозначение: a = в(mod m)
Сравнимость чисел по модулю обладает всеми свойствами эквивалентности. Поэтому множество целых чисел разбивается на классы чисел, сравнимых между собой по модулю т. Обозначим их следующим образом:
с0 – числа, которые делятся на т,
с1 – которые при делении на т дают в остатке 1,
с2 – 2,
…,
ст-1 – т-1.
Составим теперь новое множество, элементами которого являются классы чисел, сравнимых по модулю т 𝑍т = с0, с1, …, сm-1. Оно состоит из т элементов, и в нем можно определить действия сложения и умножения.
Рассмотрим это на конкретном примере.
Пусть т = 2, тогда с0 = 0; ±2; ±4; ±6;… = 0
с1 = ±1; ±3; ±5;… = 1
𝑍2 = 0;1 Таблица сложения Таблица умножения
0 1
0 0 1
1 1 0
0 1
0 0 0
1 0 1
Опр. Отношение R в А называется отношением толерантности, если оно рефлексивно и симметрично.
Напр.: отношение «быть знакомым»
(!!) Очевидно, что отношение эквивалентности есть частный случай толерантности, когда к двум перечисленным свойствам добавляется транзитивность.
Опр. Отношение R в А называется отношением строгогонестрогого порядка, если оно антирефлексивнорефлексивно, асимметричноантисимметрично и транзитивно.
Обозначение: <≤(!!) Отношение порядка дает возможность сравнивать между собой различные элементы множества А.
Опр. Множество А, которое обладает отношением порядка, называется упорядоченным.
Напр.: упорядочено множество цифр в телефонном номере или множество букв в слове («ракета» и «карета»)
5. Функции и отображения
5.1. Функциональные отношения
Опр. Отношение R ⊂ А × В называется функциональным (функцией), если каждому элементу а ∈А такому, что (а; в) ∈R, соответствует один и только один элемент в ∈В.Матрица функционального отношения содержит в каждой строке не более одного единичного элемента. Элементам из А, не входящим в область определения отношения, соответствует нулевая строка в матрице.
Напр.: Пусть А = {a1; a2; a3; a4; a5; a6}, B = {b1; b2; b3}. Функциональное отношение R = {(a1; b1); (a2; b2); (a3; b1); (a5; b3); (a6; b1)} имеет матрицу:
b1 b2 b3
а1 1 а2 1 а3 1 a4 a5 1
a6 1 В случае функционального отношения первую координату упорядоченной пары называют аргументом, а вторую – значением функции. Обычная запись y = f(х) соответствует соотношению х f у или (х; у) ∈ f.
Очевидно, что отношение R-1, обратное функциональному отношению R, может и не быть функциональным. Так, отношение R-1 = {(b1; a1); (b1; a3); (b1; a6); (b2; a2); (b3; a5)}, обратное рассмотренному выше отношению, не является функцией.
5.2. Отображения и их типы
Если функциональное отношение R ⊂ А × В всюду определено на А, т.е. Dom R = А, то оно называется отображением множества А в В.
При этом элемент а называется прообразом, а элемент в – образом.
(!!) Отображение - частный случай функции.
Опр. Отображение множества А во множество В, при котором различные элементы из А имеют различные образы в В, называется инъекцией.
При инъективном отображении каждый элемент из А имеет образ в В, однако некоторые элементы из В могут не иметь прообраза в А.
155702019685001758951968500
6045204191000
42354511620500
8045451651000
А В
Опр. Отображение множества А во множество В, при котором любой элемент из В имеет прообраз, называется сюръекцией.
При сюръективном отображении различные элементы из А могут иметь один и тот же образ.
155702019685001758951968500
8140701568450053784514732000
49022010731500
7283456731000


А В
Опр. Взаимно-однозначное отображение одного множества на другое называется биекцией.
(!!) Очевидно, что между множествами А и В можно установить биекцию лишь тогда, когда мощности этих множеств равны.
Если В = А, то говорят, что определено отображение множества А на себя.
5.3. Подстановки как отображения
Опр. Взаимно-однозначное отображение множества N = 1;2;…;n на себя называется подстановкой n-ой степени.
Обычно подстановку записывают двумя строками, заключенными в скобки. Первая строка содержит прообразы, а вторая – соответствующие им образы.
Напр.: Взаимно-однозначное соответствие четырёх чисел, заданное множеством упорядоченных пар {(1; 2); (2; 4); (3; 3); (4; 1)} запишется как подстановка 4-ой степени:
а = 12342431, в которой 1 переходит в 2, 2 – в 4, 3 – в 3 и 4 – в 4.
Т.к. безразлично, в каком порядке следуют упорядоченные пары отображения, то одна и та же подстановка допускает различные представления:
12342431 = 13242341 = 43211342= …
Опр. Подстановка n-ой степени, переводящая каждое число в себя, называется тождественной подстановкой n-ой степени.
Обозначение: еп = 123…n123…nОпр. Если в подстановке а поменять местами ее строки, то получится подстановка а-1, обратная а.
Напр.: Если а = 12342431, то а-1 = 12344132.
Опр. Композицией подстановок n-ой степени а и в называется подстановка n-ой степени с. являющаяся результатом последовательного выполнения подстановок: сначала - а, затем - в.
Обозначение: с = а ○ в.
Напр.: Пусть а = 12342431 и в = 12341432.
Тогда с = 12344231(!!) Очевидно: 1) а ○ еп = еп ○ а = а; 2) а ○ а-1 = а-1 ○ а = еп.

Задания для самостоятельного решения
1. Прочитайте записи: А = х 2-х=3, В = х x2+1=0, C = х х=10к, где к ∈ Z, D = х∈ N х-3≤2, М = х∈ Z x2+3х<0.
Определите вид каждого множества. Задайте множества перечислением элементов, если это возможно.
2. Классифицируйте следующие множества: А = х 2х≥5, В = {х │ x2-2=0}, М = х х⋮10, К – множество конденсаторов в радиоприемнике, Е – множество деревьев на Луне. Какова мощность множеств В и Е?
3. Задайте множество М = х∈ N -2<х≤3 списком и запишите все его двухэлементные подмножества.
4. Пусть К = х х3-25х=0. Задайте множество списком его элементов и найдите булеан этого множества.
5. Пусть М – множество значений выражения 3,5 – 9а при а = - 1 и 0,5. Задайте это множество перечислением элементов и запишите все его подмножества.
5. Пусть А = -4;-3;-2;-1;0;1;2, В = 4;3;2;1;0;-1;-2 и N – множество натуральных чисел. Найдите: А ∩ N, А ∩ В, В ∪ N, А ∪ В, А \ N, N \ В, А ⊕ В.
6. Найдите дополнение множества В до множества А, если А = х∈ R -5≤х≤2 и В = х∈ R -1,5<х<2.
7. Осуществите пошаговое построение диаграмм Эйлера-Венна для множеств:
1) А ∩В \ А2) А \ (А ∩В ∩С)
3) (А ∪В ∪С) ∩ (А \ С)
8. Упростите:
1) Р \ М ∪ Р ∩ М
2) ((А∩ В) ∪А ∩ В∪В) ∩ А
3) А∪В ∪А∪В9. Докажите с помощью тождественных преобразований:
1) К \С=К ∪С
2) ((А ∩ В) ∪(А ∩В)) ∪(А \В)= В∩А10. Используя основные тождества алгебры множеств, докажите, что (А \ В)∩В=Ø. Проиллюстрируйте результат с помощью кругов Эйлера.
11. Найдите М2 и М × С, если С = {1; 5; 9}, М = {4; 6}.
12. Дано: A = {a, b, c, d, e, f, g, h}, B = {1, 2, 3, 4, 5, 6, 7, 8}. Найти: А × В (что это за множество?)
13. Дано: М – множество букв алфавита в русском языке. Что собой представляет множество М4? Сколько в нем элементов?
14. Какие бинарные отношения можно задать на множестве учащихся одной группы?
15. Во множестве N = 1;2;3;4;5 задано бинарное отношение R = 1;2;1;4;3;1;3;2;3;3;4;1;4;2;5;1;5;3;(5;4). Для данного отношения запишите область определения и область значений. Составьте его матрицу.
16. Какое отношение будет обратным для отношения «быть сыном»? «быть ≥»?
17. Дано отношение R – «быть взаимно простыми» во множестве М = 2; 5; 14; 15; 26. Опишите матрицей данное отношение R, а также обратное ему отношение R-1. Сформулируйте его.
18. Дано: А = 2, 8, В = 4, 6, 8, С = 6, 8, R⊂ А × В: R = 2;4, 2;6, 2;8, (8;8), S ⊂ В × С: S = 4;8, 6;6, 8;8. Получите матрицу композиции R и S.
19. Определите свойства следующих отношений: а) «быть делителем» во множестве целых чисел; б) «быть параллельными» во множестве прямых плоскости»; в) «быть знакомым» во множестве людей, проживающих в одном городе»; г) «пересекаться» во множестве прямых пространства; д) «быть равными» во множестве треугольников»; е) «быть подобными» во множестве фигур.
20. Найдите а-1, в ○ а, в2 и а3, если
а = 1234521354 и в = 1234541253.

Контрольные вопросы
Дайте понятие множества.
Какие множества называются конечными и бесконечными? Приведите примеры таких множеств.
Что такое мощность множества?
Какое множество называется пустым? Чему равна его мощность?
Какие два множества называются равномощными? равными? Приведите примеры. Можно ли равномощные множества считать равными?
Дайте понятие подмножества множества.
Какие множества считают несобственными подмножествами исходного множества?
Какая существует связь между количеством элементов во множестве и числом его подмножеств?
Как называется множество всех подмножеств исходного множества?
Перечислите способы задания множеств и охарактеризуйте каждый из них.
Что называется объединением множеств? Перечислите основные свойства этой операции.
Что называется пересечением множеств? Каковы основные свойства этой операции?
Дайте понятие разности 2-х множеств. Как исключить эту операцию?
Как найти дополнение одного множества до другого? до универсума?
Что называют дизъюнктивной суммой множеств? Как выразить эту операцию через простейшие операции над множествами?
Дайте понятие декартова произведения множеств. Как связана его мощность с мощностью исходных множеств?
Что понимают под декартовой степенью множества?
Дайте понятие бинарного отношения. Приведите примеры таких отношений на множестве чисел и людей.
Как найти область определения и область значений бинарного отношения?
Как заполняется матрица бинарного отношения?
Какое бинарное отношение называется соответствием? отношением на А? отношением в А?
Что значит полное отношение? тождественное отношение? пустое отношение?
Какие матрицы соответствуют полному, тождественному и пустому отображениям?
Дайте понятие обращения бинарного отношения. Какими свойствами обладает эта операция?
Определите композицию бинарных отношений? Как получается матрица композиции?
Какое бинарное отношение называется рефлексивным? антирефлексивным? Приведите примеры.
Дайте понятия симметричных, антисимметричных и асимметричных бинарных отношений и приведите примеры таких отношений.
Когда бинарное отношение является транзитивным? антитранзитивным? Приведите примеры таких отношений.
Какое отношение называется отношением эквивалентности? толерантности? строгого порядка? нестрогого порядка?
Дайте понятие функционального отношения.
Какое функциональное отношение называется отображением?
Дайте определения инъективного, сюръективного и биективного отображений.
Что называют подстановкой п-ой степени и как ее записывают?

Тест для самоконтроля
Задание № 1. (выберите два варианта ответов) Верными являются следующие утверждения...
Варианты ответов:
1) 2 ∈ х x2-1≤0 2) 2 ∈ N 3) – 5 ∈ Z 4) 10 ∉ nn⋮3Задание № 2. (выберите два варианта ответов) Истинными являются следующие утверждения о числовых множествах...
Варианты ответов:
Множество целых чисел является подмножеством натуральных чисел
Множество иррациональных чисел является подмножеством действительных чисел
Промежуток [-1;12 является подмножеством отрезка 0;12 Множество корней уравнения х2 – 4 = 0 является подмножеством целых чисел
Задание № 3. (выберите один вариант ответа) Пусть А = 1;2;3 и В = 2;4, тогда множество А \ В имеет вид…
Варианты ответов:
1) 1;3 2) 1;3;4 3) 1;2;3;4 4) 4Задание № 4. (выберите один вариант ответа) Даны два множества А и В
172021511112500
272986577470В
00В
2566035889000
211074016510А
00А

Серым цветом выделено(а)…
Варианты ответов:
объединение множеств А и В
пересечение множеств А и В
разность множеств А и В
Задание № 5. (выберите несколько вариантов ответов) Отношение «параллельность прямых» на множестве прямых на плоскости обладает свойством…
Варианты ответов:
1) рефлексивности 2) антирефлексивности
3) симметричности 4) транзитивности
Задание № 6. (выберите несколько вариантов ответов) Свойством транзитивности обладают следующие бинарные отношения…
Варианты ответов:
отношение «быть сравнимыми по модулю т» во множестве натуральных чисел
отношение «быть знакомыми» во множестве жителей одного города
отношение «быть перпендикулярными» во множестве прямых на плоскости
отношение «подобия» во множестве фигур на плоскости
Задание № 7. (выберите один вариант ответа) Обратной для подстановки а = 12342341 является подстановка…
Варианты ответов:
1) 12344213 2) 12344132 3) 12344123 4) 12344321
Задание № 8. (выберите один вариант ответа) Композицией двух подстановок а = 12344321 и в = 12343142 является подстановка…
Варианты ответов:
1) 12342431 2) 12342413 3) 12342341 4) 12342143
Ответы на тест:
№1 – 3,4; №2 – 2,4; №3 – 1; №4 – 2; №5 – 1,3,4; №6 – 1,4; №7 – 3; №8 – 2.

Приложенные файлы

  • docx file7.doc
    Размер файла: 143 kB Загрузок: 3