ВВЕДЕНИЕ. Дискретная математика – часть математики, которая зародилась в глубокой древности

Дискретная математика – часть математики, которая зародилась в глубокой древности. Главной её спецификой является дискретность, т.е. антипод непрерывности.

В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в середине XX века в связи с внедрением ЭВМ.

Научно-технический прогресс XX века поставил перед дискретной математикой проблему изучения сложных управляющих систем, в связи с чем в дискретной математике появились новые разделы, такие как теория функциональных систем, теория графов и сетей, теория кодирования, комбинаторный анализ, целочисленное программирование, криптография и т.п. Теория функциональных систем включает в себя алгебру логики; конечнозначную логику; ограниченно-детерминированные (автоматные) функции; вычислимые функции.

Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования. Главной задачей курса дискретной математики является обучение методам и мышлению, характерным для дискретной математики. Материал курса дискретной математики подобран таким образом, чтобы сократить число необходимых понятий до минимума и, с другой стороны, дать небольшое количество (10–15) серьезных теорем с непохожими доказательствами, а также познакомить с применениями понятия алгоритма, владение которым особенно важно для специалистов в области прикладной математики.

В основу данного курса дискретной математики положен курс, который впервые был прочитан С.В. Яблонским (научным руководителем лектора данного курса) на механико-математическом факультете МГУ имени М.В. Ломоносова в 1964 году, с определенными изменениями, связанными с течением времени, бурным развитием вычислительной техники и появлением новых и новых специальностей, для которых дискретная математика является обязательным курсом.

В рабочую программу курса дискретной математики включены следующие разделы:

1. Элементы теории множеств.

2. Элементы комбинаторики.

3. Алгебра логики.

4. Синтез управляющих систем.

5. Теория графов.

6. Элементы математической логики.

7. Конечнозначная логика.

8. Ограниченно-детерминированные (автоматные) функции.

9. Вычислимые функции.

10. Теория кодирования.

11. Криптография.

Первые пять разделов читаются в первом семестре, остальные разделы – во втором.

Раздел 1
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ