§ 2. Проблема разрешимости
1. Общезначимость и выполнимость.
Вопросы, подобные только что рассмотренному, относятся к кругу вопросов так называемой проблемы разрешимости. Под этим в современной логике понимается проблема нахождения общих методов распознавания общезначимости или же выполнимости логических формул.
При этом рассматриваемые формулы образуются с помощью логических знаков из предикатных переменных и равенств. Переменные, стоящие на местах субъектов, трактуются нами как индивидные переменные. Каждая из них должна быть связана квантором всеобщности или существования.
Формула такого рода называется общезначимой, если она представляет собой истинное высказывание при любом замещении переменных предикатов. Она называется выполнимой, если она оказывается истинным высказыванием при подходящем замещении переменных предикатов.
Формулы
дают нам простые примеры общезначимых формул.
Формулы
являются примерами выполнимых формул.
Эти последние, например, превратятся в истинные высказывания в индивидной области, состоящей из чисел 1 и 2, если в первую из них вместо 
подставить предикат 
есть четное число», во вторую — вместо 
предикат 
а в третью — вместо 
предикат 
Следует обратить внимание на то, что при определении предикатов должна быть также указана индивидная область, к которой относятся переменные 
. В рассматриваемой логической формуле эта область в известном смысле фигурирует в качестве скрытой переменной. Разумеется, выполнимость какой-либо логической формулы представляет собой свойство, инвариантное относительно взаимно однозначных отображений одной индивидной области на другую, так как индивиды фигурируют в формулах лишь в качестве переменных субъектов. Поэтому единственной существенной характеристикой индивидной области является число составляющих эту область индивидов.
Итак, в отношении общезначимости и выполнимости мы должны различать следующие вопросы:
1. Вопрос об общезначимости в любой индивидной области, соответственно о выполнимости в какой-либо индивидной области.
2. Вопрос об общезначимости, соответственно о выполнимости при заданном числе индивидов.
3. Вопрос о том, при каком числе индивидов имеет место общезначимость, соответственно выполнимость.
