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

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

линейного порядка.

3) ρ

≥

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

линейного порядка.

4) Отношение A ⊆ B всех пар подмножеств (A, B) заданного

универсального множества U, таких что A является подмножеством

множества B называют отношением включения. Отношение

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

отношением линейного порядка.

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

строгого порядка ≺. Пусть элемент x ∈ X таков, что

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

Тогда элемент x называют наименьшим.

Лемма 1.3.9 . Если на конечном непустом множестве X задан

линейный строгий порядок, то существует наименьший элемент, и он

единственен.

Доказательство. Самостоятельно.

Теорема 1.3.10 . Пусть на конечном непустом множестве X задано

отношение линейного строгого порядка ≺. Тогда на X можно выбрать

такую нумерацию элементов X = {x

, x

, ..., x

}, что соотношение x

≺

будет выполняться в том и только в том случае, когда i < j.

Доказательство. Согласно лемме 1.3.9 для множества X существует

наименьший элемент x

∈ X, такой что x

≺ y для любых y ∈ X. Удалим

элемент x

из множества X.

Множество X \ {x

} также удовлетворяет условиям леммы 1.3.9 и,

значит, в нем тоже существует наименьший элемент — x

Мы можем повторять этот процесс до тех пор, пока в множестве X

не закончатся элементы. Очевидно, по способу выбора элементов x

, x

, ..., x

} и есть искомая нумерация.

Определение 1.3.13 . Два нестрого упорядоченных множества X и

Y называются изоморфными, если существует биекция ϕ : X → Y ,

сохраняющая отношение нестрогого порядка. Иными словами, если ¹

и ¹

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

Y , то

⇐⇒ ϕ(x

) ¹

ϕ(x

Пример 1.3.8 . Рассмотрим множество 2

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

множества A = {1, 2, 3}, упорядоченное отношением включения, и

множество X = {1, 2, 3, 5, 6, 10, 15, 30}, упорядоченное отношением

x ¹ y ⇔ y делится на x.

Из рисунка 7 хорошо видно, что эти два упорядоченных множества

изоморфны.

{1}

{2}

{3}

{1,2}

{1,3}

{2,3}

{1,2,3}

Рисунок 7: Изоморфные нестрого упорядоченные множества

Теорема 1.3.11 . Всякое нестрого упорядоченное множество X

изоморфно некоторой системе подмножеств множества X, нестрого

упорядоченной отношением включения.

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

множестве X. Для каждого элемента a ∈ X рассмотрим множество

= {x ∈ X | x ¹ a}. Ясно, что S

⊆ X для любого a ∈ X. Покажем,

что система подмножеств {S

| a ∈ X}, упорядоченная отношением

включения, есть искомая система подмножеств. Рассмотрим отображение

ϕ : X → {S

| a ∈ X}

такое, что ϕ(a) = S

. Если S

= S

, то, поскольку a ∈ S

, то b ∈ S

и, следовательно, b ¹ a. Аналогично a ¹ b. Таким образом, в силу

антисимметричности отношения ¹, a = b. Значит, отображение ϕ

инъективно. С другой стороны, у любого множества S

есть прообраз

a. Значит, ϕ сюрьективно. Следовательно ϕ — биекция.

Пусть a ¹ b. Тогда из x ¹ a в силу транзитивности отношения следует

x ¹ b, а значит S

⊆ S

. Пусть S

⊆ S

. Тогда, поскольку a ∈ S

, то

a ∈ S

и, следовательно, a ¹ b. Таким образом биекция ϕ сохраняет

отношение нестрогого порядка.

1.3.5 Лексикографический порядок

Заслуживающим отдельного упоминания является лексикографический

порядок. Лексикографический порядок - это порядок, в котором

выстроены слова, например, в русско-английских словарях.

Лексикографический порядок может быть введен на множестве слов над

любым множеством, на котором уже введен линейный порядок.

Пусть на множестве X введен строгий линейный порядок ≺. Введем

отношение ≺

lex

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

∗

= {(x

, x

, ..., x

) | k ∈ N, x

∈ X} всех

слов над множеством X. Пусть ex

= (x

, ..., x

) ∈ X

∗

, ey

= (y

, ..., y

) ∈

∗

, ex

6= ey

и k ≤ l .

Будем говорить, что ex

≺

lex

, если 1) существует такой индекс t,

1 ≤ t ≤ k, что x

= y

, i = 1, t − 1 и x

≺ y

, или 2) k < l и x

= y

, i = 1, k.

В противном случае ey

≺

lex

Замечание 1.3.3 . На множестве слов одинаковой длины определение

лексикографического порядка упростилось бы и приняло бы вид:

≺

lex

⇔ ∃t ∈ {1, ..., k} : x

= y

, i = 1, t − 1, x

≺ y

Пример 1.3.9 . Выпишем все возможные перестановки чисел {1, 2, 3,

4} выстроенные в лексикографическом порядке:

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

2 1 3 4

2 1 4 3

2 3 1 4

2 3 4 1

2 4 1 3

2 4 3 1

3 1 2 4

3 1 4 2

3 2 1 4

3 2 4 1

3 4 1 2

3 4 2 1

4 1 2 3

4 1 3 2

4 2 1 3

4 2 3 1

4 3 1 2

4 3 2 1

Заметим, что здесь мы привели только перестановки —

последовательности из различных символов. Если мы захотим

выписать все слова в данном алфавите, их окажется гораздо больше.

Подробнее о перестановках смотри раздел 1.4.

Отметим также, что существует еще так называемый

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

лексикографическому порядку бинарным отношением. Список всех

перестановок n чисел в антилексикографическом порядке может быть

получен следующим образом: сначала нужно выстроить все такие

перестановки в лексикографическом порядке, а затем развернуть

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

перестановку. Такой порядок может быть полезен, например, для

словаря окончаний.

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

лексикографического порядка, антилексикографический порядок можно

определить следующим образом:

Будем говорить, что ey

≺

alex

, если 1) существует такой индекс t,

1 ≤ t ≤ k, что x

k−i

= y

k−i

, i = 1, t − 1 и x

k−t

≺ y

k−t

, или 2) k < l и

k−i

= y

l−i

, i = 1, k. В противном случае ey

≺

alex

Замечание 1.3.4 . На множестве слов одинаковой длины определение

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

≺

alex

⇔ ∃t ∈ {1, ..., k} : x

= y

, i = t + 1, k, y

≺ x

Пример 1.3.10 . Приведем все возможные перестановки чисел {1, 2,

3, 4} выстроенные в антилексикографическом порядке:

1 2 3 4

2 1 3 4

1 3 2 4

3 1 2 4

2 3 1 4

3 2 1 4

1 2 4 3

2 1 4 3

1 4 2 3

4 1 2 3

2 4 1 3

4 2 1 3

1 3 4 2

3 1 4 2

1 4 3 2

4 1 3 2

3 4 1 2

4 3 1 2

2 3 4 1

3 2 4 1

2 4 3 1

4 2 3 1

3 4 2 1

4 3 2 1

Лексикографический и антилексикографический порядки являются

отношениями строгого линейного порядка.

1.4 Перестановки

1.4.1 Понятие перестановки

Определение 1.4.1 . Перестановкой на множестве {1, ..., n}

называется инъективная функция

π : {1, ..., n} → {1, ..., n}.

Число n называется порядком перестановки π.

Замечание 1.4.1 . Как любая инъективная на конечном множестве

функция, перестановка является биективной.

Замечание 1.4.2 . В общем случае, перестановкой произвольного

множества X называют биекцию

π : X → X.

Обозначим σ

множество всех перестановок порядка n. Очевидно, что

|σ

| = n!

Существует несколько способов задания перестановки. Явное задание

перестановки

π =

1 2 ... n

π(1) π(2) ... π(n)

В записи выше первая строка всегда одинакова. Для задания

перестановки достаточно второй строки

π = π(1)π(2)...π(n).

Также можно задать перестановку перечислением ее циклов, о чем мы

скажем позже.

Определение 1.4.2 . Пусть π

, π

∈ σ

. Произведением перестановок

и π

называют композицию этих функций: π

◦ π

(i) = π

(π

(i)),

i = 1, n.

Докажем, что произведение перестановок есть перестановка.

Очевидно, что π

◦ π

: {1, ..., n} → {1, ..., n}. Покажем инъективность.

Пусть i, j ∈ {1, ..., n} и i 6= j. Поскольку π

инъективна, π

(i) 6= π

(j), а

поскольку инъективна π

, π

(π

(

i)) 6= π

(π

(j)). Следовательно,

◦ π

(i) = π

(π

(i)) 6= π

(π

(j)) = π

◦ π

(j).

То есть π

◦ π

— инъективна, а значит является перестановкой.

1.4.2 Группа перестановок

Определение 1.4.3 . Группой называется непустое множество G

с определенной на нем бинарной операцией ¦, удовлетворяющей трем

аксиомам:

1 ассоциативность: для любых a, b, c ∈ G верно, что

(a ¦ b) ¦ c = a ¦ (b ¦ c);

2 наличие нейтрального элемента: существует такой элемент

e ∈ G, что для любого a ∈ G справедливо

a ¦ e = e ¦ a = a;

3 наличие обратного элемента: для любого элемента a ∈ G найдется

такой элемент a

−1

∈ G, что

−1

¦ a = a ¦ a

−1

= e.

Произведение перестановок ассоциативно:

((π

◦ π

) ◦ π

)(i) = (π

◦ π

)(π

(i)) = π

(π

(i)) =

= π

((π

◦ π

)(i)) = (π

◦ (π

◦ π

))(i)

Нейтральным элементом для множества σ

будет служить

тождественная перестановка e =

1 2 ... n

. Легко заметить,

что для любой перестановки π ∈ σ

верно π ◦ e = e ◦ π = π.

Для любой перестановки π ∈ σ

, как для любой биективной функции,

существует обратная функция π

−1

: π

−1

◦ π = π ◦ π

−1

= e. Для любых i ∈

{1, ..., n} π(i) = j ⇒ π

−1

(j) = i. Функция π

−1

обратная для биективной

функции π также будет биективной фукнцией: π

−1

: {1, ..., n} →

{1, ..., n}. То есть, π

−1

∈ σ

Замечание 1.4.3 . Заметим, что обратная перестановка π

−1

для

данной перестановки π единственна. Действиетльно, если бы

существовала еще одна такая перестановка π

, что π ◦ π

= e, то

= e ◦ π

= π

−1

◦ π ◦ π

= π

−1

◦ e = π

−1

;

если перестановка π

такова, что π

◦ π = e, то

−1

= e ◦ π

−1

= π

◦ π ◦ π

−1

= π

◦ e = π

Таким образом мы доказали, что множество перестановок σ

операцией произведения перестановок образуют группу. Эту группу

называют группой перестановок или симметрической группой.

Замечание 1.4.4 . Произведение перестановок в общем случае не

коммутативно.

Пример 1.4.1 . Пусть

1 2 3

2 1 3

, π

1 2 3

3 1 2

Тогда

◦ π

1 2 3

1 3 2

1 2 3

3 2 1

= π

◦ π

1.4.3 Циклы перестановки

Будем обозначать

= π ◦ π ◦ · · · ◦ π

| {z }

; π

= e;

−k

= π

−1

◦ π

−1

◦ · · · ◦ π

−1

| {z }

Определение 1.4.4 . Циклом длины l называется такая перестановка

π которая тождественна на всём множестве {1, 2, ..., n}, кроме

подмножества {x

, ..., x

}. Кроме того π(x

) = x

и π(x

) = x

i+1

i = 1, l − 1.

Цикл обычно обозначается

, ..., x

) = (x

, π(x

), ..., π

l−1

)).

Определение 1.4.5 . Транспозиция - перестановка элементов

множества {1, 2, ..., n}, которая меняет местами только два

элемента.

Замечание 1.4.5 . Транспозиция — цикл длины 2.

Утверждение 1.4.1 . Пусть π ∈ σ

и i ∈ {1, ..., n}. Тогда существует

такое число k ∈ N, что π

(i) = i.

Доказательство. Пусть для любого k ∈ N верно π

(i) 6= i.

Так как множество {1, ..., n} конечно, то элементы последовательности

i, π(i), π

(i), ..., π

(i), ... начинают повторяться начиная с некоторого

момента. Тогда последовательность имеет вид:

= i, a

, ..., a

, b

, ..., b

, b

, ..., b

, b

, ...

где l ≥ 1, i /∈ {a

, ..., a

, b

, ..., b

} и {a

, a

, ..., a

} ∩ {b

, b

, ..., b

} = ∅.

Но тогда π(a

) = π(b

) = b

и по инъективности перестановки π

получаем a

= b

Для произвольной перестановки π ∈ σ

введем бинарное отношение ρ

на множестве {1, 2, ..., n}:

xρ

y ⇔ ∃k ∈ Z : y = π

(x).

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

∈ σ

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

1) Рефлексивность. Для любого x ∈ {1, ..., n } x = π

(x) ⇒ xρ

2) Симметричность. Для любых x, y ∈ {1, ..., n}, для которых xρ

существует k ∈ Z: y = π

(x). Следовательно x = π

−k

(y) и yρ

3) Транзитивность. Пусть x, y, z ∈ { 1, 2, ..., n}, xρ

y и yρ

z. Тогда

существуют k

, k

∈ Z: y = π

(x), z = π

(y). Следовательно

z = π

(π

(x)) = π

(x).

То есть xρ

Пусть {1, 2, ..., n} = B

∪ B

∪ ... ∪ B

— разбиение {1, 2, ..., n}

на классы эквивалентности относительно ρ

. B

называются орбитами

перестановки.

Утверждение 1.4.2 . Пусть π ∈ σ

. Пусть B

∪B

∪...∪B

разбиение

множества {1, 2, ..., n} на классы эквивалентности, порожденное отно-

шением ρ

, и пусть x

∈ B

1) для любого i ∈ {1 , 2, ..., m} существует n

∈ N:

= {x

, π(x

), ..., π

−1

)}.

2) перестановка π представима в виде произведения циклов:

π = (x

, π(x

), ..., π

−1

)) ◦ (x

, π(x

), ..., π

−1

))◦

◦ · · · ◦ (x

, π(x

), ..., π

−1

)).

Доказательство. 1) По определению, B

состоит из всех таких y для

которых существует s ∈ Z: y = π

). По утверждению 1.4.1, для

существует k ∈ N: π

) = x

. Пусть n

— наименьшее из таких

чисел. Тогда x

, π(x

), ..., π

−1

) — различные элементы из {1, 2, ..., n}

и {x

, π(x

), ..., π

−1

)} ⊆ B

Пусть y ∈ B

\ {x

, π(x

), ..., π

−1

)}. Тогда существует такое s ∈ Z,

что y = π

) и s /∈ {1, 2, ..., n

− 1}. s = p · n

+ q, p ∈ Z \ {0},

q ∈ {0, 1, ..., n

− 1}. Следовательно,

y = π

) = π

(π

p·n

)).

Если p > 0, то

p·n

) = π

◦ π

◦ · · · ◦ π

| {z }

) = x

. (∗)

Пусть теперь p < 0. Тогда, используя равенство (∗), получим

p·n

) = π

−n

◦ π

−n

◦ · · · ◦ π

−n

| {z }

−p

) =

= π

−n

◦ π

−n

◦ · · · ◦ π

−n

| {z }

−p

(π

◦ π

◦ · · · ◦ π

| {z }

−p

)) = x

поскольку

−n

◦ π

(i) = π

−1

◦ π

−1

◦ ... ◦ π

−1

| {z }

◦ π ◦ π ◦ ... ◦ π

| {z }

(i) = i.