Искусство доказательства в математике: Курс лекций с упражнениями (4000,00 руб.)

Стр.5

Стр.6

Стр.7

УДК 519.63 ББК 22.193 В27 В27 Искусство доказательства в математике / пер. с англ. В. С. Яценкова. – М.: ДМК Пресс, 2021. – 444 с.: ил. Веллеман Д. ISBN 978-5-97060-911-8 Чего от вас ждут, когда просят что-то доказать? Что отличает правильное доказательство от неправильного? Эта книга поможет вам узнать ответы и разъяснит основные принципы, используемые при построении доказательств. В отличие от школьного подхода к доказательствам как к пронумерованному списку утверждений и причин, в настоящем издании используется структурированный подход, характерный для программирования: математические доказательства также строятся путем объединения некоторых базовых структур. Выбор структуры определяется логической формой доказываемого утверждения, поэтому в начале книги рассматривается элементарная логика и читатель знакомится с различными формами математических выражений. Далее обсуждаются отношения, функции, математическая индукция и более сложные математические темы, в частности теория чисел. В конце разделов каждой главы представлен список упражнений, для части которых приводятся решения или подсказки. Издание адресовано всем, кто интересуется логикой и доказательствами: математикам, специалистам по информатике, философам, лингвистам. УДК 519.63 ББК 22.193 Copyright Original English language edition published by Cambridge University Press is part Все права защищены. Любая часть этой книги не может быть воспроизведена в каof the University of Cambridge. Russian language edition copyright © 2021 by DMK Press. All rights reserved. кой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. ISBN 978-1-108-42418-9 (англ.) ISBN 978-5-97060-911-8 (рус.) © Daniel J. Velleman, 2020 © Оформление, издание, перевод, ДМК Пресс, 2021

Стр.5

Содержание От издательства ......................................................................................................7 Предисловие к третьему изданию ...............................................................8 Введение ..................................................................................................................11 Глава 1. Пропозициональная логика .........................................................17 1.1. Дедуктивное мышление и логические связки .......................................17 1.2. Таблицы истинности ..................................................................................23 1.3. Переменные и множества .........................................................................34 1.4. Операции над множествами .....................................................................43 1.5. Условные и равнозначные связки ............................................................53 Упражнения ........................................................................................................62 Глава 2. Кванторная логика ............................................................................65 2.1. Кванторы ......................................................................................................65 2.2. Эквивалентности, включающие кванторы .............................................74 2.3. Другие операции с множествами .............................................................83 Глава 3. Доказательства ...................................................................................93 3.1. Стратегии доказательства .........................................................................93 3.2. Доказательства, связанные с отрицаниями и условиями ..................104 3.3. Доказательства с использованием кванторов .....................................116 3.4. Доказательства с использованием конъюнкций и равносильностей ..........................................................................................133 3.5 Доказательство дизъюнкций ...................................................................144 3.6. Доказательства существования и единственности .............................155 3.7. Более сложные примеры доказательств ................................................164 Глава 4. Соответствия ......................................................................................174 4.1. Упорядоченные пары и декартовы произведения ..............................174 4.2. Соответствия .............................................................................................182 4.3. Подробнее о соответствиях .....................................................................190 4.4. Отношения порядка .................................................................................199 4.5. Отношения эквивалентности .................................................................213 Глава 5. Функции ................................................................................................226 5.1. Определение функции .............................................................................226 5.2. Однозначность и сюръективность .........................................................236 5.3. Инверсия функций ...................................................................................245

Стр.6

6  Содержание 5.4. Замкнутые множества .............................................................................254 5.5. Образы и прообразы: исследовательский проект ...............................262 Глава 6. Математическая индукция .........................................................267 6.1. Доказательство путем математической индукции .............................267 6.2. Дополнительные примеры ......................................................................274 6.3. Рекурсия .....................................................................................................287 6.4. Сильная индукция ....................................................................................297 6.5. Вновь про замыкания ..............................................................................311 Глава 7. Теория чисел .......................................................................................317 7.1. Наибольшие общие делители .................................................................317 7.2. Простые множители .................................................................................324 7.3. Модульная арифметика ...........................................................................333 7.4. Теорема Эйлера .........................................................................................341 7.5. Криптография с открытым ключом .......................................................349 Глава 8. Бесконечные множества ..............................................................361 8.1. Равномощные множества .......................................................................361 8.2. Счетные и несчетные множества ...........................................................370 8.3. Теорема Кантора–Шредера–Бернштейна ............................................377 Приложение. Решения некоторых упражнений ................................385 Дополнительные материалы ......................................................................438 Краткое изложение методов доказательства ....................................439 Предметный указатель ...................................................................................441

Стр.7