Уровень B1 · Intermediate

Формальная логика

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

Уровень B1 — это момент, когда язык перестаёт быть только описательным и становится инструментом компетентного мышления: логика высказываний и логика предикатов строятся строго, символ за символом, а модели превращают синтаксис в нечто, что можно сверить с семантикой — и всё это увенчивается двумя самыми знаменитыми теоремами Гёделя.

Что вы узнаете

—Язык пропозициональных формул из трёх правил порождения, и как Modus Ponens вместе с правилом подстановки движут вывод.
—Логику предикатов первого порядка: термы, формулы, кванторы и аксиомы равенства и конгруэнтности, которые делают подстановку безопасной.
—Интерпретацию и модели: что значит быть истинной «в» структуре, и как это связано с непротиворечивостью и совместностью теории.
—Теорему Гёделя о полноте как критерий: непротиворечива ⟺ имеет модель — прямое доказательство Гёделя для одного направления, и почему обратное тривиально следует из корректности.
—Теоремы Гёделя о неполноте: почему любая непротиворечивая, рекурсивно перечислимая теория, способная интерпретировать арифметику, обязана оставить какое-то истинное предложение недоказуемым.

1. От умения говорить к умению мыслить

Формализация самой логики — превращение её в объект математического изучения — была главным проектом на рубеже XX века: «Principia Mathematica» Фреге, Рассела и Уайтхеда и программа Гильберта были нацелены на строгие аксиоматические системы логики, достаточно сильные, чтобы перестроить на них всю математику. На уровне B1 книга идёт тем же путём: пропозициональные формулы определяются ровно тремя правилами (любая переменная — формула; комбинации под $\neg,\land,\lor,\to$ — формулы; ничего больше), и всё дальнейшее — выводимость, корректность, полнота — строится строго на этом синтаксисе.

Награда — настоящий сдвиг в возможностях языка. Вплоть до уровня A2 язык $\Math$ описывал вещи. Теперь он способен удостоверить, что одно описание следует из других описаний, — разница между умением говорить на языке и умением компетентно на нём рассуждать.

2. Непротиворечива тогда и только тогда, когда есть модель

Теория непротиворечива, если из неё не выводимы одновременно формула и её отрицание; она совместна, если у неё есть модель — структура, в которой истинны все её теоремы. Звучит как два разных свойства: одно про доказательства, другое про семантику. Теорема Гёделя о полноте логики предикатов говорит, что это одно и то же свойство, сформулированное как единый критерий.

Теорема Гёделя о полноте (как критерий)

Теория непротиворечива тогда и только тогда, когда она совместна (у неё есть модель).

Два направления этого критерия весят совсем не одинаково. Гёделю принадлежит доказательство содержательного направления, слева направо — непротиворечива $\Rightarrow$ совместна, — которое строит модель из одних лишь термов самого языка: все константные символы отправляются в универсум, а каждая истинная экзистенциальная формула даёт терм-«свидетель», выразимый в самом языке. Обратное, справа налево, сравнительно тривиально: оно прямо следует из корректности исчисления предикатов относительно моделей — если в какой-то модели истинны все аксиомы теории, то по индукции по длине вывода всякая формула, выводимая из этих аксиом, тоже истинна в этой модели, а значит, теория, у которой есть модель, никогда не может вывести одновременно $\varphi$ и $\neg\varphi$.

Равносильная формулировка того же критерия: $\Gamma\Vdash\varphi$ равносильно $\Gamma\vdash\varphi$ — семантическое следование и синтаксическая выводимость оказываются в классической логике предикатов одним и тем же отношением.

Неполнота затем проводит границу: чистая логика предикатов, теория порядков, теория равенства, теория групп — все они непротиворечивы и полны относительно метатеории. В тот момент, когда теория получает способность говорить о собственной доказуемости (как это умеет арифметика Пеано через гёделевскую нумерацию), полнота теряется — факт, который снова и снова подтверждают независимые формулы вроде аксиомы выбора относительно $\mathsf{ZF}$ или пятого постулата Евклида относительно абсолютной геометрии.

3. Проверьте себя

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

Определите, какие из следующих формул являются тавтологиями (всегда истинны):
1. $(\mathcal{A} \to \mathcal{B}) \to (\neg\mathcal{B} \to \neg\mathcal{A})$;
2. $((\mathcal{A} \to \mathcal{B}) \to \mathcal{A}) \to \mathcal{A}$ (закон Пирса);
3. $(\mathcal{A} \to \mathcal{B}) \lor (\mathcal{B} \to \mathcal{A})$ (линейность импликации);
4. $(\mathcal{A} \land \mathcal{B}) \to (\mathcal{A} \lor \mathcal{B})$.
Найдите оценку (присваивание значений $0/1$ переменным $\mathcal{A}, \mathcal{B}, \mathcal{C}$), при которой следующие формулы ложны:
1. $(\mathcal{A} \lor \mathcal{B}) \to (\mathcal{A} \land \mathcal{B})$;
2. $(\mathcal{A} \to \mathcal{B}) \to \mathcal{A}$;
3. $(\mathcal{A} \lor \mathcal{B}) \land \mathcal{C} \to \mathcal{A} \land (\mathcal{B} \lor \mathcal{C})$.
Используя законы Де Моргана и двойное отрицание, упростите:
1. $\neg(\mathcal{A} \lor \neg\mathcal{B})$;
2. $\neg(\mathcal{A} \to (\mathcal{B} \land \neg\mathcal{C}))$;
3. $\neg(\forall x \exists y (\varphi(x, y) \to \neg \psi(x)))$.
Следуя соглашению книги, свободные переменные (параметры) обозначаются буквами $a, b, c$, а связанные переменные — $x, y, z$. Перепишите следующие «сырые» формулы в соответствии с этим соглашением:
1. $\forall k (P(k) \to Q(m))$;
2. $(\forall x P(x)) \land Q(x)$ (подсказка: второй $x$ свободен);
3. $\exists z (u < z \to \forall u (u = z))$ (подсказка: разрешите коллизию переменных $u$);
4. $\int_0^x t^2\,dt$ (интерпретируйте верхний предел как параметр).
Пусть $\varphi = \exists y (a < y)$ (где $a$ свободна).
1. Выполните подстановку $\varphi[a/b]$.
2. Выполните подстановку $\varphi[a/S(b)]$.
3. Объясните, почему подстановка $\varphi[a/y]$ запрещена (некорректна) в нашей логике.

Всего в уровне B1 — 20 упражнений, каждое с полным разобранным решением в приложении книги.

Остальная часть уровня B1 — и ещё два уровня

Этот конспект пропускает полное построение языков высказываний и предикатов с правилами редуцирования скобок, теорему о дедукции, аксиомы равенства и конгруэнтности, рецепт построения формальной теории с нуля и разобранные примеры — теории порядков, равенства, полугрупп и групп. Уровни B2 и C1 применяют этот же аппарат к арифметике Пеано, а затем — ко всему универсуму множеств.

Все способы купить К обзору книги

← Уровень A2 — У чертога логики Уровень B2 — Фундамент математики →