Дискретная математика & математическая логика
..pdfМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Пермский национальный исследовательский политехнический университет»
С.Ф. Тюрин, В.М. Ланцов
ДИСКРЕТНАЯ МАТЕМАТИКА & МАТЕМАТИЧЕСКАЯ ЛОГИКА
Рекомендовано Учебно-методическим объединением по образованию в области инфокоммуникационных технологий и систем связи в качестве учебного пособия для студентов
высших учебных заведений, обучающихся по направлению подготовки 210700 – Инфокоммуникационные технологии и системы связи, квалификации (степени)
«бакалавр» и «магистр»
Издательство Пермского национального исследовательского
политехнического университета
2013
УДК 621.399 Т98
Рецензенты:
доктор технических наук, профессор В.А. Твердохлебов (Институт точной механики и проблем управления РАН, г. Саратов); доктор технических наук, профессор А.В. Частиков
(Вятский государственный университет, г. Киров)
Тюрин, С.Ф.
Т98 Дискретная математика & математическая логика : учеб. пособие / C.Ф. Тюрин, В.М. Ланцов. – Пермь : Изд-во Перм. нац. исслед. политехн. ун-та, 2013. – 271 с.
ISBN 978-5-398-00964-4
Изложен материал по дискретной математике и математической логике, отсутствующийв ранее изданныхавторами учебных пособиях.
Предназначено для студентов, изучающих дисциплины «Дискретная математика», «Математическая логика и теория алгоритмов» и «Исследование операций». Может быть полезно магистрам и аспирантам при проведении научных исследований.
УДК 621.399
ISBN 978-5-398-00964-4 |
© ПНИПУ, 2013 |
ОГЛАВЛЕНИЕ |
|
ПРЕДИСЛОВИЕ........................................................................................................ |
5 |
1. ИСТОРИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ |
|
ИДИСКРЕТНОЙ МАТЕМАТИКИ..................................................................... |
6 |
2. КОМБИНАТОРИКА.......................................................................................... |
39 |
2.1. Разбиения и числа Стирлинга.......................................................... |
39 |
2.2. Задача кавалера Де Мере.................................................................. |
41 |
2.3. Задача ландскнехта........................................................................... |
43 |
2.4. Принцип включения-исключения и рекуррентные |
|
соотношения..................................................................................... |
45 |
2.5. Задачи о разбиении плоскости и пространства.............................. |
49 |
2.6. Обобщённый факториал и числа Каталана.................................... |
55 |
2.7. Латинские прямоугольники и квадраты......................................... |
61 |
2.8. Блок-схемы и конечные проективные плоскости......................... |
68 |
2.9. Дополнительные виды факториалов............................................... |
71 |
3. ТЕОРИЯ ГРАФОВ.............................................................................................. |
72 |
3.1. Трансверсаль и теорема о свадьбах. |
|
Трансверсальное покрытие............................................................. |
72 |
3.2. Множества внутренней и внешней устойчивости орграфа........... |
76 |
3.3. Транспортная сеть и задача нахождения |
|
максимального потока..................................................................... |
79 |
3.4. Транспортная задача......................................................................... |
84 |
3.5. Задача о знакомствах и теория Рамсея........................................... |
91 |
3.6. Покрытия, независимость, связность.............................................. |
96 |
3.7. Эйлеровы и гамильтоновы графы................................................... |
99 |
3.8. Анализ графа марковской цепи..................................................... |
103 |
3.9. Перечисление графов ..................................................................... |
113 |
4. ОПТИМИЗАЦИЯ.............................................................................................. |
119 |
4.1. Полный перебор.............................................................................. |
120 |
4.2. Метод ветвей и границ................................................................... |
122 |
4.3. Линейное программирование........................................................ |
126 |
4.4. Целочисленное программирование............................................... |
137 |
4.5. Генетический алгоритм оптимизации .......................................... |
146 |
4.6. Парето-оптимизация....................................................................... |
151 |
4.7. Синтез структурной схемы надёжности системы |
|
в соответствии с методикой оптимального резервирования |
|
на основе процедуры наискорейшего спуска............................. |
152 |
3
5. ТЕОРИЯ АВТОМАТОВ.................................................................................. |
166 |
5.1. Эквивалентность автоматов. Теорема Мура............................... |
168 |
5.2. Минимизация конечных автоматов ............................................. |
175 |
5.3. Автоматы Мили и Мура................................................................ |
182 |
5.4. Реактивные системы...................................................................... |
184 |
5.5. Коллективы автоматов .................................................................. |
186 |
6. СИНТЕЗЛОГИЧЕСКИХ АВТОМАТОВ.................................................. |
195 |
6.1. Абстрактный синтез последовательностного автомата |
|
при недетерминированной входной последовательности......... |
195 |
6.2. Абстрактный синтез последовательностного автомата |
|
при детерминированной входной последовательности............. |
200 |
6.3. Синтез синхронного автомата ...................................................... |
203 |
6.3.1. Синтез счётчика................................................................... |
203 |
6.3.2. Синтез автомата-распознавателя |
|
с повторяющимися символами........................................... |
205 |
7. ЭЛЕМЕНТЫ ТЕОРИИИГР.......................................................................... |
209 |
8. АЛГОРИТМЫ УПОРЯДОЧЕННОГО ПЕРЕБОРА.............................. |
218 |
9. СЛОЖНОСТЬАЛГОРИТМОВ.................................................................... |
238 |
10. ПРИМЕРЫ ПРОГРАММИРОВАНИЯ |
|
АБСТРАКТНЫХ МАШИН........................................................................... |
245 |
10.1. Программирование машины Тьюринга..................................... |
245 |
10.2. Программирование машины Поста............................................ |
246 |
10.3. Вычисление логической функции.............................................. |
247 |
10.4. Задача распознавания последовательности символов |
|
на ленте.......................................................................................... |
250 |
11. ДОПОЛНИТЕЛЬНЫЙ МАТЕРИАЛ........................................................ |
253 |
11.1. Математическая логика. Доказательство правильности |
|
программ....................................................................................... |
253 |
11.2.Особенности построения модифицированного дерева опровержения с предположением, содержащим квантор
общности....................................................................................... |
255 |
11.3. Многозначные переключательные функции |
|
и их функциональная полнота.................................................... |
257 |
11.4. Реляционная алгебра и реляционное исчисление..................... |
260 |
12. ЗАДАЧИ............................................................................................................. |
267 |
СПИСОК ЛИТЕРАТУРЫ.................................................................................. |
269 |
4 |
|
ПРЕДИСЛОВИЕ
Учебное пособие предполагается использовать совместно с книгами: Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006; Тюрин С.Ф., Аляев Ю.А. Дискретная математика: практическая дискретная математика и математическая логика. – М.: Финансы и статистика, 2010; Тюрин С.Ф. Дискретная математика и математическая логика: учеб. пособие. – Пермь: Изд-во Перм. гос. техн. ун-та, 2009.
Наше издание в основном содержит материал, отсутствующий в ранее изданных учебных пособиях.
5
1.ИСТОРИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ
ИДИСКРЕТНОЙ МАТЕМАТИКИ
До конца XX века дискретная математика не выделялась как отдельная дисциплина, а была специальным разделом математики. Когда один из авторов этой книги еще в конце 60-х, будучи старшеклассником, посещал так называемую ШЮМ – Школу юных математиков Пермского ордена Трудового красного знамени Государственного университета имени А.М. Горького (кто сейчас помнит об этом названии!), никто не употреблял словосочетание «дискретная математика». Называли разделы математики вообще – « теория множеств», «теория групп», «алгебраические системы» и пр.
Математическая логика считалась разделом дискретной математики. Название дисциплины «Дискретная математика», вероятнее всего, стало употребляться с середины 70-х годов. Потом появилась и соответствующая кафедра МГУ (её возглавил О.Б. Лупанов). В середине 90-х годов XX века, когда стали формироваться первые государственные образовательные стандарты, наверное,
ипроизошло разделение на две разные дисциплины: «Дискретная математика» и «Математическая логика и теория алгоритмов». Причём вначале изучается дискретная математика, а в следующем семестре – математическая логика и теория алгоритмов. Тем не менее бывает очень сложно разделить некоторые темы между двумя дисциплинами: «Булевы функции», они же «Логические функции», «Автоматы», которые используются и в теории алгоритмов, «Языки
играмматики» – этот раздел нужен и для теории автоматов, и для теории алгоритмов, т.е. это разделение, в общем-то, условное. Рассмотрим историю дискретной математики и математической логики в персоналиях.
6
Античность
Исторический экскурс следует начать с Сократа. В начале была логика, причём логика как раздел философии. Впрочем, тогда вся наука была единой и называлась философией. Да и сейчас на Западе учёные получают учёную степень «Доктор философии» – Ph.D. Только более чем через две тысячи лет логика трансформировалась в математическую логику.
Итак, Сократ – рис. 1.1 (др.-греч. Σωκράτης, ок. 469 до н.э. – 399 до н.э.) – древнегреческий философ, учение которого знаменует поворот в философии – от рассмотрения природы и мира к рассмотрению человека.
Рис. 1.1. Сократ
Широко известны его изречения: «Все люди смертны. Сократ – человек. Следовательно, Сократ смертен…», « Я знаю, что ничего не знаю, но многие не знают и этого», «Здоровье – не всё, всё остальное без здоровья – ничто…». О Сократе мы знаем из сочинений его ученика Платона. Есть даже мнение, что Сократ – вымышленный образ (так же, как Атлантида). Но о Сократе писал не только Платон.
Согласно Платону, Сократ был осуждён на смерть и выпил по приговору суда чашу с ядом – рис. 1.2:
7
Рис. 1.2. Смерть Сократа
Когда друзья хотели его похитить из тюрьмы, он не согласился и даже посмеялся над ними, спросив, знают ли они такое место за пределами Аттики, куда не было бы доступа смерти.
Учеником Сократа был Платон – рис. 1.3 (428 или 427 до н.э., 348 или 347 до н.э.) – древнегреческий философ. Настоящее имя его – Аристокл. Платон – это прозвище, означающее «широкий, широкоплечий».
Рис. 1.3. Платон
Аристотель – рис. 1.4 (др.-греч. Аριστοτέλης), называемый также Стагирит по месту рождения (384, Стагир – 322 до н.э., полуостров Халкидикав Македонии) – древнегреческий философ иучёный.
Ученик Платона, с 343 до н.э. воспитатель Александра Македонского.
8
Именно он считается создателем формальной логики, силлогистики, основанной на дедукции. Основной труд Аристотеля по логике – « Органон». Считается, что наукавЕвропеначаласьс Аристотеля.
Рис. 1.4. Аристотель
Семнадцатилетний Аристотель сказал о своём шестидесятилетнем учителе Платоне: «Платон мне друг, но истина дороже!»
Евклид, или Эвклид (др.-греч. Ευκλείδης, вторая половина III в. до н.э.) – древнегреческий математик – рис. 1.5. Евклид был старше учеников Платона, но моложе Архимеда; он жил и работал в Александрии во времена Птолемея I.
Рис. 1.5. Эвклид
9
Именно с Эвклида началась так называемая аксиоматика, геометрия Эвклида строилась на аксиомах, из которых выводились теоремы. Только в XIX веке пришло понимание того, что можно взять другие аксиомы (например, исключить аксиому о параллельных) и получить совершенно другую геометрию – Лобачевского, Римана. Поиском ответа на вопрос «эвклидово ли наше пространство?» занимаются современные учёные.
Как-то царь Птолемей спросил Евклида, нет ли более короткого пути к изучению геометрии кроме как через изучение его основного труда «Начал», на что Евклид ответил: «В геометрии нет царского пути».
Один юноша спросил у Евклида: «А какая мне будет выгода от этой науки?» Евклид подозвал раба и сказал: «Дай ему три обола, раз он хочет извлекать прибыль из учёбы». Обол́– это название монеты и единицы веса.
Кроме того, в науке известен так называемый алгоритм Эвклида– процедура поиска наименьшего общего делителя, хотя сама теорияалгоритмов считается основанной гораздопозже– в Средние века.
Средневековье
Полагают, что теория алгоритмов как раздел математической логики началась с Аль-Хорезми (полное имя – Абу Абдулла (или Абу Джафар) Мухаммед ибн Муса аль-Хорезми), ок. 783 – ок. 850,
рис. 1.6.
Аль Хорезми написал первое руководство по арифметике, основанное на позиционном принципе. Ему принадлежит процедура (алгоритм) вычислений в десятичной арифметике (так мы и вычисляем – « столбиком»). Написал знаменитую книгу «Китаб аль-джебр валь-мукабала» – « Книга о восстановлении и противопоставлении» (посвящена решению линейных и квадратных уравнений), от названия которой произошло слово «алгебра». Имя автора в латинизированной форме Algorismus и Algorithmus стало, как считается, обозначать в средневековой Европе всю систему десятичной арифметики.
10