Просолупов Е.В. Конспект курса: Основы дискретной математики

Подождите немного. Документ загружается.

— прямое (декартово) произведение множеств A и B.

Во многих случаях порядок проведения операций произведения не

важен. Тогда считают, что

A × (B × C) = (A × B) × C = {(a, b, c) | a ∈ A, b ∈ B, c ∈ C}.

Аналогично определяется прямое произведение любого конечного

числа множеств.

× A

× ... × A

= {(a

, a

, ..., a

) | a

∈ A

, i = 1, t}

Если речь будет идти о прямом произведении множества на себя, то будем

заменять запись нескольких множеств, на знак степени:

A × A × ... × A

| {z }

= A

1.3 Бинарные отношения и функции

1.3.1 Бинарные отношения

Определение 1.3.1 . Бинарным (двуместным) отношением ρ

называется множество упорядоченных пар. Если некоторая пара (x, y)

принадлежит отношению ρ пишут (x, y) ∈ ρ или xρy.

Замечание 1.3.1 . n-арным отношением называют множество

упорядоченных n-ок. Любое множество можно назвать унарным

отношением.

Областью определения бинарного отношения ρ называется множество

= {x | существует такое y, что xρy}.

Областью значений бинарного отношения ρ называется множество

= {y | существует такое x, что xρy}

Пример 1.3.1 . 1) ρ = {(1, 2), (2, 3), (1, 5), (3, 3)}. Тогда D

= {1, 2, 3},

= {2, 3, 5}.

2) {(x, x) | x — вещественное число}. Тогда D

= R

= R.

3) {(x, y) | x, y — целые числа и найдется такое целое число z, что

x + z = y}. Тогда D

= R

= Z.

Каждое бинарное отношение является подмножеством прямого

произведения множеств X и Y таких, что D

⊆ X и R

⊆ Y .

Обратным отношением для отношения ρ называют отношение

−1

= {(x, y) | (y, x) ∈ ρ}.

Композицией отношений ρ

и ρ

называется отношение

◦ ρ

= {(x, z) | существует такое y, что xρ

y и yρ

z}.

Утверждение 1.3.1 . Для любых бинарных отношений ρ, ρ

, ρ

выполняются следующие свойства:

1) (ρ

−1

)

−1

= ρ;

2) (ρ

◦ ρ

)

−1

= ρ

−1

◦ ρ

−1

Доказательство. Пункт 1 непосредственно следует из определения

обратного отношения. Покажем истинность пункта 2:

(ρ

◦ ρ

)

−1

= {(z, x) | ∃y : xρ

y, yρ

z} =

= {(z, x) | ∃y : yρ

−1

x, zρ

−1

y} = ρ

−1

◦ ρ

−1

1.3.2 Функции

Определение 1.3.2 . Бинарное отношение f называется функцией,

если из (x, y) ∈ f и (x, z) ∈ f следует, что y = z.

Две функции равны, если они состоят из одних и тех же элементов (как

и любые множества).

Иногда приходится сталкиваться с трудностями в определении области

значений функций. Тогда, если D

= X и R

⊆ Y , то говорят,

что функция f задана на множестве X со значениями в множестве Y

(осуществляет отображение множества X во множество Y ), и пишут

f : X → Y .

Если f — функция, вместо (x, y) ∈ f пишут f(x) = y и говорят, что y

— значение соответствующее аргументу x (образ элемента x). x называют

прообразом элемента y.

Пример 1.3.2 . 1) {(1, 2), (2, 3), (48, ? ), (¤, 4)} — функция;

2) {(1, 2), (1, 3), (2, 4)} — не функция;

3) ρ{(x, x

+ 2x + 1) | x — вещественное число} — функция y = x

2x + 1. Обратное бинарное отношение ρ

−1

в этом случае функцией не

является.

Пусть f : X → Y .

Определение 1.3.3 . Функцию (отображение) f назовем инъектив-

ной фукнцией (инъекцией), если для любых x

, x

∈ X и любого y ∈ Y из

y = f(x

) и y = f(x

) следует, что x

= x

Определение 1.3.4 . Функция f называется сюръективной функцией

(сюрьекцией), если для любого элемента y ∈ Y существует элемент

x ∈ X такой, что y = f(x).

Определение 1.3.5 . Функция f называется биективной функцией

(биекцией), если она и сюръективна, и инъективна.

Если указана биективная функция f : X → Y , говорят. что

осуществляется взаимнооднозначное соответствие между множествами X

и Y .

Пример 1.3.3 . Рассмотрим функции f : R → R.

1) f(x) = e

инъективна, но не сюръективна (рис. 5-a));

2) f(x) = x

− x сюръективна, но не инъективна (рис. 5-b));

3) f(x) = 2x + 1 биективна.

y=e

y=x -x

Рисунок 5: Примеры функций

Утверждение 1.3.2 . Композиция двух функций есть функция. При

этом, если f : X → Y и g : Y → Z, то g ◦ f : X → Z.

Доказательство. Пусть (x, z

) ∈ g◦f и (x, z

) ∈ g◦f. Тогда существуют

и y

: z

= g(y

) и z

= g(y

). При этом y

= f(x) и y

= f(x).

Поскольку, f — функция, то y

= y

. Поскольку g — функция, то

= g(y

) = g(y

) = z

. Таким образом, g ◦ f — функция.

Покажем, что g ◦ f : X → Z. Так как f : X → Y , для любого x ∈ X

существует y ∈ R

⊆ Y : f(x) = y. Так как g : Y → Z, существует

z ∈ R

⊆ Z: z = g(y) = g(f(x)) = (g ◦ f)(x). Таким образом, для любого

x ∈ X мы нашли такой z ∈ Z, что (x, z) ∈ g◦f. Следовательно, D

g◦f

= X.

С другой стороны, R

g◦f

⊆ R

⊆ Z, что и требовалось доказать.

Утверждение 1.3.3 . Композиция двух биективных функций есть

биективная функция.

Доказательство. Пусть, f : X → Y и g : Y → Z — биекции. Пусть,

для некоторых x

, x

∈ X и z ∈ Z верно z = g ◦ f(x

) и z = g ◦ f(x

Пусть, y

, y

∈ Y те элементы, для которых y

= f(x

) и y

= f(x

Тогда, z = g(y

) = g(y

). Поскольку g инъективна, y

= y

и, поскольку

f инъективна, x

= x

. Следовательно, g ◦ f — инъективна.

Пусть z ∈ Z. Тогда, поскольку g сюрьективна, существует y ∈ Y :

g(y) = z. Поскольку f сюрьективна, существует x ∈ X: f(x) = y.

Следовательно, g ◦ f(x) = z и g ◦ f сюрьективна. Таким образом, g ◦ f —

биекция.

Пусть f

−1

— отношение обратное к f. Если f

−1

осуществляет

отображение множества Y во множество X, говорят, что f

−1

— обратное

отображение.

Утверждение 1.3.4 . Отображение f : X → Y имеет обратное

отображение f

−1

: Y → X тогда и только тогда, когда f — биекция.

При этом f

−1

тоже будет биекцией.

Доказательство. Пусть, (y, x

) ∈ f

−1

и (y, x

) ∈ f

−1

. Тогда, f(x

) =

f(x

) = y. Из инъективности функции f следует, что x

= x

и,

следовательно, f

−1

— функция.

Из сюрьективности функции f следует, что для любого y ∈ Y

существует x ∈ X: f(x) = y. Другими словами, для любого y ∈ Y

существует x ∈ X: f

−1

(y) = x. Следовательно, D

−1

= Y и f

−1

осуществляет отображение из Y в X.

Покажем, что f

−1

— биекция. Поскольку f определена на всем

множестве X, f

−1

— сюрьекция. Пусть существуют такие y

, y

∈ Y и

x ∈ X, что x = f

−1

) = f

−1

). Тогда, (x, y

) ∈ f и (x, y

) ∈ f и,

поскольку f функция, y

= y

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

−1

— инъекция.

Замечание 1.3.2 . Чтобы обратное отношение f

−1

было функцией,

достаточно инъективности f.

Тождественным отображением множества X на себя называется

отображение e

: X → X такое, что для любого x ∈ X верно e

(x) = x.

Если f : X → Y тогда верно, что e

◦ f = f и f ◦ e

= f.

Утверждение 1.3.5 . Если f : X → Y — биекция, то

1) (f

−1

◦ f) = e

;

2) (f ◦ f

−1

) = e

Доказательство. Для любого x ∈ X, (f

−1

◦ f)(x) = f

−1

(f(x)) = x. Для

любого y ∈ Y , (f ◦ f

−1

)(y) = f(f

−1

(y)) = y.

1.3.3 Специальные бинарные отношения: Отношение эквивалентности

Говорят, что ρ — бинарное отношение на множестве X, если ρ ⊆ X × X.

Для произвольного отношения ρ имеет смысл выбирать X = D

∪ R

Отношение ρ на множестве X называется рефлексивным, если для

любого элемента x ∈ X выполняется xρx

Отношение ρ на множестве X называется иррефлексивным, если для

любых x ∈ X из (x, x) /∈ ρ.

Отношение ρ на множестве X называется симметричным, если для

любых x, y ∈ X из xρy следует yρx

Отношение ρ на множестве X называется антисимметричным, если

для любых x, y ∈ X из xρy и yρx следует x = y.

Отношение ρ на множестве X называется транзитивным, если для

любых x, y, z ∈ X из xρy и yρz следует xρz.

Определение 1.3.6 . Бинарное отношение ρ на множестве X

называется отношением эквивалентности, если оно рефлексивно,

транзитивно и симметрично.

Если ρ — отношение эквивалентности и xρy, говорят, что x и y

эквивалентны.

Пример 1.3.4 . 1) ρ

= {(x, y) | x, y ∈ R, x = y} — отношение

эквивалентности.

2) Отношение подобия на множестве треугольников является

отношением эквивалентности.

3) Отношение сравнимости по модулю n

xρy ⇔ x ≡ y(mod n)

на множестве всех целых чисел Z является отношением

эквивалентности.

Определение 1.3.7 . Пусть на множестве X введено отношение

эквивалентности ρ. Классом эквивалентности, порожденным

элементом x, назвается подмножество множества X, состоящее из

всех элементов эквивалентных x:

[x] = {y | y ∈ X, xρy}.

Пример 1.3.5 . Продолжим пример 1.3.4.

1) Классы эквивалентности по отношению равенства на множестве

вещественных чисел состоят из единственного элемента: [x] = x.

2) Класс эквивалентности по отношению подобия треугольников

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

3) Класс эквивалентности для отношения сравнимости по модулю

n на множестве целых чисел Z, порожденный элементом a, имеет

вид {a + kn | k ∈ Z}. Очевидно, что числа 0, 1, 2, ..., n − 1

порождают различные классы. С другой стороны, для любого числа

t ∈ Z оно представимо в виде t = a + kn, где k ∈ Z, а a ∈

{0, 1, ..., n−1}. Значит, для любого целого числа порожденный им класс

эквивалентности совпадает с одним из указанных. Таким образом,

отношение сравнимости по модулю n порождает n различных классов

эквивалентности: [0], [1], ..., [n − 1].

Утверждение 1.3.6 . Пусть ρ — отношение эквивалентности на

множестве X. Тогда 1) для любого x ∈ X верно, что x ∈ [x];

2) для любых x, y ∈ X, если xρy, то [x] = [y] (класс эквивалентности

порождается любым своим элементом).

Доказательство. Доказательство пункта 1) следует из рефлексивности

отношения ρ.

Докажем 2). Пусть yρz. Тогда в силу транзитивности отношения ρ

имеем xρz и z ∈ [x]. Следовательно [y] ⊆ [x]. В силу симметричности

отношения ρ получим [x] ⊆ [y], что и требовалось доказать.

Определение 1.3.8 . Разбиением множества A называется

совокупность его попарно непересекающихся непустых подмножеств

таких, что каждый элемент x ∈ A принадлежит одному из этих

подмножеств:

∪ A

∪ ... ∪ A

}, A

6= ∅, i = 1, k,

∩ A

= ∅, i, j = 1, k, i 6= j,

A = A

∪ A

∪ ... ∪ A

Утверждение 1.3.7 . Всякое разбиение множества X определяет на

X отношение эквивалентности ρ: xρy тогда и только тогда, когда x

и y принадлежат одному подмножеству разбиения.

Доказательство. Рефлексивность и симметричность очевидны.

Покажем транзитивность. Пусть xρy и yρz. Тогда x, y ∈ X

и y, z ∈ X

где X

и X

— подмножества разбиения X. Поскольку y ∈ X

и y ∈ X

то X

= X

. Таким образом x, z ∈ X

и xρz.

Утверждение 1.3.8 . Всякое отношение эквивалентности ρ

определяет разбиение множества X на классы эквивалентности

по этому отношению.

Доказательство. Из утверждения 1.3.6 следует, что каждый элемент

множества X принадлежит некоторому классу эквивалентности. В то

же время, из того же утверждения следует, что любые два класса

эквивалентности либо не пересекаются, либо совпадают, если имеют хоть

один общий элемент: z ∈ [x], z ∈ [y] ⇒ xρz, zρy ⇒ xρy ⇒ [x] = [y].

Совокупность классов эквивалентности элементов множества X

по отношению эквивалентности ρ называется фактор-множеством

множества X по отношению ρ и обозначается X/ρ

1.3.4 Специальные бинарные отношения: Отношение порядка

Определение 1.3.9 . Бинарное отношение ρ на множестве

X называется отношением порядка, если оно транзитивно и

антисимметрично. Множество, на котором введено отношение

порядка, называют упорядоченным.

Пример 1.3.6 . Множество всех пар (x, y) людей, для которых x

старше y, является отношением порядка.

Определение 1.3.10 . Отношение порядка ¹ называется

отношением нестрогого (частичного) порядка на множестве X,

если оно рефлексивно.

Отношение порядка ≺ называется отношением строгого порядка на

множестве X, если оно иррефлексивно:

∀x, y ∈ X : x ≺ y ⇒ x 6= y.

Определение 1.3.11 . Отношение порядка ρ на множестве X

называется отношением линейного порядка, если любые x, y ∈ X,

x 6= y, сравнимы в смысле отношения ρ (либо xρy, либо yρx обязательно

выполняется).

Пример 1.3.7 . 1) Отношение родитель-ребенок (рисунок 6-a)) не

является отношением порядка. Очевидно, что у такого отношения

отсутствует транзитивность: дед не является родителем своего

внука.

С другой стороны, отношение предок-потомок является

отношением порядка. На рисунке 6-b) представлено то же фамильное

дерево, что и на рисунке 6-a), но с указанием всех связей от дедов к

внукам.

Отношение предок-потомок является отношением строгого порядка

и не является линейным порядком.

Рисунок 6: Генеалогическое древо

2) ρ

= {(x, y) | x, y ∈ R, x > y} — является отношением строгого