2Введение в математическую логику

2.1Высказывания

2.1.1Примеры высказываний

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

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

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

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

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

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

Таблица истинности для отрицания выглядит так:

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

2.1.3Раскрытие скобок с отрицанием

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для формулирования таких утверждений также есть специальное короткое обозначение:

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

Аналогично квантору всеобщности (см. замечание 3), квантор существования «связывает» соответствующую переменную. Утверждение $\exists nR\left(n\right)$, хотя в нём фигурирует переменная $n$, не является предикатом, зависящим от $n$. Это просто высказывание, которое является истинным (если совершенные числа существуют), или ложным (если их нет).

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

2.2.4Кванторы и отрицание

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

Рассмотрим высказывание $\forall xP\left(x\right)$ («все крокодилы красные»). Чтобы его опровергнуть (то есть доказать его отрицание), достаточно предъявить какого-нибудь крокодила, который бы не был красным. Иными словами, верно равенство:

Аналогично, можно рассмотреть утверждение $\exists xP\left(x\right)$ («существует по крайней мере один красный крокодил»). Чтобы его опровергнуть, нужно перебрать всех крокодилов, и проверить, что каждый из них не является красным. Иными словами, верно такое равенство:Можно сказать, что при переносе знака отрицания через квантор он меняется на обратный: существование на всеобщность и наоборот.

2.3Кванторы и предикаты с несколькими переменными

2.3.1Связывание одной переменной

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

Если задать конкретное значение $y$, например, $y=4$, получается такая штука: $\exists xS(x,4)$, или попросту

Иными словами, получается высказывание о том, что существует квадратный корень из числа $4$. Это высказывание ни от чего не зависит и является верным, чтобы его доказать, достаточно предъявить $x=2$.

Однако, можно выбрать другое значение $y$, например, положить $y=-1$. Тогда получается утверждение

Это утверждение неверно: мы знаем, что квадраты вещественных чисел неотрицательны, и значит не существует такого $x$, что его квадрат равен $-1$.

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

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

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

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

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

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

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

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

2.3.3Отрицание и серия кванторов

Мы уже опровергли утверждение (2.5), но давайте ещё раз более подробно поговорим, как мы это сделали. Чтобы опровергнуть утверждение с кванторами обычно проще всего записать к нему отрицание, а потом доказать это отрицание. Воспользуемся формулами из раздела 2.2.4. Обозначим предикат $\forall m(n>m)$ через $W\left(n\right)$. Утверждение (2.5) можно переписать в виде:Применим к нему равенство (2.2): Теперь можно к выражению $\neg \left(\forall m\right(n>m\left)\right)$ применить формулу (2.1) и подставить результат в (2.6):Мы как бы последовательно перекинули знак отрицания сначала через первый квантор, а потом через второй. Каждый раз квантор менялся на противоположный. Наконец, отрицание оказалось записано перед предикатом $n>m$, но мы знаем, что отрицание к утверждение $n>m$ — это утверждение, что $n⩽m$. Итак, отрицанием к высказыванию (2.5) является высказываниеДокажем его. Для этого нужно научиться для всякого $n$ предъявлять такое $m$, что $n⩽m$. Это просто: достаточно взять, например, $m=n$. С тем же успехом можно было бы взять $m=n+1$ или $m=n+100$.

2.4Импликация

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

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

Взяв отрицание от этой формулы, получим формулировку для исходного утверждения:Иными словами, мы утверждаем, что для всякого $n$ выполняется следующее. Либо оно не делится на 4 (тогда $\neg Q\left(n\right)$ является истинным: про числа, которые не делятся на 4, мы ничего не утверждаем, а если мы ничего не утверждаем, то нечему быть неверным), либо, если оно делится на 4 (то есть $\neg Q\left(n\right)$ ложно), оно обязано делиться на 2 (чтобы вся дизъюнкция была истинной, если второй её аргумент ложный, то первый — в данном случае, $E\left(n\right)$ — должен быть истинным).

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

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

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

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

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

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

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

2.5Применение языка матлогики в этой книге

2.5.1Формальный и естественный язык

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

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

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

2.5.2Сокращённые обозначения

Чтобы немножко упростить обозначения в формулах с кванторами и приблизить их к естественному языку, я разрешу себе чуть-чуть отступить от правил формального языка, введённого выше. Во-первых, часто после серии кванторов я буду ставить двоеточие — например, вместобуду писатьДвоеточие тут не несёт никакой содержательной нагрузки и служит просто для визуального отделения предиката, на который навешиваются кванторы. Оно также будет заменять скобки — например, в высказываниикванторы навешиваются целиком на предикат $(x\ne 0\Rightarrow xy=1)$, а не только на часть $x\ne 0$. Иными словами, эта запись эквивалентна такой:Во-вторых, я буду зачастую писать условие, которому должно удовлетворять значение переменной, сразу после квантора. Например, утверждение (2.9) можно записать так:Аналогично я часто буду указывать, из каких множеств допустимо брать значения переменных. Например, если бы я хотел сказать, что для любого натурального числа найдётся такое рациональное число, что их произведение больше 9, то записал бы это так:Формально более аккуратная, но громоздкая запись этого же утверждения звучит следующим образом:

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

2.6Заключение

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

---