Просветов Г.И. Дискретная математика

Просветов Г. И. Менеджмент: Задачи и решения. М.: Издательство «Аль- фа-Пресс», 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