Цель работы: научиться использовать язык логики предикатов для записи математических утверждений и применять метод математической индукции.
Ход выполнения работы:
1. Изучить теоретический материал.
2. Получить задание у преподавателя.
3. Выполнить задание.
4. Ответить на контрольные вопросы.
5. Защитить выполненное задание.
Краткие теоретические сведения.
Метод математической индукции – специальный метод доказательства, применяемый для доказательства истинности утверждений типа или, что аналогично .
Такие утверждения выражают тот факт, что некоторое свойство Р присуще каждому натуральному числу.
Формальной основой метода математической индукции служит одна из аксиом, называемая аксиомой индукции (или математической индукции) и выражающая свойство естественного отношения порядка, имеющегося на множестве всех натуральных чисел.
Эта аксиома такова. Если свойством Р обладает число 1 и для всякого натурального числа из того, что оно обладает этим свойством, следует, что и непосредственно следующее за ним натуральное число также обладает им, то и всякое натуральное число обладает свойством Р.
Эта аксиома дает следующий метод доказательства утверждений, выражающих некоторые свойства всех натуральных чисел.
Если нужно доказать утверждение (" у)(Р (у)), где у Î N («Всякое натуральное число обладает свойством Р»), достаточно установить истинность высказывания Р (1) («Число 1 обладает свойством Р») и доказать, что (" х)(Р (х) ® Р (х + 1)) («Если х обладает свойством Р, то этим свойством обладает и число х + 1, непосредственно следующее за х»)
Таким образом, логическая схема доказательства методом математической индукции может быть представлена следующим образом:
(1): Р(1) – устанавливается проверкой;
(2): ("х)(Р (х) ® Р (х + 1)) – доказывается;
(3): P(1) Ù (" х)(Р (х) ® Р (х + 1)) – из (1), (2) по правилу введения конъюнкции;
(4): (P (1) Ù (" х)(Р (х) ® Р (х + 1))) ® (" y)(P (y)) – аксиома индукции;
(5): (" y)(Р (у)) – из (3), (4) по правилу вывода (правило МР).
При этом установление истинности утверждения Р (1) представляет собой основание или базу индукции; предположение об истинности утверждения Р (х) – предположение индукции; последующее доказательство истинности утверждения Р (х + 1) представляет собой шаг индукции.
Образец выполнения
1. Записать на языке логики предикатов определение точки максимума
Решение.
Словесная формулировка определения точки максимума имеет вид: «Точка x 0 из области определения функции f называется точкой локального максимума функции f, если существует такая d-окрестность данной точки, что для всех х из этой окрестности f (х) < f (x 0)»
На языке логики предикатов это определение запишется следующим образом:
2. Используя принцип математической индукции доказать, что:
1 + 2 +… + n = n (n + 1)/2
Решение.
Проверим основание индукции – установим истинность утверждения при
Сделаем предположение индукции. Пусть утверждение истинно при
Сделаем шаг индукции. Докажем истинность утверждения при . Это означает, что нужно доказать равенство
Используя предположение индукции, получаем:
Таким образом, истинность утверждения при доказана.
Следовательно, утверждение верно для всех натуральных чисел.
Задания
1. Записать на языке логики предикатов определения:
1) монотонной последовательности
2) ограниченной последовательности
3) предела последовательности (сходящейся последовательности)
4) возрастающей функции, монотонной функции
5) четной функции
6) периодической функции
7) функции, стремящейся к бесконечности в точке
8) предела функции в точке
9) непрерывности функции в точке.
2. Используя принцип математической индукции доказать, что
1)
2)
3)
4)
5)
6)
7)