Аристотель: логика как наука
До Аристотеля (384–322 до н.э.) греки рассуждали, но не изучали сами рассуждения. Аристотель в «Органоне» создал силлогистику — первую формальную систему вывода. Силлогизм: «Все люди смертны. Сократ — человек. Следовательно, Сократ смертен». Две посылки, одно заключение, три термина. Аристотель систематизировал 256 возможных форм силлогизмов и показал, что только 24 из них гарантируют правильный вывод.
Силлогистика оставалась вершиной логики более 2000 лет. Кант в 1787 году писал, что логика «со времён Аристотеля не сделала ни одного шага назад и ни одного шага вперёд». Он ошибался — шаг вперёд назревал.
Математизация: Буль, Фреге, Рассел
Джордж Буль в «Исследовании законов мышления» (1854) показал: логические операции можно записать алгеброй. «И» = умножение, «ИЛИ» = сложение, «НЕ» = вычитание из единицы. Любое рассуждение — уравнение. Через 80 лет Клод Шеннон (1937) применил булеву алгебру к электрическим схемам — так родились цифровые компьютеры.
Готлоб Фреге в «Begriffsschrift» (1879) создал логику предикатов первого порядка: переменные, кванторы (∀ — «для всех», ∃ — «существует»), функции. Силлогизм Аристотеля записывается одной формулой: ∀x(Человек(x) → Смертен(x)) ∧ Человек(Сократ) → Смертен(Сократ). Фреге охватил рассуждения, недоступные силлогистике: «Для каждого числа существует большее» — ∀x∃y(y > x).
Бертран Рассел и Альфред Уайтхед в «Principia Mathematica» (1910–1913) попытались вывести всю математику из логики. Три тома, 362 страницы до доказательства 1 + 1 = 2. Программа логицизма казалась успешной.
Крах и триумф: теоремы Гёделя
Курт Гёдель в 1931 году доказал две теоремы, изменившие философию математики навсегда. Первая теорема о неполноте: в любой непротиворечивой формальной системе, достаточно богатой для арифметики, существуют истинные утверждения, которые нельзя доказать внутри этой системы. Вторая: такая система не может доказать собственную непротиворечивость.
Это означало: программа «Principia» принципиально неосуществима. Математика не может быть полностью формализована — всегда найдутся истины за пределами любой аксиоматики. Гёделю было 25 лет.
Основные законы классической логики
Закон тождества: A = A. Вещь равна себе.
Закон противоречия: ¬(A ∧ ¬A). Утверждение не может быть одновременно истинным и ложным.
Закон исключённого третьего: A ∨ ¬A. Утверждение либо истинно, либо ложно — третьего не дано. Интуиционисты (Брауэр, 1908) отвергают этот закон для бесконечных объектов.
Modus ponens: если A истинно и A → B, то B истинно. Основное правило вывода.
Логика и информатика
Алан Тьюринг (1936) и Алонзо Чёрч (1936) независимо показали: существуют математические вопросы, на которые не может ответить ни одна программа (проблема остановки). Это прямое следствие идей Гёделя.
SQL-запросы — предикатная логика: SELECT * WHERE age > 18 AND city = 'Moscow'. Пролог (1972) — язык программирования, где программа — набор логических правил. Системы автоматического доказательства теорем используются в верификации ПО и при сертификации авиационного и ядерного оборудования.