Лекции по дискретной математике
Покупка
Издательство:
ИНТУИТ
Автор:
Дехтярь Михаил Иосифович
Год издания: 2016
Кол-во страниц: 126
Дополнительно
Вид издания:
Курс лекций
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-94774-714-0
Артикул: 826688.01.99
Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ("законы логики”), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул. Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул
(выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и
проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Тематика:
ББК:
УДК:
- 51: Математика
- 519: Комбинатор. анализ. Теория графов. Теория вер. и мат. стат. Вычисл. мат., числ. анализ. Мат. кибер..
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.03: Механика и математическое моделирование
- 02.03.01: Математика и компьютерные науки
- 02.03.02: Фундаментальная информатика и информационные технологии
- 02.03.03: Механика и математическое моделирование
- ВО - Магистратура
- 01.04.01: Математика
- 01.04.02: Прикладная математика и информатика
- 01.04.03: Механика и математическое моделирование
- 02.04.01: Математика и компьютерные науки
- 02.04.02: Фундаментальная информатика и информационные технологии
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Основы дискретной математики 2-е издание, исправленное Дехтярь М.И. Национальный Открытый Университет “ИНТУИТ”
УДК 51”735”(076.6) ББК 10 Д39 Лекции по дискретной математике / Дехтярь М.И. - M.: Национальный Открытый Университет “ИНТУИТ”, 2016 (Основы информационных технологий) ISBN 978-5-94774-714-0 Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции. Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества (“законы логики”), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул. Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал. (c) ООО “ИНТУИТ.РУ”, 2007-2016 (c) Дехтярь М.И., 2007-2016
Предварительные сведения
Множества и операции над ними. Как доказывать равенство множеств? Отношения и
функции. Отношения эквивалентности и частичного порядка. Мощность множеств
Множества
Множество - это одно из основных понятий математики, как дискретной, так и
непрерывной. Оно не определяется через другие понятия. Содержательно, под
множеством понимается некоторая совокупность элементов. Основное отношение
между элементами и множеством - это отношение принадлежности элемента
множеству. Оно обозначается знаком
означает, что элемент x принадлежит
множеству A.
означает, что элемент x не входит в множество A.
означает
что каждый элемент множества A является также элементом множества B. В этом
случае множество A называется подмножеством множества B. Если
и
то A=B, т.е. множества A и B равны. Если
и
то A называется собственным
подмножеством множества B, и в этом случае пишем
Множество, не
содержащее элементов, называется пустым и обозначается
.
Обычно множества обозначаются с помощью пары фигурных скобок, в которые
заключены их элементы. Небольшие множества задаются прямым перечислением
всех элементов. Например, множество простых чисел, не превосходящих 10, это {2,
3, 5, 7} ; множество (имен) летних месяцев: {июнь, июль, август}. В описаниях
“больших” конечных множеств используют многоточие. В них часто указывается
несколько первых элементов и последний элемент множества. Например, множество
целых неотрицательных чисел, не превосходящих 100, записывают как {0, 1, 2, … ,
100}, множество всех месяцев года - как { январь, февраль, …, декабрь}. Такое
задание требует определенной аккуратности. Например, если некоторое множество A
задано как {3, 5, 7, … , 19}, то не ясно, является ли A множеством нечетных чисел,
лежащих в интервале от 3 до 19, или это множество простых чисел из того же
интервала (возможны и другие его расшифровки). Перечисления элементов
бесконечных множеств начинаются несколькими начальными элементами, а
завершаются многоточием. При этом часто указывают общий вид элемента
задаваемого множества. Основное бесконечное множество, рассматриваемое в
дискретной математике, это множество всех натуральных чисел N={1, 2, 3, … } .
Множество всех квадратов этих чисел можно задать, например, так: {1, 4, 9, …, n2,
… } .
Как мы уже отметили, большие множества не всегда можно точно определить,
используя перечисление с многоточием. Основной способ их описания имеет вид: {
Elem | условие на Elem}, где Elem - это общий вид элемента определяемого
множества, а после вертикальной черты описано условие, которому этот элемент
должен удовлетворять. Например,
- это множество целых
чисел в интервале от 10 до 1000,
- множество квадратов натуральных
чисел,
- множество всех простых чисел.
Множества, элементами которых являются другие множества, часто называют
семействами или классами. Семейство ( множество ) всех подмножеств множества A
обозначается через 2A, т.е.
Например, если A={ 0, 1, {2,3}}, то
а для пустого
множества
семейство его подмножеств
Операции над множествами
Имеется целый ряд операций, позволяющих получать одни множества из других.
Рассмотрим основные из них.
Объединением множеств A и B называется множество
Объединением семейства множеств
называется множество
Пересечением множеств A и B называется множество
Пересечением семейства множеств
называется множество
Из определения операций объединения и пересечения непосредственно следует, что
они обладают свойствами ассоциативности:
и коммутативности
Разностью множеств A и B называется множество
Обычно все рассматриваемые множества являются подмножествами некоторого
“универсального” множества U. Разность U \ A называется дополнением множества
(в U ) и обозначается через
Ясно, что
и
Симметрической разностью множеств A и B называется множество
Иногда симметрическую разность множеств называют дизъюнктивной суммой и
обозначают
или
Декартовым (прямым) произведением множеств A1, … , An называется множество n -
ок
Если A1= … =An=A, то A1 x … An называется декартовой (прямой) степенью множества
и обозначается через An .
Пример1.1. Пусть заданы множества A= {0,1,… ,n} и B={0,1,… m}, где
и
- числа и n < m.
Тогда
A x B = {(i,j)| 0 <= i
<= n, 0 <= j <= m}.
Как доказывать равенство множеств?
Многие математические утверждения, в том числе и многие теоремы в этой книге,
имеют следующую форму. Даны разные определения двух множеств A и B. Требуется
доказать, что A = B.
Стандартный способ доказательства такого утверждения состоит в доказательстве двух
утверждений о включениях:
1.
и
2.
Доказательства этих включений проводятся по такой схеме: рассматривается
произвольный элемент, удовлетворяющий определению меньшего множества (слева
от знака
), и устанавливается, что он удовлетворяет также определению большего
множества (справа от знака
).
В качестве примера докажем одно из свойств (законов) дистрибутивности для
операций объединения и пересечения:
1. Пусть a - произвольный элемент из
Тогда по определению операции
имеем
или
В первом случае из того же определения
выводим, что
и
Но тогда по определению операции
получаем, что
Во втором случае из определения
следует,
что
и
Из этого и из определения
снова следует, что
и
и
Таким образом, мы установили, что
2. Пусть теперь
Тогда по определению операции
имеем
и
Если
то оба эти включения выполнены. Но тогда
Если же то из первого включения следует, что а из второго - Следовательно, и Таким образом, и наше утверждение доказано. Используя эту же схему, можно установить много других свойств введенных выше операций над множествами и связей между ними (см. задачи 1.2 и 1.5). Отношения и функции. Мощность множества Бинарным или двуместным отношением между элементами множеств A и B называется любое подмножество R их декартова произведения A x B . Говорят также, что R является отношением из A в B. При A = B отношение R называется бинарным отношением на A. Вместо часто пишут xRy. Например, для отношений порядка на множестве натуральных чисел N используют записи вида 3 <= 7, x >= 23, z > y и т.п. Тождественным отношением на множестве A называется отношение Его обозначают знаком равенства ” = “. С бинарным отношением R связана его область определения: и его область значений: Обратным отношением для бинарного отношения R называется множество пар Образом множества X относительно R называется множество прообразом X относительно R называется R-1(X). Произведением отношений и называется следующее отношение : Важную роль среди бинарных отношений играют отношения эквивалентности. Бинарное отношение R на множестве A называется отношением эквивалентности, если для него выполнены следующие условия: 1. Рефлексивность: для любого ; 2. Симметричность: для любых a, b из ; 3. Транзитивность: для любых трех элементов a, b,c из A, если и
то и Примером отношения эквивалентности на множестве натуральных чисел N является равенство остатков при делении на некоторое фиксированное число n: a = b (mod n). С каждым отношением эквивалентности на множестве A связано разбиение A на непересекающиеся подмножества - классы эквивалентности. Для каждого его класс эквивалентности включает все эквивалентные a элементы: Из определения эквивалентности непосредственно следует, что, если то а если то Таким образом, разбиение A на классы эквивалентности не зависит от выбора конкретных представителей этих классов в качестве их имен. Если в приведенном выше примере в качестве n взять, например, 5, то все числа из N разобьются на 5 классов эквивалентности: N0, N1, N2, N3, N4, где в класс Ni (i=0,1,2,3,4) войдут числа, дающие при делении на 5 остаток i. Еще один важный класс отношений - отношения (частичного) порядка. Бинарное отношение R на множестве A называется отношением частичного порядка, если для него выполнены следующие условия: 1. Антирефлексивность: для любого \ ; 2. Антисимметричность: для любых a, b из A, если и то a = b ; 3. Транзитивность: для любых трех элементов a, b,c из A, если и то и Примером такого отношения является отношение строгого включения на множестве 2A всех подмножеств некоторого множества A. Обычное отношение строгого порядка < на N также удовлетворяет условиям 1 - 3. Но для него выполнено еще одно существенное условие: 4. Линейность: для любых a, b из A либо либо Отношения, для которых выполнены условия 1 - 4 называются отношениями линейного порядка. Отношение f называется функцией из A в B ( из A на B ) , если (соответственно, ) и для всех x, y1, y2 из того, что и следует, что y1 = y2. Запись: f : A -> B. В качестве синонимов термина “функция” часто используются слова отображение и преобразование. Если f функция, то вместо пишем f(x) = y и называем y значением f на аргументе x. f называется 1-1функцией (или обратимой функцией), если для любых x1, x2, y из того, что f(x1) = y и f(x2) = y следует, что x1 = x2 . Функция f : A -> B называется взаимно однозначной функцией, если она является 1-1-функцией и Взаимно однозначная функция f : A -> A называется перестановкой множества A .
Определения бинарных отношений и функций с одним аргументом естественным
образом обобщаются на многоместные отношения и функции.
n -арным (или n - местным) отношением на множествах A1,…, An называется любое
подмножество A1 x … x An. Функцию f : A1 x … x An -> B называем n -арной (или n -
местной) функцией и пишем f(x1, …, xn) = y при
Чаще всего мы
будем рассматривать n -арные функции для A1 = … = An =A. В этом случае f : An -> B
будем называть n -арной функцией из A в B.
Множество A называется эквивалентным (по мощности ) множеству B, если между A и
B можно установить взаимно однозначное соответствие. Мощностью множества A
называется класс всех множеств, эквивалентных множеству A, и эта мощность
обозначается через |A| .
Для каждого
мощность множества Nn={0,1,…,n-1} обозначим через n.
Множество называется конечным, если оно для некоторого
эквивалентно
множеству Nn. Для конечных множеств их мощность - это количество элементов. В
частности, для пустого множества
Каждое множество, эквивалентное N, называется счетным и его мощность
обозначается
В нашем курсе мы будем рассматривать только конечные и счетные множества, а
также - отношения и функции на таких множествах. Отметим, что многие объекты,
изучаемые в дискретной математике, являются частными случаями отношений и
функций на конечных множествах. К ним относятся, в частности, слова. Пусть
алфавит A={a1, …, am} - это конечное множество элементов, называемых символами
(буквами). Слово в алфавите A - это конечная последовательность символов этого
алфавита:
при i = 1, …, n . Число букв в этой
последовательности называется длиной слова и обозначается |w|. Имеется одно
специальное “пустое” слово длины 0. Будем обозначать его через
Нетрудно понять,
что слова длины n взаимно однозначно соответствуют функциям вида f: {1,…, n} ->
A. А именно, слову w = w1… wn, соответствует функция fw(i) = wi, i = 1, …, n. Языком
в алфавите A называется произвольное множество слов этого алфавита . На языках,
как и на множествах, определены операции объединения, пересечения и разности.
Язык, включающий все слова в алфавите A ( в том числе и пустое), обычно
обозначается через A*. Дополнение языка
это язык L = A* \ L.
Задачи
Задача 1.1. Доказать следующие включения:
;
Задача 1.2. Доказать следующие тождества:
;
;
;
;
;
;
;
и
Задача 1.3. Найти все подмножества множеств
{1,2,3},
Задача 1.4. Пусть A={ 0, 1}, B ={a,b,c}. Определите множества Ax B и B x A.
Задача 1.5. Доказать, что
;
;
A x (B \ C) = (Ax B)\ (Ax C) ;
если
и
то
Задача 1.6. Для каждого из следующих отношений определить
:
;
;
;
;
R = {(a,b), (b,c), (b,d), (c,d), (d, b)}.
Задача 1.7. Пусть множество S ={ (i, j) | 1<= i, j <= 8} задает клетки шахматной
доски. Опишите следующие бинарные отношения на S:
L ={ (a,b) | ладья за 1 ход может перейти с клетки a на клетку b };
K= { (a,b) | конь за 1 ход может перейти с клетки a на клетку b }.
Будут ли эти отношения эквивалентностями? Опишите отношение
Задача 1.8. Пусть - множество прямых на плоскости. Будут ли следующие
отношения отношениями эквивалентности:
параллельность прямых;
перпендикулярность прямых.
Задача 1.9. Пусть A={a1,…, am} - произвольный конечный алфавит. Обозначим через An