- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
-
Примеры задач и упражнений. Пример 1
Доказать, что
. (1)
Доказательство
Метод математической индукции будем оформлять по следующей схеме.
1. Базис индукции: проверим равенство при . Левая часть (ЛЧ)=1, правая часть (ПЧ)=. Равенство при , то есть базис индукции, выполняется.
2. Индуктивное предположение: допустим, равенство (1) верно при , то есть допустим, что
. (2)
3. Индуктивный переход: докажем равенство (1) при , то есть докажем, что . В самом деле, . Здесь мы применили индуктивное предположение. Далее , что и требовалось доказать.
На основании ММИ равенство (1) верно при любом .
Пример 2
Доказать, что для любого
. (3)
Доказательство
1. Базис индукции: проверим утверждение (3) при . ЛЧ=, ПЧ=. Базис индукции доказан.
2. Индуктивное утверждение: допустим, (3) верно при , то есть допустим:
. (4)
3. Индуктивный переход: докажем (3) при , используя (4), то есть докажем, что
.
В самом деле,
.
Пример 3
Доказать, что для любого делится на 9. (5)
Доказательство
1. Базис индукции: проверим (5) при . ЛЧ=4+15-1=18 делится на 9.
2. Индуктивное предположение: допустим, (5) выполняется при , то есть делится на 9. (6)
3. Индуктивный переход: докажем (5) при , используя (6), то есть докажем, что делится на 9.
.
Первая скобка делится на 9 по индуктивному предположению. Осталось доказать, что второй слагаемый делится на 9, то есть надо доказать, что делится на 3. Это утверждение мы будем доказывать методом математической индукции, то есть нам придется применять "индукцию в индукции". При m=1 4+5=9 делится на 3. Допустим, делится на 3. Докажем, что делится на 3, но . Первый слагаемый делится на три по индуктивному предположению, а второе – очевидно. Таким образом, мы доказали, что делится на 3, а вместе с этим, что делится на 9.
Пример 4
для любого .
Доказательство
При n=1 неравенство очевидно: 2>1. Допустим, . Докажем, что . В самом деле, , так как по индуктивному предположению и – очевидное неравенство.
Пример 5
для любого натурального .
Доказательство
При n=5 получаем верное неравенство 32>25. Допустим, неравенство верно при , то есть . Докажем, что . Это неравенство равносильно . Если мы докажем, что , то будет доказано и исходное неравенство. Неравенство доказываем индукцией (индукция в индукции). При имеем верное неравенство . Допустим, неравенство верно при , то есть . Докажем при , то есть докажем, что или . Очевидно, что это неравенство верно в силу индуктивного предположения.
-
Задачи для самостоятельного решения.
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого ;
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого ;
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого ;
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого справедливо равенство
-
Доказать методом математической индукции, что для любого
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого .
-
Доказать методом математической индукции, что для любого ;
-
Доказать методом математической индукции, что для любого .