Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Южно-Уральский государственный университет

Кафедра автоматики и управления

Барбасова Т.А.

Дискретная математика

Конспект лекций

Челябинск

Издательство ЮУрГУ

2010

Барбасова Т.А. Дискретная математика: Конспект лекций. – Челябинск: ЮУрГУ, 2010. – 78с.

Конспект лекций предназначен для студентов очной и заочной форм обучения специальности 220200 “Управление в технических системах”.

Рецензент: к.т.н., доц. Радкевич И.А.

Содержание

Введение 4

1. Введение в теорию множеств 5

1.1. Множества 5

1.2. Отношения 13

2. Теория графов 18

2.1. Основные понятия 18

2.2. Способы задания графов 23

2.4. Сети и их свойства 25

3. Введение в математическую логику 35

3.1. Логика высказываний 36

3.2. Логика предикатов 56

4. Прикладная теория алгоритмов 61

4.1. Алгоритм: определение и основные свойства 61

4.2. Реализация управляющих алгоритмов 62

4.3. Формализация понятия алгоритма 62

4.4. Машина Тьюринга 65

4.5. Свойства машины Тьюринга 68

4.6. Реализация машины Тьюринга 69

4.7. Формальные системы и алгоритмы. 71

5. Комбинаторный анализ 72

5.1. Основное правило комбинаторики 72

5.2. Правило суммы 73

5.3. Правило прямого произведения 74

5.4. Перестановки 74

5.5. Число различных k-элементарных подмножеств n-элементарного множества 75

5.6. Число подмножеств данного множества 77

5.7. Размещение элементов множества 78

5.7. Размещения с повторениями 79

5.8. Размещения без повторений 80

5.9. Комбинации элементов с повторениями 80

6. Языки и грамматики 84

6.1. Основные определения 84

6.2. Формальные грамматики 85

6.3. Грамматики с ограничениями на правила 87

6.4. Способы записи синтаксиса языка 89

Список рекомендуемой литературы 93

Введение

Дискретная математика – бурно развивающаяся в 21 веке ветвь математики. Ее роль и место определяются в основном тремя факторами:

- дискретную математику можно рассматривать как теоретические основы компьютерной математики,

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

- язык дискретной математики чрезвычайно удобен и стал фактически языком всей современной математики.

Математика как наука, естественно, от рождения делится на дискретную и континуальную математику. Что мы относим к континуальной математике? Все, что явно или неявно содержит идеи теории пределов и непрерывности. Все остальное – дискретная математика (т.е. арифметика, алгебра. Теория множеств и общая теория отображений, математическая логика, комбинаторный анализ, теория алгоритмов и многое другое).

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

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

В учебный предмет «Дискретная математика» включает только тот круг вопросов, который можно озаглавить «Теоретические основы компьютерной математики».