Специальная математика (стр. 1 )

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

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

СПЕЦИАЛЬНАЯ МАТЕМАТИКА

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

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

Пермь, 2001г.

Оглавление

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

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

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

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

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

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

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

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

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. Подрешетки........................................................................................................ 17

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.12. Клика........................................................................................................................ 61

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

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

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

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

5.4. Группа Диэдра (D3).................................................................................................. 65

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

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

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

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

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

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

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

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

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

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

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

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