Дискретная математика


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




С.В. РЕНИН





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




Утверждено Редакционно-издательским советом университета в качестве конспекта лекций











НОВОСИБИРСК

2011

УДК 519.1 (075.8)
     Р 392

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

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

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


       Ренин С.В.
Р 392 Дискретная математика: конспект лекций /С.В. Ренин. -Новосибирск: Изд-во НГТУ, 2011. - 64 с.

         ISBN978-5-7782-1596-2

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







ISBN 978-5-7782-1596-2

УДК 519.1 (075.8)

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

ОГЛАВЛЕНИЕ



Введение..........................................4
1. МНОЖЕСТВА. ОТНОШЕНИЯ НА МНОЖЕСТВАХ.............4

  1.1. Основные понятия теории множеств...................4
  1.2. Операции над множествами...........................6
  1.3. Алгебра множеств..................................13
  1.4. Соответствия......................................16

2. ТЕОРИЯ ГРАФОВ.............................35

  2.1. Основные понятия и определения.......................35

  2.2. Операции над графами............................39

  2.3. Частичные графы и подграфы.......................40

  2.4. Связность.............................................41

  2.5. Деревья........................................46
3. КОМБИНАТОРИКА......................................54
  3.1. Основные понятия и определения.................54
  3.2. Общие правила комбинаторики....................55
  3.3. Простейшие задачи пересчета....................56
Библиографический список..............................64

ВВЕДЕНИЕ
   Слово «дискретный» происходит от латинского слова discretus, означающего «прерывистый, состоящий из отдельных частей». Дискретная математика - это область математики, занимающаяся изучением дискретных, т. е. состоящих из отдельных частей, структур, которые возникают как в пределах самой математики, так и в ее приложениях. К дискретной математике относят такие разделы, как теория множеств, математическая логика, комбинаторика, теория графов, теория алгоритмов, теория игр, теория кодирования, теория автоматов, теория формальных грамматик и целый ряд других. Некоторые из этих разделов изучаются в рамках учебного плана направления 230100 «Информатика и вычислительная техника» как самостоятельные дисциплины. В курсе «Дискретная математика», для которого написан настоящий конспект лекций, рассматриваются элементы теории множеств, теории графов и некоторые разделы комбинаторики.

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

1.1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ
   Понятие «множество», подобно понятию «число» и ряду других элементарных математических понятий, не может быть строго математически определено. Мы под множеством будем понимать совокупность индивидуально различимых объектов любой природы, называемых элементами данного множества. Например, множество студентов данной учебной группы, множество учебных групп в университете, множество рыб в океане, множество планет Солнечной системы, но нельзя говорить о множестве капель в стакане воды, так как они друг от друга неотделимы. Как видно из второго примера, элементами множества могут быть другие множества.
   Множества принято обозначать большими буквами латинского алфавита, иногда с использованием индексов, элементы множества обозначаются обычно малыми буквами.


4

   Существует два основных способа задания множеств:
   1)    перечисление элементов множества, например, множество X, состоящее из элементов х ₁, х₂, х₃, записывают как Х = {х ₁, х₂, х₃};
   2)    указание свойства, которым обладают все элементы данного множества и только такие элементы, например, множество простых чисел Х= {х | х - простое число}.
   Для обозначения принадлежности некоторого элемента данному множеству используется значок е (от первой буквы греческого слова гоп. - быть). Например, если элемент х принадлежит множеству X, то это записывается как х е X. Если элемент х не принадлежит X, то пишут х <£ X.
   Множество называется конечным, если оно состоит из конечного числа элементов. Например, множество жителей г. Новосибирска, множество студентов учебной группы.
   Множество называется бесконечным, если число его элементов бесконечно. Например, множество натуральных чисел N = {1, 2, 3, ...}, множество вещественных чисел, множество точек плоскости.
   Бесконечное множество называется счетным, если его элементы можно занумеровать, т. е. установить взаимно однозначное соответствие между элементами этого множества и элементами множества натуральных чисел. Например, само множество натуральных чисел N, множество четных чисел, множество нечетных чисел, множество целых чисел Z = {..., -3, -2, -1, 0, 1, 2, 3,...}.
   Посмотрим, как, например, можно занумеровать элементы множества целых чисел. Обозначим п(z) номер целого числа z. Тогда можно установить следующее правило для вычисления п (z):

п ⁽z⁾ ⁻

(2z для [-2 z +1

z > 0, для z < 0.

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


п (z) / 2, если п - четное число,

z - ■! п (z) -1

-2

если п - нечетное число.

5

   В справедливости этих правил убедитесь самостоятельно.
   Эти правила устанавливают взаимно однозначное соответствие между элементами множества целых чисел и элементами множества натуральных чисел, следовательно, множество целых чисел является счетным.
   Бесконечное множество, не являющееся счетным, называется несчетным. Например, множество точек плоскости, множество вещественных чисел.
   Если множество не содержит ни одного элемента, то оно называется пустым и обозначается 0. Например, пусто множество людей, имеющих рост выше 3 метров. Пусто множество студентов Института социальной реабилитации (ИСР) НГТУ, имеющих диплом о высшем образовании.
   Множество А называется подмножеством множества В, если любой элемент А является и элементом множества В. Это обозначается так: А сВ. Например, множество студентов отдельной группы ИСР есть подмножество множества всех студентов ИСР, а множество студентов ИСР является подмножеством множества студентов НГТУ.
   Если множество А является подмножеством множества В и при этом может совпадать с В, то знак с подчеркивают: с.
   Множество называется универсальным, если все другие рассматриваемые в данной задаче множества являются его подмножествами. Мы будем обозначать такое множество латинской буквой I. Например, если в задаче рассматриваются множество вещественных чисел R, множество целых чисел Z, множество натуральных чисел N и множество рациональных чисел F, то для всех этих множеств множество R является универсальным множеством, так как ZcR, NcR и FcR. То есть в данном случае I = R.

1.2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

1.2.1. ОБЪЕДИНЕНИЕ МНОЖЕСТВ
   Обозначение: U
   Определение. Объединением двух множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые входят в множество А или в множество В или в оба вместе, причем элементы, принадлежащие обоим множествам одновременно, входят в объединение только один раз.


6

   Если С = А U В , то С = { с | с е А или с е В, или с е А и В одновременно}.
   Операции над множествами можно наглядно изобразить с помощью так называемых диаграмм Эйлера-Венна. На этих диаграммах универсальное множество изображается в виде прямоугольника, а множества, участвующие в операции, - кругами.
   Диаграмма Эйлера-Венна для объединения множеств показана на рис. 1.1 (результат объединения заштрихован).

   Пример 1.1. 1. Пусть А = {а, b, с, d}, В = {с, d, е, _/}, тогда С = =A U В = {а, b, с, d, е,/}.
   2.    Пусть Z¹ - множество целых положительных чисел, Z - множество целых отрицательных чисел, О = {0}, тогда С = Z U Z U О = Z -множество всех целых чисел.
   3.    Пусть А - множество студентов учебной группы, которые учатся на отлично; В - множество студентов этой группы, которые учатся без троек; С - множество студентов этой группы, имеющих удовлетворительные оценки; D - множество студентов этой группы, имеющих неудовлетворительные оценки, тогда Е = A U В U С U D - множество всех студентов этой группы. ■
   Свойства: 1) коммутативность (переместительный закон): A U5 = = В U А;
   2)    ассоциативность (сочетательныйзакон): A UВ UС = (A U5) U С = = А U (В U Q;
   3)   если А ^В, то А U В = В;
   4)   Л U 1 = 1;
   5)   А U0=А.

7

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

1.2.2. ПЕРЕСЕЧЕНИЕ МНОЖЕСТВ
   Определение. Пересечением двух множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые входят в множества А и В одновременно.
   Обозначение: П
   Если С - А П В , то С ={ с \ с е А и с е В }
   Диаграмма Эйлера-Венна для пересечения множеств показана на рис. 1.2 (результат пересечения заштрихован).


   Пример 1.2. 1. Пусть А = {а, b, с, d}, В = {с, d, е,/}, тогда С = А П В= ={ с, d}
   2.    Пусть Z¹ - множество целых положительных чисел, Z - множество целых отрицательных чисел, О = {0}, тогда С = Z П Z П 0 = 0-так как не существует чисел, одновременно положительных, отрицательных и равных нулю.
   3.    Пусть А - множество студентов учебной группы, которые учатся на отлично; В - множество студентов этой группы, которые учатся без троек; С - множество студентов этой группы, имеющих удовлетвори

8

тельные оценки, D - множество студентов этой группы, имеющих неудовлетворительные оценки, тогда Е = А П В П С П D = 0, так как нет ни одного студента, который бы одновременно входил во все четыре множества А, В, Си D ,F = А П В = А, так как каждый студент, который учится на отлично, не имеет троек, но студент, не имеющий троек, не обязательно учится на отлично. ■
   Свойства: 1) коммутативность (переместительный закон): АП В = = В П А ;
   2)    ассоциативность (сочетательныйзакон): А ПВ ПС = (А ПЬ’) ПС = = А П (В П О;
   3)    если А ^ В, то А П В = А;
   4)    А П 1 = А;
   5)    А П 0 = 0;
   6)    дистрибутивность (распределительный закон) пересечения относительно объединения: А П (В U С) = (А П В) U (А П Q;
   7)    дистрибутивность (распределительный закон) объединения относительно пересечения: A U (В П С) = (A U В) П (A U С).
   Первые пять свойств следуют из определения операции пересечения, все эти свойства легко проверяются с помощью диаграмм Эйлера-Венна (проделайте это самостоятельно).
   Нетрудно видеть, что пересечение множеств является частичным аналогом алгебраического умножения, если считать пустое множество аналогом нуля, а универсальное множество - аналогом единицы (см. свойства 1, 2, 4 и 5). Поэтому эту операцию иногда называют умножением множеств. Свойство 6 полностью аналогично известному из алгебры распределительному закону умножения относительно сложения, если считать, как мы это уже сделали, объединение аналогом сложения, а пересечение - аналогом умножения. Свойство 7 не имеет аналогов в обычной алгебре, но его легко запомнить, так как оно получается из свойства 6 взаимной заменой операций объединения и пересечения.


1.2.3. РАЗНОСТЬ И ДОПОЛНЕНИЕ МНОЖЕСТВ
   Определение. Разностью множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые входят в множество А, но не входят в множество В.

9

   Обозначение: \
   Если С = А \В, то С = {с | с е А и с £ В }.
   Диаграмма Эйлера-Венна для разности множеств показана на рис. 1.3 (разность заштрихована).


Рис. 1.3

   Пример 1.3. 1. Пусть А = {а, b, с, d}, В = {с, d, е, f}, тогда С=А\В={ а ,b }.
   2.     Пусть Z - множество целых положительных чисел, Z - множество целых отрицательных чисел, тогда С = Z\Z = Z, так как у множеств Z M.Z нет общих элементов.
   3.     Пусть А - множество студентов учебной группы, которые учатся на отлично; В - множество студентов этой группы, которые учатся без троек; С - множество студентов этой группы, имеющих удовлетворительные оценки, тогда D = А\В = 0, так как все отличники не имеют троек, т. е. А с В; Е = В\А - множество студентов, которые учатся на хорошо и отлично или только хорошо; F = С\А = С, так как ни один элемент А не входит в С. ■
   Частным случаем разности множеств является дополнение.
   Определение. Дополнением множества А называется разность 1\А.
   Обозначение: А
   Диаграмма Эйлера-Венна для дополнения показана на рис. 1.4 (дополнение заштриховано).
   Используя диаграммы Эйлера-Венна, нетрудно убедиться в справедливости равенства А \ В = А П В (сделайте это самостоятельно).


10

   Пример 1.4. 1. Пусть I = R - множество вещественных чисел, С -множество рациональных чисел, тогда С есть множество иррациональных чисел.
   2.    Пусть I = Z - множество целых чисел, N - множество натуральных чисел, тогда N есть множество целых неположительных чисел.
   3.    Пусть I - множество студентов учебной группы, А - множество успевающих студентов этой группы, тогда А - множество неуспевающих студентов этой группы. ■



1.2.4. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ

   Определение. Декартовым произведением двух множеств (А и В) называется множество всех возможных упорядоченных пар, в каждой из которых первый элемент принадлежит первому множеству (А), а второй элемент принадлежит второму множеству (В).
   Обозначение: х
   Если D = Ах В, то D = {(а, b )\ а е А, b е В}.
   Аналогично определяется декартово произведение трех и более множеств. Элементами декартова произведения п множеств являются упорядоченные наборы из п элементов, называемые в общем случае кортежами, или п-ками, в частных случаях - тройками, четверками и т. д., т. е.


D — А х А х... х А 12                     п

{(а1,

i — 1,п}.

а,,..., а ) а. е А., 2'    ' п / l I⁷

11