Лекция 1

Лекция 1

Введение

К дискретной математике относится теория множеств, теория матриц, теория графов, комбинаторика, математическая логика, теория вероятности, теория алгоритмов и многое другое.

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

Мы рассмотрим следующие разделы ДМ.

1. Элементы теории множеств.

2. Элементы теории графов.

3. Элементы комбинаторного анализа.

4. Элементы математической логики.

1. Элементы теории множеств

Множество не имеет строгого определения в математике, так как является первичным. Основатель теории множеств Георг Кантор дал интуитивное определение понятия множества как «объединение в одно общее объектов хорошо различимых нашей интуицией».

Георг Кантор
Даты жизни:	1845-1918
Место рождения:	Санкт-Петербург
Научная сфера:	математика
Место работы:	Галльский университет
Альма-матер:	Берлинский университет
Известен как	создатель теории множеств

Объекты, составляющие множество, называют его элементами. Множества обозначают прописными латинскими буквами, а его элементы − строчными.

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

Объединение множеств − множество С, состоящее из элементов, входящих хотя бы в одно из множеств А или В:

На диаграммах Эйлера-Венна результат объединения показан штриховкой.

Пересечение множеств − множество С, состоящее из общих элементов множеств А и В.

Обозначение:

Разность множеств − множество C, состоящее из элементов множеств А, не принадлежащих множеству В:

Дополнение множества A до множества B − множество C, состоящее из элементов множества В, не принадлежащих множеству А: , .

Симметрическая разность множеств A и B − множество C, состоящее из элементов, каждый из которых принадлежит или множеству А, или множеству В:

Прямое произведение множеств А и В есть множество С, состоящее из элементов, каждый из которых является упорядоченной парой, в которой первым компонентом является элемент множества А, вторым компонентом – элемент множества В.

Пример. Заданы множества:

Тогда: .

Лекция 2

2. Элементы теории графов

Теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании, анализе электрических цепей, в транспортных задачах (например, для составления оптимальных маршрутов доставки грузов) и других областях науки и практики. Созданию теории графов предшествовали две задачи для любознательных: «о семи Кёнигсбергских мостах» и « о трех домах и трёх колодцах»

Задача о семи Кёнигсбергских мостах.

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

Рис. 1. Кенигсбергские мосты

В 1736 году задача о семи мостах была решена двадцатилетним Леонардом Эйлером. Он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем семи мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

Эйлер заменил участки суши точками, а мосты − линиями. Полученную конфигурацию Эйлер назвал графом, точки − его вершинами, а линии − ребрами. Вершины он подразделил на четные и нечетные. Вершина четная, если из неё выходит четное число ребер. В противном случае вершина нечетна.

Эйлер показал, что все ребра графа можно обойти ровно по одному разу по непрерывному замкнутому маршруту, если граф содержит четные вершины. Так как граф в задаче о кенигсбергских мостах содержит только нечетные вершины, мосты невозможно обойти по непрерывному маршруту, побывав на каждом ровно по одному разу и вернувшись к началу маршрута.

Леона́рд Э́йлер — швейцарский, немецкий и российский математик и механик, внёсший фундаментальный вклад в развитие этих наук. Эйлер − автор более чем 850 работ, в том числе два десятка фундаментальных монографий. Это работы по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, математической физике, оптике, баллистике, теории музыки и др. Эйлер академик Петербургской, Берлинской, Туринской, Лиссабонской и Базельской академий наук, иностранный член Парижской академии наук. Почти полжизни провёл в России, где внёс существенный вклад в становление российской науки. Леонард Эйлер
Даты жизни:	1707-1783
Место рождения:	Базель, Швейцария
Научная сфера:	математика, механика, физика, астрономия

Задача о трех домах и трех колодцах.

Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались.

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

Рис. 2. Три дома и три колодца

Эта задача не имеет решения на плоскости, но в другом пространстве она была решена польским математиком Казимиром Куратовским в 1930 году методами топологии.

Основные понятия и определения

1. Графом G(V, E) называется совокупность двух множеств: непустого множества V (множества вершин) и множества E (множества ребер). Оба конца ребер принадлежат множеству V.

Обозначение:

Геометрически граф изображают диаграммой: вершины – точками (или кружками), ребра – прямыми или кривыми линиями.

2. Инцидентные вершины и ребра.

Пусть

Тогда вершины и ребро называют инцидентными.

3. Смежные вершины и ребра. Два ребра инцидентные одной вершине и две вершины, инцидентные одному ребру называют смежными.

4. Ориентированный граф.

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

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

5. Петля. Если элементом множества Е может быть пара одинаковых элементов множества V, то такой элемент множества Е называется петлей, а граф называется графом с петлями. Дуга (или ребро) называется петлёй, если она начинается и заканчивается в одной вершине.

6. Если E является набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными, а граф − мультиграфом.

Пример 1. Изобразить граф, заданный множеством вершин V и отображением E на V:

.

Рис. 3 Неориентированный граф с петлей и кратными ребрами.

Пример 2.

.

Т. о. это ориентированный граф с петлей и кратными ребрами.

Рис. 4. Ориентированный граф с петлей и кратными ребрами.

Пример 3.

, :

Рис. 3.5. Неориентированный граф с петлей.

7. Маршрутом называется чередующаяся последовательность инцидентных вершин и ребер:

Длиной маршрута называется количество ребер в нем. Если то маршрут замкнут.

Путем называется маршрут, в котором все вершины различны.

8. Цепью называется маршрут, у которого все ребра различны (отсутствуют кратные ребра).

9. Циклом называется замкнутая цепь.

10. Деревом называется конечный граф без циклов и петель, имеющий начальную вершину и крайние вершины. Пути от начальной вершины к крайним называются ветвями.

Лекция 3

3. Элементы комбинаторного анализа (комбинаторика)

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

1. Упорядочение данного множества.

2. Образование упорядоченных подмножеств из элементов заданного множества.

3. Образование неупорядоченных подмножеств, состоящих из элементов заданного множества.

Комбинаторика устанавливает общие законы комбинирования вариантов, дает формулы для подсчета их числа.

Пример.

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

Основные законы комбинаторики.

Правило суммы.

Если некоторый элемент a может быть выбран из множества элементов m способами, а другой элемент b может быть выбран n способами, причем любой выбор элемента b отличен от любого выбора элемента a, то выбрать либо a, либо b можно m + n способами.

На языке теории множеств это правило формулируется следующим образом:

Если пересечение конечных множеств пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В.

АВ = | АВ | = |A| + |B|

Здесь |A| и |B| количество элементов во множествах А и В соответственно (мощность множества или кардинальное число)

Пример: на блюде лежат 5 яблок и 2 груши. Сколькими способами можно выбрать один плод?

Решение: плод можно выбрать семью способами (5+2=7).

Множества A и B могут иметь непустые пересечения. Тогда правило суммы на языке множеств формулируется следующим образом.

Если пересечение конечных множеств не пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В минус количество элементов в их пересечении:

| АВ | = |A| + |B| − | АВ |.

Пример.

Среди студентов первого курса 30 человек имеют дома компьютер, 35 – учебник по информатике, 10 студентов имеют и компьютер, и учебник по информатике. Сколько студентов на первом курсе?

Решение.

Пусть множество А составляют студенты, имеющие компьютер, множество В – студенты, имеющие учебник по информатике; по условию задачи:

|A| = 30 |B| = 35 | АВ | = 10 | АВ | =?

| АВ | = |A| + |B| – | АВ | = 30 + 35 – 10 = 55.

Правило произведения.

Вторым основным правилом комбинаторики является правило произведения.

Пример.

Сколькими способами можно расставить на полке три книги: А, В, С.

Решение.

Решение легко провести с помощью построения графа. Из рисунка видно, что существует 6 способов расстановки 3-х книг на полке.

Для книги на первом месте существует m1 способов (m1=3: или А на первом месте, или В, или С), после чего для книги на 2-м месте остается 2 способа (m2= 2), после этого для книги на 3-ем месте остается 1 способ (m3 = 1). Всего: m1∙ m2 × m3 = 3× 2 ×1 = 6 способов: АВС, АСВ, ВАС, ВСА, САВ, СВА.

Сформулируем теперь правило умножения:

Пусть нужно произвести k действий: первое из них можно произвести m1 способами, второе после этого – m2 способами и т. д., последнее k-е действие можно произвести mк способами. Тогда все k действий можно произвести m1× m2 × m3 ××× mк способами.

Если элемент a можно выбрать из множества элементов m способами и после каждого такого выбора элемент b можно выбрать n способами, то два элемента (упорядоченную пару) a и b можно выбрать m•n способами.

На языке множеств это правило выражается в виде следующей теоремы.

Теорема : если множества А и В конечны, то

|AB| = |A| |B|.

Следствие: если множества А1, А2, …, Аn − конечны, то

|A1…Аn| = |A1||A2|…|An|.

Пример: сколько номеров, состоящих из двух букв, за которыми идут три цифры можно составить, если использовать 29 букв и 10 цифр.

Решение: обозначим множество букв А, множество цифр – В; каждый номер требуемого вида является набором длины n из декартова произведения ААВВВ; по условию мощность множества |А| = 29, |В| = 10, тогда по следствию из теоремы имеем:

| ААВВВ | = 2929101010 = 841000.

В практических задачах часто рассматривают различные комбинации (соединения), составленные из k элементов, взятых из множеств, состоящих из n элементов (k£ n). Простейшими из них являются размещения, перестановки и сочетания.

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

Размещения.

Размещениями данных n элементов по k элементов называются подмножества из k элементов, составленные из данного множества и отличающиеся друг от друга либо порядком элементов, либо самими элементами.

Пример 1. Даны различные предметы – n штук и ящик с k ячейками. Требуется заполнить ячейки данными предметами по одному в каждую ячейку. Сколькими вариантами это можно сделать?

Число таких вариантов и есть число “размещений”.

Обозначение: (читается: А из “n” по “k”).

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

№ яч.	1	2	3	4	×××	k-2	k-1	k
колич. способов	n	(n-1)	(n-2)	(n-3)	¼	n-(k-3)	n-(k-2)	n-(k-1)

Очевидно, что общее количество способов можно определить по принципу умножения.

, где k £ n.

Пример 2. Вычислить.

Решение.

=60.

Число всех размещений из “n” элементов по “k” элементов удобнее вычислять по формуле:

(1)

Вычислим по формуле (1):

Ответ: .

Пример 3. Во втором семестре студенты изучают 10 предметов. На первый день занятий необходимо поставить в расписание 3 предмета. Сколькими способами это можно сделать?

Решение.

Ответ: .

Перестановки

Если k=n и все предметы уложены в k ячеек, то при любом способе укладки предметов полученное подмножество будет отличаться от исходного множества только порядком, но не самими предметами. Такие размещения называют перестановками.

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

Число всех перестановок обозначают Рn. Положив в формуле (1) n=k, получим:

Рn = n(n–1)(n–2) ××× 3×2×1 или

Рn = n! , (2)

(где n! = 1×2×3×××n; 1! = 1; 0! = 1– по определению факториала).

Пример: Сколькими способами можно выстроить очередь из пяти человек?

Решение. Р5 =5∙4∙3∙2∙1=120.

Сочетания

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

Сочетаниями, содержащими k элементов, выбранных из множества из n элементов, называются все подмножества, отличающиеся друг от друга хотя бы одним элементом.

Формулу для числа сочетаний легко получить простым рассуждением.

Пусть дано n элементов. Составим из них все размещения по k элементов (k < n). Число определяется так , так как все предметы можно разбить на группы по k элементов, в которых элементы одни и те же, но порядок разный. То есть, в каждый такой группе содержатся подмножества элементов, различающихся лишь порядком. Значит таких подмножеств в каждой группе Рk. Количество же групп, в которых элементы разные равно . Тогда согласно принципу умножения:

= =>

Учитывая формулы (1) − (2), получим:

= (3)

Пример. Сколько различных вариантов может быть в тираже спортлото “5 из 36”.

Решение.

Бином Ньютона

Бином это двучлен. Бином Ньютона – это двучлен в степени n.

Формула бинома Ньютона:

Здесь − биномиальные коэффициенты. Биномиальные коэффициенты, равноотстоящие от концов формулы равны между собой.

Пример 1. Записать квадрат суммы через биномиальные коэффициенты.

Решение.

Пример 2. Записать самостоятельно куб суммы через биномиальные коэффициенты.

Лекция 4

4. Элементы математической логики

Математическая логика – это анализ методом рассуждений.

Алгебра логики (логика высказываний)

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

Джордж Буль

	1815-1864
Место рождения:	Линкольн, Линкольншир, Англия
Научная сфера:	Математика, Логика, Философия математики

Основные понятия логики высказываний

1. Высказывание - повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно.

Примеры высказываний:

−"кит - животное",

−"все углы - прямые" и т. п.

Первое из этих высказываний является, очевидно, истинным, а второе - ложным.

Предложение «площадь треугольника меньше площади прямоугольника» высказыванием не является, так как нельзя судить об истинности или ложности этого утверждения.

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

2. Логические связки

− не;

− …и…;

− …или…;

− если…, то…

− …тогда и только тогда, когда…;

3. Элементарные высказывания сформированы без использования логических связок и являются нерасчленимыми. Обозначения: a, b, c,....

4. Составные высказывания образуются с помощью логических связок.

Логическая операция производится логической связкой.

Каждая логическая операция имеет название и обладает определенным логическим смыслом.

5. Список логических операций.

− Отрицание (не А): (ùA), обозначает высказывание, противоположное высказыванию А.

− Конъюнкция (А и В): . Высказывание истинно только, если высказывания А и В оба истинны.

− Дизъюнкция (А или В ): . Высказывание истинно тогда, когда истинно хотя бы одно из высказываний А или В (или оба истинны).

− Импликация (если А, то В ): . Высказывание, истинное во всех случаях, кроме того когда А истинно, а В ложно.

− Эквиваленция (А тогда и только тогда, когда В). Высказывание истинно только тогда, когда высказывания А и В оба истинны или оба ложны

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

Каждому высказыванию можно сопоставить его значение, обозначаемое соответственно буквой И или цифрой 1 (если высказывание истинно), буквой Л или цифрой 0 (если высказывание ложно).

Значение сложных высказываний зависит от значений высказываний, составлявших сложное высказывание.

Пусть A, В − произвольные высказывания

Высказывание (ùA), которое истинно, если A – ложно, и ложно, если A – истинно можно наглядно отобразить в таблице истинности.

Таблица истинности отрицания:

A
И	Л
Л	И

Пример:

A: 2*2=4 – истинное высказывание;

: или 2*24 - ложное высказывание.

Высказывание AB ( А &В − конъюнкция), истинно тогда и только тогда, когда A, B – истинны.

Таблица истинности конъюнкции:

A	B	AB
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

Пример. A: 5 – нечетное число; B: Пушкин родился в 1799 г – истинные высказывания; поэтому высказывание AB: 5 – нечетное число Пушкин родился в 1799 г. – истинное высказывание.

Высказывание AB (дизъюнкция), ложно тогда и только тогда, когда A, B – оба ложны.

Таблица истинности дизъюнкции:

A	B	AB
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

Пример.

A: «7<10» − И; В: «3 − число четное» −Л.

Высказывание A→B (импликация) ложно тогда и только тогда, когда A – истинно, а B – ложно.

Таблица истинности импликации:

A	B	A→B
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

Пример.

A: 2*2=5−Л; В: 2=2−И. A→B: 2*2=5→ 2=2 –И.

Высказывание A«B (эквиваленция "A эквивалентно В"), считается истинным только тогда, когда оба высказывания A и В имеют одинаковое значение.

Эквивалентность А«В читается также следующим образом: "Для того, чтобы A, необходимо и достаточно, чтобы В".

Таблица истинности эквиваленции:

A	B	A«B
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

Пример.A: «7 – число простое» − И, В: «В равнобедренном треугольнике при основании углы равны» − И. A«В – И.