Читать онлайн «Дискретная математика: Алгоритмы и программы»

МАТЕМАТИКА И ПРИКЛАДНАЯ МАТЕМАТИКА Б. Н. ИВАНОВ ДИСКРЕТНАЯ МАТЕМАТИКА АЛГОРИТМЫ И ПРОГРАММЫ ПОЛНЫЙ КУРС МОСКВА ФИЗМАТЛИТ ® 2007 УДК 519(075. 8)+681. 142. 2 ББК 32. 973. 3 И 20 И в а н о в Б. Н. Дискретная математика. Алгоритмы и про- граммы. Полный курс. — М. : ФИЗМАТЛИТ, 2007. — 408 с. — ISBN 978-5-9221-0787-7. Учебное пособие по курсу дискретной математики. Изложение носит достаточно полный и строгий характер. Теоретические основы курса сопровождаются практически значимыми алгоритмами, реали- зованными в конкретных компьютерных программах. Книгу можно рассматривать в качестве хорошего справочника методов и алгоритмов дискретной математики, широко применяемых в практическом програм- мировании. Пособие рассчитано на студентов специальностей, учебные планы которых предполагают изучение каких-либо разделов курса дискретной математики, в первую очередь на математиков-прикладников, а также программистов, занятых разработкой прикладного программного обеспечения. Рекомендовано Дальневосточным региональным учебно-методи- ческим центром (УМО) в качестве учебного пособия для студентов технических специальностей вузов региона. Рецензенты: кафедра математического моделирования и информатики ДВГТУ, зав. кафедрой доктор физико–математических наук, профессор А. А. Буренин; доктор физико–математических наук, профессор В. В. Катрахов. c ФИЗМАТЛИТ, 2007 ISBN 978-5-9221-0787-7 c Б. Н. Иванов, 2007  ОГЛАВЛЕНИЕ Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Г л а в а 1. Введение в математическую логику . . . . . . . . . . . . 9 § 1. 1. Системы счисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1. 1. 1. Системы счисления . . . . . . . . . . . . . . . . . . . . . . . . 9 1. 1. 2. Смешанные системы счисления . . . . . . . . . . . . . . . 12 1. 1. 3. Задача оптимального кодирования . . . . . . . . . . . . . 14 1. 1. 4. Cистемы счисления с основаниями 2, 8 и 16 . . . . . 15 § 1. 2. Введение в булеву алгебру . . . . . . . . . . . . . . . . . . . . . . . 18 1. 2. 1. Булевы функции . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1. 2. 2. Формулы, реализация функций формулами . . . . . . 22 1. 2. 3. Замена переменных и суперпозиция . . . . . . . . . . . . 24 1. 2. 4. Существенные и фиктивные переменные . . . . . . . . 26 1. 2. 5. Интерпретация булевых функций . . . . . . . . . . . . . . 26 1. 2. 6. Алгебра Буля . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1. 2. 7. Совершенные дизъюнктивная и конъюнктивная нор- мальные формы (СДНФ и СКНФ) булевых функ- ций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 § 1. 3.