Сервер Методического Обеспечения вгуэс

  1   2   3   4   5   6   7   8   9   ...   22

• Введение

Предлагаемое учебное пособие представляет собой первую часть курса лекций по дискретной математике. Кроме этой части предполагается издание двух частей теоретического материала. Вторая часть будет посвящена дискретному анализу, логике предикатов и теории кодирования и криптографии, в частности, кодированию экономической информации. Третья часть будет посвящена теории графов и ее приложению в экономике и управлении, в частности, сетевому планированию и управлению дискретными системами. Параллельно изданию теоретического материала планируется и разработка и издание сборников задач, в частности, заданий для контрольных работ и индивидуальных домашних заданий.

Предполагаемые пособие и сборник задач создаются на базе курсов лекций по логике, теории графов и дискретной математике, которые читались ряд лет студентам разных специальностей и факультетов в Дальневосточном государственном техническом университете, Дальневосточном государственном университете, Владивостокском университете экономики и сервиса.

Первая, предлагаемая, часть посвящена по сути дела построению современного математического языка – математической логике и теории множеств. Более подробное внимание уделяется конечным объектам – методу математической индукции, комбинаторике. Здесь также можно познакомиться с алгеброй высказываний, общей теорией множеств и предикатов, с теорией бесконечных множеств. Пособие может оказаться полезным всем, в том числе и студентам, кто желает или кому необходимо познакомиться со всем курсом дискретной математики или с некоторыми ее приложениями.

• ВВОДНАЯ ГЛАВА
  Метод математической индукции (ММИ)

• §1. Формулировки ММИ. Доказательство равенств

Дискретная математика – это цикл математических наук, изу-чающих свойства конечных множеств. В настоящее время эти науки бурно развиваются, что определяется тремя очень важными факторами:

1) развитием компьютерной техники и компьютерных наук, которые базируются, а по существу являются продолжением дискретной математики;

2) запросами различных прикладных наук – теории управления, экономики, оптимизации и многих, многих других;

3) логикой внутреннего развития этих наук: появлением новых разделов, глубоких интересных проблем, развитием мощных методов их решения.

Все это и предопределило тот факт, что различные разделы дискретной математики все настойчивее внедряются не только в университеты, но и в технические и экономические и даже в гуманитарные вузы.

ММИ лежит в основе доказательства огромного числа теорем в различных разделах дискретной математики. Подчеркивая это обстоятельство, мы и начнем изложение курса с этого метода. Приведем несколько формулировок ММИ. Все они равнозначны, но доказательство этого факта из-за его сложности мы опустим, чтобы не отпугивать читателя сразу же трудностями технического порядка.

Буквой в дальнейшем мы будем обозначать множество натуральных чисел:

 – расширенное множество натуральных чисел, то есть

Пусть обозначает некоторое свойство натуральных чисел.

1. Теорема 1 (стандартный ММИ)

Пусть свойство верно при и пусть из истинности при следует его истинность при . Тогда свойство верно для любого .

1. Пример 1

Доказать, что

. (1)

• Доказательство

Метод математической индукции будем оформлять по следующей схеме.

1. Базис индукции: проверим равенство при . Левая часть (ЛЧ)=1, правая часть (ПЧ)= . Равенство при , то есть базис индукции, выполняется.

2. Индуктивное предположение: допустим, равенство (1) верно при , то есть допустим, что