- •Г.С. Розаренов, в.А. Шаруда дискретная математика Учебное пособие
- •Воронеж 2008
- •Воронеж 2008
- •Введение
- •1. Множества
- •1.1. Основные понятия
- •Упражнения
- •1.2. Операции над множествами
- •Упражнения
- •1.3. Диаграммы Венна
- •Упражнения
- •1.4. Доказательства
- •Упражнения
- •1.5. Векторы, прямые произведения, проекции векторов
- •Упражнения.
- •2. Алгебра логики
- •2.1. Функции алгебры логики
- •2.2. Формулы. Реализация функций формулами
- •2.3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности
- •2.4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
- •2.5. Полнота и замкнутость
- •2.6. Проблема минимизации булевых функций
- •Упражнения.
- •2.7. Упрощение д.Н.Ф. Тупиковые (относительно упрощения) д.Н.Ф.
- •Упражнения.
- •3. Язык логики предикатов
- •3.1. Основные понятия логики предикатов
- •3.2. Истинные формулы и эквивалентные соотношения
- •Упражнения.
- •4. Теория графов
- •4.1.Основные понятия
- •Г раф изоморфен
- •4.2. Способы задания графов
- •Матрица инцидентности (ij)
- •4.3. Операции над частями графа
- •4.4. Маршруты, пути, цепи, циклы
- •4.5. Дерево и лес
- •4.6. Сети
- •Упражнения.
- •5. Введение в теорию алгоритмов
- •5.1. Предварительные обсуждения
- •5.2. Блок-схемы алгоритмов
- •5.3. Машины Тьюринга
- •5.4. Некоторые операции над машинами Тьюринга
- •5.5. Рекурсивные функции
- •6. Автоматы
- •6.1. Определение основных понятий
- •6.2. Изоморфизм и эквивалентность автоматов
- •6.3. Сети из автоматов
- •6.4. Синхронные сети
- •6.5. Программная реализация логических функций
- •Заключение
- •394026 Воронеж, Московский просп., 14
Заключение
Представленное учебное пособие не претендует на полноту рассмотрения всех направлений бурно развивающейся в настоящее время дискретной математики. Авторы лишь хотели ознакомить читателя, в рамках выделенного на изучение курса времени, с основными понятиями и подходами дисциплины. Предложенный материал может служить фундаментом для дальнейшего изучения как теоретических и прикладных вопросов дискретной математики в целом, так и отдельных ее направлений при изучении читателем специальных дисциплин.
Библиографический список
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергия, 1980. 344с.
Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2001. 384с.
Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2002. 240с.
Уилсон Р. Введение в теорию графов. – М.: Мир. 1977. 207с.
ОГЛАВЛЕНИЕ
|
Введение |
3 |
1 |
Множества |
4 |
1.1 |
Основные понятия |
4 |
1.2 |
Операции над множествами |
9 |
1.3 |
Диаграммы Венна |
13 |
1.4 |
Доказательства |
16 |
1.5 |
Векторы, прямые произведения, проекции векторов |
23 |
2. |
Алгебра логики |
30 |
2.1. |
Функции алгебры логики |
30 |
2.2. |
Формулы. Реализация функций формулами |
33 |
2.3. |
Эквивалентность формул. Свойства эквивалентности функций. Принцип двойственности. |
38 |
2.4. |
Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма. |
42 |
2.5. |
Полнота и замкнутость |
47 |
2.6. |
Проблема минимизации булевых функций |
49 |
2.7. |
Упрощение д.н.ф. Тупиковые (относительно упрощения) д.н.ф. |
53 |
3. |
Язык логики предикатов |
56 |
3.1. |
Основные понятия логики предикатов |
56 |
3.2. |
Истинные формулы и эквивалентные соотношения |
58 |
4. |
Теория графов |
62 |
4.1. |
Основные понятия |
62 |
4.2. |
Способы задания графов |
65 |
4.3. |
Операции над частями графа |
68 |
4.4. |
Маршруты, пути, цепи, циклы |
69 |
4.5. |
Дерево и лес |
71 |
4.6. |
Сети |
72 |
5. |
Введение в теорию алгоритмов |
75 |
5.1. |
Предварительные обсуждения |
75 |
5.2. |
Блок-схемы алгоритмов |
79 |
5.3. |
Машины Тьюринга |
81 |
5.4. |
Некоторые операции над машинами Тьюринга |
88 |
5.5. |
Рекурсивные функции |
89 |
6. |
Автоматы |
95 |
6.1. |
Определение основных понятий |
95 |
6.2. |
Изоморфизм и эквивалентность автоматов |
100 |
6.3. |
Сети из автоматов |
103 |
6.4. |
Синхронные сети |
103 |
6.5. |
Программная реализация логических функций |
108 |
|
Заключение |
112 |
|
|
|
|
Библиографический список |
113 |
Учебное издание
Розаренов Георгий Сергеевич
Шаруда Владимир Алексеевич
ДИСКРЕТНАЯ МАТЕМАТИКА
В авторской редакции
Компьютерный набор Н. Г. Розаренова.
Подписано к изданию 15.10.2008.
Уч.-изд. л. 5,8.
ГОУВПО «Воронежский государственный технический университет»