Дискретная математика (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«Московский государственный институт электроники и математики

(технический университет)»

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

Утверждено Редакционно–издательским советом института в качестве учебного пособия

Москва 2011

УДК 51

ББК 16.2.12

З-38

Рецензенты:

д-р. техн. наук, проф. (декан факультета «Информатика в экономике» Социально-экономического института);

зам. нач. отделения «Циклон» .

З-38 Дискретная математика: Учебное пособие. - Моск. гос. ин-т электроники и математики. М., 20с.

ISBN

Предназначено для усвоения лекций по дискретной математике и для самостоятельного изучения теории множеств, отношений, функций, специальных бинарных отношений, алгебраических структур, кодирования, комбинаторики и теории графов. Будет полезным при решении задач на семинарах по дискретной математике в курсе дискретной математики студентами I (дневного) и II (вечернего) курсов специальности 22.0101.

ISBN УДК 51

ББК 16.2.12

© , 2011

© Московский государственный

институт электроники и

математики, 2011

Оглавление

стр.

Теория множеств

Глава 1. Счётные множества и континуум. Теорема Кантора________ 4

Множества и операции над ними_______________________ 5

Глава 2. Отношения и функции__________________________________ 9

Глава 3. Специальные бинарные отношения_______________________ 12

Алгебраические структуры

Глава 4. Алгебраические операции. Алгебры, решётки ______________ 18

Глава 5. Алгебры с одной операцией: группы, полугруппы, моноиды__ 23

Циклические группы и группы подстановок______________ 27

Изоморфизм групп____________________________________31

Смежные классы по подгруппе. Теорема Лагранжа_________33

Глава 6. Алгебры с двумя операциями: кольца и поля________________ 39

Теория кодирования

Глава 7. Расстояние Хемминга___________________________________ 44

Матричное кодирование. Групповые коды________________ 46

Коды Хемминга_______________________________________48

Кода Хаффмана_______________________________________50

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

Глава 8. Размещения и сочетания _________________________________ 52

Разбиения_____________________________________________54

Полиномиальная формула_______________________________55

Производящая функция________________________________ 55

Глава 9. Формула включений и исключений._______________________ 57

Теория графов.

Глава 10. Графы: основные понятия_______________________________ 65

Матрица смежности графов_____________________________71

Связность графов______________________________________72

Глава 11. Орграфы: основные понятия_____________________________76

Матрица смежности орграфов___________________________79

Связность орграфов____________________________________81

Глава 12. Маршруты в графах и пути в орграфах_____________________83

Эйлеровы цепи и циклы________________________________83

Гамильтоновы цепи и циклы___________________________86

Метод латинской композиции__________________________89

Минимальные маршруты и пути________________________91

Глава 13. Деревья. Циклы в двудольных графах_____________________95

Глава 14. Теорема Холла. Цепи Маркова__________________________100

Глава 15. Планарность и теорема Куратовского. Грани графа.

Теорема Эйлера_____________________________________109

Глава 16. Задачи коммивояжёра и водопроводчика_________________113

Глава 17. Раскрашивание графов. Хроматические многочлены_______120

Теория множеств

Глава 1. Счётные множества и континуум. Теорема Кантора

Множество – это совокупность различимых между собой объектов. Если в векторе могут быть одинаковые элементы, то в множестве нет. Элемент a принадлежит множеству A (aA), а элемент b не принадлежит множеству B (bB). Множество A является подмножеством множества B (AB), при этом A может и совпасть с B. Множество A является собственным подмножеством множества B (AB), при этом A не может совпасть с B, т. е. существует по крайней мере один элемент из множества B, который не является элементом A, хотя все элементы множества A являются и элементами множества B.

В теории множеств принято различать символы и . Если aA, то {a}A. Другими словами, из элемента множества можно сделать подмножество мощности единица, но сам элемент не является подмножеством.

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

Множество A целых чисел от 1 до 5 включительно можно задать списком его элементов: A={1, 2, 3, 4, 5}, или так: A={x: xN и 0<x<6}. N – это множество натуральных чисел. Символы двоеточия и вертикальная черта оба означают одно и то же «таких, что». Множество Kop корней уравнения можно задать так: Kop = {y: y*y +5*y –100 = 0}. Множество Ch чётных чисел можно задать так: Ch = {j: существует kZ: j=2*k}. Z – множество целых чисел.

Пустое множество () является подмножеством любого множества: . = 0. Универсальное множество (U) содержит любое множество: U.

Между множествами одинаковой мощности A и B можно установить взаимно однозначное соответствие. Это значит, что каждый элемент первого множества будет поставлен в соответствие с только одним элементом второго множества, и наоборот, каждый элемент второго множества будет поставлен в соответствие с только одним элементом первого множества. Получим множество пар той же мощности, что и исходные множества. Исходные множества в этом случае называются эквивалентными (A~B).

Например, множество {0, 1, 2, 3} и множество {5, 7, 10, 13} эквивалентны. Взаимно однозначное соответствие между ними: 0~5, 1~7, 2~10 и 3~13. Для этих множеств существует 4! (n!, если мощность множеств равна n) способов установить взаимно однозначное соответствие.

Множество счётно, если между его элементами и множеством натуральных чисел можно установить взаимно однозначное соответствие (перенумеровать множество). Докажем, что множество N= N*N (множество пар натуральных чисел) счётно. Выпишем множество N*N:

(1,1) (1,2) (1,3) ….

(2,1) (2.2) (2,3) ….

(3,1) (3.2) (3,3) ….

…………………………

Если начнём нумеровать первый ряд слева направо, то второй и остальные ряды останутся не нумерованными, Аналогично, если начнём нумеровать первый столбец сверху вниз, то второй и остальные столбцы останутся не нумерованными. Разобьём N*N на конечные подмножества: N1={(1,1)}, N2={(1,2),(2,1)}, … , Ni={(a, b): a+b=i+1}. В подмножестве Ni ровно I пар натуральных чисел. Номер пары (a, b) равен 1+2+…+(i-1)+a=a+(i*(i-1))/2. Нумеруем не по горизонталям и не вертикалям, а по диагоналям. Число пар на каждой диагонали конечно и равно мощности соответствующего этой диагонали подмножества.

Объединение (совокупность) конечного числа счётных множеств счётно: сначала нумеруем первые элементы множеств, потом вторые и так далее. Объединение счётного числа конечных множеств тоже счётно: сначала нумеруем первое множество, потом второе и так далее. Счётно и объединение счётного числа счётных множеств (без доказательства).

Теорема Кантора: множество всех действительных чисел отрезка [0,1] не счётно (континуум). Доказываем от противного, то есть предполагаем, что это множество нумеруется, выписываем этот ряд и находим действительное число из этого отрезка, не попавшее в этот ряд:

0, a11 a12 a13 … 0,985…

0, a21 a22 a23 … 0,034…

0, a31 a32 a33 … 0,127…

………………………………………………….

Здесь ajk целые числа от нуля до девяти включительно. Слева ряд выписан в общем виде, а справа приведён конкретный пример такого ряда. Число 0, b1 b2 b3 … не попало в этот ряд при условии, что b1a11, b2a22, b3a33 … Это число не совпадёт с первым числом в ряду, так как b1 не равно a11, …, это число не совпадёт с j-м числом в ряду, так как bj не равно ajj. Очевидно, что таких чисел много, но для доказательства теоремы достаточно одного такого числа.

Для конкретного ряда справа это число равно, например, 0,326…, 39, 23, 67. Теорема доказана. Такой метод доказательства называется диагональным методом Кантора. В теории множеств две бесконечности: счётная и континуум, кардинальное число которого равно c.

Множество P простых чисел (которые имеют делителями только единицу и самих себя) является подмножеством множества N натуральных чисел (целых, не отрицательных чисел). Поскольку множество N счётно по определению, то множество P может быть либо счётным, либо конечным.

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

Следовательно, полученное после вычитания (прибавления) из произведения всех чисел конечного множества единицы число, будет или новым простым, или будет делиться на новое простое число, не входящее в конечное множество. Теорема доказана.

Множества и операции над ними

Множество степень P(A) – это множество всех подмножеств A. Теорема: если = n, то . Доказательство: каждому подмножеству множества A поставим в соответствие двоичное число длины n по следующему правилу: если элемент множества A входит в подмножество, то на соответствующей этому элементу позиции двоичного числа находится единица, в противном случае – ноль. Например, при n = 3 и A = {1, 2, 3}. Тогда P(A) = {, {1}, {2}, {3}, {1, 2}, (1, 3}, {2, 3}, A}.

000, 100, 010, 001, 110, 101, 011, 111

Под подмножествами находятся соответствующие им двоичные числа длины три. Получили взаимно однозначное соответствие между подмножествами и соответствующими им двоичными числами. Есть подмножество – получим двоичное число, и наоборот, есть двоичное число – получим соответствующее ему подмножество.

У множеств, находящихся во взаимно однозначном соответствии, одинаковая мощность. Мощность множества – степени определить не просто, а вот число двоичных чисел длины n известно, и равно 2. На каждой из n позиций двоичного числа имеется две возможности: 0 и 1. При n = 3 число подмножеств равно 8. Взаимно однозначное соответствие устанавливалось для определения мощности множеств. Теорема доказана.

Если A счётно, то P(A) – континуум, что доказывается диагональным методом Кантора.

Объединением множеств A и B называется множество элементов, входящих или в A или в B: AB={x: xA или xB}. Диаграмма Эйлера-Венна для объединения (объединение заштриховано):

Пересечением множеств A и B называется множество элементов, входящих и в A и в B: AB=A&B={x: xA и xB}. Диаграмма Эйлера-Венна для пересечения (пересечение заштриховано):

ABAAB и ABBAB

Инверсия (абсолютное дополнение) множества A – это множество элементов, которые не принадлежат множеству A: A={x: xA}. U= и =U. Диаграмма Эйлера-Венна для инверсии имеет вид (инверсия заштрихована):

Разностью между A и B (относительное дополнение множества B до множества A или A минус B) называется множество элементов, входящих в A и не входящих в B: A/B ={x: xA и xB}. Диаграмма Эйлера-Венна для разности (она заштрихована):

A/B=AB, A=U/A.

Симметрической разностью множеств A и B называется множество элементов, входящих или в A, но не входящих в B, или входящих в B, но не входящих в A. A+B=(A/B)(B/A)=(AB)(BA)=(AB)/(AB).

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

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

При решении задач по теории множеств можно пользоваться основными тождествами алгебры множеств:

1. АВ=BA (комму - 1’. АВ=BA (комму -

тативность ); тативность );

2. А (ВC)=(AB) C (ассоциа - 2’. А (ВC)=(AB) C (ассоциа -

тивность ); тивность );

3. А (ВC)=(AB) (AC) 3’. А (ВC)=(AB) (AC)

(дистрибутивность (дистрибутивность

относительно ); относительно )

4. A=A 4’. AU=A

5. AA= U 5’. AA =

6. AA= A 6’. AA =A

7. AU=U 7’. A=

8. (AB)=AB (закон 8’. (AB)=AB (закон

Моргана) Моргана)

9. А (ВA)=A (закон поглощения) 9’. А (ВA)=A (закон

поглощения)

Законы Моргана работают и для объединения и пересечения нескольких множеств. Для каждых множеств A и B три последующих выражения попарно эквивалентны: (AB)~(AB=A)~(AB=B). Если AB=, то AB и BA.

В теории множеств A=B тогда и только тогда, когда AB и BA, поэтому при доказательстве тождеств надо сначала брать любой элемент x из правой части тождества и доказать, что он принадлежит и левой его части, а затем брать любой элемент x из левой части тождества и доказать, что он принадлежит и правой его части. Это первый точный способ доказательства тождеств. Например, докажем тождество 8: пусть x(AB)x AB x A и x B xAB.

По опред.

Под двойной двусторонней стрелкой указано, определение какой операции использовано. Поскольку стрелка двусторонняя, то любой элемент x из левой части тождества 8 принадлежит и правой его части и наоборот, но не всегда стрелка бывает двусторонней. Если надо только доказать, что левое выражение является подмножеством правого, то достаточно брать любой элемент x из левого выражения и доказать, что он принадлежит и правому.

Во втором точном способе доказательства тождеств используются основные тождества. При втором способе надо или правую часть тождества свети к левой его части, или наоборот, левую к правой, или свести обе части тождества к одному и тому же выражению (используя основные тождества алгебры множеств). Например: докажем, что если АВ=A, то АВ=B. АВ=(АВ) В=B.

По услов. 9

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

Глава 2. Отношения и функции

<x, y> - это упорядоченная пара. <x, y>=<u, v> тогда и только тогда, когда x=u и y=v. Существуют и упорядоченные тройки, четвёрки, … , n-ки в общем случае.

Бинарное отношение (далее просто отношение) – это множество упорядоченных пар. Координаты отношения – это x и y. Если упорядоченная пара <x, y> принадлежит отношению (<x, y>), то тогда x принадлежит области определения отношения (D), а y – области его значений (R).

Примерами отношений являются базы данных. Например, база данных ЗАГС: пары муж и жена. Большинство договоров бывают двусторонними: покупатель и продавец, поставщик и заказчик и так далее. Редко когда договора бывают трёхсторонними. Набор договоров – тоже база данных.

Области определения и области значения у отношения могут и совпасть. Если X=Y, то это отношение на множестве X. Отношением на целых числах является «быть меньше» (“<”). Пара <1,3> входит в отношение “<”, а пара <5,3> - нет, так как 1<3, а 5 не меньше 3.

Конечное отношение (когда области определения и значений конечны) может быть задано матрицей отношения, состоящей из нулей и единиц. Строки матрицы отношения соответствуют элементам из области определения, а столбцы – из области значений. Если пара <x, y>, то элемент матрицы отношения на пересечении строки, соответствующей x, и столбца, соответствующего y, равен единице; и этот элемент будет нулевым, если <x, y>.

Например, отношение на множестве целых чисел от 1 до 4 включительно ({1, 2, 3, 4} – область определения и область значений отношения) «быть меньше» задаётся матрицей:

В этой таблице координаты отношения и само отношение взяты в кавычки, а нули и единицы, задающие пары отношения, – нет.

Прямым произведением AB двух произвольных множеств A и B является множество всех упорядоченных пар <a, b>, таких что, aA и bB. Прямое произведение – это пример отношения. Для конечных множеств A и B матрица его прямого произведения состоит из одних единиц и .

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

Любое отношение на множествах A и B будет подмножеством их прямого произведения. Прямое произведение не коммутативно, т. е. может быть не равно . Например, A={1,2} и B={3,4}. AB={<1,3>, <1,4>, <2,3>, <2,4>}, а BA=={<3,1>, <4,1>, <3,2>, <4,2>}. Если множество X является и областью определения отношения и его областью значений, то это отношение на множестве X.

Для бинарных отношений, как и для любых множеств, определены теоретико-множественные операции объединения, пересечения, инверсии и т. д. Для двух конечных отношений матрица их объединения получается из матриц исходных отношений поэлементной операцией OR (), а матрица их пересечения – поэлементной операцией AND () и т. д. Надо, разумеется, еще учесть, что при объединении отношений объединяются и их области определения и значений, а при пересечении – пересекаются.

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

Например, инверсным отношением отношения на множестве {1, 2, 3, 4} «быть меньше» является отношение «быть больше и равно» и оно задаётся матрицей:

Для каждого отношения существует и обратное отношение - это множество упорядоченных пар <y, x> таких, что пары <x, y> принадлежат отношению . Для конечного отношения матрица его обратного отношения получается транспонированием (строки меняются со столбцами) матрицы отношения . Например, обратным отношением отношения на множестве {1, 2, 3, 4} «быть меньше» является отношение «быть больше» и оно задаётся матрицей: