Введение

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

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

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

Вводная глава Метод математической индукции (мми) §1. Формулировки мми. Доказательство равенств

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

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

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

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

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

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

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