chapter02.qq

\chapter Введение в математическую логику \label chap:02:logic

\section Высказывания
\subsection Примеры высказываний

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

\quasidefinition
    Высказывание — это утверждение с чётко определенным смыслом, которое может
    быть истинным или ложным.

Как обычно, проще привести несколько примеров.

\example \nonumber
    \itemize
        \item «$2+2=5$» — пример высказывания. Оно ложно.
        \item «$3 > 2$» — ещё один пример высказывания. Оно истинно.
        \item «$5$ — простое число» — ещё одно истинное высказывание.
        \item «Множество простых чисел конечно» — это ложное высказывание.
        \item «Если целое число простое и оно больше двух, оно нечётно» —
            истинное высказывание.
        \item 
            «Каждое чётное число, большее двух, можно представить в виде суммы
            двух простых чисел» — это высказывание, истинность которого в
            настоящий момент неизвестна (это так называемая \href[бинарная проблема
            Гольдбаха][https://ru.wikipedia.org/wiki/Проблема_Гольдбаха]).
        \item 
            «$n$ — чётное число» — это не высказывание, потому что непонятно,
            чему равно $n$ (здесь, конечно, под $n$ подразумевается не
            собственно буква, а переменная, которая может принимать разные
            значения), и поэтому это утверждение не является ни ложным, ни
            истинным. С такого типа утверждениями (они называются \emph{предикатами})
            мы познакомимся чуть позже.

Вместо «истинно» или «ложно» используются и другие синонимичные выражения:
верно (неверно), корректно (некорректно) и т.д.

\subsection Операции с высказываниями

Из существующих высказываний можно делать новые высказывания с помощью
логических операций (которые также называются операциями булевой алгебры). Пусть
даны какие-то высказывания $A$ и $B$. 

\definition
    Высказывание «верно по крайней мере одно из двух высказываний $A$ или $B$ (или
    оба)», называется \emph{дизъюнкцией} высказываний $A$ и $B$. Оно
    обозначается $A\vee B$. Другой термин для дизъюнкции — \emph{логическое
    «ИЛИ»}.


\definition
    Высказывание «верны оба высказывания $A$ и $B$» называется
    \emph{конъюнкцией} высказываний $A$ и $B$. Оно обозначается $A \wedge B$.
    Другой термин для конъюнкции — \emph{логическое «И»}.

\definition
    Высказывание «высказывание $A$ неверно» называется \emph{отрицанием} $A$.
    Обозначается $\neg A$. Другой термин — \emph{логическое «НЕ»}.
    
Если про каждое из высказываний $A$ и $B$ известно, является оно истинным или
ложным, легко установить истинность их конъюнкции, дизъюнкции и отрицания.
Например, если $A$ истинно, то $\neg A$ ложно. Если $A$ и $B$ оба истинны, то
$A\wedge B$ истинно, иначе оно ложно. И так далее. Эту информацию удобно
записывать в виде табличек, которые называются \emph{таблицами истинности}.

Таблица истинности для отрицания выглядит так:
\eq
    \begin{array}{cc}
        A & \neg A \\\\
        \hline
        \text{И} & \text{Л} \\\\
        \text{Л} & \text{И} \\\\
        \hline
    \end{array}

Таблицы истинности для конъюнкции и дизъюнкции:
\eq
    \begin{array}{cccc}
        A & B & A \vee B & A \wedge B \\\\
        \hline
        \text{И} & \text{И} & \text{И} & \text{И} \\\\
        \text{И} & \text{Л} & \text{И} & \text{Л} \\\\
        \text{Л} & \text{И} & \text{И} & \text{Л} \\\\
        \text{Л} & \text{Л} & \text{Л} & \text{Л} \\\\
        \hline
    \end{array}

В дальнейшем нам понадобится ещё одна важная логическая операция, но пока
остановимся на этих.

\subsection Раскрытие скобок с отрицанием \label ssec:02:deMorg

Пусть $A$ и $B$ — какие-то высказывания. Рассмотрим высказывание $\neg(A\vee
B)$, то есть отрицание высказывания $A \vee B$. В каком случае оно истинно?
Только в том случае, когда оба высказывания $A$ и $B$ ложны. Действительно, если
хотя бы одно из них истинно, тогда их дизъюнкция (логическое ИЛИ) истинна и
значит её отрицание ложно. Записывая это соображение в виде формулы, получаем
такое равенство:

\align \nonumber
    \item
        \neg(A\vee B)=(\neg A) &\wedge (\neg B)=
    \splitem \splonly{=}
        \neg A \splonly{&} \wedge \neg B
Второе равенство верно, поскольку операция отрицания имеет приоритет перед
конъюнкцией, то есть в формуле $\neg A \wedge \neg B$ сначала выполняются
отрицания, а потом конъюнкция, так что скобки вокруг $\neg A$ и $\neg B$ можно не
писать. 

Аналогично можно рассмотреть высказывание $\neg(A \wedge B)$. Чтобы оно стало
истинным, достаточно, чтобы хотя бы одно из высказываний $A$ или $B$ было
ложным: тогда их конъюнкция (логическое И) ложна и её отрицание истинно. Таким
образом:

\align \nonumber
    \item 
        \neg(A \wedge B) & = (\neg A) \vee (\neg B) =
    \splitem
        \splonly{&=}\neg A \vee \neg B.

Можно сказать, что при раскрытии скобок, перед которыми стоит отрицание, знак
$\vee$ меняется на $\wedge$ и наоборот.

Эти правила преобразования формул в алгебре логики называются \emph{законами де
Моргана}.

\remark
    Законы де Моргана мгновенно обобщаются на случай большего количества
    высказываний. Например: 
    \eq
        \neg(A \wedge B \wedge C) = \neg A \vee \neg B \vee \neg C.

\subsection Логические операции в программировании

В распространённых языках программирования высказываниям соответствуют
выражения, имеющие значения типа «булевская величина» (например, в Python это
\tt{bool}), то есть принимающие значения «истина» или «ложь» (\tt{True} и
\tt{False}). Например, \tt{2 + 3 == 4} имеет значение \tt{False}, а \tt{3 > 2} —
\tt{True}. К булевским значениям можно применять логические операторы \tt{and},
\tt{or} и \tt{not}. Например, \tt{2 * 0 == 1 or 3 > 2} имеет значение \tt{True}.

\comment
    Например: \tt{if x > 0 and x < 10: print("ok")} — на экран
    будет выведена строка \tt{ok} если в переменной \tt{x} находится значение больше
    0 \emph{и} меньше 10. С помощью логических операторов можно составлять сложные
    условия из простых, и это часто приходится делать, чтобы реализовать ту или
    иную логику работы приложения.

\section Предикаты и кванторы

\subsection Примеры предикатов

Выше фигурировал пример утверждения «$n$ — чётное число». Если задать вопрос,
является оно истинным или ложным, вы скорее всего скажете, что вопрос не имеет
смысла: как можно на него ответить, если не знаешь, чему равно $n$? Это пример
утверждения, не являющегося высказыванием. Утверждения такого типа называются
\emph{предикатами}.

\quasidefinition
    Грубо говоря, \emph{предикат} — это такое утверждение, которое зависит от
    одной или нескольких переменных, и становится высказыванием, если задать
    значения этих переменных.

\example
    Рассмотрим предикат «$n$ — чётное число». Его можно обозначить
    какой-нибудь буквой, аналогично обозначению функций — например,
    $E(n)$. При подстановке конкретного $n$ предикат становится
    высказыванием, которое является истинным или ложным. Например,
    $E(2)$ истинно, а $E(17)$ — ложно. Подобно функциям, у
    предикатов есть «область определения» — множество значений, которые
    могут принимать переменные. Например, давайте считать, что областью
    определения для $E(n)$ является множество натуральных чисел, $n\in
    \mathbb N$ (но можно было бы определить аналогичный предикат и для множества
    всех целых чисел).
\example
    Определим предикат $D(k, n)$ — «$n$ делится на $k$». Этот
    предикат зависит от двух переменных. Будем считать, что $n\in
    \mathbb N$ и $k \in \mathbb N$. Например, $D(2, 3)$ — ложь, а $D(2,
    4)$ — истина.
\example
    Ещё нам понадобится предикат $S(x, y):=«x^2=y»$, определенный для
    вещественных $x$ и $y$. Он проверяет, что $x^2$ равняется $y$.

\remark
    В дальнейшем в этой главе, если не оговорено обратное, мы будем считать, что
    буквы $m$, $n$, $k$ обозначают натуральные числа, а $x$ и $y$
    — вещественные.

Одни предикаты можно определять через другие. Например, если бы у нас был
готовый предикат $D$, проверяющий делимость, и нам нужно было изготовить из него
предикат $E$, проверяющий число на чётность, его легко можно было бы задать
таким образом:

\eq
    E(n):=D(2, n).

В следующем разделе мы познакомимся с ещё одним способом создания новых
предикатов из существующих.

\subsection Квантор всеобщности

Давайте рассмотрим предикат $T(n):=D(1, n)$. Он проверяет, что натуральное число
$n$ делится на $1$. Но все натуральные числа делятся на 1! Это можно
сформулировать следующим образом: 
«для всех значений $n$ предикат $T(n)$ имеет значение „истина”». Есть
специальный короткий способ записывать такого типа утверждения:
\eq
    \forall n \\ T(n).
Знак $\forall$ (перевёрнутая буква A, от \emph{all}) называется \emph{квантором
всеобщности}. Он читается «для всякого». 

\comment
    # Удалено для строгости изложения, см. раздел про обозначения в конце главы

    Часто после квантора пишут не просто
    переменную, но и её область определения:
    \eq
        \forall n \in \mathbb N\colon T(n).
    Если область определения не указана, считается, что мы её указали при
    определении предиката или её можно понять из контекста.

\question
    Рассмотрим утверждение $\forall n \\ E(n)$, где $E(n)$ — предикат,
    проверяющий, что натуральное число $n$ является чётным. Что вы можете
    сказать про построенное таким образом утверждение?
    \quiz
        \choice
            Оно истинно.
            \comment
                Вы уверены? В этом утверждении сказано: «для любого натурального
                $n$ верно, что $n$ чётно». Иными словами, это утверждение можно
                переписать так: «все натуральные числа — чётны».
        \choice \correct
            Оно ложно.
            \comment
                Да, потому что бывают нечётные числа. Например, $E(3)$ — ложно.
        \choice
            Невозможно определить его истинность, зависит от значения $n$.
            \comment
                Нет! В этом утверждении сказано: «для любого натурального $n$
                верно, что $n$ чётно». Иными словами, это утверждение можно
                переписать так: «все натуральные числа — чётны». Это утверждение
                попросту неверно.

\remark \label rem:02:bound
    Пусть $P(x)$ — какой-то предикат. Рассмотрим утверждение $\forall x \\  
    P(x)$. Если $P(x)$ при всех значениях $x$ является истинным, значит, это
    утверждение истинно. В противном случае, ложно. Поэтому получившееся
    утверждение не является предикатом, оно является просто высказыванием,
    которое может быть истинным или ложным. Заметим, что хотя переменная $x$
    фигурирует в этом утверждении, мы не можем подставлять вместо неё какие-либо
    конкретные значения. Нельзя записать $\forall 2 \\ P(2)$, это не имеет
    смысла, поскольку после квантора обязательно должна идти переменная, а не
    какое-то конкретное число. Переменная $x$ в этом случае называется
    \emph{связанной}: она существует как бы только внутри утверждения, но
    «извне» мы не можем её менять.

\subsection Квантор существования

\emph{Совершенными числами} называются натуральные числа, которые равны сумме всех
своих положительных делителей, отличных от самого числа (так
называемых «собственных делителей»).

Рассмотрим предикат $R(n)$, проверяющий, является ли натуральное число $n$
совершенным. (Иными словами, $R(n)$ соответствует утверждению «$n$ — совершенное
число».)

Если взять какое-то конкретное $n$, очень легко проверить, является ли оно
совершенным. Например, число $10$ имеет три собственных делителя, $5$, $2$ и
$1$, но $5+2+1=8\ne 10$ — значит, оно не совершенное. Но существуют ли вообще
совершенные числа? Иными словами, верно ли утверждение: «существует такое $n$,
что $R(n)$ имеет значение „истина”»?

Для формулирования таких утверждений также есть специальное короткое
обозначение:
\eq
    \exists n \\ R(n).

\comment
    или
    \eq
        \exists n\in \mathbb N\colon R(n).

Знак $\exists$ (перевернутая буква E, от \emph{exists}) называется
\emph{квантором существования}. Читается просто «существует [такое]».

Аналогично квантору всеобщности (см. \ref[замечание][rem:02:bound]), квантор
существования «связывает» соответствующую переменную. Утверждение $\exists
n\\ R(n)$, хотя в нём фигурирует переменная $n$, не является предикатом,
зависящим от $n$. Это просто высказывание, которое является истинным (если
совершенные числа существуют), или ложным (если их нет).

Кстати, совершенные числа существуют. Например, число 6 совершенно. Это
доказывает, что утверждение $\exists n \\ R(n)$ является истинным.

\subsection Кванторы и отрицание \label ssec:02:quant-neg

Есть обобщение \ref[законов де Моргана\nonumber][ssec:02:deMorg] на формулы с кванторами.
Рассмотрим какой-нибудь предикат $P(x)$. (Например, $x$ принадлежит множеству
всех крокодилов, а $P(x)$ проверяет, что крокодил $x$ является красным.)

Рассмотрим высказывание $\forall x \\ P(x)$ («все крокодилы красные»). Чтобы
его опровергнуть (то есть доказать его отрицание), достаточно предъявить
какого-нибудь крокодила, который бы не был красным. Иными словами, верно
равенство: 
\equation \label eq:02:negofrall
    \neg(\forall x \\ P(x)) = (\exists x \\ \neg P(x))
Аналогично, можно рассмотреть утверждение $\exists x \\ P(x)$ («существует по
крайней мере один красный крокодил»). Чтобы его опровергнуть, нужно перебрать
всех крокодилов, и проверить, что каждый из них не является красным. Иными
словами, верно такое равенство:
\equation \label eq:02:negexists
    \neg(\exists x \\ P(x)) = (\forall x \\ \neg P(x))
Можно сказать, что при переносе знака отрицания через квантор он меняется на
обратный: существование на всеобщность и наоборот.

\remark
    Рассмотрим какой-нибудь предикат $P(x)$, определенный на множестве $\set{1,
    2, 3}$. Тогда утверждение $\forall x \\ P(x)$ эквивалентно такому: $P(1)
    \wedge P(2) \wedge P(3)$. Его отрицание легко переписать по законам де
    Моргана: 
    \gather \nonumber
        \item \neg(P(1) \wedge P(2) \wedge P(3))=
        \splitem \splonly{=}  \neg P(1) \vee \neg P(2)
            \vee \neg P(3).
    Оно в свою очередь эквивалентно $\exists x\\ 
    \neg P(x)$. Таким образом, правило переноса знака отрицания через квантор —
    это действительно обобщение законов де Моргана.

\section Кванторы и предикаты с несколькими переменными
\subsection Связывание одной переменной

Рассмотрим предикат $S(x, y):=«x^2=y»$, определённый для вещественных $x$ и $y$.
Рассмотрим такое утверждение: $\exists x \\ S(x, y)$. Что это за объект?

Если задать конкретное значение $y$, например, $y=4$, получается такая штука:
$\exists x \\ S(x, 4)$, или попросту
\eq
    \exists x \enspace (x^2=4).
Иными словами, получается высказывание о том, что существует квадратный корень
из числа $4$. Это высказывание ни от чего не зависит и является верным, чтобы
его доказать, достаточно предъявить $x=2$.

Однако, можно выбрать другое значение $y$, например, положить $y=-1$. Тогда
получается утверждение
\eq
    \exists x \enspace (x^2=-1).
Это утверждение неверно: мы знаем, что квадраты вещественных чисел
неотрицательны, и значит не существует такого $x$, что его квадрат равен $-1$.

Вернёмся теперь к утверждению $\exists x \\ S(x, y)$. Мы видим, что в это
утверждение вместо $y$ можно подставлять различные числа и получать разные
высказывания — верные и неверные. Значит, перед нами предикат, зависящий от $y$.
Обозначим его через $Q(y)$. Можно записать:
\eq
    Q(y):=(\exists x \\ S(x, y))
Таким образом, из предиката с двумя переменными $S$ мы получили предикат с одной
переменной $y$, поскольку переменную $x$ «связали» с помощью квантора. В
высказывании $\exists x \\ S(x, y)$ переменная $y$ называется «свободной»
(мы можем задавать её значения как хотим и получать разные высказывания), а
переменная $x$ — «связанной».

\subsection Последовательное применение кванторов

Рассмотрим предикат $G(n, m):=«n>m»$, определенный на множестве натуральных
чисел. Он проверяет, что $n$ больше $m$. Введём новый предикат: 
\eq
    Z(m):=(\exists n \\ G(n, m))=(\exists n \enspace (n>m)).
Теперь можно рассмотреть высказывание $\forall m \\ Z(m)$. Его можно записать
так:
\equation
    \forall m \\ (\exists n \enspace (n > m)).
Скобки вокруг предиката $(\exists n \\ (n > m))$ можно убрать, и получится
такая запись:
\equation \label eq:02:forallexists
    \forall m\\ \exists n \enspace (n > m).
Читается: «для всякого $m$ существует такое $n$, что $n>m$».

Во-первых, нужно заметить, что получившееся утверждение не является предикатом
— мы последовательно связали обе переменные и то, что получилось, уже ни от чего
не зависит, это просто высказывание, которое может быть истинным или ложным.

Является ли оно истинным? Да, является. Действительно, возьмём любое $m$.
Заметим, что для него предикат $Z(m)$ верен, поскольку существует такое $n$
(например, можно взять $n=m+1$), для которого $n>m$. (Действительно, $m+1>m$,
каким бы ни было $m$.)

Словами это высказывание можно было бы записать так: «для всякого натурального
числа найдётся большее его число». Эта формулировка с точки зрения привычного
нам языка выглядит немножко неестественно и может возникнуть искушение сделать
её более привычной, переформулировав таким образом:
«найдется натуральное число, большее любого другого натурального числа». Однако,
то, что в результате получилось — не переформулировка исходного утверждения, а
совсем другое высказывание. Оно формально записывается так:

\equation \label eq:02:existsforall
    \exists n\\ \forall m \enspace (n > m)

Как видно, эта формулировка отличается от \ref{eq:02:forallexists} только
порядком следования кванторов. Однако, её смысл совсем иной. При доказательстве
высказывания \ref{eq:02:forallexists} мы для каждого конкретного $m$ могли
выбирать своё $n$, так, чтобы сделать предикат $n>m$ справедливым. В
высказывании \ref{eq:02:existsforall} мы должны задать одно-единственное $n$,
такое, что для него предикат $n>m$ был бы верен для всех возможных $m$. Нетрудно
видеть, что среди натуральных чисел такого $n$ нет. Действительно, каким бы мы
ни взяли $n$, можно положить $m=n$ (или $m=n+1$, или $m=n+2$ и т.д.), и предикат
$n>m$ не будет верным. Видно, что порядок следования кванторов очень важен: он
определяет порядок, в котором соответствующие переменные могут выбираться. В
данном случае при изменении порядка кванторов получились разные результаты:
утверждение с одним порядок истинное, а с другим ложное. Так бывает не всегда
(придумайте пример, когда это не так), но важно понимать, что изменение порядка
следования кванторов создаёт другое утверждение. 

\subsection Отрицание и серия кванторов \label ssec:02:quant-neg-series

Мы уже опровергли утверждение \ref{eq:02:existsforall}, но давайте ещё раз более
подробно поговорим, как мы это сделали. Чтобы опровергнуть утверждение с
кванторами обычно проще всего записать к нему отрицание, а потом доказать это
отрицание. 
Воспользуемся формулами из \ref[раздела][ssec:02:quant-neg]. Обозначим предикат
$\forall m \\ (n>m)$ через $W(n)$. Утверждение \ref{eq:02:existsforall} можно
переписать в виде:
\eq
    \neg(\exists n \enspace W(n)).
Применим к нему равенство \ref{eq:02:negexists}:

\gather
    \item \label eq:02:neg-quantors 
        \neg(\exists n \enspace W(n))=\forall n \enspace (\neg W(n))=
    \splitem \splonly{=} \forall n \enspace (\neg(\forall m \enspace (n>m)))=\ldots
Теперь можно к выражению $\neg(\forall m \\ (n>m))$ применить формулу
\ref{eq:02:negofrall} и подставить результат в \ref{eq:02:neg-quantors}:
\eq
    \ldots=(\forall n\\ \exists m \enspace \neg(n>m))=(\forall n\\ \exists m
    \enspace (n \leqslant m)).
Мы как бы последовательно перекинули знак отрицания сначала через первый
квантор, а потом через второй. Каждый раз квантор менялся на противоположный.
Наконец, отрицание оказалось записано перед предикатом $n>m$, но мы знаем, что
отрицание к утверждение $n>m$ — это утверждение, что $n \leqslant m$. Итак,
отрицанием к высказыванию \ref{eq:02:existsforall} является высказывание
\eq
    \forall n\\ \exists m \enspace (n \leqslant m).
Докажем его. Для этого нужно научиться для всякого $n$ предъявлять такое $m$,
что $n \leqslant m$. Это просто: достаточно взять, например, $m=n$. С тем же
успехом можно было бы взять $m=n+1$ или $m=n+100$.

\section Импликация \label sec:02:impl

Давайте рассмотрим такое утверждение: «если натуральное число делится на 4, то
оно делится на 2» (обозначим его за $A$). Как мы знаем, это верное утверждение.
Как его сформулировать на языке кванторов и предикатов? Давайте введём предикат
$Q(n)$, проверяющий, что $n$ делится на 4. Раньше мы вводили предикат $E(n)$,
проверяющий чётность $n$. Поскольку речь про все натуральные числа, следует
начать с квантора $\forall n$.  Очевидно, дальше нужно написать какое-то
утверждение с предикатами $Q(n)$ и $E(n)$, но какое?

Вероятно, здесь проще начать с отрицания. Что нам нужно было бы сделать, чтобы
опровергнуть утверждение $A$? Нужно придумать такое $n$, чтобы оно делилось на
$4$, но при этом \emph{не делилось} на 2. Именно такой контрпример, если бы он
был построен, опроверг бы наше утверждение. Иными словами, нам нужно было бы
предъявить такое $n$, что $Q(n)$ выполняется, а $E(n)$ нет, то есть верно
утверждение $Q(n)\wedge \neg E(n) $. Итак, отрицание к $A$
выглядит так:

\eq
    \neg A = (\exists n \enspace (Q(n) \wedge \neg E(n))).
Взяв отрицание от этой формулы, получим формулировку для исходного утверждения:
\equation \label eq:02:APnQ
    A = (\forall n \enspace (\neg Q(n) \vee  E(n))).
Иными словами, мы утверждаем, что для всякого $n$ выполняется следующее. Либо
оно не делится на 4 (тогда $\neg Q(n)$ является истинным: про
числа, которые не делятся на 4, мы ничего не утверждаем, а если мы ничего не
утверждаем, то нечему быть неверным), либо, если оно делится на 4 (то есть $\neg Q(n)$
ложно), оно обязано делиться на 2 (чтобы вся дизъюнкция была истинной, если
второй её аргумент ложный, то первый — в данном случае, $E(n)$ — должен быть
истинным).

Это ровно то, что мы хотим сказать.

\question
    Зачем городить такой огород? Почему нельзя было просто написать
    \equation \label eq:02:wrong
        \forall n \enspace (E(n) \wedge Q(n))?
    \quiz
        \choice
            Можно было так и написать, формулы \ref{eq:02:wrong} и
            \ref{eq:02:APnQ} эквивалентны.
            \comment
                А вот и нет. Например, утверждение $A$ и формула
                \ref{eq:02:APnQ} являются истинными, а утверждение в формуле
                \ref{eq:02:wrong} ложно. Действительно, возьмём, например,
                $n=6$. Оно не делится на 4, значит, $Q(6)$ ложно, и значит для
                этого значения $n$ конъюнкция ложна, а раз такое $n$ нашлось, то
                и всё утверждение ложно. Проверьте, что этот пример не
                опровергает утверждение \ref{eq:02:APnQ}.
        \choice \correct
            Потому что это совсем другое утверждение, оно не эквивалентно $A$.
            \comment
                Так и есть. Например, утверждение $A$ и формула
                \ref{eq:02:APnQ} являются истинными, а утверждение в формуле
                \ref{eq:02:wrong} ложно. Действительно, возьмём, например,
                $n=6$. Оно не делится на 4, значит, $Q(6)$ ложно, и значит для
                этого значения $n$ конъюнкция ложна, а раз такое $n$ нашлось, то
                и всё утверждение ложно. Проверьте, что этот пример не
                опровергает утверждение \ref{eq:02:APnQ}.

В общем виде это формулируется так. Пусть есть два высказывания, $A$ и $B$.
Утверждения «из $A$ следует $B$» или  «$A$ влечёт $B$» или «если $A$
истинно, то $B$ тоже истинно», формально записываются как $\neg A \vee
B$. Иными словами, говоря «если $A$ истинно, то $B$ тоже истинно», мы
говорим, что $A$ может и не быть истинным, но нас этот случай, не интересует, мы
про него никаких выводов не делаем (а значит, и ошибаться не можем), но если уж
$A$ истинно, то $B$ обязано быть истинным.

Эта операция с высказываниями $A$ и $B$ настолько важна, что хотя она и
выражается через конъюнкцию, дизъюнкцию и отрицание, у него есть специальное
название — \emph{импликация} (ср. с английским словом \emph{imply}, влечёт), и
специальное обозначение: $A\Rightarrow B$. Утверждение $A$ называется
\emph{посылкой}, а утверждение $B$ — \emph{заключением}.

Давайте построим таблицу истинности для $A\Rightarrow B$ (то есть $\neg A \vee
B$).

\eq
    \begin{array}{ccc}
        A & B & A \Rightarrow B  \\\\
        \hline
        \text{И} & \text{И} & \text{И} \\\\
        \text{И} & \text{Л} & \text{Л} \\\\
        \text{Л} & \text{И} & \text{И} \\\\
        \text{Л} & \text{Л} & \text{И} \\\\
        \hline
    \end{array}

Эта таблица, и особенно её третья строчка, обычно ставит в тупик всех, кто её в
первый раз видит. «Из лжи следует истина!» — как такое может быть? Дело в том,
что если вы делаете утверждение $A \Rightarrow B$ («Если $A$ истинно, то $B$
тоже истинно»), и $A$ оказалось ложным, то это просто означает, что вы
находитесь в ситуации, про которую вы ничего не утверждали. А раз ничего не
утверждали, то не могли и ошибиться. И значит вы правы (ваше утверждение
истинно), вне зависимости от того, является ли $B$ истинным или ложным.

Возвращаясь к примеру, который мы разбирали раньше: «если число $n$ делится на
4, то оно чётное». Рассмотрим число $n=6$. Для него посылка оказалась ложной
(оно не делится на 4), и хотя заключение оказалось истинным (оно чётно), это
никак не противоречит нашей импликации: она остаётся верна и в этом случае.

В дальнейшем мы будем постоянно пользоваться импликацией в доказательствах.
Начнём прямо со следующей лекции.

\section 
    Применение языка матлогики в этой книге
\subsection
    Формальный и естественный язык

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

Когда я учился на первом курсе и только познакомился с этим языком, я был им
очарован: какое-то время мне казалось, что достаточно записать любое утверждение
«в кванторах», и дальше станет понятно, как его доказывать. Однако очень быстро
я обнаружил, что это не так: формальная запись иногда упрощает некоторые логические
переходы, и она часто необходима, чтобы убедиться в правильности доказательства,
но чтобы придумать доказательство, нужно проникнуть в суть утверждения, а не просто
манипулировать строчками с кванторами. 

При этом «суть», то есть идеи, стоящие за математическими рассуждениями, как
правило проще передавать, пользуясь преимущественно естественным языком, а не
формальным. В конце концов, профессиональные математики пишут научные статьи
именно на естественном языке, используя формальный лишь там, где это
действительно необходимо. Что уж говорить об учебнике, читатели которого видят
все эти кванторы впервые в жизни!  Так что пусть вас не пугает обилие новых
обозначений и понятий в этой главе: мы будем ими пользоваться и их нужно
освоить, но все утверждения, сформулированные формально, мы будем подробно
комментировать «по-человечески».

\subsection Сокращённые обозначения
    \label ssec:02:short

Чтобы немножко упростить обозначения в формулах с кванторами и приблизить их к
естественному языку, я разрешу себе чуть-чуть отступить от правил формального
языка, введённого выше. Во-первых, часто после серии кванторов я буду ставить
двоеточие — например, вместо
\eq
    \forall x \\ \exists y \enspace (x < y)
буду писать
\eq
    \forall x \\ \exists y\colon x < y.
Двоеточие тут не несёт никакой содержательной нагрузки и служит просто для
визуального отделения предиката, на который навешиваются кванторы. Оно также
будет заменять скобки — например, в высказывании
\equation \label eq:02:xy1
    \forall x\\  \exists y\colon x \ne 0 \Rightarrow xy=1
кванторы навешиваются целиком на предикат $(x \ne 0 \Rightarrow xy=1)$, а не
только на часть $x\ne 0$. Иными словами, эта запись эквивалентна такой:
\eq
    \forall x\\  \exists y \enspace (x \ne 0 \Rightarrow xy=1).
Во-вторых, я буду зачастую писать условие, которому должно удовлетворять
значение переменной, сразу после квантора. Например, утверждение \ref{eq:02:xy1}
можно записать так:
\eq
    \forall x \ne 0 \\ \exists y\colon xy=1.
Аналогично я часто буду указывать, из каких множеств допустимо брать значения
переменных. Например, если бы я хотел сказать, что для любого натурального числа
найдётся такое рациональное число, что их произведение больше 9, то записал бы
это так:
\eq
    \forall x \in \mathbb N \\ \exists y \in \mathbb Q\colon xy > 9.
Формально более аккуратная, но громоздкая запись этого же утверждения звучит
следующим образом:
\equation \label eq:xygr1
    \forall x\\ \exists y \enspace (x \in \mathbb N \Rightarrow (y \in \mathbb Q
    \wedge xy > 9)).
\question
    Останется ли это утверждение верным, если заменить условие $x \in \mathbb N$
    на условие $x \in \mathbb Z$?
    \quiz
        \choice
            Да.
            \comment
                Прямо-таки для любого целого числа вы можете найти рациональное,
                чтобы их произведение было больше 9? Гм… А какие ненатуральные
                целые числа вы знаете? Приведите пару примеров.
        \choice \correct
            Нет.
            \comment
                Конечно, достаточно взять $x=0$
\question
    Останется ли это это утверждение верным, если заменить условие $y\in \mathbb
    Q$ на условие $y < 0$?
    \quiz
        \choice
            Да.
            \comment
                Какой знак имеет произведение натурального числа и
                отрицательного?
        \choice \correct
            Нет.
            \comment
                Конечно, произведение натурального числа и отрицательного всегда
                отрицательно и не может быть больше 9.

Условия, записываемые после квантора существования, в более подробной записи
приписываются к предикату через конъюнкцию (потому что нам нужно, чтобы
существовало значение переменной, удовлетворяющей условию, \strong{и} предикат был бы
верен), а те, что идут после квантора всеобщности — через импликацию (потому что
мы утверждаем, что предикат верен для всех значения переменной, удовлетворяющей
условию, а для тех, кто не удовлетворяют, ничего не утверждаем).

\exercise
    Запишите отрицание к утверждению \ref{eq:xygr1}, пользуясь правилами переноса
    отрицания через кванторы и законами де Моргана. Запишите получившееся
    утверждение в краткой форме, размещая условия сразу после кванторов. Что
    происходит с этими условиями при переносе через них отрицания — меняются ли
    они?

\section Заключение

Теперь у нас есть математический аппарат, своего рода язык, который позволяет
аккуратно записывать и даже в какой-то мере автоматически анализировать довольно
сложные утверждения.  Мы рассматривали самые простые примеры, чтобы было
понятно, как работает «механика» математической логики. Совсем скоро мы будем
использовать её в условиях реальных математических задач.