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

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




С.В. РЕНИН





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




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











НОВОСИБИРСК

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