Отношения и функции

dlyachainikov.ru · Дискретная математика

Основные определения

Отношение – это подмножество декартова произведения множеств. Обозначается как $R \subseteq A \times B$ .
Пример отношения: $R = \{ (x,y) | x^2 + y^2 \leq 9 \}$ , где $A$ и $B$ – множества действительных чисел.
Функция – отображение одного множества в другое, при котором каждому элементу из области определения соответствует единственный элемент из области значений.
Обозначение функции: $f : X \rightarrow Y$ .

Рефлексивность

Отношение $R$ называется рефлексивным, если $(a,a) \in R$ для любого элемента $a$ из множества $A$ .
Пример: отношение равенства $=$

Симметричность

Отношение $R$ симметрично, если $(a,b) \in R$ тогда и только тогда, когда $(b,a) \in R$ .

Транзитивность

Отношение $R$ транзитивно, если $(a,b) \in R$ и $(b,c) \in R$ влечет за собой $(a,c) \in R$

Упорядоченные пары

Упорядоченная пара – это множество $\{ a, b \}$ с указанием порядка элементов. Записывается как $(a, b)$ .

Декартово произведение

Декартово произведение множеств $A$ и $B$ обозначается $A \times B$ и состоит из всех упорядоченных пар $(a, b)$ , где $a \in A$

Инъекция

Формально: $f(x_1) = f(x_2)$ тогда и только тогда, когда $x_1 = x_2$

Сюръекция

Формально: для каждого $y \in Y$ существует хотя бы один $x \in X$ такой, что $f(x) = y$ .

Композиция функций

Композиция двух функций $f : X \rightarrow Y$ и $g : Y \rightarrow Z$ определяется как $g \circ f : X \rightarrow Z$

Основные определения

Отношение – это подмножество декартова произведения множеств. Обозначается как

R \subseteq A \times B

Пример отношения:

R = \{ (x,y) | x^2 + y^2 \leq 9 \}

, где

A

B

– множества действительных чисел.

Функция – отображение одного множества в другое, при котором каждому элементу из области определения соответствует единственный элемент из области значений.

Обозначение функции:

f : X \rightarrow Y