- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
-
Элементы комбинаторики.
-
Основные понятия комбинаторики. Определение.
-
Комбинаторика — раздел математического анализа, посвященный способам подсчета числа элементов в конечных множествах.
Особенно полезными являются сами комбинаторные рассуждения. Они позволяют обойтись без излишнего формализма, и там, где эти принципы срабатывают, получаются красивые и понятные результаты.
Ярким примером эффективности комбинаторного подхода является теория бинома Ньютона. Все красивые результаты — различные соотношения между биномиальными коэффициентами — имеют простое комбинаторное истолкование.
Определение.
Говорят, что отрезок натурального ряда нумерует множество , если существует биективное отображение .
Если задана нумерация множества , то применяют следующие обозначения:
Теорема – правило суммы. Пусть и – конечные непересекающиеся множества, то есть , тогда
Доказательство.
Зафиксируем , нумерации и соответственно и рассмотрим отображение
,
заданное правилом:
Очевидно, – биективное отображение, тогда на основании основного принципа комбинаторики получаем
.
Теорема (следствие из предыдущей). Пусть и – конечные множества, тогда .
Доказательство.
Очевидно, и множества , не пересекаются тогда из равенства правила суммы получим
. (*)
Очевидно, и множества , тогда из равенства правила суммы получаем
. (**)
Подставляя выражение для из (**) в (*), получаем
.
Теорема – правило включения-исключения.
Пусть – конечные множества, тогда
В правой части этой формулы, называемой формулой включения исключения, стоят с чередующимися знаками скобки, содержащие всевозможные попарные пересечения множеств , пересечения троек множеств и так далее.
Доказательство.
Докажем формулу включения-исключения по индукции.
Справедливость её для случая доказана в предыдущей теореме. Рассмотрим индуктивный переход, т.е. предположим, что формула верна для любых множества и покажем, что тогда она верна и для множеств.
Здесь мы воспользовались равенствами
Теорема – правило суммы непересекающихся множеств.
Если – конечное попарно не пересекающиеся множества (т.е. ,), то
.
Ясно, что это тривиальное следствие из предыдущей теоремы.
-
Декартово произведение множеств.
Определение.
Декартовым произведением множества и называется множество, обозначенное , элементами которого являются упорядоченные пары , где , . Равенство упорядоченных пар понимается в следующем смысле:
пусть
Теорема.
Если и – конечные множества, то – конечное множество и .
Доказательство.
Ясно, что в случае, когда одно из множеств , пусто, то и пусто и тривиально выполнено. Рассмотрим случай, когда и – непустые множества. Зафиксируем в нумерацию
.
Ясно, что и множества попарно не пересекаются, тогда по правилу суммы имеем:
(*).
Рассмотрим отображение , действующее по правилу
.
Ясно, что – биективное отображение, тогда по основному принципу комбинаторики получаем
(**).
Подставляя (**) в (*), получим:
.
-
Множество степень.
Определение.
Пусть – множество и . Определим декартовы степени множества следующими выражениями:
Теорема.
Если – конечное множество, то
.
Доказательство.
Ясно, что эта теорема является следствием из предыдущей теоремы.
Определение.
Пусть и – непустые множества. Обозначим через множество отображений, действующих из в , то есть
.
Множество называется множеством степень.
При доказательстве теоремы о числе элементов во множестве степень, когда и – конечные множества, необходимо доказать две леммы.
Лемма 1. Пустьи – конечные непустые множества и ,
тогда
.
Доказательство.
Зафиксируем в и нумерации – , .
Занумеруем элементы множества условием:
.
Ясно, что нумерующий отрезок – .
Лемма 2. Пустьи – конечные непустые множества и , , тогда
.
Доказательство.
Зафиксируем в и нумерации, выбрав такую нумерацию множества , при которой .
Множество представим в виде объединения попарно непересекающихся множеств , отнеся ко множеству , если
.
По правилу суммы получаем:
. (*)
Рассмотрим одно из множеств . Каждое отображение однозначно определяется своим ограничением (сужением) на множество . (Стрелочная диаграмма любого отображения , содержит стрелку, ведущую из в )
Стрелки указанные пунктиром – ограничение на .
Ясно, что . (**)
Подставляя из (**) в (*), получаем
.
Теорема. Пусть , – конечные непустые множества, тогда –конечное множество и
.