2. Распознавание в случае конечных индивидных областей.

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

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

Следствием этого обстоятельства является тот факт, что в случае заданного конечного числа индивидов общезначимость, а также выполнимость всякой конкретной логической формулы представляет собой чисто комбинаторный факт, который может быть проверен элементарным перебором всех возможных случаев.

В самом деле, если число индивидов, а — число субъектов («мест») какого-либо предиката, то число различных наборов значений переменных равно и так как для каждого из этих наборов рассматриваемый предикат является истинным или ложным, то для пробега значений -местного предиката имеется в точности различных возможных значений.

Так что если

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

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

В соответствии с этим общезначимость нашей формулы означает, что для всех

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

связываемые кванторами всеобщности или существования переменные могут принимать лишь значений, так что квантор всеобщности оказывается равнозначным некоторой -членной конъюнкции, а квантор существования — -членной дизъюнкции. Рассмотрим в качестве примера две следующие формулы:

(первая из них фигурировала в качестве примера общезначимой, а вторая — выполнимой формулы). Мы отнесем их к двухэлементной индивидной области.

Эти индивиды мы можем обозначить цифрами 1 и 2. Тогда в рассматриваемом нами примере Следовательно, число различных систем предикатов будет равно

Вместо мы можем подставить а вместо

Тогда первая из рассматриваемых нами формул перейдет в

Эта импликация является истинной для тех предикатов для которых

является ложным, а также и для тех для которых

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

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

Вторая из упомянутых формул в случае двухэлементной индивидной области равнозначна конъюнкции

Так как высказывания являются истинными, то два первых конъюнктивных члена являются истинными всегда; оба последних члена истинны тогда и только тогда, когда

ложно.

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

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