Конспект лекций по дискретной математике

В. Н. ДЕСНИЦКАЯ

В. Г. ДМИТРИЕВ

С. В. ПЕТРАС

КОНСПЕКТ ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Учебное пособие

ИЗДАТЕЛЬСТВО 

САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО

ЭКОНОМИЧЕСКОГО УНИВЕРСИТЕТА

2019

Десницкая В. Н.,

Дмитриев В. Г.,

Петрас С. В.

 

 

Конспект лекций по дискретной математике:

Учебное пособие / В. Н. Десницкая, В. Г. Дмитриев, С. В. Петрас. – СПб.: Изд-во СПбГЭУ, 2019. - 87 c.

 

Учебное пособие «Конспект лекций по дискретной математике» составлено по материалам лекций, прочитанных в 2017-2019 годах преподавателями кафедры высшей математики СПбГЭУ для специальностей 38.03.05 «Бизнес-информатика», 10.03.01 «Информационная безопасность» и 09.03.03 «Прикладная информатика».

    Из всего многообразия разделов дисциплины «Дискретная математика» aвторы пособия выбрали те, которые в наибольшей степени соответствуют перечисленным специальностям, при этом основной упор сделан на основы теории чисел. В качестве примеров приложения теории чисел приведены алгоритмы проверки чисел на простоту и кодирования RSA, снабженные теоретическими обоснованиями.

Пособие предназначено для студентов специальностей «Бизнес-информатика», «Информационная безопасность» и «Прикладная информатика», но может быть полезно и обучающимся по другим специальностям, особенно тем, чье образование связано с информатикой. Пособие может быть также полезно преподавателям, читающим курс лекций и ведущим практические занятия по дисциплине «Дискретная математика».

 

 

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

                    д-р экон. наук, проф. В. П. Чернов

Содержание

ПРЕДИСЛОВИЕ…………………………………………………………..

Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ, ОТОБРАЖЕНИЯ,                   ОТНОШЕНИЯ …………………………………………………………….

§ 1. Множества и операции над ними…………………………………….

§ 2. Отображения и функции……………………………………………..

§ 3. Сравнение множеств………………………………………………….

§ 4. Бинарные отношения………………………………………………….

§ 5. Метод математической индукции…………………………………….

Глава 2.ОСНОВЫ ТЕОРИИ ЧИСЕЛ………………………………………

§ 1. Делимость чисел…………………………………………………………

§ 2. Деление с остатком…………………………………………………….

§ 3. Наибольший общий делитель…………………………………………..

§ 4. Вычисление НОД. Алгоритм Евклида…………………………………

§ 5. Взаимно простые числа………………………………………………...

§ 6. Решение неопределенных уравнений при помощи алгоритма  

  Евклида…………………………………………………………………..

§ 7. Модулярная арифметика. Сравнения по модулю, их свойства………

§ 8. Простые числа……………………………………………………………

§ 9. Функция Эйлера………………………………………………………….

§ 10. Решение сравнений первой степени…………………………………..

§ 11. Системы сравнений. Китайская теорема об остатках………………..

§ 12. Представление рациональных чисел конечными цепными    

дробями………………………………………………………………..

§ 13. Подходящие дроби, их свойства и применение……………………..

§ 14. Представление иррациональных чисел цепными дробями…………

§ 15. Квадратичные вычеты. Символ Лежандра…………………………..

§ 16. Символ Якоби………………………………………………………….

§ 17. Проверка чисел на простоту ………………………………………….

§ 18. Теория чисел в криптографии…………………………………………

 

ПРЕДИСЛОВИЕ

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

   Учебная дисциплина “Дискретная математика” состоит из разделов, которые традиционно относят к таким разделам математики как теория множеств, алгебра, в частности теория чисел и теория алгебраических структур, математическая логика, теория графов, комбинаторика и целый ряд других. В зависимости от специальности обучающихся формируется структура учебного курса по дискретной математике. Поскольку пособие предназначено в первую очередь для студентов специальностей «Бизнес-информатика», «Информационная безопасность» и «Прикладная информатика», упор в нем сделан на теорию чисел, на основе которой строятся алгоритмы криптографии.

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

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

Название пособия отражает его назначение. В пособии изложен материал в объеме курса лекций (22-32) часов, поэтому пособие может быть практически без изменений использовано преподавателями для чтении курса лекций по дискретной математике. 

                

 

 

 

 

Отображения и функции

 

Определение 2.1. Рассмотрим два непустых множества X  и Y. Если каждому элементу множества X соответствует один элемент множества Y, то говорят, что задано отображение f множества X в множество Y.

Этот факт обычно записывают в виде:

                       .    

Определение 2.2. Элемент из множества Y, соответствующий элементу , обозначают  и называют образом элемента x относительно отображения f.  При этом элемент x называется прообразом элемента  относительно отображения f.  Множество X называется областью определения отображения f.

Определение 2.3. Пусть f – отображение множества X в множество Y, а множество A является подмножеством множества X. Множество  называется образом множества X при отображении f  и обозначается . В этом случае множество A называется прообразом множества .

Пример. Пусть X – множество студентов потока, находящихся в аудитории на лекции, а Y – множество стульев, находящихся в этой аудитории. Рассмотрим отображение f, сопоставляющее каждому студенту стул, на котором он сидит (при условии, что все студенты на лекции сидят). Тогда стул, занимаемый студентом является образом данного студента при отображении f. Рассмотрим множество , A – множество студентов из одной определенной группы потока. Тогда  – множество стульев, занимаемых студентами из данной группы.

Определение 2.4. Отображение f множества X в множество Y называется функцией, если множество Y – числовое множество.

Определение 2.5. Отображение f множества X в множество Y называется сюръективным, или “ отображением на ”, если образом области определения X является все множество Y.

Отображение f множества X в множество Y называется инъективным, если для любых из условия  следует .

Отображение f множества X в множество Y называется биективным, если оно сюръективно и инъективно. Биективное отображение также называют взаимно однозначным соответствием.

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

2) Пусть , . Отображение  задается формулой:

. Тогда отображение f является функцией. При этом оно не сюръективно (). Оно также и не инъективно, так как разным значениям x могут соответствовать равные образы, например, .

3) Пусть , . Отображение  задается формулой:

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

4) Пусть , . Отображение  задается формулой:

. В этом случае отображение f  сюръективно, так как , но не инъективно.

5) Пусть , , Отображение  задается формулой:

. В этом случае отображение f  , очевидно, сюръективно и инъективно, следовательно, биективно.

 

Сравнение множеств

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

    Определение 3.1. Говорят, что два множества имеют одинаковую мощность (равномощны), если между элементами этих множеств можно установить взаимно однозначное соответствие.

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

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

    Определение 3.2. Бесконечное множество называется счетным, если оно имеет одинаковую мощность с множеством натуральных чисел N.

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

Примеры. 1) Множество целых чисел Z счетно. Действительно, составим таблицу, в первой строке которой записаны целые числа, а во второй – их натуральные номера:

Z	0	-1	1	-2	2	-3	3	-4	…
N	1	2	3	4	5	6	7	8	…

 

2) Пусть множества A и B счетны. Тогда их прямое произведение  тоже счетно. Для доказательства этого составим бесконечную (вправо и вниз) таблицу, в которой каждой строке соответствует элемент множества A, а каждому столбцу – элемент множества B. В клетках таблицы поставим натуральные числа – номера элементов множества  так, как показано стрелками. Очевидно, что таким образом каждому элементу  будет соответствовать свой определенный номер, причем разным элементам будут соответствовать разные номера. Это и доказывает счетность множества .

 

					…
	1	4	5	16
	2	3	6	15
	9	8	7	14
	10	11	12	13

 

3) Множество рациональных чисел Q счетно. Для доказательства этого рассмотрим прямое произведение двух счетных множеств: , оно, как было доказано в примере 2, счетно. Это значит, что каждой упорядоченной паре чисел , где , можно присвоить натуральный номер. Тогда и каждой обыкновенной дроби , можно присвоить натуральный номер, следовательно, множество обыкновенных дробей также счетно. Поскольку каждое рациональное число может быть представлено в виде различных обыкновенных дробей (например, рациональное число  можно представить также в виде дробей ,  и т. д.), множество рациональных чисел Q можно отождествить с некоторым подмножеством множества обыкновенных дробей. А так как множество Q бесконечно, то оно, очевидно, счетно.

    Рассмотрим теперь пример множества, которое не является счетным. Докажем, что интервал не является счетным.

    Предположим, что интервал  – счетное множество. Это значит, что все числа из  удалось каким-то образом занумеровать:  . Каждое такое число можно записать в виде бесконечной десятичной дроби:

               ,

     ,

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

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

      ,

где , .

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

    Этот пример показывает, что имеются множества, не являющиеся счетными.

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

    Примеры. 1) Множество всех действительных чисел R имеет мощность континуум. Действительно, взаимно однозначное соответствие между интервалом  и множеством R можно установить, например, с помощью функции , которая каждому числу  ставит в соответствие число y по формуле . Из свойств этой функции следует, что она является взаимно однозначным соответствием, значит множества  и R равномощны, а это и означает, что R имеет мощность континуум.

2) Очевидно, что любой интервал  также имеет мощность континуум. Привести пример взаимно однозначного соответствия интервалов  и  предоставляется читателю.

3) Полуинтервал также имеет мощность континуум. Для доказательства этого построим биективное отображение полуинтервала  на интервал следующим образом. В интервале выделим какое-нибудь счетное подмножество, например, . Если мы объединим это множество с множеством , то полученное множество также, очевидно, будет счетным. Это значит, что существует биективное отображение f  множества A на множество B. Распространим отображение f на точки множества \ A следующим образом: . Таким образом мы получили, что существует биективное отображение f интервала  на полуинтервал , что и доказывает равномощность этих множеств.

Можно доказать, что мощность континуум имеет и множество всех

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

 

Бинарные отношения

 

Определение 4.1. Пусть A – некоторое множество. Рассмотрим декартово произведение   и некоторое его подмножество . Тогда называется бинарным отношением на множестве A.

Говорят, что элемент находится в отношении  с элементом , если упорядоченная пара . Этот факт также записывают в виде .

Примеры. 1) Пусть . Определим бинарное отношение  на множестве R следующим образом: , .

2) Пусть A – множество студентов потока, тогда  – множество упорядоченных пар студентов. Рассмотрим , определяемое следующим образом: студенты x и y учатся в одной группе.

     Рассмотрим ряд определений, связанных с понятием бинарного отношения.

    Определение 4.2. Пусть , , т. е. отношение не выполняется ни для одной пары элементов множества A. Тогда отношение называется пустым.

Пример. Пусть , тогда . Рассмотрим отношение . Очевидно, что .

    Определение 4.3. Пусть . Тогда отношение называется полным.

    Определение 4.4. Пусть . Рассмотрим бинарное отношение . Бинарное отношение называется дополнительным к бинарному отношению .

Пример. Рассмотрим предыдущий пример, где A – множество студентов потока и бинарное отношение определяется так: студенты x и y учатся в одной группе. Тогда  студенты x и y учатся в разных группах.

    Определение 4.5. Пусть . Рассмотрим бинарное отношение , определяемое следующим образом: .  Бинарное отношение называется противоположным бинарному отношению .

Примеры. 1) Пусть . Пусть , . Тогда .

2) Пусть A – множество студентов потока и бинарное отношение определяется так: студенты x и y учатся в одной группе. Тогда, очевидно, .

 

Свойства бинарных отношений

 

    Рассмотрим бинарное отношение на множестве A.

1. Рефлексивность. Бинарное отношение называется рефлексивным, если

выполняется , для всех .

2. Симметричность. Бинарное отношение называется симметричным,

если , для всех .

3. Транзитивность.Бинарное отношение называется транзитивным,

если , для всех .

Примеры. 1) Пусть . Рассмотрим бинарное отношение  на множестве R, определяемое следующим образом: . Тогда обладает свойством рефлексивности, поскольку  для всех . Бинарное отношение не обладает свойством симметричности, поскольку из неравенства  не следует неравенство . Бинарное отношение  обладает свойством транзитивности, поскольку из неравенств следует .

2) Пусть A – множество всех людей на Земле. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: человек x является братом или сестрой человека y (т. е. x и y имеют хотя бы одного общего родителя). Тогда , очевидно, рефлексивно, симметрично, но не транзитивно.

    Определение 4.6. Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности называется отношением эквивалентности.

Примеры. 1) Пусть . Рассмотрим бинарное отношение  на множестве R, определяемое следующим образом: . Тогда является отношением эквивалентности. Действительно, рефлексивно, поскольку  для всех . Бинарное отношение , очевидно, также симметрично и транзитивно.

2) Пусть A – множество студентов потока. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: студенты x и y учатся в одной группе. Тогда  является отношением эквивалентности. Действительно, рефлексивность означает, что каждый студент учится сам с собой в одной группе. Симметричность  означает, что если студент x учится в одной группе со студентом y, то и студент y учится в одной группе со студентом x. Транзитивность  означает, что если студент x учится в одной группе со студентом y, а студент y учится в одной группе со студентом z, то студент x учится в одной группе со студентом z.

    Отношение эквивалентности часто обозначают знаком .

    Определение 4.7. Рассмотрим множество A и  – отношение эквивалентности на множестве A. Пусть  – подмножество множества A, определяемое следующим образом: . Тогда множество называется классом эквивалентности элемента x, порожденным отношением эквивалентности .

    Свойства классов эквивалентности

1. Классы эквивалентности элементов множества не пусты. Действительно, класс эквивалентности множества x содержит элемент x: .

2. Пусть . Тогда .

Доказательство. Пусть . Это значит, что . Но , значит . Из транзитивности отношения  следует, что . Значит, . Следовательно, .

Пусть теперь . Это значит, что . Поскольку , имеем . Из симметричности отношения  следует, что , а тогда по транзитивности отношения  получим, что . Это значит, что . Следовательно, .

Если  и , то .

3. Если , то .

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

Определение 4.8. Рассмотрим множество A. Пусть , . Множество  называется разбиением множества A, если оно удовлетворяет условиям:

1) ,

2) , при .

    Примеры. 1) Множества четных чисел и нечетных чисел составляют разбиение множества целых чисел.

2) Множество всех людей живущих на Земле можно представить в виде разбиения на подмножества, состоящих из людей определенного года рождения.

    Теорема 4.1. Классы эквивалентности множества A составляют разбиение множества A.

    Доказательство.  Рассмотрим множество  – классов эквивалентности множества A, порожденных некоторым отношением эквивалентности. Докажем, что множество является разбиением множества A.

1) Докажем, что . Пусть  и , . Очевидно, что , , следовательно, .

Пусть . Тогда найдется такой класс эквивалентности , что

. Значит, , и тогда .

Если  и , то .

2) Условие  при  следует из свойства 3 классов эквивалентности. Теорема доказана.

    Определение 4.9. Рассмотрим множество A и  – отношение эквивалентности на A. Пусть  – классы эквивалентности, порожденные отношением  . Множество называется фактор-множеством множества A по отношению эквивалентности  , и обозначается   A │_̴̴ .

Примеры. 1) Пусть A – множество студентов потока. Рассмотрим бинарное отношение на множестве A, определяемое следующим образом: студенты x и y учатся в одной группе. Тогда, как было установлено выше, отношение  является отношением эквивалентности. При этом элементами фактор-множества A │_Δ, порожденного отношением , являются группы данного потока.

2) Рассмотрим множество целых чисел Z и введем на этом множестве бинарное отношение :  разность является четным числом. Отношение  , очевидно, является отношением эквивалентности. Фактор-множество Z│_Δ  состоит из двух элементов – множества четных чисел и множества нечетных чисел.

 

Продолжим изучение свойств бинарных отношений.

 

4. Бинарное отношение  на множестве A называется антисимметричным,  если из условия  следует, что .

Пример. Пусть . Рассмотрим бинарное отношение  на множестве R, определяемое следующим образом: . Тогда бинарное отношение  антисимметрично. Действительно, .

5. Бинарное отношение  на множестве A называется асимметричным, если из условия следует, что , т. е.  – неверно.

Пример. Пусть . Рассмотрим бинарное отношение на множестве , определяемое следующим образом: . Тогда бинарное отношение  aсимметрично. Действительно, если  , то, очевидно, что  – неверно.

6. Бинарное отношение  на множестве A называется антирефлексивным, если не существует такого элемента , что .

Пример. В предыдущем примере бинарное отношение , очевидно, антирефлексивно.

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

Примеры. 1) Пусть . Рассмотрим бинарное отношение на множестве , определяемое следующим обр