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

(х) А и (Ех) А,

где А, как обычно, обозначает любую формулу предметного языка.

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

Опираясь на эти определения, мы можем теперь вычислить таблицу истинности для произвольной формулы, например, формулы, универсум которой состоит всего из двух объектов: 1 и 2.

Чтобы вычислить истинностные значения, например, формулы

Р(у) v (х) (Р(х) → Q).

необходимо учесть определенное распределение, состоящее из семантической функции для Р(х), значения истинности подформулы Q и значения для свободной переменной у. В связи с этим на входах таблицы истинности для рассматриваемой формулы будут три величины. Но предварительно следует выписать список четырех (2²) распределений значений истины семантической функции одной переменной для универсума |1, 2| (табл. 12).

Основываясь на этом распределении, можно вычислить таблицу истинности для рассматриваемой функции (табл.13).

Этот пример показывает, что построение таблицы истинности для исчисления предикатов составляет несравненно более трудную задачу, чем построение таблицы для исчисления высказываний. В самом деле, если универсум рассуждения будет состоять из 10 элементов, то для этого придется построить 210 = 1024 семантические функции только для одной независимой переменной, а число строк в таблице в огромной степени возрастает по мере усложнения формул. В нашем примере речь шла только о двух объектах универсума рассуждений, а формула была крайне проста. Поэтому к таблицам истинности в исчислении предикатов обращаются главным образом для иллюстраций, используя для этого весьма простые формулы с крайне ограниченным универсумом рассуждений.

Тем не менее аналогия с исчислением высказываний оказывается весьма полезной для объяснения таких понятий, как общезначимая (или тождественно истинная) формула исчисления предикатов и логическое следование в этом исчислении. Формула А считается общезначимой в исчислении предикатов, если при всяком выборе универсума рассуждений (области ее значений) столбец ее значений в таблице будет состоять только из истин. Если универсум будет фиксирован, то формула называется общезначимой только в этом универсуме.

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

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

Чтобы установить, следует ли логически формула В исчисления предикатов из множества формул A¹, А²,..., A^m (m > 1), необходимо, как и в исчислении высказываний, построить соответствующую таблицу истинности и убедиться в том что формула В будет иметь истинное значение во всех тех строках, где A¹, А²,..., A^m одновременно являются истинными, и это условие выполняется во всех универсумах рассуждения. Такое условие играет существенную роль, ибо одна формула будет логически следовать из другой (или других) в одном универсуме, но не следовать в ином универсуме.

Символически это определение можно представить в следующей форме:

A¹ ,A², ,A^m | = B

где знак | = обозначает следование.

В приведенном выше определении логического следования свободные переменные рассматриваются как обозначающие некоторые элементы из универсума рассуждения. Поэтому в течение всего рассуждения они, так же, как и предикаты, должны оставаться фиксированными. При другом определении переменные могут быть различными в разных формулах. Чтобы яснее представлять различия между двумя подходами к определению логического следования, обратимся к языку алгебры, в котором, как известно, различают, с одной стороны, уравнения (или условные равенства), а с другой - тождества (или тождественные равенства). В то время как уравнению удовлетворяют только определенные значения переменной, называемые его корнями, тождество выполняется при любых значениях переменной. Именно поэтому уравнения считаются условными равенствами. Действительно, например, в уравнении х2 + 2х - 3 = 0 левая часть равняется правой только при значениях х = 1 и х = -3, а в тождестве (х + 1)2 = х2 + 2х + 1 вместо переменной можно подставлять любые числа.

Соответственно этому будем говорить, что для переменных в уравнениях дается условная интерпретация, а в тождествах - интерпретация всеобщности. При условной интерпретации переменной х в определенном допущении А(х) - куда х входит свободно - любое следствие, полученное из него, должно относиться к тому же самому элементу из универсума А(х). Иными словами, переменная х в этом случае фиксирована, так как представляет то же самое число в процессе рассуждения. При тождественной интерпретации значения переменных могут изменяться. Отсюда становится ясным, что приведенное выше определение для логического следования в исчислении предикатов соответствует условной интерпретации свободных переменных, входящих в допущения A¹, А²,..., Aⁿ. Чтобы сформулировать другое определение следования, необходимо опираться на интерпретацию всеобщности для всех переменных. Для этого необходимо, во- первых, связать все допущения А¹, А², ..., A^m кванторами общности, а во-вторых, построить таблицы истинности, как и в первом определении.

Приведенные выше понятия общезначимой формулы логического следования в конечном итоге опираются на построение таблицы истинности. Но проверка с помощью таблиц оказывается, как мы видели, и крайне громоздким, и весьма неэффективным средством. Такой способ проверки целесообразно использовать для выявления общезначимых формул и логического следования в исчислении высказываний, где с помощью таблицы истинности мы можем всегда ответить на вопрос, является ли данная формула общезначимой или законом логики в этом исчислении, а также следует ли формула В из формул A¹, А²,..., А^m. Когда существует определенная процедура, посредством которой можно за конечное число шагов разрешить определенный вопрос, тогда в логике и математике говорят, что для ответа на него существует алгоритм или эффективная процедура. Мы можем, например, сказать, что для сложения, умножения, деления и других хорошо известных математических действий существуют определенные алгоритмы. То же самое относится и к исчислению высказываний, где с помощью таблицы истинности всегда можно в конечном итоге ответить на вопрос, является ли данная формула законом исчисления или нет, либо следует ли рассматриваемая формула из другой или других формул.