Лекция 2. Кванторы и методы доказательства

Лекция 1 дала язык множеств и логических связок. Вторая добавляет кванторы: это переход от пропозициональной логики к логике первого порядка, на языке которой записаны все дальнейшие определения и теоремы курса. Вторая половина — базовые способы доказательства: прямое, контрапозиция, от противного, разбор случаев, контрпример, индукция. Формальная логика с правилами вывода будет позже, после множеств и функций, а пока доказательства пишутся обычным языком, но с опорой на кванторную запись.

1. Предикаты и предметная область

1.1. Зачем нужны кванторы

Хочется сказать «квадрат любого числа неотрицателен». Средствами пропозициональной логики получается только бесконечная серия однотипных высказываний: $0^2 \ge 0$, $1^2 \ge 0$, $(-1)^2 \ge 0$, $2^2 \ge 0$, … Такая серия, объединённая общей формой, называется схемой утверждений; если принять их без доказательства, получится схема аксиом.

В логике первого порядка всю серию записывают одной формулой с квантором:

$\forall x\ \ x^2 \ge 0.$

1.2. Предикат

Определение 1. Предикат $P(x)$ — утверждение, истинность которого зависит от значения переменной $x$.

Пусть $P(x)$ означает «$x$ — чётное число». Тогда $P(2) = T$, а $P(3) = F$ (истину и ложь также записывают как $1$ и $0$). Сам $P(x)$ не высказывание: его истинность определена только после подстановки значения. Точно так же «$x > 1$» не истинно и не ложно, пока вместо $x$ ничего не подставлено.

Предикат может зависеть от нескольких переменных. $M(y, x)$ — «$y$ — мать $x$» — бинарный предикат. Порядок аргументов важен: отношение «быть матерью» работает в одну сторону, и $M(y, x)$ не то же самое, что $M(x, y)$.

1.3. Предметная область

Определение 2. Предметная область (domain of discourse) — множество значений, которые пробегает переменная.

Фраза «все студенты сдали экзамен» формализуется как $\forall x\ S(x)$, где $S(x)$ — «$x$ сдал экзамен». Формула осмысленна только вместе с указанием, что $x$ пробегает студентов.

Значение одной и той же формулы зависит от предметной области. Например, $\exists x\ (x > 3)$ ложно в области $A = \{1, 2, 3\}$: перебрали все элементы и не нашли подходящего. В $\mathbb{N}$ та же формула истинна.

2. Кванторы

2.1. Квантор всеобщности

$\forall x\ P(x)$ читается «для всех $x$ истинно $P(x)$». Формула истинна, если $P$ выполняется на каждом элементе предметной области, и ложна, если найдётся хотя бы один контрпример.

Между кванторами и выражением ставят точку, запятую или берут выражение в скобки: $\forall x.\ P(x)$, $\forall x,\ P(x)$ и $\forall x\ (P(x))$ означают одно и то же.

2.2. Квантор существования

$\exists x\ P(x)$ читается «существует $x$, для которого $P(x)$». Фраза «некоторые студенты опоздали» — это $\exists x\ L(x)$, где $L(x)$ — «$x$ опоздал».

Чаще всего $\exists$-утверждение доказывают, предъявив пример. Иногда существование выводят без примера, например от противного; такие доказательства называют неконструктивными.

2.3. Истинность по пустоте

Если предметная область пуста, $\forall x\ P(x)$ истинно при любом $P$: контрпример взять неоткуда. Это та же истинность по пустоте, что и в доказательстве $\varnothing \subseteq A$.

Пример: предметная область — единороги, их нет. Тогда «у всех единорогов красный рог» $\forall x\ R(x)$ и «у всех единорогов рог не красный» $\forall x\ \neg R(x)$ истинны одновременно. А вот $\exists x\ R(x)$ на пустой области ложно: предъявить некого.

2.4. Квантор как большая конъюнкция

Для конечной предметной области $\{a_1, \dots, a_n\}$ кванторы раскрываются в связки:

$\forall x\ P(x) \iff P(a_1) \wedge P(a_2) \wedge \dots \wedge P(a_n),$ $\exists x\ P(x) \iff P(a_1) \vee P(a_2) \vee \dots \vee P(a_n).$

$\forall$ — «большая конъюнкция» по всем элементам, как $\sum$ — большая сумма, $\exists$ — большая дизъюнкция. Для бесконечной области так уже не распишешь, но смысл тот же.

В программировании квантор похож на цикл по всем значениям: $\forall$ — проверить условие для всех (all), $\exists$ — найти хотя бы одно (any).

3. Связанные и свободные переменные

Определение 3. Переменная под знаком квантора — связанная, вне кванторов — свободная.

Квантор вводит переменную, как объявление let или var в программе: переменная «связывается» и существует внутри области действия квантора (scope). Квантор распространяется на всё, что стоит справа от него; ограничить его действие можно скобками.

Определение 4. Формула без свободных переменных — замкнутая: это высказывание, оно истинно или ложно. Формула со свободной переменной — открытая: это предикат, её значение зависит от этой переменной.

В четвёртой строке скобки ограничили квантор, и $x$ в $Q(x)$ оказался вне его действия. Это две разные переменные с одним именем.

4. Отрицание кванторов

$\neg \forall x\ P(x) \iff \exists x\ \neg P(x), \qquad \neg \exists x\ P(x) \iff \forall x\ \neg P(x).$

Правило: квантор меняется на двойственный, а отрицание уходит внутрь. Делать надо оба действия сразу:

Почему так: $\forall$ — большая конъюнкция, а отрицание конъюнкции по закону де Моргана — дизъюнкция отрицаний, то есть $\exists x\ \neg P(x)$. Отрицание кванторов — обобщённый закон де Моргана.

Отсюда же видно, что кванторы выражаются друг через друга: $\exists x\ P(x) \iff \neg \forall x\ \neg P(x)$.

5. Несколько кванторов

5.1. Порядок кванторов

Одноимённые кванторы подряд можно переставлять: $\forall x\ \forall y$ равносильно $\forall y\ \forall x$, и так же для $\exists$. Разноимённые переставлять нельзя: кванторы читаются слева направо, и смысл меняется.

Пример с людьми. «У каждого человека есть мать»:

$\forall x\ \exists y\ M(y, x).$

Переставим кванторы: $\exists y\ \forall x\ M(y, x)$ — «существует человек, который приходится матерью всем». Записи отличаются только порядком кванторов, а смысл совсем другой.

Пример с числами. Возьмём открытую формулу $y > x$ над $\mathbb{N}$:

• $\forall x\ \exists y\ (y > x)$ истинно: для любого числа есть большее, например $y = x + 1$;
• $\exists y\ \forall x\ (y > x)$ ложно: такое $y$ было бы больше всех натуральных чисел, в том числе самого себя.

В $\forall x\ \exists y$ значение $y$ может зависеть от $x$, а в $\exists y\ \forall x$ одно $y$ должно подойти для всех $x$.

В теоремах чаще встречается $\forall$ (утверждение про все объекты), а $\exists$ — в контрпримерах и в решениях задач, где нужно предъявить объект.

5.2. Ограниченные кванторы

Запись $\forall x \in A$ — сокращение. Квантор всегда пробегает всё, что вообще может оказаться на месте $x$, а принадлежность $A$ спрятана внутрь формулы:

$\forall x \in A\ \ P(x) \iff \forall x\ \big(x \in A \Rightarrow P(x)\big),$ $\exists x \in A\ \ P(x) \iff \exists x\ \big(x \in A \wedge P(x)\big).$

Что будет, если перепутать:

• $\exists x\ (x \in A \Rightarrow P(x))$ истинно, как только во вселенной найдётся хоть один $x \notin A$, и ничего не говорит про $A$;
• $\forall x\ (x \in A \wedge P(x))$ требует, чтобы в $A$ лежало вообще всё.

Отрицание ограниченного квантора. Ограничение остаётся на месте, квантор переворачивается, отрицание уходит внутрь:

$\neg \forall x \in A\ \ P(x) \iff \exists x \in A\ \ \neg P(x), \qquad \neg \exists x \in A\ \ P(x) \iff \forall x \in A\ \ \neg P(x).$

Пример с доски:

$\neg \exists x \in A\ \ \big(P(x) \wedge Q(x)\big) \iff \forall x \in A\ \ \neg\big(P(x) \wedge Q(x)\big) \iff \forall x \in A\ \ \big(\neg P(x) \vee \neg Q(x)\big).$

Запись $\forall x \in A\ (\neg P(x) \wedge \neg Q(x))$ неверна: отрицание конъюнкции по закону де Моргана даёт дизъюнкцию.

5.3. Существует единственный

$\exists! x\ P(x)$ — «существует ровно один $x$ с $P(x)$». В стандартной логике такого квантора нет, это удобное сокращение, которое раскрывается через уже разрешённые символы:

$\exists! x\ P(x) \iff \exists x\ \Big(P(x) \wedge \forall y\ \big(P(y) \Rightarrow y = x\big)\Big).$

Читается в два шага: во-первых, $x$ со свойством $P$ существует; во-вторых, любой $y$ с тем же свойством совпадает с $x$. Этот шаблон «если оба обладают свойством, то они равны» понадобится в теме бинарных отношений: так же устроено свойство антисимметричности.

Пример: $\exists! x \in \mathbb{R}\ (2x = 4)$ истинно, а $\exists! x \in \mathbb{R}\ (x^2 = 4)$ ложно — корней два, хотя $\exists x \in \mathbb{R}\ (x^2 = 4)$ истинно.

6. Перевод с естественного языка

Строгий перевод делается в три шага: описать предметную область и переменные, ввести предикаты, собрать формулу и проверить её обратным переводом.

Пример. «Каждый студент знает хотя бы один язык программирования».

Предикаты: $S(x)$ — «$x$ — студент», $L(y)$ — «$y$ — язык программирования», $Z(x, y)$ — «$x$ знает $y$».

Если множества студентов $S$ и языков $L$ объявлены отдельно, достаточно ограниченных кванторов:

$\forall x \in S\ \ \exists y \in L\ \ Z(x, y).$

Если переменные пробегают вообще все объекты, ограничения раскрываются по разделу 5.2:

$\forall x\ \Big(S(x) \Rightarrow \exists y\ \big(L(y) \wedge Z(x, y)\big)\Big).$

Если $x$ оказался студентом, у него должен найтись объект, который одновременно язык программирования и известен $x$. Если $x$ не студент (число, кошка), импликация истинна и про него ничего не требуется.

Кванторы можно вынести вперёд, и тогда формула записывается так:

$\forall x\ \exists y\ \Big(S(x) \Rightarrow \big(L(y) \wedge Z(x, y)\big)\Big).$

Это та же формула, если предметная область непуста: при $S(x)$ истинном обе требуют $\exists y\ (L(y) \wedge Z(x, y))$, а при ложном обе истинны.

Одна и та же буква может означать и множество ($x \in S$), и предикат ($S(x)$). Эта двойственность ещё встретится в темах про множества и бинарные отношения.

Полностью раскрытые формулы громоздки, и на практике предметную область задают контекстом или ограниченными кванторами. Зато строгая запись однозначна: её можно проверить по правилам, в том числе на компьютере.

Пример. «Массив $a_0, a_1, \dots, a_{n-1}$ отсортирован по возрастанию» (при нестрогом знаке $\le$ точнее говорить «по неубыванию»):

$\forall i\ \big(0 \le i < n - 1 \Rightarrow a_i \le a_{i+1}\big).$

Индекс $i$ идёт до $n - 2$ включительно: при $i = n - 1$ элемента $a_{i+1}$ в массиве нет. В записях с лекции стоит граница $0 \le i \le n - 1$ — с ней формула обращается к несуществующему $a_n$. Индексация с нуля выбрана потому, что речь о массиве; в математических текстах индексы часто начинают с единицы. Та же формула как цикл:

all(a[i] <= a[i + 1] for i in range(n - 1))

7. Что такое доказательство

Доказательство — цепочка утверждений. Она начинается с посылок (premise — то, что дано в условии), предположений (assumption) и аксиом, а каждое следующее утверждение получается из предыдущих по разрешённому правилу вывода. Например, modus ponens: из $P$ и $P \Rightarrow Q$ следует $Q$.

Если каждый шаг опирается на разрешённое правило, доказательство проверяемо: с ним согласится любой, кто принимает эти правила, а записанное на специальном языке — проверит и компьютер. Шаг «по интуиции» без правила доказательством не является.

Для формул пропозициональной логики хватало таблицы истинности: перебрать все интерпретации. С кванторами над бесконечной предметной областью перебрать всё невозможно, поэтому нужны методы из следующего раздела.

8. Методы доказательства

8.1. Прямое доказательство

Чтобы доказать $P \Rightarrow Q$, предполагаем $P$ и цепочкой шагов выводим $Q$. Так оформлено большинство доказательств.

Утверждение 1. Если целое $n$ чётно, то $n^2$ чётно.

Доказательство. Раз $n$ чётно, $n = 2k$ для некоторого $k \in \mathbb{Z}$. Тогда $n^2 = 4k^2 = 2 \cdot 2k^2$ делится на $2$. $\blacksquare$

Утверждение 2. Если целое $n$ нечётно, то $n^2$ нечётно.

Доказательство. $n = 2k + 1$, $k \in \mathbb{Z}$. Тогда $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ — нечётно. $\blacksquare$

8.2. Контрапозиция

Импликация равносильна своей контрапозиции: посылка и следствие меняются местами, и на обе накладывается отрицание:

$P \Rightarrow Q \iff \neg Q \Rightarrow \neg P.$

Обе формулы ложны ровно в одном случае: $P$ истинно, $Q$ ложно. Поэтому вместо исходной импликации можно доказать контрапозицию.

Утверждение 3. Если $n^2$ нечётно, то $n$ нечётно.

Доказательство. Напрямую из нечётности $n^2$ про $n$ ничего не видно. Контрапозиция: если $n$ не нечётно, то есть чётно, то $n^2$ чётно. Это Утверждение 1, оно уже доказано. $\blacksquare$

8.3. От противного

Чтобы доказать утверждение $S$, предполагаем $\neg S$ и выводим противоречие. Значит, $\neg S$ быть не может, и в классической логике $S$ истинно.

Утверждение 4. $\sqrt{2}$ иррационально.

Доказательство. Предположим противное: $\sqrt{2} = \dfrac{p}{q}$, где $p, q$ — целые, $q \ne 0$, дробь несократима. Возведём в квадрат: $p^2 = 2q^2$, значит $p^2$ чётно. Тогда и $p$ чётно — это контрапозиция Утверждения 2. Пусть $p = 2m$, тогда $4m^2 = 2q^2$, $q^2 = 2m^2$, и по той же причине $q$ чётно. Числитель и знаменатель оба делятся на $2$, а дробь была несократимой. Противоречие. $\blacksquare$

Чем это отличается от контрапозиции. При контрапозиции доказывается другая, равносильная импликация $\neg Q \Rightarrow \neg P$, обычным прямым рассуждением, никакое противоречие не ищется. При доказательстве от противного предполагается отрицание всего утверждения, и цель — прийти к противоречию с чем угодно: с условием, с аксиомой, с самим предположением.

8.4. Разбор случаев

Если все возможные ситуации перечислены и в каждой утверждение выполняется, оно доказано. Это похоже на таблицу истинности, только по смысловым случаям. Главное требование — случаи должны покрывать все возможности.

Утверждение 5. $|xy| = |x| \cdot |y|$ для любых целых $x, y$. Доказательство дословно проходит и для вещественных.

Доказательство.

1. $x \ge 0$, $y \ge 0$. Тогда $xy \ge 0$ и $|xy| = xy = |x| \cdot |y|$.
2. Числа разных знаков, два подслучая. Если $x \ge 0$, $y < 0$, то $xy \le 0$ и $|xy| = -xy = x \cdot (-y) = |x| \cdot |y|$. Случай $x < 0$, $y \ge 0$ симметричен.
3. $x < 0$, $y < 0$. Тогда $xy > 0$ и $|xy| = xy = (-x)(-y) = |x| \cdot |y|$.

Других сочетаний знаков нет, значит равенство верно всегда. $\blacksquare$

8.5. Контрпример

Чтобы опровергнуть $\forall x\ P(x)$, достаточно одного $x$, для которого $P(x)$ ложно. Это прямое следствие отрицания квантора: $\neg \forall x\ P(x) \iff \exists x\ \neg P(x)$.

Пример. «Все простые числа нечётны» — ложно: $2$ простое и чётное.

Доказать $\forall$-утверждение — значит показать, что контрпримера нет. Способы: предположить, что контрпример есть, и получить противоречие; взять наименьший контрпример (раздел 9.4); если предметная область конечна, перебрать все элементы. Разбор нескольких примеров $\forall$-утверждение не доказывает.

8.6. Эквивалентность

$P \Leftrightarrow Q$ означает $(P \Rightarrow Q) \wedge (Q \Rightarrow P)$, поэтому доказательство состоит из двух частей: «туда» и «обратно». Каждую часть можно доказывать своим методом. Другой вариант — цепочка равносильных переходов от $P$ к $Q$, где каждый шаг работает в обе стороны. Метод двух включений из лекции 1 устроен именно так.

Теоремы вида «… тогда и только тогда, когда …» встречаются постоянно, потому что они самые полезные: их можно применять в обе стороны. Часто одна сторона почти очевидна, а вся работа — во второй.

8.7. Логические ошибки

Импликация работает в одну сторону. Названия ошибок запоминать не обязательно; главное — делать только те шаги, которые разрешены правилами вывода.

Во всех примерах $P$ — «$n$ делится на $4$», $Q$ — «$n$ чётно».

9. Математическая индукция

9.1. Схема

Индукция позволяет доказать $\forall n \ge n_0\ P(n)$ над бесконечной областью, не перебирая её:

1. База: доказать $P(n_0)$.
2. Шаг: для произвольного $k \ge n_0$ из $P(k)$ (индуктивное предположение) вывести $P(k + 1)$.

Тогда $P(n)$ верно для всех $n \ge n_0$. Откуда берётся этот принцип, разобрано в лекции 2 по матанализу.

Базу проверяют всегда, даже когда она кажется очевидной. Если база ложна, доказывать шаг бессмысленно, а без проверки базы можно долго строить переход для неверного утверждения.

9.2. Пример

Утверждение 6. $1 + 2 + \dots + n = \dfrac{n(n + 1)}{2}$ для всех $n \ge 1$.

Доказательство. База $n = 1$: слева $1$, справа $\dfrac{1 \cdot 2}{2} = 1$.

Шаг. Пусть $1 + 2 + \dots + k = \dfrac{k(k + 1)}{2}$. Тогда

$1 + 2 + \dots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2},$

а это и есть формула для $n = k + 1$. $\blacksquare$

Типичный приём в шаге: раскрыть левую часть $P(k + 1)$ так, чтобы в ней появилась левая часть $P(k)$, и подставить индуктивное предположение.

9.3. Сильная индукция

В шаге сильной индукции предполагается не только $P(k)$, а утверждение для всех предыдущих значений:

$\big(P(n_0) \wedge P(n_0 + 1) \wedge \dots \wedge P(k)\big) \Rightarrow P(k + 1).$

Её удобно применять, когда задача размера $k + 1$ распадается на подзадачи произвольного меньшего размера, а не ровно размера $k$. По силе обычная и сильная индукция равносильны: всё, что доказывается одной, доказывается и другой. Разница только в удобстве.

Утверждение 7 (основная теорема арифметики, существование разложения). Любое целое $n \ge 2$ раскладывается в произведение простых чисел.

Доказательство сильной индукцией. База $n = 2$: число простое и само является разложением.

Шаг. Пусть все целые $m$ с $2 \le m \le k$ раскладываются в произведение простых. Рассмотрим $k + 1$, разбором случаев:

1. $k + 1$ простое — оно само себе разложение.
2. $k + 1$ составное: $k + 1 = ab$, где $2 \le a, b \le k$. По индуктивному предположению $a$ и $b$ раскладываются в произведения простых. Перемножив эти разложения, получаем разложение $k + 1$. $\blacksquare$

Внутри индукции оказался разбор случаев: методы доказательства свободно комбинируются. Обычной индукции здесь не хватило бы: множители $a$ и $b$ могут быть любыми числами меньше $k + 1$, а не обязательно $k$.

9.4. Принцип вполне упорядоченности

Принцип вполне упорядоченности (другое название — принцип наименьшего числа). Любое непустое подмножество натуральных чисел имеет наименьший элемент.

Это не теорема и не определение, его принимают как аксиому, отсюда слово «принцип». Для натуральных чисел он выглядит естественно: они образуют линейный порядок, начинающийся с наименьшего элемента. Для других порядков это неверно: у $\mathbb{Z}$ и у интервала $(0; 1)$ наименьшего элемента нет.

Принцип вполне упорядоченности и принцип математической индукции равносильны: приняв один, получаем другой.

9.5. Все лошади одного цвета

Классический пример неверного доказательства по индукции, которое выглядит правдоподобно.

«Утверждение». В любом множестве из $n \ge 1$ лошадей все лошади одного цвета.

«База» $n = 1$: одна лошадь одного цвета сама с собой.

«Шаг». Пусть утверждение верно для $k$ лошадей. Возьмём $k + 1$ лошадей с номерами $1, \dots, k + 1$. Множества $\{1, \dots, k\}$ и $\{2, \dots, k + 1\}$ содержат по $k$ лошадей, и в каждом по предположению все одного цвета. Множества пересекаются, значит все $k + 1$ лошадей одного цвета.

Частые ошибки

1. Отрицание без переворота квантора: $\neg \forall x\ P(x)$ заменяют на $\forall x\ \neg P(x)$.
2. «Не все» переводят как «никто»: $\forall x\ \neg S(x)$ вместо $\exists x\ \neg S(x)$.
3. Путают раскрытие ограниченных кванторов: $\exists x \in A$ раскрывают через импликацию, $\forall x \in A$ — через конъюнкцию. Правильно наоборот.
4. Переставляют разноимённые кванторы: $\forall x\ \exists y$ и $\exists y\ \forall x$ — разные утверждения.
5. Одно имя у связанной и свободной переменной в одной формуле. Переименуйте связанную.
6. Контрапозицию путают с обратной импликацией: из $P \Rightarrow Q$ следует $\neg Q \Rightarrow \neg P$, но не $Q \Rightarrow P$.
7. Доказывают $\forall$ на примерах. Пример доказывает только $\exists$, а $\forall$ примером можно лишь опровергнуть.
8. Пропускают базу индукции или не проверяют шаг при самых маленьких $k$, как в примере с лошадьми.
9. Считают, что одна из формул $\forall x\ P(x)$ и $\forall x\ \neg P(x)$ обязательно ложна. На пустой области обе истинны.

Мини-тренажёр

1. Какие вхождения переменных свободны в формуле $\forall x\ \big(P(x, y) \Rightarrow \exists y\ Q(x, y)\big)$? Формула открытая или замкнутая?
2. Постройте отрицание $\forall x \in \mathbb{R}\ \exists y \in \mathbb{R}\ (y > x)$ так, чтобы знак $\neg$ не стоял перед кванторами.
3. Какие из формул истинны над $\mathbb{N}$: $\forall x\ \exists y\ (y > x)$, $\exists y\ \forall x\ (y > x)$?
4. Раскройте $\forall x \in A\ P(x)$ и $\exists x \in A\ P(x)$ через неограниченные кванторы.
5. Истинны ли $\forall x \in \varnothing\ P(x)$ и $\exists x \in \varnothing\ P(x)$?
6. Запишите $\exists! x\ P(x)$ без знака $!$.
7. Какую импликацию нужно доказать, чтобы по контрапозиции доказать «если $n^2$ чётно, то $n$ чётно»?
8. Докажите разбором случаев, что $n^2 + n$ чётно для любого целого $n$.
9. Докажите по индукции $1^3 + 2^3 + \dots + n^3 = \left(\dfrac{n(n + 1)}{2}\right)^2$.
10. На каком значении $k$ ломается шаг в «доказательстве» про лошадей и почему?
11. Переведите «не все простые числа нечётны» в формулу без отрицания перед квантором. Истинно ли это?

Шпаргалка