Добавим к трем правилам построения формул еще одно дополнительное:

Формулами также будут:

4. конструкции вида λ(Ψ₁,...Ψ_n), где λ - предикатная константа или предикатная переменная арности n с областями определения X₁,...X_n для соответствующих параметров, а Ψ_i - есть либо формула (если X_i = TF), либо предметная переменная, имеющая область допустимых значений X_i (в противном случае).

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

Четвертое правило допускает, помимо прочего, вложенные обозначения, например: P(x, y, P(z), a & b & P(x)). Для вычисления значения такой формулы надо сначала вычислить все параметры предиката, а потом - сам предикат.

Осталось добавить правило для кванторов. Пока мы добавим только правило, а процесс вычисления рассмотрим далее. Формулами также будут:

5. строки вида γ Ψ и строки вида γ Ψ, где γ - булева, предметная или предикатная переменная, и Ψ - формула.

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

Квантор - это символ, позволяющий построить формулу, которая характеризует область истинности некоторого предиката.

Наиболее распространенными являются квантор всеобщности (символ "") и квантор существования (символ ""). Для них практически всегда вводятся следующие соотношения:

γ Ψ = ~γ ~Ψ

γ Ψ = ~γ ~Ψ

где γ - некоторая переменная, Ψ - некоторая формула, результат вычисления которой есть true или false.

Введем понятие связанной и свободной переменной для РБА.

• Если формула Ξ состоит из одной только булевой переменной, то это единственное вхождение переменной считается свободным по отношению к формуле Ξ.
• Если формула Ξ имеет вид (Ψ & Ω), (Ψ Ω), (Ψ Ω), (Ψ Ω), (Ψ Ω), ~Ψ, где Ψ и Ω - формулы, то все вхождения переменных, которые были свободными или связанными по отношению к Ψ или Ω, остаются свободными или связанными соответственно по отношению к Ξ.
• Если формула Ξ имеет вид λ(Ψ₁,...Ψ_n), где λ - предикатная константа, то все вхождения переменных, которые были свободными или связанными по отношению к Ψ_i остаются свободными или связанными соответственно по отношению к Ξ.
• Если формула Ξ имеет вид λ(Ψ₁,...Ψ_n), где λ - предикатная переменная, то все вхождения переменных, которые были свободными или связанными по отношению к Ψ_i остаются свободными или связанными соответственно по отношению к Ξ. Кроме того, самое первое вхождение переменной λ в Ξ будет свободным по отношению к Ξ.
• Если формула Ξ имеет вид γ Ψ или γ Ψ, то самое первое вхождение переменной γ в Ξ будет связанным по отношению к Ξ и называется "кванторной переменной". Все вхождения переменных, которые были связанными по отношению к Ψ остаются связанными по отношению к Ξ. Все вхождения переменных, отличных от γ, которые были свободными по отношению к Ψ остаются свободными по отношению к Ξ. Все вхождения переменной γ, которые были свободными по отношению к Ψ становятся связанными по отношению к Ξ. При этом будем говорить, что такое вхождение переменной γ "подпало под действие квантора", конкретно того, который стоит в начале формулы.

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

Возможно, удобнее распознавать структуру формул, если рассматривать конструкции вида γ и γ как унарные операции, имеющие тот же приоритет, что и отрицание. Например, в формуле x ~x & y под действие квантора x подпадает формула ~x, а в формуле x (~x & y) под действие квантора x подпадает формула (~x & y).

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

Теперь определим порядок вычисления формул с кванторами.

Если формула Ψ не содержит свободной переменной γ (в том числе когда вовсе не содержит переменных), то

γ Ψ = Ψ

γ Ψ = Ψ

Если формула Ψ содержит одну свободную переменную γ, то надо построить по формуле Ψ предикат P:

P(γ) = Ψ

и вычислить результат по схеме:

γ Ψ = (P true)    (1)

γ Ψ = (P false)    (2)

- то есть, надо определить, является ли предикат P тождественно истинным (выполнимым), получить ответ в виде true или false и подставить в (1) или (2). Если предикат тождественно истинный, то квантор всеобщности дает true (иначе false). Если предикат выполнимый, то квантор существования дает true (иначе false).

Последний случай: формула Ψ содержит n свободных переменных, включая γ. В этом случае добавление квантора образует предикат, зависящий от n − 1 переменных: всех тех же, что свободны в формуле Ψ, за исключением γ. Пусть для определенности в формуле Ψ содержатся свободные переменные x₁,...,x_n, а переменная γ - это x_i. Пусть также P - это предикат, построенный по формуле Ψ.

Тогда формула x_i Ψ образует предикат:

P'(x₁,...x_i−1, x_i+1,... x_n) = x_i P(x₁,...x_i−1, x_i, x_i+1,... x_n)     (3)

То есть, произвольно взятый кортеж (_x₁,...x_i−1, x_i+1,... x_n_) отображается предикатом P' на true, если предикат P отображает кортеж (_x₁,...x_n_) на true при любом x_i. А иначе отображается предикатом P' на false.

А формула x_i Ψ образует предикат:

P'(x₁,...x_i−1, x_i+1,... x_n) = x_i P(x₁,...x_i−1, x_i, x_i+1,... x_n)     (4)

То есть, произвольно взятый кортеж (_x₁,...x_i−1, x_i+1,... x_n_) отображается предикатом P' на true, если предикат P отображает кортеж (_x₁,...x_n_) на true хотя бы при одном x_i. А иначе отображается предикатом P' на false.