Конспект_лекций_по_курсу_Дискретная_математика

Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

________________________________________________________________

С.В. РЕНИН

ДИСКРЕТНАЯ МАТЕМАТИКА

Конспект лекций для студентов II курса Института социальной реабилитации

Новосибирск

2011

УДК 519.1 (075.8)

Рецензенты В.Г. Секаев, канд. техн. наук, доц.,

В.Е. Хиценко, канд. техн. наук, доц.

Работа выполнена на кафедре автоматизированных систем управления для студентов Института социальной

реабилитации НГТУ, обучающихся по направлению бакалаврской подготовки

230100 – Информатика и вычислительная техника

Ренин, С.В.

Дискретная математика. Конспект лекций. – Новосибирск: Изд-во НГТУ,

2011.

Конспект лекций содержит описание основных понятий и методов реше-

ния задач дискретной математики, относящихся к теории множеств, теории графов и комбинаторике, и предназначается студентам Института социальной реабилитации НГТУ, обучающимся по направлению 230100 "Информатика и вычислительная техника", для использования при подготовке к учебным заня-

тиям и при самостоятельной работе над курсом.

УДК 519.1 (075.8)

© С.В. Ренин, 2011

© Новосибирский государственный технический университет, 2011 г.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.......................................................................................................................	3
1. МНОЖЕСТВА. ОТНОШЕНИЯ НА МНОЖЕСТВАХ ........................................	4
1.1. Основные понятия теории множеств ...................................................................	4
1.2. Операции над множествами ..................................................................................	6
1.3. Алгебра множеств.................................................................................................	13
1.4. Соответствия .........................................................................................................	15
2. ТЕОРИЯ ГРАФОВ ....................................................................................................	35
2.1. Основные понятия и определения ......................................................................	35
2.2. Операции над графами.........................................................................................	39
2.3. Частичные графы и подграфы.............................................................................	40
2.4. Связность ...............................................................................................................	41
2.5. Деревья...................................................................................................................	47
2.6. Поиск кратчайших и длиннейших путей в графе .............................................	50
3. КОМБИНАТОРИКА ................................................................................................	54
3.1. Основные понятия и определения ......................................................................	54
3.2. Общие правила комбинаторики ..........................................................................	55
3.3. Простейшие задачи пересчета.............................................................................	56
ЛИТЕРАТУРА ...............................................................................................................	64

ВВЕДЕНИЕ

Слово "дискретный" происходит от латинского слова discretus, означающего

"прерывистый, состоящий из отдельных частей". Дискретная математика – это об-

ласть математики, занимающаяся изучением дискретных, т.е. состоящих из от-

дельных частей, структур, которые возникают как в пределах самой математики,

так и в её приложениях. К дискретной математике относят такие разделы матема-

тики, как теория множеств, математическая логика, комбинаторика, теория гра-

фов, теория алгоритмов, теория игр, теория кодирования, теория автоматов, тео-

рия формальных грамматик и целый ряд других. Некоторые из этих разделов изу-

чаются в рамках учебного плана направления 230100 "Информатика и вычисли-

тельная техника" как самостоятельные дисциплины. В курсе "Дискретная матема-

тика", для которого написан данный конспект лекций, рассматриваются элементы теории множеств, теории графов и некоторые разделы комбинаторики.

-3-

1. МНОЖЕСТВА. ОТНОШЕНИЯ НА МНОЖЕСТВАХ

1.1. Основные понятия теории множеств

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

ектов любой природы, называемых элементами данного множества. Например,

множество студентов данной учебной группы, множество учебных групп в уни-

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

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

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

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

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

1)перечисление элементов множества, например, множество Х, состоящее из элементов x1, x2, x3, записывают как X = {x1, x2, x3};

2)указание свойства, которым обладают все элементы данного множества, и

только такие элементы, например, множество простых чисел X = {x | x – простое число}.

Для обозначения принадлежности некоторого элемента данному множеству используется значок (от первой буквы греческого слова – быть). Например,

если элемент x принадлежит множеству X, то это записывается как x X. Если эле-

мент x не принадлежит X, то пишут x Х.

Множество называется конечным, если оно состоит из конечного числа эле-

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

-4-

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

Например, множество натуральных чисел N = {1, 2, 3, ...}, множество веществен-

ных чисел, множество точек плоскости.

Бесконечное множество называется счетным, если его элементы можно за-

нумеровать, т.е. установить взаимно однозначное соответствие между элементами этого множества и элементами множества натуральных чисел. Например, само множество натуральных чисел N, множество четных чисел, множество нечетных чисел, множество целых чисел Z = {..., –3, –2, –1, 0, 1, 2, 3, ...}.

Посмотрим, как, например, можно занумеровать элементы множества целых чисел. Обозначим n(z) номер целого числа z. Тогда можно установить следующее правило для вычисления n(z):

2z для z 0

n(z) 2z 1 для z 0

При использовании этого правила положительные числа получат четные но-

мера, а 0 и отрицательные числа – нечетные, и каждое целое число получит свой вполне определенный номер, равный некоторому натуральному числу. Наоборот,

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

n(z) / 2, если n четное число,
z n(z) 1		, если n нечетное число.
	2

В справедливости этих правил убедитесь самостоятельно.

Эти правила устанавливают взаимно однозначное соответствие между эле-

ментами множества целых чисел и элементами множества натуральных чисел,

следовательно, множество целых чисел является счетным.

Бесконечное множество, не являющееся счетным, называется несчетным.

Например, множество точек плоскости, множество вещественных чисел.

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

и обозначается . Например, пусто множество людей, имеющих рост выше 3 мет-

-5-

ров. Пусто множество студентов Института социальной реабилитации (ИСР)

НГТУ, имеющих диплом о высшем образовании.

Множество A называется подмножеством множества B, если любой элемент

A является и элементом множества B. Это обозначается так: A B. Например, мно-

жество студентов отдельной группы ИСР есть подмножество множества всех сту-

дентов ИСР, а множество студентов ИСР является подмножеством множества сту-

дентов НГТУ.

Если множество A является подмножеством множества B и при этом может совпадать с B, то знак подчеркивают: .

Множество называется универсальным, если все другие рассматриваемые в данной задаче множества являются его подмножествами. Мы будем обозначать такое множество латинской буквой I. Например, если в задаче рассматриваются множество вещественных чисел R, множество целых чисел Z, множество нату-

ральных чисел N и множество рациональных чисел F, то для всех этих множеств множество R является универсальным множеством, так как Z R, N R и F R. Т.е.

в данном случае I = R.

1.2.Операции над множествами

1.2.1.Объединение множеств

Обозначение:

Определение. Объединением двух множеств A и B называется множество, со-

стоящее из всех тех и только тех элементов, которые входят в множество A или в множество B или в оба вместе, причем элементы, принадлежащие обоим множест-

вам одновременно, входят в объединение только один раз.

Если C A B , то C = {c| c A или c B или c A и B одновременно}.

Операции над множествами можно наглядно изобразить с помощью так на-

зываемых диаграмм Эйлера-Венна. На этих диаграммах универсальное множество изображается в виде прямоугольника, а множества, участвующие в операции, –

кругами.

-6-

Диаграмма Эйлера-Венна для объединения множеств показана на рис. 1.1 (ре-

зультат объединения заштрихован).

I

A B

A B

Рис. 1.1

Пример 1.2.1. 1. Пусть A = {a, b, c, d}, B = {c, d, e, f}, тогда C = A B = {a, b,

c, d, e, f}.

2.Пусть Z+ – множество целых положительных чисел, Z – множество целых отрицательных чисел, О = {0}, тогда C = Z+ Z O = Z – множество всех целых чисел.

3.Пусть A – множество студентов учебной группы, учащихся на отлично, B –

множество студентов этой группы, учащихся без троек, C – множество студентов этой группы, имеющих удовлетворительные оценки, D – множество студентов этой группы, имеющих неудовлетворительные оценки, тогда E = A B C D –

множество всех студентов этой группы.

Свойства: 1) коммутативность (переместительный закон): А В = B A;

2)ассоциативность (сочетательный закон): А В С = (А В) С = А (В С);

3)если A B, то A B = B;

4)А I = I;

5)A = A.

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

ряются с помощью диаграмм Эйлера-Венна (проделайте это самостоятельно).

Нетрудно видеть, что объединение множеств является частичным аналогом алгебраического сложения, если считать пустое множество аналогом нуля (см.

свойства 1, 2 и 5). Поэтому эту операцию иногда называют сложением множеств.

-7-

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

Определение. Пересечением двух множеств A и B называется множество, со-

стоящее из всех тех и только тех элементов, которые входят во множества A и B

одновременно.

Обозначение:

Если C A B , то C = {c| c A и c B}

Диаграмма Эйлера-Венна для пересечения множеств показана на рис. 1.2 (ре-

зультат пересечения заштрихован).

I

A B

A B

Рис. 1.2

Пример 1.2.2. 1. Пусть A = {a, b, c, d}, B = {c, d, e, f}, тогда C=A B={c, d}

2.Пусть Z+ – множество целых положительных чисел, Z – множество целых отрицательных чисел, О = {0}, тогда C = Z+ Z O = – так как не существует чисел, одновременно положительных, отрицательных и равных нулю.

3.Пусть A – множество студентов учебной группы, учащихся на отлично, B –

множество студентов этой группы, учащихся без троек, C – множество студентов этой группы, имеющих удовлетворительные оценки, D – множество студентов этой группы, имеющих неудовлетворительные оценки, тогда E = A B C D = = , так как нет ни одного студента, который бы одновременно входил во все че-

тыре множества A, B, C и D, F = A B = A, так как каждый студент, учащийся на отлично, не имеет троек, но студент, не имеющий троек, не обязательно учится на отлично.

Свойства: 1) коммутативность (переместительный закон): A B = B A

2)ассоциативность (сочетательный закон): А В С = (А В) С = А (В С)

3)если A B, то A B = A;

-8-

4)А I = A;

5)A = ;

6)дистрибутивность (распределительный закон) пересечения относительно объе-

динения: А (В С) = (А В) (А С);

7) дистрибутивность (распределительный закон) объединения относительно пере-

сечения: А (В С) = (А В) (А С)

Первые пять свойств следуют из определения операции пересечения, все эти свойства легко проверяются с помощью диаграмм Эйлера-Венна (проделайте это самостоятельно).

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

универсальное множество аналогом единицы (см. свойства 1, 2, 4 и 5). Поэтому эту операцию иногда называют умножением множеств. Свойство 6 полностью аналогично известному из алгебры распределительному закону умножения отно-

сительно сложения, если считать, как мы это уже сделали, объединение аналогом сложения, а пересечение аналогом умножения. Свойство 7 не имеет аналогов в обычной алгебре, но его легко запомнить, так как оно получается из свойства 6

взаимной заменой операций объединения и пересечения.

1.2.3. Разность и дополнение множеств

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

Обозначение: \

Если C = A\B, то C = {c| c A и c B}

Диаграмма Эйлера-Венна для разности множеств показана на рис. 1.3 (раз-

ность заштрихована).

-9-

I

A B

A \ B

Рис. 1.3

Пример 1.2.3. 1. Пусть A = {a, b, c, d}, B = {c, d, e, f}, тогда C=A\B={a, b}.

2. Пусть Z+ – множество целых положительных чисел, Z – множество целых отрицательных чисел, тогда C = Z+\Z = Z+, так как у множеств Z+ и Z нет общих элементов.

3. Пусть A – множество студентов учебной группы, учащихся на отлично, В –

множество студентов этой группы, учащихся без троек, С – множество студентов этой группы, имеющих удовлетворительные оценки, тогда D = A\B = , так как все отличники не имеют троек, т.е. А В; E = B\A – множество студентов, учащихся на хорошо и отлично или только хорошо; F = C\A = C, так как ни один элемент A

не входит в С.

Используя диаграммы Эйлера-Венна, нетрудно убедиться в справедливости равенства A \ B A B (сделайте это самостоятельно).

Частным случаем разности множеств является дополнение.

Определение: Дополнением множества A называется разность I\A.

Обозначение: А

Диаграмма Эйлера-Венна для дополнения показана на рис. 1.4 (дополнение заштриховано).

-10-