Специальная математика

Пермский Государственный Технический Университет

А. Е. СОЛОВЬЕВ

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

для студентов специальности АСУ

Пермь, 2001г.

Оглавление

Введение......................................................................................................................... 5

1. Теория множеств................................................................................................................ 6

1.1 Понятие множества...................................................................................................... 6

1.2. Операции над множествами...................................................................................... 7

1.3. Диаграммы Эйлера - Венна....................................................................................... 7

1.4. Алгебра множеств....................................................................................................... 8

1.5. Кортеж. График.......................................................................................................... 9

1.6. Соответствия............................................................................................................. 11

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

1.7.1 Отношение эквивалентности............................................................................ 13

1.7.2. Отношения порядка........................................................................................... 14

1.7.3. Морфизмы........................................................................................................... 14

1.8. Решетки...................................................................................................................... 15

1.8.1. Диаграммы Хассе............................................................................................... 15

1.8.2. Понятие решетки................................................................................................ 15

1.8.3. Алгебраическое представление решеток. Булевы решетки.......................... 16

1.8.4. Подрешетки........................................................................................................ 18

1.8.5. Морфизмы решеток............................................................................................ 18

1.9. Мощность множества............................................................................................... 18

1.9.1. Понятие мощности............................................................................................. 18

1.9.2. Аксиоматика Пеано.......................................................................................... 18

1.9.3. Сравнение мощностей....................................................................................... 19

1.9.4. Мощность множества R.. Теорема Кантора.................................................... 20

1.9.5. Арифметика бесконечного................................................................................ 20

1.9.6. Противопоставление системного и................................................................. 21

теоретико-множественного подходов................................................................... 21

2. Математическая логика................................................................................................... 21

2.1. Логика высказываний.............................................................................................. 21

2.1.1. Операции над высказываниями....................................................................... 21

2.1.2. Построение и анализ сложных высказываний............................................... 22

2.1.3. Алгебра высказываний...................................................................................... 24

2.1.4. Формы представления высказываний............................................................. 24

2.1.5. Преобразование высказываний........................................................................ 25

2.1.6. Минимизация высказываний методом Квайна.............................................. 26

2.1.7. Минимизация с помощью карт Вейча............................................................. 28

2.1.8. Функциональная полнота................................................................................. 29

2.2. Логика предикатов.................................................................................................... 30

2.2.1. Основные равносильности для предикатов.................................................... 31

2.2.2. Получение дизъюнктов..................................................................................... 31

2.3. Аксиоматические теории........................................................................................ 32

2.3.1. Аксиоматическая теория исчисления высказываний.................................... 32

2.3.2. Непротиворечивость и полнота аксиоматической теории исчисления высказываний 33

2.4. Аксиоматические теории первого порядка............................................................ 34

2.5. Метод резолюций...................................................................................................... 35

2.6. Система Генцена....................................................................................................... 37

2.7. Система Аристотеля................................................................................................. 38

2.8. Примеры неклассических логик............................................................................. 41

3. Теория Автоматов............................................................................................................ 43

3.1. Понятие автомата...................................................................................................... 43

3.2. Примеры автоматов.................................................................................................. 43

3.3. Минимизация автоматов.......................................................................................... 45

3.4. Особенности минимизации автомата Мура........................................................... 46

3.5. Переход от автомата Мура к автомату Мили и наоборот..................................... 47

4.Теория графов.................................................................................................................... 48

4.1. Понятие графа........................................................................................................... 48

4.2. Теорема Эйлера......................................................................................................... 51

4.3. Полные графы и деревья.......................................................................................... 53

4.4. Деревья....................................................................................................................... 54

4.5. Алгоритм Краскала................................................................................................... 55

4.6. Планарные графы...................................................................................................... 56

4.7. Задача о 4 красках..................................................................................................... 57

4.8. Определение путей в графе..................................................................................... 58

4.9. Приведение графа к ярусно-параллельной форме................................................. 59

4.10. Внутренняя устойчивость графа........................................................................... 60

4.11. Множество внешней устойчивости. Ядро графа................................................. 61

4.12. Клика........................................................................................................................ 62

5. Теория групп..................................................................................................................... 63

5.1. Понятие группы........................................................................................................ 63

5.2. Морфизмы групп....................................................................................................... 64

5.3. Инвариантные (нормальные) подгруппы.............................................................. 65

5.4. Группа Диэдра (D₃).................................................................................................. 66

5.5. Смежные классы....................................................................................................... 67

5.6. Фактор-группы.......................................................................................................... 67

5.7. Группа Клейна четвертой степени.......................................................................... 68

6. Теория алгоритмов........................................................................................................... 69

6.1. Понятие алгоритма................................................................................................... 69

6.2. Конкретизация понятия алгоритма......................................................................... 69

6.3. Сложность вычислений............................................................................................ 70

6.4. Машины Тьюринга................................................................................................... 71

6.5. Нормальные алгорифмы Маркова........................................................................... 71

6.6. Рекурсивные функции.............................................................................................. 73

6.7. l-исчисление............................................................................................................. 74

7. Формальные грамматики................................................................................................ 76

7.1. Понятие формальной грамматики........................................................................... 76

7.2. Деревья вывода.......................................................................................................... 77

7.3. Классификация языков по Хомскому..................................................................... 78

7.4. Распознающие автоматы.......................................................................................... 79

7.5. Понятие транслятора................................................................................................ 80

7.6. Основные функции компилятора........................................................................... 81

Лексический анализ..................................................................................................... 81

7.7. Переход от недетерминированного распознающего автомата к......................... 82

детерминированному................................................................................................... 82

7.8. Переход от праволинейной грамматики к автоматной........................................ 82

7.9. LEX............................................................................................................................. 83

7.10. Детерминированные автоматы с магазинной памятью (МП-автоматы).......... 85

7.11. Транслирующие грамматики................................................................................. 87

7.12. S и q - грамматики................................................................................................... 87

7.13. LL(1) - грамматики.................................................................................................. 88

(left - leftmost)............................................................................................................... 88

7.14. Метод рекурсивного спуска................................................................................... 89

7.15. LR - грамматики...................................................................................................... 90

(left - rightmost)............................................................................................................. 90

7.16. Функции предшествования................................................................................... 93

7.17. Атрибутные грамматики........................................................................................ 94

7.18. YACC....................................................................................................................... 95

7.19. Область действия и передача параметров............................................................ 96

7.20. Генерация выходного текста. Польская инверсная запись................................ 97

7.21. Оптимизация программ.......................................................................................... 99

8. Функциональное программирование.......................................................................... 100

9. Логическое программирование.................................................................................... 104

Язык Пролог................................................................................................................... 104

10. Объектно-ориентированное программирование...................................................... 105

Заключение......................................................................................................................... 108

Литература.......................................................................................................................... 109