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

Основы дискретной математики

2-е издание, исправленное

Дехтярь М.И.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 51”735”(076.6)
ББК 10
Д39
Лекции по дискретной математике / Дехтярь М.И. - M.: Национальный Открытый Университет
“ИНТУИТ”, 2016 (Основы информационных технологий)
ISBN 978-5-94774-714-0

Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для
изучения основного материала предварительные сведения о множествах, комбинаторике и методе
математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные
представления, связь с логикой высказываний, основные логические тождества (“законы логики”),
дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы
функций (теорема Поста), задача выводимости для Хорновских формул. Даны краткое введение в
логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в
теорию графов, включающее представления графов, граф достижимости, компоненты сильной
связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул
(выражений), три классические задачи теории графов: построение минимального остова, обход графа
в глубину (задачу о лабиринте) и задачу о кратчайших путях. Решение большинства
рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и
проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями,
позволяющими закрепить пройденный материал.

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Дехтярь М.И., 2007-2016

3

Предварительные сведения

Множества и операции над ними. Как доказывать равенство множеств? Отношения и
функции. Отношения эквивалентности и частичного порядка. Мощность множеств

Множества

Множество - это одно из основных понятий математики, как дискретной, так и
непрерывной. Оно не определяется через другие понятия. Содержательно, под
множеством понимается некоторая совокупность элементов. Основное отношение
между элементами и множеством - это отношение принадлежности элемента
множеству. Оно обозначается знаком 
 
 означает, что элемент 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, 
 - множество квадратов натуральных

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

4

Множества, элементами которых являются другие множества, часто называют
семействами или классами. Семейство ( множество ) всех подмножеств множества A
обозначается через 2A, т.е. 
 Например, если A={ 0, 1, {2,3}}, то 

 а для пустого

множества 
 семейство его подмножеств 

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

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

Объединением множеств A и B называется множество

Объединением семейства множеств 
 называется множество

Пересечением множеств A и B называется множество

Пересечением семейства множеств 
 называется множество

Из определения операций объединения и пересечения непосредственно следует, что
они обладают свойствами ассоциативности: 
 

 и коммутативности 
 

Разностью множеств A и B называется множество

Обычно все рассматриваемые множества являются подмножествами некоторого
“универсального” множества U. Разность U \ A называется дополнением множества 
(в U ) и обозначается через 
 Ясно, что 
 и 

Симметрической разностью множеств A и B называется множество

Иногда симметрическую разность множеств называют дизъюнктивной суммой и
обозначают 
 или 

5

Декартовым (прямым) произведением множеств 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. Пусть теперь 
 Тогда по определению операции 
 имеем 

 и 
 Если 
 то оба эти включения выполнены. Но тогда 

6

 Если же 
 то из первого включения следует, что 
 а из

второго - 
 Следовательно, 
 и 
 Таким образом, 

 и наше утверждение доказано.

Используя эту же схему, можно установить много других свойств введенных выше
операций над множествами и связей между ними (см. задачи 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, если 
 и 

7

 то и 

Примером отношения эквивалентности на множестве натуральных чисел 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 .

8

Определения бинарных отношений и функций с одним аргументом естественным
образом обобщаются на многоместные отношения и функции.

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. Доказать следующие включения:

 ;

9

Задача 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

10