Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 826688.01.99
Доступ онлайн
1 000 ₽
В корзину
Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции. Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ("законы логики”), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул. Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Дехтярь, М. И. Лекции по дискретной математике : курс лекций / М. И. Дехтярь. - Москва : ИНТУИТ, 2016. - 126 с. - ISBN 978-5-94774-714-0. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2140217 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов

Основы дискретной математики
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


Доступ онлайн
1 000 ₽
В корзину