Сформулируем классификационные определения для формул логики предикатов. Рассмотрим некоторую интерпретацию с множеством М.

Определение. Формула А выполнима в данной интерпретации, если существует набор <a₁, …, a_n>, a_i M, значений свободных переменных x_i1, …, x_in формулы А такой, что А|<a₁, …, a_n>=И.

Определение. Формула А истинна в данной интерпретации, если она принимает значение И на любом наборе  <a₁, …, a_n>, a_iM, значений своих свободных переменных x_i1, …, x_in.

Определение. Формула А выполнима (в логике предикатов), если существует  интерпретация, в которой А выполнима.

Определение. Формула А, истинная при любой интерпретации, называется общезначимой или тождественно-истинной (в логике предикатов).

Теорема Черча. Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

Аналогично вводятся понятия опровержимого и тождественно-ложного предиката.

Пример 64.

Выяснить является ли формула выполнимой и опровержимой: .

Решение.

Поскольку на переменную х  навешены кванторы, то она является связной. В свою очередь переменная у является свободной. Формула не имеет вхождений нуль-местных предикатов. Значит, интерпретация будет состоять из трех шагов.

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

· Зададим множество М = {0}.

· Зададим предикат Р(х, у): «х = у».

· Поскольку заданное множество М имеет единственный элемент, то свободному вхождению переменной у припишем значение 0.

При такой интерпретации данная формула обращается в истинное высказывание.

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

Значит, исходная формула является выполнимой.

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

· Зададим множество М = N.

· Зададим предикат Р(х, у): «х < у».

· Свободному вхождению переменной у припишем значение 5.

При такой интерпретации данная формула обращается в ложное высказывание.

Действительно, посылка данной импликации принимает значение и, так как действительно во множестве натуральных чисел N найдутся числа меньше числа 5. Заключение импликации принимает значение л, так как не верно, что любое натуральное число меньше числа 5.

Значит, исходная формула является опровержимой.

Пример 65.

Доказать общезначимость формулы "х Р(х) ® $х Р(х).

Решение.

Допустим, что Р поставлен некоторый предикат на множестве М. Данная формула представляет собой импликацию. Вспомним, что импликация ложна только тогда, когда посылка истинна, а заключение ложно. В нашем случае такая ситуация невозможна. Поскольку, если не для любого элемента хÎМ выполняется предикат Р, то автоматически исходная формула обращается в истинное высказывание (независимо от того какое значение примет заключение импликации). Если же для любого элемента хМ выполняется предикат Р, то естественно заключение верно, т.е. найдется хÎМ такой, что выполняется предикат Р.

Таким образом, исходная формула "х Р(х) ® $х Р(х) общезначима.