Множества, логика и язык математики¶
§ 1. Три вопроса без предупреждения¶
Запишите ответы на листке — не обсуждая с соседом.
-
Верно ли рассуждение: «Все крокодилы зелёные, а моя сумка зелёная, значит, моя сумка — крокодил»? Если нет, объясните, в чём именно логическая ошибка.
-
Существует ли множество, которое содержит само себя? Если да — приведите пример. Если нет — обоснуйте.
-
Как доказать, что чёрных лебедей не существует? Сколько белых лебедей нужно увидеть, чтобы быть уверенным?
На первый вопрос большинство отвечает правильно: «нет». Но далеко не все могут точно назвать нарушенное правило. Второй вопрос с 1901 года стоит на границе математики и философии. Третий вопрос отделяет научное утверждение от простого ожидания.
Добро пожаловать в математическую логику.
Математика — это не только формулы и вычисления. Прежде всего это способ рассуждать точно. В предыдущих главах мы уже пользовались словами «если», «равно с допуском», «существует ошибка», «для всех входов». Теперь эти слова перестанут быть бытовыми и станут математическими инструментами.
Физик строит модель мира и проверяет её экспериментом. Программист пишет код и проверяет его тестами. Математик строит цепочку рассуждений и проверяет её логикой. Все трое работают с одним фундаментом: определениями, утверждениями и правилами вывода.
Обычный язык для этого слишком свободен. Что значит «большое число»? Что значит «все числа обладают свойством» — включая нуль, отрицательные, комплексные? Что значит «если условие выполнено, то...» — а если оно не выполнено?
Ключевая идея главы проста: математический язык нужен не для украшения, а для защиты смысла.
Множества описывают коллекции объектов. Логика описывает правила построения истинных утверждений. Доказательства связывают известные факты с новыми. Вместе они дают язык, на котором можно строго перечитать и главу о числе, и главу о вычислении — и увидеть в них одну систему.
Историческая линия: от Аристотеля до Буля¶
Аристотель первым систематизировал правила рассуждения. Его силлогизмы — это шаблоны вывода вроде: «Все люди смертны. Сократ — человек. Следовательно, Сократ смертен». Эта система почти без изменений использовалась две тысячи лет.
В 1847 году Джордж Буль свёл логические рассуждения к алгебре: истина стала похожа на \(1\), ложь — на \(0\), операция «и» — на умножение, операция «или» — на сложение. Сегодня это не музейная идея, а основа работы каждого компьютера: логические элементы процессора реализуют булевы операции в кремнии.
Георг Кантор создал теорию множеств — язык, на котором формулируется современная математика. Готтлоб Фреге построил одну из первых формальных систем математической логики. А Бертран Рассел обнаружил в этой области парадокс, к которому мы вернёмся в конце главы.
§ 2. Навигатор символов¶
Эти обозначения будут встречаться на протяжении всей главы и всего курса.
| Символ | Как читать | Пример |
|---|---|---|
| \(\in\) | принадлежит | \(3 \in \{1,2,3\}\) |
| \(\notin\) | не принадлежит | \(4 \notin \{1,2,3\}\) |
| \(\subseteq\) | является подмножеством | \(\{1,3\}\subseteq\{1,2,3\}\) |
| \(\forall\) | для всех | \(\forall n\in\mathbb{N}: n+1>n\) |
| \(\exists\) | существует | \(\exists n\in\mathbb{N}: n^2=4\) |
| \(\neg\) | не | \(\neg(2>5)\) истинно |
| \(\wedge\) | и | \((2>1)\wedge(3>2)\) |
| \(\vee\) | или | \((2>5)\vee(3>2)\) истинно |
| \(\to\) | если..., то... | «делится на \(6\)» \(\to\) «делится на \(3\)» |
| \(\leftrightarrow\) | тогда и только тогда | \(n\) чётно \(\leftrightarrow \exists k\in\mathbb{Z}: n=2k\) |
Не пытайтесь заучить таблицу механически. Символы станут понятными, когда вы увидите, какую работу они выполняют.
§ 3. Множества: язык коллекций¶
Множество — одно из самых фундаментальных понятий математики. Натуральные числа, координатные плоскости, графы, состояния программы, пространства событий в вероятности — всё это удобно описывать через множества.
Интуитивно множество можно понимать как совокупность различных объектов, объединённых общим свойством или описанием. Объекты, входящие в множество, называются его элементами.
Если объект \(a\) принадлежит множеству \(A\), пишут
Если не принадлежит, пишут
Множества обычно обозначают заглавными буквами: \(A\), \(B\), \(C\), \(\mathbb{Z}\), \(\mathbb{R}\). Элементы — строчными: \(a\), \(b\), \(x\), \(y\).
Множество определяется своими элементами и только ими. Если два множества содержат одни и те же элементы, они равны — независимо от того, как мы их описали. Множество «чётных простых чисел» и множество \(\{2\}\) — одно и то же множество.
Первый способ задания множества — перечисление:
Порядок не важен:
Повторения тоже не имеют смысла:
Второй способ — описание свойства:
Это читается так: «множество всех целых \(x\), таких что \(x^2\) меньше \(10\)».
Стандартные множества чисел имеют специальные обозначения:
Пустое множество обозначают \(\varnothing\) или \(\{\}\). Оно не содержит ни одного элемента.
Подмножество¶
Множество \(A\) называется подмножеством множества \(B\), если каждый элемент \(A\) является элементом \(B\). Пишут:
Формально:
Множества \(A\) и \(B\) равны тогда и только тогда, когда
Пустое множество является подмножеством любого множества:
Это не странность, а следствие логики. Утверждение «каждый элемент \(\varnothing\) является элементом \(A\)» истинно, потому что в \(\varnothing\) нет ни одного элемента, который мог бы его нарушить.
Типичные ошибки с множествами¶
Первая ошибка — путать принадлежность и включение. Число \(3\) является элементом множества \(\{1,2,3\}\), поэтому
Но число \(3\) не является подмножеством этого множества. Подмножеством будет одноэлементное множество:
Вторая ошибка — путать \(\varnothing\) и \(\{\varnothing\}\). Пустое множество не содержит элементов. А \(\{\varnothing\}\) содержит один элемент, и этот элемент — пустое множество. Поэтому
Третья ошибка — забывать, что элементом множества может быть другое множество. Запись
верна. А запись
неверна: элементы правого множества — числа, а не множества.
§ 4. Операции над множествами¶
Как из чисел можно строить новые числа сложением и умножением, так из множеств можно строить новые множества.
Объединение множеств \(A\) и \(B\):
Пересечение:
Разность:
Дополнение относительно универсального множества \(U\):
Симметрическая разность:
Она содержит те элементы, которые лежат ровно в одном из двух множеств.
Пусть
Тогда
Смысл этих операций легко увидеть на диаграммах Эйлера — Венна: множества изображаются областями, а операции выделяют нужные части этих областей.
Основные законы алгебры множеств¶
Коммутативность:
Ассоциативность:
Дистрибутивность:
Законы де Моргана:
Идемпотентность:
Нейтральные элементы:
Законы де Моргана особенно важны. Они повторяются не только в теории множеств, но и в логике, программировании, SQL-запросах и инженерных проверках условий.
Диаграммы Эйлера — Венна¶
Диаграммы Эйлера — Венна — визуальный инструмент для работы с множествами. Каждое множество изображается как область на плоскости. Пересечения областей соответствуют пересечениям множеств.
Леонард Эйлер использовал подобные диаграммы в XVIII веке. Джон Венн позже систематизировал их. Эйлеровы диаграммы обычно изображают только существующие отношения, а диаграммы Венна — все возможные пересечения. В учебной практике это различие часто не принципиально, но идея важна: рисунок помогает увидеть отношение, а доказательство показывает, почему оно верно.
Задачи к § 3–4¶
Базовая. Пусть
Найдите \(A\cap B\). Что это за множество с точки зрения арифметики? Подсказка: подумайте о наибольшем общем делителе.
Аналитическая. Докажите по определению:
Исследовательская. Напишите функцию Python power_set(S), которая возвращает множество всех подмножеств множества \(S\). Для вложенных множеств используйте frozenset. Сколько подмножеств у множества из \(n\) элементов?
§ 5. Высказывания и логические операции¶
Логика — наука о правильных рассуждениях. Не о том, красивы ли они, и не о том, нравятся ли нам выводы, а о том, следует ли заключение из посылок.
Высказывание — это повествовательное предложение, которое является либо истинным, либо ложным, и никаким иным.
Примеры высказываний:
— истинно.
«Луна — звезда» — ложно.
«Каждое чётное число больше \(2\) есть сумма двух простых» — тоже высказывание. Мы можем не знать его истинность, но оно имеет определённое значение: либо истинно, либо ложно.
Не являются высказываниями вопрос «Который час?», приказ «Закрой дверь!» и выражение \(x>5\), пока не указано значение \(x\). Последнее называется предикатом; к нему мы вернёмся в разделе о кванторах.
Три базовые логические операции¶
Отрицание \(\neg P\) истинно тогда и только тогда, когда \(P\) ложно.
Конъюнкция \(P\wedge Q\) истинна тогда и только тогда, когда истинны оба высказывания: и \(P\), и \(Q\).
Дизъюнкция \(P\vee Q\) истинна тогда, когда истинно хотя бы одно из высказываний \(P\) и \(Q\).
В быту слово «или» часто означает «одно из двух, но не оба»: «чай или кофе?» В математике \(\vee\) является включающим «или»: оно истинно и тогда, когда истинны оба высказывания. Исключающее «или» обозначают отдельно, например \(\oplus\).
Таблица истинности¶
Таблица истинности — это полный перебор всех комбинаций значений. Для \(n\) логических переменных будет \(2^n\) строк.
| \(P\) | \(Q\) | \(\neg P\) | \(P\wedge Q\) | \(P\vee Q\) | \(P\to Q\) | \(P\leftrightarrow Q\) |
|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | \(1\) | \(0\) |
| \(0\) | \(0\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
Значение \(1\) означает истину, \(0\) — ложь. Такая таблица может выглядеть механически, но именно она позволяет компьютеру работать с логикой без интуиции и догадок.
§ 6. Импликация: самая коварная связка¶
Импликация \(P\to Q\) читается: «если \(P\), то \(Q\)». Она ложна только в одном случае: когда \(P\) истинно, а \(Q\) ложно. Во всех остальных случаях, включая случай ложной посылки, импликация считается истинной.
Это определение часто кажется странным. Представьте обещание: «Если пойдёт дождь, я возьму зонт». Когда обещание нарушено? Только если дождь пошёл, а зонт вы не взяли. Если дождя нет, обещание не нарушено.
Так же и в логике: импликация контролирует только тот случай, где посылка выполнена.
Пример истинной импликации:
«Если число делится на \(6\), то оно делится на \(3\)».
Пример, который звучит нелепо, но логически истинен:
«Если \(2+2=5\), то Луна — куб из сыра».
Посылка ложна, поэтому импликация истинна. Этот принцип иногда формулируют по-латыни: ex falso quodlibet — из ложного следует что угодно.
В математике это не приглашение к абсурду, а строгий способ определить, когда условное утверждение нарушено.
Четыре связанных утверждения¶
Пусть дано утверждение
Тогда можно построить ещё три утверждения.
Прямое:
Обратное:
Контрапозиция:
Обратное к контрапозиции:
Ключевой факт:
Прямое утверждение и контрапозиция логически эквивалентны. А вот обратное утверждение — совсем другая история.
Теперь вернёмся к первому вопросу главы.
«Все крокодилы зелёные» имеет форму
где \(P\) — «объект является крокодилом», а \(Q\) — «объект зелёный».
«Моя сумка зелёная» — это утверждение \(Q\).
Вывод «моя сумка — крокодил» пытается из \(Q\) получить \(P\). Это логическая ошибка: утверждение следствия. Из того, что крокодилы зелёные, не следует, что всё зелёное является крокодилом.
Эквиваленция¶
Эквиваленция \(P\leftrightarrow Q\) читается: «\(P\) тогда и только тогда, когда \(Q\)». Она истинна, когда \(P\) и \(Q\) имеют одинаковые значения истинности.
Формально:
В математике выражение «тогда и только тогда» означает, что доказаны оба направления: из \(P\) следует \(Q\), и из \(Q\) следует \(P\).
Необходимые и достаточные условия¶
Пусть верно
Тогда \(Q\) — необходимое условие для \(P\): без \(Q\) не бывает \(P\). А \(P\) — достаточное условие для \(Q\): если выполнено \(P\), то \(Q\) гарантировано.
Если верно
то условия являются необходимыми и достаточными друг для друга.
Мнемоника: стрелка указывает от достаточного условия к необходимому.
В физике для протекания тока необходима замкнутая цепь, но сама по себе она не достаточна: нужен источник электродвижущей силы. Замкнутая цепь вместе с источником — уже достаточное условие.
В математике для сходимости ряда \(\sum a_n\) необходимо, чтобы \(a_n\to 0\), но этого недостаточно: гармонический ряд расходится.
В программировании для корректной работы классического бинарного поиска необходимо, чтобы массив был отсортирован. Более того, для стандартной постановки это условие является тем, что делает алгоритм применимым: без порядка поиск теряет смысл.
§ 7. Типичные логические ошибки¶
Логические ошибки выглядят убедительно, потому что копируют форму правильного рассуждения, но ломают правило вывода. Умение распознавать их полезно не только в математике: оно защищает от плохих аргументов в науке, рекламе, политике и повседневных разговорах.
Ошибка 1. Утверждение следствия. Из \(P\to Q\) и \(Q\) ошибочно выводят \(P\).
Пример: «Если идёт дождь, асфальт мокрый. Асфальт мокрый. Значит, идёт дождь». Асфальт мог быть полит.
Ошибка 2. Отрицание основания. Из \(P\to Q\) и \(\neg P\) ошибочно выводят \(\neg Q\).
Пример: «Если дождь идёт, асфальт мокрый. Дождя нет. Значит, асфальт сухой». Но асфальт может быть мокрым и без дождя.
Ошибка 3. Путаница включающего и исключающего «или». Фраза «студент изучает математику или физику» в математике допускает, что он изучает оба предмета.
Ошибка 4. Подмена порядка кванторов. Формулы
и
не равны по смыслу. «Для каждого человека есть блюдо, которое ему нравится» не означает «существует блюдо, которое нравится всем».
Задачи к § 7¶
Базовая. Определите тип ошибки: «Все программисты знают математику. Маша знает математику. Значит, Маша — программист».
Аналитическая. Запишите формально и найдите разрыв: «Если задача решена правильно, ответ верен. Ответ верен. Значит, задача решена правильно».
Исследовательская. Придумайте по одному примеру каждой из четырёх ошибок из повседневной жизни.
§ 8. Кванторы: «для всех» и «существует»¶
Высказывания \(P\) и \(Q\) имеют фиксированное значение истинности. Но в математике мы постоянно говорим о свойствах, зависящих от переменной: \(x>5\), \(n\) — простое число, \(a_n\to L\). Такие выражения называются предикатами.
Чтобы превратить предикат в высказывание, нужен квантор.
Квантор всеобщности:
читается: «для каждого \(x\) из \(S\) свойство \(P(x)\) истинно».
Квантор существования:
читается: «существует хотя бы один \(x\) из \(S\), для которого \(P(x)\) истинно».
Квантор единственности:
означает: «существует ровно один такой \(x\)».
Примеры:
— истинно.
— истинно, например при \(n=1\).
— истинно.
— ложно в \(\mathbb{R}\), но истинно в \(\mathbb{C}\).
Область, в которой живёт переменная, не мелочь. Одно и то же утверждение может быть ложным в вещественных числах и истинным в комплексных.
Отрицание кванторов¶
Правила отрицания кванторов — один из главных навыков строгой математики:
На обычном языке: «не все» означает «существует хотя бы один, для которого нет». А «не существует» означает «ни один не удовлетворяет».
При отрицании кванторы \(\forall\) и \(\exists\) меняются местами, а само свойство отрицается.
Рассмотрим формулу:
Это определение того, что последовательность \(a_n\) стремится к \(L\).
Её отрицание:
Это не просто фраза «не сходится». Это точная логическая формула: найдётся такой положительный допуск \(\varepsilon\), что как далеко ни уходи по последовательности, всё равно найдётся член, который не попадает в этот допуск.
Такие конструкции нужны не только в анализе. В программировании похожие формы возникают в спецификациях, инвариантах циклов и проверке корректности алгоритмов.
Мини-практикум: русский язык и формулы¶
Перевод на язык кванторов:
«Для любого простого \(p\) существует простое \(q>p\)».
Один из вариантов записи:
Перевод с формального языка:
означает: «квадрат любого натурального числа не меньше самого числа».
Поиск двусмысленности: «Если задача решена правильно, ответ верен». Что значит «правильно» — по алгоритму, без арифметической ошибки, с корректной моделью? Что значит «верен» — совпадает с эталоном или получен строгим способом? Перед доказательством смысл нужно зафиксировать.
Поиск контрпримера: утверждение «все числа вида \(2^n-1\) просты» ложно. При \(n=4\) получаем
§ 9. Контрпример как оружие¶
Чтобы опровергнуть утверждение вида
достаточно одного контрпримера: найти конкретный \(x_0\), для которого \(P(x_0)\) ложно.
Это следует из правила отрицания квантора:
Контрпример — не «частное замечание». Это полноценное доказательство ложности всеобщего утверждения.
Утверждение «все простые числа нечётны» ложно. Контрпример:
Число \(2\) простое и чётное.
Утверждение «\(n^2+n+41\) простое для всех натуральных \(n\)» долго выглядит правдоподобно. Оно даёт простые значения при многих первых \(n\): \(n=1\) даёт \(43\), \(n=2\) даёт \(47\), \(n=3\) даёт \(53\), и так до \(n=39\), где получается \(1601\) — тоже простое. Сорок подряд. Сильнейшее эмпирическое свидетельство.
Но при \(n=40\):
Один пример разрушает всеобщность. И это не случайность исторической формулы Эйлера: вообще ни одна полиномиальная формула не может давать только простые числа для всех натуральных \(n\) — это доказанный факт. Урок шире, чем формула: проверка конечного числа случаев — сколь угодно масштабная — не заменяет доказательство. Это относится и к математике, и к программированию: тесты не доказывают корректность программы, они лишь показывают отсутствие найденных ошибок.
Вернёмся к третьему вопросу главы: как доказать, что чёрных лебедей не существует?
Наблюдением — никак. Сколько бы белых лебедей вы ни увидели, это не доказывает утверждение
Но один чёрный лебедь опровергает его:
Так появляется важный принцип научного метода: теория должна указывать, какой опыт мог бы её опровергнуть. Именно поэтому фальсифицируемость стала одним из центральных критериев научности у Карла Поппера.
§ 10. Логика в коде¶
Python умеет работать с множествами и логикой почти теми же словами, которыми мы пользовались в математике.
# Множества
primes = {2, 3, 5, 7, 11}
odds = {1, 3, 5, 7, 9}
print(primes & odds) # пересечение: {3, 5, 7}
print(primes | odds) # объединение: {1, 2, 3, 5, 7, 9, 11}
print(3 in primes) # принадлежность: True
# Логика
x = 7
print((x > 0) and (x % 2 != 0)) # конъюнкция
print(not (x > 10)) # отрицание
# Кванторы: all() — для всех, any() — существует
print(all(n + 1 > n for n in range(1, 101)))
Функция all() ведёт себя как квантор \(\forall\): она проверяет, что условие выполнено для всех элементов. Функция any() ведёт себя как квантор \(\exists\): ей достаточно одного подходящего элемента.
def is_prime(n):
if n < 2:
return False
return all(n % d != 0 for d in range(2, int(n ** 0.5) + 1))
ps = [p for p in range(2, 100) if is_prime(p)]
print(all(p % 2 != 0 for p in ps)) # False: контрпример p = 2
# Законы де Моргана для множеств
U = set(range(1, 11))
A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}
comp = lambda S: U - S
print(comp(A | B) == comp(A) & comp(B))
print(comp(A & B) == comp(A) | comp(B))
Этот код не заменяет доказательство законов де Моргана, но показывает важную связь: математическая логика превращается в исполняемые проверки.
Логика в кремнии¶
В 1937 году 21-летний Клод Шеннон написал в MIT магистерскую диссертацию, которую позже назвали одной из самых влиятельных работ XX века. Он показал, что булева алгебра — операции \(\neg\), \(\wedge\), \(\vee\) — может быть реализована электрическими переключателями, и что с помощью таких схем можно выполнять любые арифметические вычисления.
Это прямой мост от абстрактной логики XIX века к физическому компьютеру XX. Каждый транзистор в современном процессоре — реализация одной логической операции. Миллиарды таких операций в секунду — и вот вы читаете этот текст.
Простейший полусумматор — цифровая схема, складывающая два одноразрядных двоичных числа — состоит ровно из двух логических элементов:
Из полусумматоров строятся полные сумматоры, из сумматоров — АЛУ, из АЛУ — процессор. Вся иерархия вычислений — от таблицы истинности до суперкомпьютера — начинается с трёх булевых операций.
SQL-запрос — это тоже логическая формула, только записанная языком баз данных.
SELECT name FROM students
WHERE (grade >= 90 OR extra_credit = TRUE)
AND NOT (absent > 5)
AND course IN ('math', 'physics');
Предикат в WHERE можно прочитать так:
AND, OR, NOT, IN, EXISTS — это не случайные слова, а прямые наследники математической логики.
§ 11. Парадокс Рассела: когда множество ломает само себя¶
Мы начали с интуитивной фразы: множество — это совокупность объектов, объединённых свойством. Но если разрешить любое свойство, возникает опасность.
В 1901 году Бертран Рассел рассмотрел множество
Это должно быть множество всех множеств, которые не содержат сами себя. Вопрос: принадлежит ли \(R\) самому себе?
Если
то по определению \(R\) не должно принадлежать самому себе:
Если же
то оно удовлетворяет условию \(x\notin x\), значит должно принадлежать \(R\):
Оба варианта ведут к противоречию.
Это не игра словами, а настоящий парадокс наивной теории множеств. Его бытовая аналогия — парикмахер, который бреет всех и только тех, кто не бреется сам. Бреет ли он себя?
Выход нашли в аксиоматической теории множеств Цермело — Френкеля с аксиомой выбора, которую часто обозначают ZFC. В ней нельзя просто «собрать» множество по любому произвольному свойству. Существование множеств регулируется аксиомами.
Для нашего курса важен вывод: определение «множество — любая совокупность» слишком широко. Математика требует аккуратности даже в самых базовых понятиях.
Теперь можно ответить и на второй вопрос из начала главы: в стандартной теории множеств ZFC множество, содержащее само себя, не существует.
§ 12. Методы доказательства¶
Доказательство — конечная цепочка логических шагов от аксиом, определений и уже доказанных утверждений к новому утверждению.
В физике решающим аргументом является эксперимент. В программировании — тест, хотя тест никогда не покрывает все случаи. В математике решающим аргументом является доказательство. Оно не показывает «похоже на правду», а устанавливает: это следует из принятых оснований.
Ниже — четыре базовых образца доказательства.
Прямое доказательство¶
Утверждение: если \(a\) и \(b\) — чётные целые числа, то \(a+b\) чётно.
Доказательство. Если \(a\) чётно, то существует \(k\in\mathbb{Z}\) такое, что
Если \(b\) чётно, то существует \(m\in\mathbb{Z}\) такое, что
Тогда
Число \(k+m\) целое, значит \(a+b\) делится на \(2\). Следовательно, \(a+b\) чётно. \(\square\)
Доказательство от противного¶
Утверждение: \(\sqrt{2}\) не является рациональным числом.
Идея доказательства такова. Предположим противное: пусть
где дробь несократима, то есть \(\gcd(p,q)=1\). Тогда
Значит, \(p^2\) чётно, а следовательно, \(p\) чётно. Пусть \(p=2k\). Тогда
откуда
Значит, \(q\) тоже чётно. Получили, что \(p\) и \(q\) оба делятся на \(2\), что противоречит несократимости дроби. Следовательно, предположение было неверным, и \(\sqrt{2}\) иррационально. \(\square\)
Это одно из самых знаменитых доказательств в истории математики. Оно показывает, что строгая логика может разрушить даже очень устойчивую интуицию.
По преданию, иррациональность \(\sqrt{2}\) открыл пифагореец Гиппас Метапонтский — и был убит за это своими соучениками, считавшими, что «всё есть число» в смысле рационального числа. Открытие, противоречащее догме, в Древней Греции могло стоить жизни. Сегодня это просто упражнение на доказательство от противного — но история того, какой ценой иррациональные числа вошли в математику, осталась как напоминание: красивое доказательство и удобное мировоззрение не всегда совместимы.
Доказательство по случаям¶
Утверждение: для любого целого \(n\) произведение \(n(n+1)\) чётно.
Рассмотрим два случая.
Если \(n\) чётно, то \(n=2k\), и
поэтому произведение чётно.
Если \(n\) нечётно, то \(n+1\) чётно. Значит, \(n+1=2m\), и
поэтому произведение снова чётно.
В обоих случаях результат чётен. \(\square\)
Доказательство по индукции¶
Индукция — метод доказательства утверждений вида \(\forall n\in\mathbb{N}: P(n)\). Мы подробно разобрали её в главе «Натуральные числа» — там она появилась как пятая аксиома Пеано. Здесь — её логическая суть.
Чтобы доказать \(\forall n\ge n_0: P(n)\), достаточно доказать два факта:
База: \(P(n_0)\) — утверждение верно для стартового значения.
Переход: \(\forall k\ge n_0: P(k)\to P(k+1)\) — из верности для \(k\) следует верность для \(k+1\).
Логически это выглядит так:
Метафора: бесконечная цепочка домино. Если первая костяшка упала (база) и каждая падающая роняет следующую (переход), то упадут все. Логически принцип индукции эквивалентен принципу наименьшего элемента, который мы тоже видели в главе о натуральных числах. Два взгляда, одна сила.
Опровержение контрпримером¶
Утверждение «все простые числа нечётны» ложно.
Контрпример:
— простое и чётное число. Одного примера достаточно для опровержения утверждения вида \(\forall x:P(x)\). \(\square\)
Контрпример не доказывает новое всеобщее правило. Он делает другое: точно показывает, что старое всеобщее правило неверно.
Задачи к § 12¶
Базовая. Докажите прямо: произведение двух нечётных чисел нечётно.
Аналитическая. Докажите от противного: если \(n^2\) нечётно, то \(n\) нечётно.
Аналитическая. Докажите по индукции: \(1+3+5+\ldots+(2n-1)=n^2\) для всех \(n\in\mathbb{N}\).
Аналитическая. Запишите с помощью кванторов утверждение: «Для каждого \(\varepsilon>0\) существует \(\delta>0\) такое, что для всех \(x\), удовлетворяющих \(|x-a|<\delta\), выполнено \(|f(x)-f(a)|<\varepsilon\)». Что это за определение?
Исследовательская. Напишите программу на Python, которая проверяет законы де Моргана для множеств и для логических значений на универсуме из \(10\) элементов.
§ 13. Итог: от интуиции к строгости¶
Эта глава дала язык, на котором говорит строгая математика.
Множества позволяют точно описывать коллекции объектов. Логические связки \(\neg\), \(\wedge\), \(\vee\), \(\to\), \(\leftrightarrow\) строят сложные утверждения из простых. Кванторы \(\forall\) и \(\exists\) превращают свойства в высказывания. Пять методов доказательства — прямое, от противного, по случаям, по индукции, опровержение контрпримером — инструменты установления истины. Контрпример разрушает ложное всеобщее утверждение. Доказательство устанавливает истину не по привычке и не по совпадению, а по правилам вывода.
Главный вывод: математический язык — это инструмент точности. Определения фиксируют смысл. Теоремы устанавливают связи. Доказательства гарантируют истинность. Без этого инструмента нельзя отличить корректное рассуждение от убедительной ошибки, строгий факт от правдоподобной гипотезы.
Вернёмся к трём вопросам из начала.
Первое рассуждение — «все крокодилы зелёные, сумка зелёная, значит, сумка — крокодил» — ошибочно. Это утверждение следствия: из \(P\to Q\) и \(Q\) нельзя вывести \(P\).
В стандартной теории множеств ZFC множество, содержащее само себя, не существует. Попытка наивно построить множество всех множеств, не содержащих себя, приводит к парадоксу Рассела.
Доказать отсутствие чёрных лебедей наблюдением невозможно. Никакое количество белых лебедей не доказывает всеобщность. Но один чёрный лебедь опровергает утверждение «все лебеди белые».
Три главы складываются в три слоя одного здания.
Первая отвечала на вопрос, что такое число как объект: от натурального ряда до вычислительных ограничений. Вторая показывала, что делает с числом машина и какова цена вычисления. Эта глава дала язык, на котором можно говорить об обоих слоях без двусмысленности.
Теперь, когда вы видите фразу «для любого \(\varepsilon>0\) существует \(N\) такое, что...», это уже не загадочное заклинание, а точная инструкция. Когда вы пишете условие в коде, вы строите логическую формулу. Когда проверяете алгоритм, вы ищете контрпример или строите доказательство.
Математическое мышление — это не склад формул. Это привычка формулировать точно, рассуждать корректно и знать, что именно доказано, а что только предполагается.
§ 14. Что осталось за рамками главы¶
Аксиоматическая теория множеств ZFC — строгий фундамент, где множества строятся не произвольно, а по аксиомам. В этой главе мы только увидели, зачем такая осторожность нужна.
Теоремы Гёделя о неполноте показывают, что в любой достаточно богатой непротиворечивой формальной системе существуют истинные, но недоказуемые внутри неё утверждения. Это фундаментальное ограничение формальных систем.
Нечёткая логика и многозначные логики расширяют классическую картину, где истина равна \(1\), а ложь — \(0\). Такие идеи используются в управлении, поиске и некоторых системах искусственного интеллекта.
Теория типов предлагает другой фундамент, особенно важный для информатики. Языки Haskell, Rust и системы доказательств вроде Lean используют идеи типов для связи программирования, логики и доказательств.
Полная логика предикатов первого порядка изучает формальные языки, правила вывода, модели и доказуемость. В этой главе мы использовали предикаты и кванторы содержательно; строгий формализм — отдельная дисциплина.
В этой главе мы научились говорить строго: задавать множества, строить высказывания, читать кванторы, распознавать логические ошибки и понимать, что такое доказательство.
Но строгий язык нужен не только для рассуждений о множествах. Следующий шаг — зависимости. Величины меняются, графики изгибаются, формулы задают правила перехода от входа к выходу. Чтобы описывать такие связи, нужен язык функций.
Этим мы займёмся в следующей главе: «Функции и графики».
Математика начинается там, где интуиция перестаёт быть достаточной. Теперь у нас есть язык, чтобы идти дальше.