- •Лекция 2
- •Лекция 3
- •Лекция 4
- •Лекция 5
- •Лекция 13
- •Лекция 14
- •Лекция 16
- •Основные понятия
- •Понятие множества. Способы задания множеств.
- •Понятие множества. Способы задания множеств.
- •Отношения между множествами.
- •3, Операции над множествами.
- •Алгебра множеств.
- •Теорема о количестве подмножеств конечного множества.
- •Формула включений и исключений.
- •Лекция 2
- •1.Понятие вектора. Прямое произведение множеств.
- •2.Теорема о количестве элементов прямого произведения.
- •Понятие вектора. Прямое произведение множеств.
- •Теорема о количестве элементов прямого произведения.
- •Лекция 3
- •2. Понятие высказывания.
- •3. Логические операции над высказываниями
- •4.Формулы алгебры логики.
- •Лекция 4
- •2. Важнейшие равносильности алгебры логики.
- •3.Равносильные преобразования формул.
- •Задачи для самостоятельного решения
- •Лекция 5
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Проблема разрешимости.
- •Лекция 6
- •Функции алгебры логики.
- •3. Представление произвольной функции алгебры логики в виде формулы алгебры логики.
- •4.Приложения алгебры логики в технике (релейно-контактные схемы).
- •Контрольные вопросы
- •Лекция 7
- •Совершенная дизъюнктивная нормальная форма.
- •Совершенная конъюнктивная нормальная форма.
- •Совершенная дизъюнктивная нормальная форма.
- •2.Совершенная конъюнктивная нормальная форма.
- •Лекция 8
- •2.Понятие минимальной днф. Метод минимизирующих карт.
- •3.Метод Квайна.
- •4.Метод Карно.
- •5.Постановка задачи минимизации в геометрической форме.
- •6.Сокращенная днф.
- •7.Тупиковая днф. Днф Квайна.
- •Лекция 9
- •Некоторые логические операции. Двоичное сложение.
- •Полином Жегалкина.
- •Некоторые логические операции. Двоичное сложение.
- •Полином Жегалкина.
- •Лекция 10
- •Полная система . Достаточное условие полноты.
- •Критерий полноты системы булевых функций.
- •Независимые системы. Базис замкнутого класса.
- •Полная система. Достаточное условие полноты.
- •Критерий полноты системы булевых функций.
- •3. Независимые системы. Базис замкнутого класса.
- •Лекция 11
- •Понятие предиката.
- •Логические операции над предикатами.
- •1. Понятие предиката
- •2. Логические операции над предикатами
- •Лекция 12
- •2. Формулы логики предикатов.
- •Значение формулы логики предикатов.
- •4. Равносильные формулы логики предикатов.
- •Лекция 13
- •Построение противоположных утверждений.
- •3. Прямая, обратная и противоположная теоремы.
- •4. Необходимые и достаточные условия.
- •5. Доказательство методом от противного.
- •Задачи для самостоятельного решения
- •Лекция 14
- •2. Использование метода математической индукции для нахождения сумм конечного числа слагаемых
- •3. Использование метода математической индукции для доказательства неравенств и делимости выражений, зависящих от n на некоторое число
- •4. Обобщение метода математической индукции
- •Контрольные вопросы
- •Лекция 15
- •Операции над бинарными отношениями.
- •3. Свойства бинарных отношений.
- •4. Специальные бинарные отношения.
- •Контрольные вопросы
- •Лекция 16
- •Функция
- •1. 4. Отображение
- •Обратная функция
- •2. Свойства отображений и функций
- •3.Операции над функциями. Свойства операций
- •Контрольные вопросы
- •Лекция 17
- •Основные понятия .
- •2. Смежность, инцидентность, степени вершин.
- •3. Способы задания графов
- •Маршруты в неориентированном графе
- •Операции над графами.
- •Связность. Компоненты связности
- •Контрольные вопросы
- •Лекция 18
- •2. Метрические характеристики неориентированного графа
- •Минимальные маршруты в нагруженных графах
- •Задачи на деревьях
- •Цикловой ранг графа. Цикломатическое число
- •Контрольные вопросы
- •Лекция 19
- •Эйлеровы цепи и циклы
- •Гамильтоновы циклы и цепи
- •Эйлеровы цепи и циклы
- •Гамильтоновы циклы и цепи.
- •Контрольные вопросы
- •Лекция 20
- •Двудольный граф. Условие существования двудольного графа
- •Паросочетания . Реберные покрытия
- •Двудольный граф. Условие существования двудольного графа
- •Паросочетания. Реберные покрытия
- •Контрольные вопросы
- •Лекция 21
- •Основные определения
- •Алгоритм плоской укладки графа
- •Контрольные вопросы
- •Лекция 22
- •Способы задания ориентированного графа
- •Путь в ориентированном графе
- •4. Связность. Компоненты связности в орграфе
- •Контрольные вопросы
- •Лекция 23
- •2. Минимальные пути в нагруженных орграфах
- •3. Порядковая функция орграфа без контуров
- •Контрольные вопросы
Лекция 14
ТЕМА: МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
Понятие индукции. Аксиома математической индукции.
Использование метода математической индукции для нахождения сумм конечного числа слагаемых
Использование метода математической индукции для доказательства неравенств и делимости выражений, зависящих от n на некоторое число
Обобщение метода математической индукции
Главная
Понятие индукции. Аксиома математической индукции
Все утверждения можно разделить на общие и частные. Например, утверждение «Во всяком параллелограмме диагонали делятся в точке пересечения пополам» является общим, так как относится ко всему множеству параллелограммов. В то же время утверждение «В параллелограмме ABCD диагонали в точке пересечения делятся пополам» является частным утверждением, так как относится к конкретному параллелограмму ABCD.
На основе частных утверждений делают некоторые предположения (гипотезы) о справедливости какого-либо общего утверждения. Иногда эти предположения оказываются верными, иногда неверными. Переход от частных утверждений к общим называют индукцией (от латинского слова inductio — наведение). Например, знаменитый математик XVII в. П. Ферма, проверив, что
числа
простые, сделал по индукции предположение, что для всех п = 1, 2, ... числа вида - простые. Однако это предположение оказалось неверным, так как в XVIII в. Л. Эйлер нашел, что — составное число. Как видим, индукция не является методом доказательства, а лишь помогает сформулировать неизвестный результат в виде некоторой гипотезы, справедливость которой потом надо доказать.
В случае, когда утверждение касается конечного числа объектов, его можно доказать, проверяя для каждого объекта. Например, утверждение «Каждое четное однозначное число является суммой двух простых чисел» легко проверить, рассмотрев равенства 2=1 + 1, 4 = 3+1, 6 = 5+1, 8 = 3 + 5.
Метод доказательства, при котором утверждение проверяется для каждого из конечного числа случаев, называют полной индукцией. Если же утверждение проверяется лишь для некоторых случаев и по индукции делается заключение о его справедливости для всех случаев, то индукцию называют неполной.
Индуктивные гипотезы формулируются обычно в виде утверждений, относящихся ко всем натуральным числам. Последовательная проверка такого утверждения для каждого натурального числа п, начиная с 1, разумеется, невозможна, если говорить обо всех натуральных числах. Но сама идея последовательного перехода от натурального числа п к следующему за ним числу n +1 осуществляется в строгой форме в одном из самых важных методов математических доказательств, называемом методом математической индукции. В основе этого метода лежит аксиома индукции:
Предположение, что Р (n) справедливо для всякого натурального n, если:
1) оно справедливо для n =1;
2) из справедливости утверждения для какого-либо произвольного натурального n = k следует его справедливость для n = k +1.
Действительно, из того, что утверждение верно при n= 1, вытекает по второму условию его справедливость для n= 1 + 1 = 2, но тогда оно верно и для n = 2 + 1=3, n = 3+1= 4 и т. д. Ясно, что в конце концов мы дойдем до любого натурального числа n.
Сам метод математической индукции состоит в следующем:
Для доказательства справедливости P(n) для любого n (P(n) – есть одноместный предикат от n, значит, доказываем nP(n) 1)
проверить истинность при n = 1, т.е. Р(1) = 1(истина);
допускают, что Р(n) = 1 при n = k и
проверяют истинность для n = k + 1.
Если P(k + 1) = 1, то nP(n) 1.