В процессе обсуждения первой части статьи выявилась необходимость дополнительно прояснить семантику кванторов.

Формулу

∀x P(x)

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

P(x₁) ∧ P(x₂) ∧ … ∧ P(x_n)

по всем индивидам x₁, x₂, … x_n конечной индивидной области. Т.е. “все x есть P” означает “x₁ есть P, и x₂ есть P, … и x_n есть P”. Соответственно, формулу

∃x P(x)

можно понимать как бесконечный аналог логической суммы

P(x₁) ∨ P(x₂) ∨ … ∨ P(x_n).

Т.е. “существует такое x, которое есть P” означает “x₁ есть P, или x₂ есть P, … или x_n есть P”.

3. Исчисление предикатов

В «Первой аналитике» Аристотель разбирает 14 схем правильных умозаключений, называемых им силлогизмами. Силлогизм гарантирует истинность заключения при условии истинности посылок независимо от содержания входящих в них терминов. В принципе 14 силлогизмов – это не так уж много и все их можно выучить наизусть, что, судя по всему, и требовали от бедных студентов средневековых университетов, за что они возненавидели логику на всю оставшуюся жизнь.

В логике предикатов ситуация кардинально иная. Там бесконечное множество логически общезначимых формул, причем невозможен алгоритм, который для любой данной формулы определял бы, является она логически общезначимой или нет. Это доказали в 1936 году независимо друг от друга Алонзо Черч и Алан Тьюринг.

Но Аристотель подсказал выход. В «Первой аналитике» Аристотель продемонстрировал, что силлогизмы второй и третьей фигуры могут быть сведены к силлогизмам первой фигуры с помощью правил обращения посылок и рассуждения от противного. В свою очередь третий и четвертый силлогизм первой фигуры могут быть сведены к первым двум. Наконец первый и второй силлогизм сводятся к одному правилу, известному как Dictum de omni et nullo.

“А «[одно] сказывается обо всем [другом]» мы говорим, когда не может быть найдено что‑либо из того, что принадлежит подлежащему, о чем другое не высказывалось бы. И точно так же, когда говорим «не сказывается ни об одном»”. – Аристотель. Первая аналитика, 1.1. 24b28.

Таким образом, Аристотель строит силлогистику как дедуктивную систему: из правила Dictum de omni et nullo как аксиомы он выводит все четырнадцать силлогизмов как теоремы.

Возникает вопрос, не можем ли мы и в логике предикатов поступить аналогично – отталкиваясь от небольшого числа аксиом выводить теоремы, которые потенциально охватывали бы все логически общезначимые формулы? Другими словами, не можем ли мы превратить логику предикатов в дедуктивную систему? Оказывается, это возможно. Причем таких дедуктивных систем существует несколько, хотя все они в определенном смысле эквивалентны. Они называются исчислениями предикатов. Три основные типа исчислений – системы гильбертовского типа, системы натурального вывода, и исчисления секвенций. Последние две системы созданы гениальным немецким логиком Герхардом Генценом. В 1936 году им была решена одна и труднейших проблем Гильберта – доказана непротиворечивость формальной арифметики.

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

p ∨ ¬p

и его частные случаи, такие как

R(x, y) ∨ ¬R(x, y).

Последняя формула истинна в любой модели при любых значениях индивидных переменных x, y, а значит является общезначимой в логике предикатов.

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

(1) ∀x (p ⊃ Q(x)) ⊃ (p ⊃ ∀x Q(x))

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

Различие между левой и правой частью формулы (1) заключается в положении квантора. Если бы вместо p стояло бы P(x) формула была бы не верна.

(2) ∀x P(x) ⊃ P(y)

Если P истинно для все х, то P истинно и для какого-то y. Если все люди смертны, то и Сократ смертен.

Эти аксиомы впервые были сформулированы Фреге в его пионерской работе “Исчисление понятий” (1879).

Аналогом формулы (1) для конечной индивидной области является формула

((p ⊃ Q(x₁)) ∧ (p ⊃ Q(x₂)) ∧ … ∧ (p ⊃ Q(x_n))) ⊃ (p ⊃ Q(x₁) ∧ Q(x₂) ∧ … ∧ Q(x_n))

Если из p следует каждое из Q(x_i), то из p следует их конъюнкция.

Аналогом формулы (2) –

P(x₁) ∧ P(x₂) ∧ … ∧ P(x_n) ⊃ P(y)

Квантор существования ∃x можно определить через квантор всеобщности. Тогда формула

∃x P(x)

понимается как сокращенная запись для формулы

¬ (∀x ¬ P(x)).

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

(1ʹ) ∃x (Q(x) ⊃ p) ⊃ (∃x Q(x) ⊃ p)
(2ʹ) P(y) ⊃ ∃x P(x)

В исчислении предикатов имеется также правило вывода, называемое правило обобщения, которое из доказанной формулы A выводит формулу ∀x A, Символически

          A
(3)   ───     или     A ⊢ ∀x A
       ∀x A

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

“Согласно теореме Пифагора, в любом прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов. Треугольник ABC прямоугольный с гипотенузой AB. Следовательно,
AB ² = AC ² + BC ²”.

Такое рассуждение можно было бы назвать конкретизацией – применением общей теоремы к конкретному случаю. Для этого как раз и требуется аксиома (2).

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

Логик, который строит тот или иной вариант исчисления предикатов, подбирает аксиомы и правила вывода исчисления исходя из различных соображений. Например, он желает минимизировать число аксиом, или правил вывода, или стремится к тому, чтобы они были как можно проще и очевиднее. Но в любом случае полученное исчисление должно обладать свойствами непротиворечивости и полноты. Непротиворечивость исчисления означает, что в нем невозможно доказать две противоречащие друг другу формулы: A и ¬A. Полнота исчисления означает, что любая теорема данного исчисления является общезначимой формулой, а любая общезначимая формула является теоремой. Непротиворечивость доказывается сравнительно легко. Полнота исчисления предикатов первого порядка была доказана в 1929 году Куртом Гёделем.