Повышению уровня математической подготовки студентов, специализирующихся в области вычислительной техники, в последнее время уделяется большое внимание. Особое значение в этом плане имеет изучение современных разделов математики, таких как теория множеств, математическая логика, теория графов, теория алгоритмов и др. Указанные разделы в настоящее время принято относить к дискретной математике.
Предлагаемый конспект лекций подготовлен в соответствии с программой соответствующей дисциплины, изучаемой студентами ИТФиТК ПГУ. Данный конспект лекций имеет своей целью дать студентам материал для самостоятельной работы и для более глубокого усвоения новых понятий, а также облегчить преподавателям подготовку и проведение занятий.
В данном пособии рассматриваются основные разделы, относящиеся к теории множеств, математической логике, алгебре, теории графов, теории алгоритмов и др. Данные разделы дискретной математики являются методологической основой задач проектирования вычислительных систем, сетей ЭВМ, подсистем САПР различного функционального назначения.
Bезде, где возможно, в каждой новой теме используются понятия и термины из предыдущих тем, материал сопровождается примерами. Разбор и решение примеров на практических занятиях является составной частью изучения данного курса.

Раздел 1. Множества
1.1: Множества и их спецификации

Изложение курса дискретной математики традиционно принято начинать с исходного неопределяемого понятия множества. Понятие множества описывается перечислением его свойств. Исходя из этого, можно определить все последующие понятия математически приемлемым образом. Такой подход необходим, так как любую ошибку можно проследить, вернуть назад к неправильному предложению где-то в цепочке рассуждений.
Определение1.1: Множество — это совокупность определенных различаемых объектов, таких, что для любого объекта можно установить, принадлежит этот объект данному множеству или не принадлежит. Объекты множества называются так же элементами множества.
Определяемое таким образом множество может содержать объекты почти любой природы.
Пример:
— множество всех подземных станций метро Москвы;
— множество натуральных чисел: 1, 2, 3,…
— множество кодов операций конкретного компьютера;
— множество зарезервированных слов языка Бейсик;
— множество идентификаторов, встречающихся в определенной программе;
— множество операций в той же самой программе;
— множество операций, которые могут быть выполнены после данной инструкции в той же программе.
Но эти множества достаточно важны для исследования, поэтому для большинства примеров будем исследовать некоторые абстрактные множества, такие, например, как множества чисел.
Условимся множества обозначать большими латинскими буквами A, B, ….. Z, а его элементы малыми латинскими буквами: а, b, с, …, z. Если множество бесконечное, то используются эти же буквы с индексами.
Множества можно специфицировать (задать) четырьмя способами:
1) Если множество содержит несколько элементов (т.е. конечно), то просто записываем все его элементы — перечисление элементов.
Пример: Определим множество A как множество целых чисел строго между 6 и 10.
A = {7, 8, 9}. Читается: “Множество A, содержащее целые числа 7, 8, 9 ”
2) Множество можно охарактеризовать свойствами элементов:
Пример: A = {x | x ?Z, 6 < x < 10} Читается: “A есть множество всех x, таких что …”
3) Задается порождающая процедура, которая описывает способ получения элементов множества из уже полученных элементов либо из других объектов.
Пример: Множество всех корней уравнения соs x = 0 — это числа вида
B данном случае, исходными объектами для построения являются целые числа, а порождающей процедурой является вычисление, описанное формулой . Правила, описанные таким образом, являются индуктивными или рекурсивными.
4) Образование множеств из других множеств с помощью операций над множествами, которые рассмотрим ниже.
Множества часто рассматривают как “неупорядоченные совокупности элементов”, и иногда полезно подчеркнуть, что например {7, 8, 9} = {8, 9, 7} = {9, 8, 7} = … ; Т.о., мы не делаем никакой оговорки о порядке, в котором рассматриваются элементы, поэтому было бы неправильно допускать какой-либо определенный порядок.
Знак принадлежности множеству: 7 ? A читается: 7 является элементом множества, принадлежит множеству A. 6 ?A — 6 не принадлежит множеству A.
Понятие принадлежности не обладает свойством транзитивности, т. е., если а?A и A?B, то отсюда не следует, что а ?B.
A={a, b} B={{a, b}, b} a?B
Пример: Какие из приведенных определений множества являются правильными?:
1) A={1, 2, 3} — число элементов множества A легко вычисляется, и среди элементов множества нет повторений. Верно.
2) B={5, 6, 6, 7} — выглядит правильно, но число 6 встречается дважды. Но мы можем проверить, принадлежит ли элемент множеству или нет. Наиболее важное требование в определении множества сохраняется. Следовательно, можно рассмотреть эту запись как верную и эквивалентную {5, 6, 7}. Будем рассматривать повторение символов в определении множеств как упоминание одного и того же символа, а его дублирование как недосмотр; удаление повторяющихся символов образует основу для некоторых дальнейших математических рассуждений. Но в то же время, если рассматривать элементы множества не как числа, а их названия (обозначения, имена), то может быть ловушка. Необходима правильная спецификация рассматриваемых объектов.
Х = {“Введение в Паскаль”, ”Основы структурных данных”, “Введение в Паскаль”}. Что это? — Множество названий двух книг с одним элементом, случайно записанным дважды, или это множество трех книг, две из которых имеют одно название? Если верно последнее, то две книги “Введение в Паскаль” следует каким-то образом разделить. Т.о., из данной информации нельзя выяснить правильный ответ, необходима осторожность.
3) С={x | x?A} — справедливо ,т.к. если x?A, то x?С и если x?A, то x?С. Множество С велико, оно содержит “все”, что не содержит A. “Все” опасно с математической точки зрения.
4) Д={A, C} — множество множеств (!) — справедливо, содержит два элемента. 1?Д, хотя 1?A и A?Д, 1? A, 1?С, только множества A и С являются элементами Д.
5) Е = {x | x =1 или y = {x} и y?E} — рекурсивно определяемое множество. Оно частично определяется в понятиях самого себя. Конструктивный процесс продолжается бесконечно, поэтому мы должны иметь правило для определения элементов. Мы не можем записать их явно. Заметим, что Е не определяется полностью в терминах Е. Мы должны знать о множестве что-то, что не зависит от определения. B данном случае, это то, что 1? Е.
Имеем: 1?Е, потому {1}?E,
{1}?E, потому {{1}} ?E,
{{1}}?E, потому {{{1}}}?E и т.д.
Хотя конструктивный процесс неограничен, беря любой элемент и, располагая достаточным временем, можно определить, содержится ли этот элемент в Е.
6) F={множества, которые не являются элементами самих себя} = {x | x -множество и x?x} — не существует такого множества.
Докажем это от противного. Пусть F — существует. Покажем, что существует особый элемент y такой, что мы не можем определить y?F или y?F. Будем использовать само множество F. Обозначим это множество через G. Если предполагаем, что F искомое множество, то или G?F или G?F.
а) G?F . Тогда G удовлетворяет условию содержания, т.е. G?G и ? G?F;
б) G?F. Тогда G не удовлетворяет условию вхождения в F и, следовательно, G?F.
Во всех случаях пришли к противоречию. Поэтому F не может существовать.
Множество множеств может существовать, бесконечно большие множества (U) так же разрешаются. Но с “множествами всех множеств” нельзя работать в обычной теории множеств — это требуют другого рода математики. Эта аномалия теории множеств известна как парадокс Рассела. Если мы уже имеем множество Н, то можно определить T:
T = {x | x? H и x?x}.
Таким образом, будем использовать только множества, которые могут быть явно записаны или же построены путем хорошо определенных процессов. Множества не так тривиальны, как может показаться.

1.2: Простейшие операции над множествами. Диаграммы Эйлера – Венна

Как было указано ранее, одним из способов задания множества является получение его из других с помощью операций над множествами. Пусть даны два множества A и B.
Определение 1.2: Пересечением множеств A и B называется множество всех элементов, принадлежащих и A и B (Рис.1.1)
AB =  x | x  A и x B

Данное определение можно обобщить для n множеств.
A1 A2 … An= x | x  A1, x A2, … , x  An=x | x  Ai , i = 1, 2,…, n }
Рис. 1.1. Пересечение множеств.
Для графического изображения результатов операций над множествами служат диаграммы Эйлера — Венна.
Определение 1.3: Пустое множество (обозначается ) есть множество, обладающее свойством: x для любого элемента x.
Определение 1.4: Два множества A и B не пересекаются, если AB=.
Определение 1.5: Объединением множеств A и B называется множество, элементы которого принадлежат хотя бы одному из множеств A или B или обоим одновременно (Рис.1.2).
AB= x | x  A или x B
Данное определение можно обобщить для n множеств:
A1A2… An= x | x  A1 или x A2 или … или x  An ={x |  Ai, x  Ai , i=1,2,…,n}
Рис.1.2. Объединение множеств.

Определение пересечения и объединения множеств выводится из слов “и” и “или”, и, как следствие, мы имеем AB=BA, AB=BA и, что менее очевидно, AA=A, AA=A.
Пример:
A = {1, 2, 3, 4}, B = {1, 2, a, b}
AB = {1, 2, 3, 4, a, b}
AB = {1, 2}
Определение 1.6: Разностью множеств A и B (также называемой дополнением B до А) называется множество, элементы которого принадлежат A и не принадлежат B (Рис.1.3).
A\B=A-B= {x | x  A и x  B}
Рис.1.3. Разность множеств.
Замечание 1.1: aAB  a A или а B
aAB  a A и а B
a A\B  a A или а B
Следующее определение включено для полноты. Его редко используют непосредственно, но этот оператор имеет большое значение в машинной арифметике.
Определение 1.7: Симметрической разностью множеств A и B называется множество, которое равно AB=(AB)\ (AB) = (A\ B) (B\ A) (Рис.1.4)
Для симметрической разности имеет место свойство ассоциативности:
(A  B) С=A  (B  С)

Рис.1.4. Симметрическая разность множеств.

Пример: Пусть мы имеем две программы P и Q, и A — множество всех данных, доступных P.
B- множество всех данных, доступных Q. Тогда :
AB — множество всех данных, доступных P и Q.
AB — множество всех данных, доступных, по крайней мере, P или Q.
A\B — множество всех данных, доступных P, но не доступных Q.
AB — множество всех данных, доступных только одной из программ P или Q.
Следующее множество, которое мы рассмотрим, зависит от решаемой задачи. Его называют универсальным.
Определение 1.8: Универсальное множество U есть множество всех рассматриваемых в задаче элементов.
Рис.1.5. Дополнение множества до универсального

Определение 1.9: B каждом случае, когда U задано, определим дополнение множества A до универсального как A’= = U\ A={x | x  U, x  A} (Рис.1.5)

Из определений , U, A’ следует справедливость тождеств:
A A’ = U A A’= 
Замечание 1.2: Относительно данного множества U дополнение любого множества A до универсального A’ единственно.
Чтобы доказать это, предполагают, что существуют два таких объекта, а затем доказывают, что они совпадают.
Пример: Пусть U={1, 2, 3, 4}, A={1, 3, 4}, B={2, 3}, C={1, 4}. Легко найти A’, BС. Но может понадобиться вычислить и более сложные выражения, включающие несколько операций. Встает вопрос, как определить порядок вычислений. Приоритет операций над множествами следующий:
1) в скобках
2) ’ (дополнение)
3) , , \, 
Вычислить выражение (A’  (B  С))’. Тогда
(A’(BС))’=(({1,2,3,4}\{1,3,4})({2,3}{1,4}))’=({2})’=({2})’={1,2,3,4}\{2}={1,3,4}.
Рассмотрим теперь множество A= {1, 2,… ,n} = {x | x N, 1 x N}.Оно имеет n элементов. Будем говорить, что мощность (или размер, норма, длина) этого множества n.
|A| = card (A) = n.
Далее, множество B, которое имеет то же число элементов, что и A, имеет такую же мощность. Для небольших множеств достаточно легко пересчитать элементы, но для других множеств (например, N — множество натуральных чисел) это может быть невозможно. Дадим строгое, но неформальное правило для вычисления количества элементов.
Определение 1.10 : Говорят, что Х конечно, если Х= или, если для некоторого n N {1, 2,…,n} такое, что оно имеет такое же самое число элементов, что и Х. Если Х   и никакого n не может быть найдено, то Х называется бесконечным.

1.3: Подмножества и доказательства. Свойства операций над множествами

Операции , , \, ’ позволяют формировать новые множества. Но мы не можем сказать, как эти множества будут соотноситься друг с другом. Например, даны множества Х и Y. XY в некотором смысле “меньше” (уже не больше), чем Х. Все элементы множества XY принадлежат множеству Х. Из этого наблюдения можно формально определить равенство множеств и различных выражений.
Определение 1.11: Пусть множества A и B таковы, что из того, что xA следует, что xB. Тогда говорят, что A есть подмножество B и обозначается AB или B A (рис.1.6.)

Рис.1.6.
Определение 1.12: Если AB и существует элемент yB такой, что yA, то A называется собственным подмножеством B (Рис.1.7.). Обозначается A  B или B  A
Это означает, что в некотором смысле. B “больше”, чем A.

Рис.1.7.
B обоих случаях B называют еще надмножество (собственное надмножество) A.
Очевидно, что для A справедливо: A A, AU, A (Пустое множество является подмножеством любого множества).
Определение 1.13: Множества A и B эквивалентны A=B, если A B, BA. Т.е. все элементы A являются элементами B, а все элементы B — элементами A.
Определение 1.14: Два множества A и B неэквивалентны, если они не эквивалентны или, что равносильно тому A\ B   или B\A  .

Свойства операций над множествами
Идемпотентный закон. (1.1)
Ассоциативный закон. (1.2)
Дистрибутивный закон. (1.3)
Коммутативный закон. (1.4)
Закон поглощения. (1.5)
Закон де Моргана для множеств. (1.6)
Закон двойного отрицания (1.7)
(1.8)
Все эти тождества доказываются взаимным включением, т.е., например, чтобы доказать, что надо доказать, что .
Возникает вопрос, почему следует заботиться о доказательствах в компьютерной науке. Мы должны доказать что-либо только один раз. Затем мы исходим из того, что эта часть информации является правильной и, следовательно, может рассматриваться как факт. Т.к. зачастую важен и сам метод и результат. После анализа доказательства становятся понятными предположения и последствия, процессы вывода, которые можно использовать при решении других задач. Кроме того, доказательства теории формируют основу всех решающихся автоматически задач.
Пример: Доказать равенство: .
1. Докажем, что .
Пусть или или
2. Докажем, что . Пусть

Из 1. и 2. следует, что ч. т.д.
Определение 1.15: Множество всех подмножеств данного множества Х называется степенью множества Х.
P(X) = {Y | Y  X}.
Т.к.   Х и Х  Х, то Р(Х), ХР(Х).
Замечание 1.3: Если |X| = n, то | P(X) | = 2 n
Пример: Х={1, 2}, |X| = 2, P(X)={{1},{2},{1,2}, }, |P(X)|=22=4.

1.4: Произведение множеств

До сих пор строили из существующих множеств множества меньшего размера. Рассмотрим способ конструирования больших множеств.
Определение 1.16: Обозначим упорядоченную последовательность из n элементов x1, x2, … ,xn через (x1, x2, … ,xn ) Будем называть такую последовательность набором длины n.
Набор длины 2 называется парой.
Следует различать множество 2-х элементов и упорядоченную пару:
{2, 3}={3, 2}, но (2, 3)(3, 2).
(a, b)=(c, d)a=c и b=d.
Пусть даны n множеств A1, A2, …. An.
Определение 1.17: Прямым произведением n множеств A1, A2, …. An, называется множество всевозможных упорядоченных наборов вида (x1, x2, … ,xn ) из n элементов таких, что х1A1, x2A2,…,xnAn.

Пример:
1. Шахматная доска представляет собой игровое поле из клеток, в котором столбцы обозначены латинскими буквами, а строки — цифрами.
Пусть F = {a, b,…, h}- cтолбцы, R = {1, 2,… 8}- cтроки, Тогда a1, f7, e3 и др. — клетки шахматной доски — это элементы произведения множеств FR.
2. RR=R2 — множество всех точек плоскости с координатами (x, y), x, y  R.
3. A={1,2,3}, B={a,b}, AB={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}.

Теорема 1.1: Пусть A1, A2, …. An — конечные множества |A1|=m1, …, |An|=mn. Тогда мощность множества: .
Следствие: |An| = |A|n.

Раздел 2. Отношения
2.1: Основные понятия

Определение 2.1: Любое подмножество  прямого произведения A1A2….An называется n-местным (n-арным) отношением, определенным на множествах A1, A2, …. An.
 A1 A2 …An .
Другими словами элементы x1,x2,…,xn (где х1A1, х2A2,…,хnAn) связаны отношением  тогда и только тогда, когда (x1, x2, …, xn ) . (x1, x2, …, xn ) — упорядоченный набор из n элементов.
Отношения, хотя и являются множествами, принято обозначать малыми буквами греческого алфавита , , , …, , .
Определение 2.2: Любое подмножество  прямого произведения A1A2 называется бинарным отношением, определенным на множествах A1 и A2.
Часто используют следующие обозначения:
1. (a,b), т.е. a и b находятся в отношении .
2. ab, т.е. a связано с b отношением .
3. b(a), (a)=b.
Рассмотрим частный случай, когда A1 = A2 = A, тогда AA=A2={(а,b)| a, bA}
=An = {(a1, a2, …, an ) | aiA, i=1n},
A1=A.
Т.о. будем иметь, что любое подмножество A2 определяет отношение на A. Очевидно, что =, =A2 также являются бинарными отношениями.
Пример:
A={1, 2, 3} A2= {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}
={(1, 1), (3, 2), (2, 3)}  A2
={(1, 1), (3, 2), (1, 4)}  A —  не является бинарным отношением на A.
Аналогично определяется тернарное отношение, определенное на множестве A, а именно   A3=A  A  A.
Пример:
1) Пусть A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Тогда
={(x, y)}| x, yA, x-делитель y, х 5} может быть записано в частном виде
={(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10), (2,2), (2,4), (2,6), (2,8), (2,10), (3,3), (3,6), (3,9), (4,4), (4,8), (5,5), (5,10)}
2) R-множество действительных чисел.  R2=R  R.
={(x, y) | x, y R, x y.
3) Шахматы. Пусть F = {a, b, c, d, e, f, g, h}, R={1, 2, 3, 4, 5, 6, 7, 8} и S=FR — множество всех клеток обозначаемых парами (x,y), где xF, yR. Определим бинарное отношение  для ладьи на S т.о., что клетка (s,t) S тогда и только тогда, когда, s и t элементы S, s,tS и ладья может пройти от s к t одним ходом на пустой доске. (Ладья может изменять либо горизонтальную, либо вертикальную координату, но не обе одновременно). Поэтому,   S  S и  = {(fs, rs), (ft, rt)) | (fs=ft и rsrt) или (fs ft и rs=rt)}.
Для бинарных отношений можно использовать любые способы задания множеств, например, список пар, для которых данное отношение выполняется. Отношения на конечных множествах обычно задаются списком или матрицей.
Матрица бинарных отношения  на множестве М={a1,…,am} — это квадратная матрица C порядка m, в которой элемент сij, стоящий на пересечении i-ой строки и j-го столбца, определяется следующим образом:

Пример: M={1, 2, 3, 4, 5, 6},   M2=M  M.
1.  = {(a, b)| a, b M и a  b}
1 2 3 4 5 6
1 1 1 1 1 1 1
2 0 1 1 1 1 1
3 0 0 1 1 1 1
4 0 0 0 1 1 1
5 0 0 0 0 1 1
6 0 0 0 0 0 1
2.  = {(a, b)| a, b M и a и b имеют общий делитель}
1 2 3 4 5 6
1 1 1 1 1 1 1
2 1 1 0 1 0 1
3 1 0 1 0 0 1
4 1 1 0 1 1 1
5 1 0 0 0 1 1
6 1 1 1 0 0 1

3.  = {(a, b)| a, b M и a — делитель b}
1 2 3 4 5 6
1 1 1 1 1 1 1
2 1 1 0 1 0 1
3 1 0 1 0 0 1
4 1 0 0 1 0 0
5 1 0 0 0 1 0
6 1 0 0 0 0 1

Так как отношения на М задаются подмножествами М2, то для них можно определить те же операции, что и над множествами.
Рассмотрим еще три отношения, которые полезны при рассмотрении множеств.
Определение 2.3: Для любого множества A определим тождественное отношение A и универсальное отношение A следующим образом:
A = {(a, a) |  a A},
A = {(a, b) |  aA, bA}.
Таким образом, A = A2
Т. к.   A2, то  является отношением на A и называется пустым отношением.
Пусть А={1, 2, 3, 4}. Матрица смежности тождественного, универсального и пустого отношений, определенных на множестве A, будут иметь соответственно вид:
1) матрица тождественного отношения:
1 2 3 4
1 1 0 0 0
2 0 1 0 0
3 0 0 1 0
4 0 0 0 1

2) матрица универсального отношения:
матрица универсального отношения:
1 2 3 4
1 1 1 1 1
2 1 1 1 1
3 1 1 1 1
4 1 1 1 1

3) матрица пустого отношения:
1 2 3 4
1 0 0 0 0
2 0 0 0 0
3 0 0 0 0
4 0 0 0 0

Пусть отношение  определено в соответствии с изображением на рисунке 2.1.

Элементы A, Элементы A и B, Элементы В,
не включаемые в  включаемые в  не включаемые в 
Рис.2.1. Бинарное отношение .

Рассмотрим элементы множеств A и В, находящиеся в отношении . Они имеют специальные названия.
Определение 2.4: Свяжем с каждым бинарным отношением , определенным на множествах A и B,   A B, два множества — область определения D() и область значений R(). Они определяются следующим образом.
D() = {x| (x, y)},
R() = {у| (x, y) }.
Пример : A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
 = {(x, y) | x, yA, х — делитель y, x  5}.
Тогда: D() = {1, 2, 3, 4, 5}, R(  ) = A.
Пример: Предположим, что мы имеем некоторую программу, она читает два числа из множества A = {1, 2, 3, 4, 5}, обозначенных x и y, и если х < y, печатает число z (так же из A) такое, что х  z < y. В любом случае программа останавливается после считывания всех чисел из A. Задача определяет отношение A2A такое, что ={((x,y),z)|x1073. Чтобы они совпадали нужно выравнивать число разрядов у всех сравниваемых чисел, приписывая с лева нули. Получим 0020<1073. Такое выравнивание чисел автоматически происходит при записи целых чисел в ЭВМ. 3. Лексико-графическое упорядочение цифровых представлений дат вида 05.08.86.(5 августа 1986) не совпадает с естественным упорядочением дат от ранних к поздним: например, 05.08.86 лексико-графически “старше” третьего числа любого года. Чтобы возрастание дат совпадало с лексико-графическим упорядочением, обычное представление надо “перевернуть”, т.е. слева направо 86. 08. 05. Так делают при представлении дат в ЭВМ. Определение 2.21: Рассмотрим конечное множество A   . Говорят, что элемент y покрывает элемент х, если xy и xВ, и тогда т.к. отображение всюду определено в А найдутся два элемента, которым соответствует один элемент из В и нарушится единственность образа ; либо В>Аи тогда нарушится единственность прообраза. Этот факт позволяет установить равенство мощностей двух множеств, не вычисляя мощностей двух множеств, а также установив взаимно однозначное соответствие со множеством, мощность которого известна, вычислить мощность множества.
Определение 2.29: Если между элементами двух множеств можно установить взаимно однозначное соответствие, то такие множества называются равномощными.
Для конечных множеств это утверждение доказывается, а для бесконечных является определением равномощности.
Определение 2.30: Множества, равномощные множеству натуральных чисел, называются счетными .
Утверждение 2.4: Объединение конечного числа счетных множеств счетно.
Теорема 2.2(Кантора): Множество всех действительных чисел [0;1] не счетно. Множество такой мощности называется континуальным, а его мощность – мощностью континуума.
Утверждение 2.5: Множество всех подмножеств счетного множества континуально.
Не существует множества максимальной мощности.