Дискретные структуры. Теория множеств. Cоответствия. Функции. Отображения

1. ТЕОРИЯ МНОЖЕСТВ CООТВЕТСТВИЯ. ФУНКЦИИ. ОТОБРАЖЕНИЯ

ДИСКРЕТНЫЕ СТРУКТУРЫ
ТЕОРИЯ МНОЖЕСТВ
CООТВЕТСТВИЯ. ФУНКЦИИ.
ОТОБРАЖЕНИЯ
ЛЕКЦИЯ 2
Математический факультет. Кафедра математического
моделирования
1

2. Цель лекции – ознакомиться и овладеть понятием «соответствие», изучить свойства соответствий для применения в задачах

Тема: Соответствия. Функции. Отображения
Цель лекции – ознакомиться и овладеть понятием
«соответствие», изучить свойства соответствий для
применения в задачах компьютерной инженерии
Содержание:
• Понятие упорядоченной пары и вектора
• Декартово произведение множеств
• Определение соответствия
• Свойства соответствий
• Взаимно-однозначное соответствие
• Функции
• Отображения
2

3.

Литература
• Горбатов В.А. Основы дискретной математики. М.: Высш. шк.,
1986. 9-12 с.
• Лавров И.А., Максимова Л.Л. Задачи по теории множеств,
математической логике и теории алгоритмов. М.: Наука. Главная
редакция физико-математической литературы, 1984. 4-10 с.
• Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная
математика для инженера. М.: Энергия, 1980. 344 с.
• Богомолов А.М., Сперанский Д.В. Аналитические методы в
задачах контроля и анализа дискретных устройств. Саратов: Изд-во
Саратовкого ун-та, 1986. 240с.
• Новиков Ф.А. Дискретная математика для программистов. С.-П.,
2001. С. 4-24.
• Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В.
Методичні вказівки до практичних занять з курсу “Дискретна
математика”. Харків, ХНУРЕ. 2001. 87с.
3

4.

Термины
Базовые понятия:
Ключевые слова:
множество,
упорядоченная
пара,
подмножество
декартово (прямое)
произведение
множеств,
соответствие,
всюду
определенность,
сюръективность,
инъективность,
функциональность,
биекция (взаимная
однозначность)
4

5.

Основные понятия: упорядоченная пара, вектор
Множество
Упорядоченная
пара
Информация
Упорядоченная пара является одним из первичных понятий
в теории множеств
Под упорядоченной парой следует понимать двухэлементное упорядоченное множество
Вектор (кортеж) представляет собой упорядоченный набор
элементов
х = (х1, х2, …, хn), где хi – координаты (компоненты)
Длина (размерность) вектора определяется количеством его
координат
5

6.

Проекция вектора на ось
Два вектора x, y одинаковой размерности равны, если
их соответствующие компоненты равны:
x=y i xi=yi
Def: проекцией вектора х=(х
, vх| v2 ,V…,
хn) на i-ю ось
Pr V 1Pr
называется его i-й компонент Pr i x = хi
i
i
Def: пусть V – множество векторов одинаковой длины,
тогда проекцией множества V на i-ю ось называется
множество проекций всех векторов из V:
6

7.

Примеры
Координаты точки плоскости
образуют упорядоченную пару: на
первой позиции – абсцисса, на
второй – ордината. Они являются
проекциями на первую и вторую
оси соответственно
Дано множество V векторов
размерности 3:
V = { (a,b,c), (c,b,d), (b,b,d) }
Можно найти проекции множества
V на оси
y
y1
0
(x1, y1)
x
x1
Pr1V={a,c,b}
Pr2V={b}
Pr3V={c,d}
7

8.

Декартово (прямое) произведение множеств
1
Def: прямое (декартово) произведение множеств
A и B есть множество всех упорядоченных пар (a,b)
таких, что a A, b B:
A B={ (a,b) | a A, b B }
Примеры
1. Декартово произведение множеств А={1,2}, B={3,4,5}
есть
А B = { (1,3), (1,4), (1,5), (2,3), (2,4), (2,5) }
2. A={1,2,3,4,5,6,7,8}, B={a,b,c,d,e,f,g,h}
А В – обозначение клеток шахматной доски
8

9.

Декартово (прямое) произведение множеств
Декарту принадлежит координатное
представление точек плоскости
2
Множество точек плоскости R R=R есть
множество пар вида (a,b), a R, b R :
R2={(a,b) | a R, b R}
Декартов квадрат (А=В):
А А=А2={(a,b) | a А, b А}
2
Рене Декарт
XVI-XVII вв.
Def: прямое произведение n множеств
А1 А2 … Аn ={(а1, а2, …… , аn)| ai Аi , i=1,n}
Мощность декартова произведения
множеств:
| А1 А2 … Аn | = |А1 |•|А2|• … •|Аn|
9

10.

Соответствия
Def: соответствие – подмножество декартова
произведения двух множеств:
G A B
А – область определения (множество отправления)
соответствия G :
Pr1G={ x | (x,y) G }
В – область значений (множество прибытия)
соответствия G :
Pr2G={ y | (x,y) G }
10

11.

Образы и прообразы
Def: множество всех элементов y B, соответствующих
элементу x A, называется образом элемента х
в множестве B при соответствии G.
Def: множество всех элементов x A, которым соответствует
элемент y B, называется прообразом элемента y в
множестве A при соответствии G.
B
A
Пример
А={1,2,3}, B={e,f,g}
G={(1,e), (2,e)} A B
1.
2.
3.
.e
.f
.g
G
прообразы образы
11

12.

Time Out
12

13.

Свойства соответствий. 1
Всюду определенность: Pr1G = A
1.
2.
3.
Сюръективность: Pr2G = В
B
A
G
.e
.f
.g
Пример
Схема
B
A
1.
2.
3.
G
G
.e
.f
.g
Пример
G
Схема
13

14.

Свойства соответствий. 2
Инъективность:
in G : A B y Pr2 G B !x Pr1 G A
B
A
1.
2.
3.
G •. eh
.f
.g
Пример
Функциональность:
G
Схема (контрпример)
G : A B x Pr1 G A ! y Pr2 G B
G
Пример
Схема (контрпример)
14

15.

Взаимно-однозначное соответствие (биекция).
Функция. Отображение
Всюду
Биекция =
+ Sur + In + Функциональность
определенность
Соответствие взаимно-однозначно
(биективно), если оно обладает
одновременно всеми названными свойствами
Функция – функциональное соответствие
f : A B x Pr1 A ! y Pr2 B: f ( x ) y
x – аргумент, y – значение функции
Отображение – всюду определенная
функция
15

16.

Пример
Соответствие G={ (x,y) | y = exp x } R R
всюду определено: Pr1G = (- ; ) = R
не sur: Pr2G = (0; ) R
in: образ имеет единственный прообраз
функционально: каждому прообразу
соответствует единственный образ
y
не является bi
1
0
x
16

17. Выводы

Соответствие представляет собой
произвольное подмножество
декартова произведения двух
множеств
Если множества имеют одинаковое
количество элементов, то между
ними можно установить взаимнооднозначное соответствие
Классификация соответствий
применяется в задачах
компьютерной инженерии и
управления
17
Множества
Декартово
произведение A B,
A1 A2 … An
Соответствие
G A B

18.

Тест-вопросы. 1
1. Могут ли повторяться
компоненты
вектора?
а) да;
б) нет.
2. Длина вектора
определяется:
а) числом различных
элементов;
б) числом координат.
3. Какое из
cоответствий
называется взаимнооднозначным:
а) сюръективное,
инъективное и
функциональное?
б) сюръективное и
инъективное?
в) всюду определенное,
сюръективное,
инъективное и
функциональное?
18

19.

Тест-вопросы. 2
4. Является ли
отображение
биективным,
если оно
сюръективно и
инъективно?
а) да;
б) нет.
5. Отображение А в В это:
а) частично определенная
функция;
б) всюду определенная
функция;
в) сюръективное
соответствие;
г) инъективное соответствие.
19

20.

Тест-вопросы. 3
8. Верно ли: |Аn| = |A|n ?
6. Верно ли: A,B A B=B A ?
а) да
а) да;
б) нет.
б) нет.
9. Соответствие является
7. Указать проекцию
подмножеством
множества A={(3,3,5), (3,3,6), а) объединения двух
(3,5,5), (3,5,6), (8,3,5), (8,3,6), множеств;
б) пересечения двух
(8,5,5), (8,5,6)}
множеств;
на третью ось
в) теоретико-множественной
а) ПРA={3,8},
разности двух множеств;
б) ПРA={3,5},
г) декартова произведения
в) ПРA={5,6}.
нескольких множеств;
д) декартова произведения
двух множеств.
20