Lektsia_po_Diskr

3

Предисловие

Наука и техника, экономика и социология, лингвистика и медицина, все отрасли человеческой деятельности в той или иной степени используют математику. Тем более, в профессиях, связанных с информатикой и информационными технологиями.

Одним из разделов математики является дискретная математика, которая в отличие от классической математики непрерывных величин, рассматривает величины дискретные, конечные.

Дискретная математика включает в себя теорию множеств, алгебраические структуры, комбинаторику, математическую логику, теорию графов, теорию конечных автоматов.

Дискретная математика широко используется в смежных дисциплинах, таких как информатика, программирование, кодирование и защита информации, методы и алгоритмы принятия решений, и т.п. Все эти курсы основаны на логике, алгебре и графах.

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

Большое внимание уделено словесному описанию используемых алгоритмов, что предполагает дополнительную самостоятельную работу читателя при решении задач на практических и лабораторных занятиях, а также и вне этих занятий.

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

Комбинаторика является основой при рассмотрении алгоритмов в задачах перебора вариантов, а также подготавливает читателя к восприятию теории вероятностей.

Основы математической логики являются базой всего, что имеет отношение к программированию и компьютеру, в том числе и кодированию информации.

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

1. Основные понятия

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

Очень часто (но не всегда) определение дается по родовому и видовому признакам, то есть вначале указывается, к какому классу ранее определенных понятий относится определяемое понятие, и затем приводятся отличительные признаки.

Аксиома-это предложение, в котором содержится некоторое утверждение, истинность которого не обсуждается.

Математическая теория-это совокупность определений и набора аксиом, на основании которых выявляются те или иные свойства объектов (теоремы).

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

2. Множества

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

Множество состоит из некоторых объектов различных и различаемых, которые называются элементами множества.

Например:

N − Множество натуральных чисел. N0 − множество натуральных чисел и 0. Z − Множество целых чисел.

Q − Множество рациональных чисел. Множество Q так же можно представить в виде множества дробей p , q

где p и q – целые числа.

R − Множество действительных чисел.

Одинаковые элементы, входящие во множество, не различаются и считаются один раз.

4

Порядок элементов во множестве не определен.

Множество, не содержащее ни одного элемента, называется пустым - .

Способы задания множества:

1)Перечислением всех элементов множества. А={3,1,2,5}.

2)С помощью характеристического свойства.

B={x R/ (x+3)<4} или В={x (-∞;1)}.

3)Процедурой.

2.1. Подмножества

Пусть задано множество А. Множество В, состоящее из элементов множества А, называется подмножеством

А.

Например. A={a, w, b, c} и В={w, a, b}, тогда В		А или А		В
(В включается в А или А включается в В).
Множество А является собственным подмножеством.
Пустое множество является подмножеством любого множества.

2.2. Равенство множеств

Два множества называются равными, если они состоят из одних и тех же элементов.

А={3, 2, а}. В={а, 3, а, 3, 2, а}. Имеем А=В.

Теорема. Множество А равняется множеству В, если А является подмножеством В, а В является подмножеством А.

Доказательство:

1)Пусть х А и А В. По определению подмножества, х В. Так как х − произвольный элемент А, то все элементы множества А принадлежат множеству В.

2)Пусть х В и В А. По определению подмножества, х А. Так как х − произвольный элемент В, то все элементы множества В принадлежат множеству А.

3)Так как все элементы множества А принадлежат множеству В, а все элементы множества В принадлежат множеству А, то по определению равенства множеств, А = В.

Что и требовалось доказать.

Все множества рассматриваются как подмножества некоторого универсального множества U.

2.3.Мощность множеств

Количество элементов, входящих во множество, называется его мощностью.

Для бесконечных множеств говорить о количестве элементов не имеет смысла, но говорить о мощности множества можно.

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

Пример:

Имеется множество натуральных чисел и имеется множество четных чисел. Равномощны ли они?

Ответ: Да.	1	2	3	4	5…
	↓	↓	↓	↓	↓
	2	4	6	8	10…

Множества, равномощные множеству натуральных чисел, называются счетными.

2.4. Алгебра множеств. Операции		над множествами.
Условимся U изображать в виде прямоугольника
а множество А-	(круги Эйлера-Венна).

А

Рис.1. Множества А и U

1) Объединение множеств. А B.

5

Объединением множеств А и В называется множество, состоящее из элементов, входящих или в А, или в

В.

Рис.2. Объединение множеств 2) Пересечение. А В.

Пересечением двух множеств называется множество, состоящее из элементов, входящих и в А, и в В.

Рис.3. Пересечение множеств

3) Разность. А\B.

Разностью множеств А и В называется множество, состоящее из элементов, входящих в А, но не входящих в В.

Рис.4. Разность множеств

4) Дополнение. Ā.

Дополнением множества А называется множество, состоящее из элементов не входящих в А.

Рис.5. Дополнение множества А

2.5. Свойства операций

1)Коммутативность.

А B= B A.

A B = B A.

2)Ассоциативность.

А(B C) = (A B) C. A (B C) = (A B) C.

3)Дистрибутивность.

А(B C)=(A B) (A C).

A (B C) = (A B) (A C).

4)Законы Де-Моргана.

	A B = A ∩ B					A B = A B
5)	A A = A			A A = A
6)	A = A			A∩ =
7)	A U = U			A U = A
8)	A		U	A		Ø
		A			A

9)A A

10)A\B= В А

Доказательства.

ство

6

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

Введем обозначения для второго закона дистрибутивности:

D1 = A (B C)

D2 = (A B) (A C)

1.Пусть х D1. Докажем, что х D2.

Так как х

D1, то х принадлежит

объединению, то есть х

А или

хВ C.

a)Пусть х А, тогда, по определению объединения, х A B и, по этому же определению, х A C. Тогда, по определению пересечения, х (A B) (A C). То есть х D2.

b) Пусть х B C. Тогда, по определению пересечения, х B и х C. По определению объединения х A B и х В С. По определению пересечения, х (A B) (A C), то есть х D2.

Так как х - произвольный элемент множества D1, то все элементы множества D1 являются элементами множества D2, то есть D1 –подмножество D2.

2.Пусть у D2. Докажем, что у D1.

Так	как у		D2,	то по	определению	пересечения у		A B и
у A	C.
a)	Пусть	у		А,	тогда,	по	определению	объединения,
у A	(B C) = D1.
b)	Если у не принадлежит А, то у В и у С (так как у						A B и у A C соответственно). По

определению пересечения, у B C. По определению объединения, у A (B C) = D1.

Так как у – произвольный элемент множества D2, то все элементы множества D2 являются элементами множества D1, то есть D2 –подмножество D1, а так как D1 является подмножеством D2, то D1 = D2. Что и требовалось доказать.

Рис.6. Второй закон дистрибутивности

2.6. Разбиение множества на классы

Пусть задано некоторое множество, например, множество треугольников. В этом множестве выделим свой- (например, быть прямоугольным). Тогда множество треугольников разбивается на два класса: прямо-

угольные и непрямоугольные.

Разбиение множества на классы (классификация) означает, что данное множество А разбивается на подмножества k1, k2, … , km таких, что

1)Эти подмножества попарно не пересекаются, то есть ki kj = (i, j = 1,…, m, i ≠ j);

2)Объединение всех подмножеств дает множество А

m

ki A

i 1

3)Ни одно из подмножеств не пусто: k i ≠ .

Пример: Пусть имеется А – множество всех грибов. Свойства:

1)1 – быть съедобным грибом;

2)2 – быть трубчатым грибом.

Таким образом, с помощью этих свойств мы получаем 4 подмножества: съедобные и несъедобные, трубчатые и не трубчатые.

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

7

Пусть В – множество съедобных грибов, а С – множество трубчатых. k1 = B C – съедобные и трубчатые,

k2 =B С – съедобные и не трубчатые,

k3 = В C – несъедобные и трубчатые,

k4 = В ∩ С – несъедобные и не трубчатые.

Рис.7. Разбиение на классы

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

Пусть у нас имеется два элемента a1 и a2. Пара (a1, a2) называется упорядоченной. 1-ый элемент ее – a1, 2-ой

– a2.

Пары (a1, a2) и (b1, b2) считаются равными, если a1 = b1, и a2 = b2. Пара (a1, a2) = (a2, a1), если только a1= a2.

Пусть заданы два множества

А = { a1, a2,…, an} и В = { b1, b2,…, bm}.

Декартовым, или прямым, произведением множества А на множество В называется множество упорядо-

ченных пар, 1-ый элемент которых принадлежит множеству А , а 2-ой – множеству В. Обозначается декартово произведение знаком .

Для данных множеств получим

А В={(a1, b1),( a1, b2),…,( a1, bm),…,( a2, b1),…,( an, bm)}.

Мощность декартового произведения равна n m. Обозначение: |A B| = n m.

Пример 1:

A= {1, 4} и В = {2, 3, 4}.

A B={(1,2),(1,3),(1,4),(4,2),(4,3),(4,4)}.

Геометрически каждой паре чисел соответствует точка координатной плоскости. Для примера 1

Рис.8. Декартово произведение А В для конечных А и В

Пример 2:

A = {x R, \ x [-1; 2]};

B = {y Z, \ y [-3; 3]}.

Рис.9. А В, где А – непрерывное множество

Пример 3:

8

A = {x R, \ x [-1; 2]};

B = {y R, \ y [-3; +∞)}.

Рис.10. А В непрерывных множеств

2.7.1. Декартова степень

Если в качестве множества В в декартовом произведении выбрать множество А, мы будем говорить о декартовом квадрате.

АА = А 2

АА 2 =А 3

…

АА n 1 =А n

2.7.2. Декартово произведение n множеств

Набор n элементов будем называть кортежем.

Декартовым произведением А1 А2 А3 … Аn будем называть множество упорядоченных кортежей, первый элемент которых принадлежит множеству А1, второй множеству А2 и т.д.

2.7.3. Свойства декартового произведения

1)А В ≠ В А.

2)(А В) С ≠ А (В С).

3)А (В С) = (А В) (А С).

4)А (В С) = (А В) (А С).

5)(А В) С = (А С) (В С).

6)(А В) С = (А С) (В С).

7)А (В \ С) = (А В) \ (А С).

8)(А \ B) C = (A C)\ (B C).

Доказательство свойства 3:

Обозначим А (В С) = D1 и (А В) (А С) = D2.

a) Пусть z D1, z – элемент декартового произведения, z = (x,y), где х А, а у (В С), то есть у В и у С по определению пересечения. Тогда (x, y) (А В) и (x, y) (А С). По определению пересечения (x ,y)D2. Мы доказали, что D1 – подмножество D2.

b) Пусть (x, y) D2. Это означает, что (x, y) (А В) и (x, y) (А С) – по определению пересечения. Следовательно, х А, а у В и у С. Так как у В и у С, то у (В С). Следовательно, (x, y) D1. Значит, D2 является подмножеством D1.

По теореме о равенстве множеств D1= D2. Что и требовалось доказать.

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

2.8. Отношения

Пусть заданы два множества А и В. Найдем А В.

Подмножество k А В называется отношением из множества А во множество В.

Отношения задаются знаками =, <, >, , и т.д.

Пример:

А = {2,3,4}, B={1,4,3}.

A B = {(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}.

9

Выделим отношения больше (>) : k1 = {(2,1),(3,1),(4,1),(4,3)} и меньше (<) : k 2 = {(2,4),(2,3),(3,4)}.

Рис.11. Отношение >

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

Пусть отношение k1 А С и отношение k 2 С В.
Композицией этих отношений является отношение k = k1 k2, где	k A B.
Композицией отношений из А в В называется множество пар	(а, b) таких, что, а А, b B и существует

такое с С, что (а, с) k1 и (с, b) k2.

Пример:

А = {2,3,4},

B = {1,4,3}, С = {2,5}

A В = {(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}, A C = {(2,2),(2,5),(3,2),(3,5),(4,2),(4,5)},

C B = {(2,1),(5,1),(2,4),(5,4),(2,3),(5,3)}.

Определим отношение >:

k1 A C = {(3,2),(4,2)}

и отношение <

k2 C B = {(2, 4), (2, 3)}.

Возьмем пару (3,2) k1. В k2 есть пары, начинающиеся с 2. Это пары (2,4) и (2,3). Значит пары (3, 4) и (3, 3) войдут в композицию k.

Берем пару (4,2) k1. В k2 есть пары, начинающиеся с 2. Это те же пары (2,4) и (2,3). Значит пары (4, 4) и (4,

3) войдут в k.
Получим k = k1 k2 = (k A B) = {(3, 4), (3, 3), (4, 4), (4, 3)}.
Таким образом, для элемента (2,4) А В, в k войдут {(2,х), (у,4)}, где (2, х) k1, а (у, 4)									k2 для всех х и
y.
		2.8.2. Отношения на множестве
Если в декартовом произведении в качестве множества В выбрать множество А ( то есть									А А= А 2 ), то
отношение k из А 2	называется отношением на множестве.
Для отношений на множестве вводятся понятия:
Обратное	отношение	–	это		множество	пар	(а,	b)	таких,	что
(b, a) А 2 . Обозначение k -1.
Дополнение – это множество пар (а ,b) k:					.
				k
Тождественное отношение – множество пар (а, а) таких, что,						а А: I = {(a, a), a A}.
Универсальное отношение U = {(a, b), a A, b A}.

2.8.3. Виды отношений

1)Инъекция.

Если каждый элемент множества А соответствует элементу из множества В, то отношение f называется инъективным.

10

Рис.12. Инъекция
2) Сюръекция.
Если для каждого элемента y множества В существует элемент	х А, соответствующий элементу y, то
такое отношение f называется сюръекцией.

Рис.13.Сюръекция.

3)Биекция.

Если для каждого элемента y B существует ровно один элемент х А, которому соответствует y , то такое отношение называется биективным.

Биективное отношение инъективно и сюръективно. Биективное отношение имеет обратное отношение.

Рис.14. Биекция

2.9. Функции

Пусть заданы множества А и В. Найдем А В.

Выберем отношение f А В = {( a1, b1), (a2, b2),…}, состоящее из пар таких, что ai ≠ aj, i, j = 1,2,3,…, т.е. отношение, в котором все первые элементы пар различны. Такие отношения называются функциями.

F	f: A B; b = f (a); a f b.
Способы задания: А В;

Пример: А = {2,3,4}, B = {1,4,3}.

A В = {(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}.

Выделим функции: f1 ={(2,1),(3,1),(4,1)} и f 2 = {(2,4),(3,1),(4,1)}.

Рис.15. Функция f1

Рис.16. Функция f2

2.9.1. Представление функций в ЭВМ

11

Пусть f: A B. Мощность п множества А невелика. Тогда функцию можно задать в виде массива array [1.. n] of B, где В – тип данных, значения которого представляют элементы множества В.

Такое представление функции эффективно по времени, поскольку реализация массивов в большинстве случаев позволяет получить значения за по-

стоянное время, не зависящее ни от размеров массива, ни от значения индекса. Если п достаточно велико, то функцию следует описывать как подпрограмму-функцию.

3. Комбинаторика

Задачи, в которых требуется определить количество возможных операций, называются комбинаторными. Пусть имеется группа некоторых объектов a1, a2, …, am которые мы будем называть элементами.

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

3.1. Размещения

Размещениями из m элементов по n называются соединения, каждое из которых содержит n элементов, взятых из данных m и которые отличаются друг от друга или элементами, или их порядком.

Предполагается, что элементы в одном размещении не повторяются.

3.1.1. Формула числа размещений без повторений

Размещения из m по одному. Очевидно, что их число: А 1m = m.

Составим размещения по 2:

a1 a2 , a1 a3 , a1 a4 ,…, a1 am − размещений (m-1),

a2 a1 , a2 a3 , a2 a4 ,..., a2 am

m – строк a3 a1 , a3 a2 , a3 a4 ,..., a3am

...................................

am a1 , am a2 , am a3 ,..., am am 1

Итого: А 2m = m (m-1).

Размещения по 3:

В каждой строке будет (m-2) размещений.

12

a1a2 a3 , a1a2 a4 ,..., a1a2 am

, a1a3 a4 ,..., a1a3 am

a1a3a2

Am2 − строк

...................................

a

m

a

m 1

a , a

m

a

m 1

a

2

,..., a

m

a

m 1

a

m 2

1

Ясно, что А 3m = А m2 (m-2)

= m (m-1) (m-2).

А m4 = m(m-1)(m-2)(m-3).

………………………………

А mn = m (m-1) (m-2) …. (m-(n-1))

( * )

Пример:

В группе 21 студент. Требуется выбрать старосту, профорга и физорга. Сколькими способами это можно сделать?

Решение:

Каждая тройка студентов может отличаться от другой тройки или распределением обязанностей, или хотя бы одним из студентов, то есть мы должны вычислить число размещений из 21 по 3:

m = 21, n = 3.

А 321 = 21 20 19 = 7980.

3.1.2. Другой вид формулы числа размещений

Умножим числитель и знаменатель формулы ( * ) на (m-n)! Получим

А mn = m (m 1) ... (m n 1) (m n) (m n 1) ... 2 1 ,
(m n) (m n 1) ... 2 1
или		m!
n	=
А m

(m n)!

Каждое размещение содержит одно и то же количество элементов, взятых из данных m элементов.

3.2. Перестановки

Размещения из n элементов по n, каждое из которых отличается друг от друга только порядком элемен-

тов, называются перестановками.

Их число обозначается Pn:

Pn = А nn = n·(n-1) ·(n-2) ·…·2·1, то есть Pn = n!

Пример:

Сколькими способами могут сесть 6 человек на 6-местную лавочку?

Решение:

В данном случае каждое расположение лиц на лавочке отличается от другого расположения только порядком. Поэтому мы имеем дело с перестановками:

P6 = 6! = 720.

3.3. Сочетания

Сочетания – это размещения, каждое из которых отличается от других хотя бы одним элементом. Другими словами: сочетания – это соединения, содержащие n элементов из данных m, отличающиеся хотя

бы одним элементом.

Число сочетаний С nm . Если мы имеем m элементов, и из них составим всевозможные сочетания по n и внутри каждого произведем перестановку, то получим размещения.