Просветов Г.И. Дискретная математика
.pdfПросветов Г. И. Менеджмент: Задачи и решения. М.: Издательство «Аль- фа-Пресс», 2009.
Просветов Г. И. Прогнозирование и планирование: Задачи и решения. 2-е изд. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Социологические исследования: Задачи и решения. М.: Издательство «Альфа-Пресс», 2009.
Просветов Г. И. Теория вероятностей и статистика для школьников: Задачи и решения. М.: Издательство «Альфа-Пресс», 2009.
Просветов Г. И. Управление запасами: Задачи и решения. М.: Издательство «Альфа-Пресс», 2009.
Просветов Г. И. Управление проектами: Задачи и решения. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Управление рисками: Задачи и решения. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Управленческие решения: Задачи и решения. М.: Издательство «Альфа-Пресс», 2009.
Просветов Г. И. Управленческий учет: Задачи и решения. 2-е изд. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Финансовый анализ: Задачи и решения. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Финансовый менеджмент: Задачи и решения. М.: Издательство «Альфа-Пресс», 2007.
Просветов Г. И. Финансы, денежное обращение и кредит: Задачи и решения. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Цены и ценообразование: Задачи и решения. М.: Издательство «Альфа-Пресс», 2007.
Просветов Г. И. Экономика и статистика труда: Задачи и решения. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Экономика предприятия: Задачи и решения. М.: Издательство «Альфа-Пресс», 2008.
Просветов Г. И. Экономический анализ: Задачи и решения. М.: Издательство «Альфа-Пресс», 2008.
Пухначев Ю. В., Попов Ю. П. Математика без формул. М.: Столетие, 1995.
Содержание
Предисловие ..................................................................................................... |
3 |
||
|
|
Р а з д е л I. |
|
|
|
МАТЕМАТИЧЕСКАЯ ЛОГИКА |
|
ГЛАВА 1. |
Множество ...................................................................................... |
6 |
|
ГЛАВА 2. |
Булевы функции .............................................................................. |
9 |
|
2.1. |
Высказывания ...................................................................................... |
9 |
|
2.2. Основные операции ............................................................................. |
9 |
||
2.3. Равносильные функции ....................................................................... |
11 |
||
2.4. Булевы функции от n переменных ...................................................... |
12 |
||
2.5. Формулы ............................................................................................... |
12 |
||
ГЛАВА 3. |
Нормальные формы ........................................................................ |
14 |
|
3.1. Совершенная дизъюнктивная нормальная форма ............................. |
14 |
||
3.2. Совершенная конъюнктивная нормальная форма ............................ |
15 |
||
ГЛАВА 4. |
Минимизация нормальных форм .................................................... |
16 |
|
4.1. Минимизация дизъюнктивных нормальных форм ............................ |
16 |
||
|
4.1.1. Импликант .................................................................................. |
16 |
|
|
4.1.2. Сокращенная ДНФ ..................................................................... |
17 |
|
|
4.1.3. Тупиковые и минимальные ДНФ .............................................. |
18 |
|
4.2. Минимизация конъюнктивных нормальных форм ........................... |
20 |
||
4.3. Минимизация в классе нормальных форм ......................................... |
21 |
||
ГЛАВА 5. |
Минимизация частично определенных функций ............................. |
22 |
|
ГЛАВА 6. |
Двойственные функции ................................................................... |
25 |
|
ГЛАВА 7. |
Классы функций, сохраняющих константу ..................................... |
28 |
|
7.1. |
Класс T0 ............................................................................................... |
28 |
|
7.2. |
Класс T1 ............................................................................................... |
28 |
|
ГЛАВА 8. |
Линейные функции .......................................................................... |
30 |
|
8.1. Полином Жегалкина ............................................................................ |
30 |
||
8.2. Класс линейных функций ................................................................... |
31 |
||
ГЛАВА 9. |
Монотонные функции ..................................................................... |
33 |
|
ГЛАВА 10. |
Теорема Поста ................................................................................. |
35 |
|
ГЛАВА 11. |
Контактные схемы .......................................................................... |
37 |
|
ГЛАВА 12. |
Исчисление высказываний .............................................................. |
39 |
|
12.1. Алфавит исчисления высказываний ................................................... |
39 |
||
12.2. Формулы и подформулы ...................................................................... |
39 |
235
12.3. Система аксиом исчисления высказываний ...................................... |
40 |
2.4. |
Обратное отношение ........................................................................... |
79 |
|||
12.4. Правила вывода .................................................................................... |
41 |
2.5. |
Композиция отношений ...................................................................... |
80 |
|||
12.5. Доказуемые формулы ........................................................................... |
41 |
2.6. |
Свойства отношений ........................................................................... |
80 |
|||
12.6. Производные правила вывода ............................................................. |
41 |
2.7. |
Отношение эквивалентности .............................................................. |
82 |
|||
12.7. Вывод из совокупности формул .......................................................... |
42 |
2.8. |
Классы эквивалентности ..................................................................... |
83 |
|||
12.8. Правила выводимости ......................................................................... |
43 |
ГЛАВА 3. Принцип математической индукции |
84 |
||||
12.9. Некоторые законы логики |
44 |
||||||
ГЛАВА 4. Делимость |
85 |
||||||
12.10. Связь между булевыми функциями и исчислением высказываний |
44 |
||||||
4.1. |
Делители |
85 |
|||||
12.11. Проблемы аксиоматического исчисления высказываний |
46 |
||||||
4.2. |
Деление с остатком |
85 |
|||||
ГЛАВА 13. Правила вывода и получение выводимых суждений |
47 |
||||||
4.3. |
Простые числа |
86 |
|||||
|
|
|
|
||||
ГЛАВА 14. Логика предикатов .......................................................................... |
50 |
4.4. |
Наибольший общий делитель ............................................................. |
86 |
|||
14.1. Одноместный предикат ....................................................................... |
50 |
4.5. |
Алгоритм Евклида ................................................................................ |
87 |
|||
14.2. Кванторные операции ......................................................................... |
51 |
4.6. |
Взаимно простые числа ....................................................................... |
88 |
|||
14.3. Алфавит логики предикатов ................................................................ |
52 |
4.7. |
Функция Эйлера .................................................................................. |
89 |
|||
14.4. Формулы логики предикатов .............................................................. |
52 |
4.8. Наименьшее общее кратное ................................................................ |
89 |
||||
14.5. Равносильные формулы ...................................................................... |
53 |
4.9. Решение уравнения ax + by = c в целых числах ................................. |
90 |
||||
14.6. Нормальные формы ............................................................................. |
54 |
ГЛАВА 5. Сравнения |
92 |
||||
|
14.6.1. Предваренная нормальная форма |
54 |
|||||
|
5.1. Классы вычетов по модулю n |
92 |
|||||
|
14.6.2. Стандартная форма Скулема |
54 |
|||||
|
5.2. |
Решение сравнений |
92 |
||||
14.7. Общезначимость и выполнимость формул |
55 |
||||||
5.3. |
Китайская теорема об остатках |
93 |
|||||
14.8. Проблема разрешимости в логике предикатов |
55 |
||||||
ГЛАВА 6. Многочлены |
95 |
||||||
ГЛАВА 15. Решение логических задач с помощью булевых функций |
56 |
||||||
6.1. |
Действия с многочленами |
95 |
|||||
|
|
|
|
||||
ГЛАВА 16. Алгоритм ......................................................................................... |
57 |
6.2. |
Схема Горнера ...................................................................................... |
96 |
|||
16.1. Что такое алгоритм? ............................................................................. |
57 |
ГЛАВА 7. Группы, кольца и поля |
98 |
||||
16.2. Основные свойства алгоритма |
57 |
||||||
7.1. |
Группы |
98 |
|||||
|
|
|
|
||||
ГЛАВА 17. Вычислимые функции ..................................................................... |
60 |
7.2. |
Кольца .................................................................................................. |
100 |
|||
17.1. Простейшие функции .......................................................................... |
60 |
7.3. Поля ...................................................................................................... |
101 |
||||
17.2. Суперпозиция функций ....................................................................... |
60 |
ГЛАВА 8. Подстановки |
102 |
||||
17.3. Схема примитивной рекурсии |
61 |
||||||
8.1. |
Определение подстановки |
102 |
|||||
17.4. Операция минимизации |
61 |
||||||
8.2. |
Произведение подстановок |
102 |
|||||
17.5. Тезис Черча |
62 |
||||||
8.3. |
Обратная подстановка |
103 |
|||||
|
|
|
|
||||
ГЛАВА 18. Машина Тьюринга ........................................................................... |
63 |
8.4. |
Симметрическая группа ...................................................................... |
104 |
|||
ГЛАВА 19. Нормальные алгоритмы Маркова |
65 |
8.5. |
Циклы ................................................................................................... |
105 |
|||
8.6. |
Знак подстановки |
105 |
|||||
Ответы |
|
|
66 |
||||
.............................................................................................................. |
|
ГЛАВА 9. Рекуррентные отношения |
107 |
||||
Программа учебного курса «Математическая логика» |
67 |
||||||
|
|
|
|||||
Задачи для контрольной работы по курсу «Математическая логика» ........... |
70 |
ГЛАВА 10. Кодирование .................................................................................... |
109 |
||||
|
|
|
|
10.1. Блочный двоичный (m, n)-код ............................................................ |
109 |
||
|
|
Р а з д е л II. |
|
10.2. Код с проверкой четности ................................................................... |
109 |
||
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ И ТЕОРИЯ КОДИРОВАНИЯ |
|
10.3. Код с тройным повторением ............................................................... |
110 |
||||
|
|
|
|
10.4. Расстояние Хемминга .......................................................................... |
111 |
||
ГЛАВА 1. |
Отображения ................................................................................... |
74 |
ГЛАВА 11. Коды Хемминга |
112 |
|||
|
|
|
|
||||
ГЛАВА 2. |
Отношения ...................................................................................... |
77 |
11.1. Проверочная матрица кода Хемминга ................................................ |
112 |
|||
2.1. Декартово произведение множеств ..................................................... |
77 |
11.2. Порождающая матрица кода Хемминга ............................................. |
113 |
||||
2.2. |
Отношение множеств .......................................................................... |
77 |
11.3. Кодирование ........................................................................................ |
113 |
|||
2.3. |
Матрица отношения ............................................................................ |
78 |
11.4. Исправление ошибок ........................................................................... |
114 |
236 |
237 |
ГЛАВА 12. Код Хаффмана ................................................................................ |
116 |
|
ГЛАВА 13. Система шифрования с открытым ключом ..................................... |
119 |
|
Ответы |
.............................................................................................................. |
120 |
Программа учебного курса «Алгебраические системы и теория кодирования» |
121 |
|
Задачи для контрольной работы по курсу «Алгебраические системы и тео- |
|
|
рия кодирования» ............................................................................................. |
123 |
|
|
Р а з д е л III. |
|
|
КОМБИНАТОРИКА |
|
ГЛАВА 1. Размещения, перестановки, сочетания ........................................... |
128 |
|
1.1. |
Размещения .......................................................................................... |
128 |
1.2. |
Перестановки ....................................................................................... |
129 |
1.3. |
Сочетания ............................................................................................. |
129 |
ГЛАВА 2. Повторения ..................................................................................... |
130 |
|
2.1. |
Перестановки с повторениями ............................................................ |
130 |
2.2. |
Сочетания с повторениями ................................................................. |
130 |
2.3. Размещения с повторениями .............................................................. |
131 |
|
ГЛАВА 3. Бином Ньютона ............................................................................... |
132 |
|
3.1. Формула бинома Ньютона .................................................................. |
132 |
|
3.2. Биномиальные коэффициенты ........................................................... |
132 |
|
3.3. |
Треугольник Паскаля ........................................................................... |
133 |
ГЛАВА 4. Формула включений и исключений ................................................. |
134 |
|
ГЛАВА 5. Арифметические треугольники ........................................................ |
136 |
|
5.1. |
Треугольник Люка ................................................................................ |
136 |
5.2. |
Треугольник Фибоначчи ...................................................................... |
137 |
5.3. |
Треугольник Каталана .......................................................................... |
137 |
5.4. |
Треугольник Эйлера ............................................................................. |
138 |
ГЛАВА 6. Производящие функции .................................................................. |
139 |
|
6.1. Производящие функции и решение рекуррентных отношений ....... |
139 |
|
ГЛАВА 7. Производящие функции и комбинаторные подсчеты ...................... |
143 |
|
ГЛАВА 8. Экспоненциальные производящие функции .................................... |
144 |
|
Ответы |
.............................................................................................................. |
145 |
Программа учебного курса «Комбинаторика» ................................................ |
146 |
|
Задачи для контрольной работы по курсу «Комбинаторика» ........................ |
147 |
|
|
Р а з д е л IV. |
|
|
ТЕОРИЯ ГРАФОВ |
|
ГЛАВА 1. Основные понятия теории графов ................................................... |
150 |
|
ГЛАВА 2. Задача определения кратчайшего пути ........................................... |
157 |
|
2.1. |
Метод присвоения меток ..................................................................... |
157 |
2.2. Задача о кратчайшем пути между двумя пунктами ............................ |
161 |
|
ГЛАВА 3. Построение коммуникационной сети минимальной длины ............. |
163 |
ГЛАВА 4. Задача определения максимального потока .................................... |
166 |
|
ГЛАВА 5. Задача единого среднего ................................................................. |
170 |
|
ГЛАВА 6. Задача охвата .................................................................................. |
172 |
|
ГЛАВА 7. Задача коммивояжера. Метод ветвей и границ ............................... |
173 |
|
ГЛАВА 8. Транспортная задача в сетевой постановке ..................................... |
179 |
|
8.1. |
Что такое транспортная сеть ............................................................... |
179 |
8.2. |
Первоначальный план поставок ......................................................... |
180 |
8.3. |
Проверка плана поставок на оптимальность ...................................... |
181 |
8.4. |
Улучшение плана поставок .................................................................. |
183 |
8.5. |
Открытая модель .................................................................................. |
186 |
|
8.5.1. Фиктивный потребитель ........................................................... |
186 |
|
8.5.2. Фиктивный поставщик .............................................................. |
187 |
ГЛАВА 9. Дерево решений ............................................................................... |
189 |
|
ГЛАВА 10. Сетевое планирование и управление ............................................... |
195 |
|
10.1. Основные понятия ............................................................................... |
195 |
|
10.2. Правила построения сетевых графиков .............................................. |
196 |
|
10.3. Метод критического пути .................................................................... |
196 |
|
10.4. Управление проектами с неопределенным временем выполнения |
|
|
|
работ ..................................................................................................... |
200 |
10.5. Стоимость проекта. Оптимизация сетевого графика ......................... |
203 |
|
10.6. График Ганта ......................................................................................... |
206 |
|
10.7. Распределение ресурсов. Графики ресурсов ....................................... |
207 |
|
10.8. Параметры работ .................................................................................. |
210 |
|
ГЛАВА 11. Балансировка линий сборки ............................................................ |
213 |
|
ГЛАВА 12. Задача о назначениях ...................................................................... |
216 |
|
12.1. Минимизация целевой функции ........................................................ |
216 |
|
12.2. Максимизация целевой функции ....................................................... |
219 |
|
ГЛАВА 13. Эйлеров цикл .................................................................................. |
220 |
|
ГЛАВА 14. Раскраска графов ............................................................................ |
222 |
|
Ответы |
.............................................................................................................. |
223 |
Программа учебного курса «Теория графов» .................................................. |
225 |
|
Задачи для контрольной работы по курсу «Теория графов» .......................... |
227 |
|
Литература ........................................................................................................ |
233 |
238