Формы логики первого порядка

Целью параграфа является введение понятия, вынесенного в заголовок параграфа. В принципе это делается так же, как и в логике высказываний, т.е. сначала вводится понятие атомарной формулы, а затем формулы. Только с определением атомарной формулы в случае логики первого порядка ситуация несколько сложнее.

Будем исходить из следующих трех множеств: F,R,V. Элементы множества F – символы (или имена) функций, элементы R – символы (или имена) предикатов, элементы множества V – переменные. Будем считать, что каждому символу функции и предиката поставлено в соответствие натуральное число или ноль – местность (т.е. число аргументов) этого символа. Допускаются нульместные символы функций, которые называются константами, и нульместные символы предикатов (последние будут играть роль атомарных формул логики высказываний). Объединение F и R будем называть сигнатурой. Сигнатуру заранее фиксировать не будем, она будет определяться содержанием решаемой задачи. Множество V предполагается бесконечным, для обозначения его элементов будут использоваться, как правило, буквы x,y,z,u,y,w с индексами и без них.

В примерах, приведенных выше, мы видели, что для записи предикатов использовались арифметические выражения: 2x, x+y, – x². Аналогом арифметического выражения в логике служит понятие терма.

Определение. Термом называется

1) переменная и константа;

2) выражение вида f(t₁,…,t_n), где t₁,…,t_n – термы, а f – n-местный функциональный символ.

Можно сказать, что терм – выражение, полученное из переменных и констант с помощью символов функций.

Определение. Атомарной формулой называется выражение вида r(t₁,…,t_n), где t₁,…,t_n – термы, r – символ n-местного предиката.

Примерами атомарных формул являются выражения x£y²+1, |x-y|<z, x делит нацело y-3.

Определение. Формулой логики первого порядка называется

1) атомарная формула,

2) выражения вида (F)&(G), (F₁)Ú(G), Ø(F), (F)®(G),(F)«(G), ("v)(F), ($v)(F), где F и G – формулы логики предикатов, v – переменная.

Формула F в двух последних выражениях называется областью действия квантора по переменной .

К соглашениям о приоритете операций, принятом в логике высказываний, добавим следующее: кванторы имеют одинаковый приоритет, который больше приоритета всех связок.

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

Например, в формуле F=t(x)&("y)[s(x,y)®($x)(r(x,y)Út(y))]

Первое и второе вхождение переменной x свободны, третье и четвертое связаны. Все вхождения переменной y связаны.

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

Формула F из предыдущего примера имеет одну свободную переменную x.

Если x₁,…,x_n – все свободные переменные формулы F, то эту формулу будем обозначать через F(x₁,…,x_n). Это обозначение будем применять и в том случае, когда не все переменные из x₁,…,x_n являются свободными в F.

Как и в логике высказываний, в логике первого порядка вводится понятие подформулы. Соответствующее определение получится из определения подформулы добавлением фразы: «Подформулами формул ("v)(F) и ($v)(F) являются они сами и все подформулы формулы F».