Прокопчук Ю.Ю., Широков А.И. Дискретная математика. Раздел: Логико-математические методы

Учебное пособие. — М.: МИСиС, 1997. — 93 с.Цель данного пособия — по возможности подробно осветить вопросы, связанные с доказательствами соотношений методом математической индукции (ММИ). Подробно изложены логические и математические предпосылки ММИ, описан сам метод и его разновидности, и указан класс задач, решение которых этим методом наиболее целесообразно. Решение некоторых из них детально изложено. В качестве иллюстраций к применению ММИ подробно разобраны задачи из различных разделов математики. Поэтому пособие может оказаться полезным при чтении таких разделов математических и общетеоретических курсов как, например, "Алгебра" (раздел: комбинаторика), "Лингвистические основы информатики" (раздел: элементы семиотики), "Теории информации" (раздел: алфавитное кодирование), "Информатика" (раздел: основы логической теории алгоритмов). Предназначено для студентов специальностей 002202 и 000719.Введение.
Логические основы принципа математической индукции.
О понятиях "натуральное число" и "натуральный ряд".
Естественный порядок на натуральном ряде.
Перенос естественного порядка на непустые подмножества натурального ряда. Наименьший элемент подмножества.
Принцип полной упорядоченности натурального ряда.
Принцип наименьшего числа.
Описание метода математической индукции.
Принцип математической индукции.
Эквивалентность принципов полной упорядоченности и математической индукции.
Характеристики метода математической индукции.
О разновидностях метода математической индукции.
Индукция, начиная с m.
Возвратная индукция.
Метод бесконечного спуска.
Индукция, ограниченная интервалом.
Индукция спуска.
Индукция с кратным базисом.
Индукция по двум переменным.
О некоторых классах задач, решаемых методом математической индукции.
Этапы решения задачи.
Задачи, связанные с установлением свойств термов.
Задачи построения термов, находящихся с фиксированным термом в заданном отношении.
Задачи, решение которых направлено на установление логических связей между свойствами термов и отношениями между ними.
Ограниченность метода математической индукции.
Упражнения.
Задачи на выявление свойств термов.
Задачи на построение термов, синонимичных заданному.
Задачи на установление и доказательство неравенств.
Задачи, связанные с установлением рекуррентных зависимостей и выявлением явных выражений для термов, заданных рекуррентно.
Задачи на установление логических связей между свойствами термов и отношениями между ними.
Примечания.
Литература.