Q(1; 1) = 1; Q(1; 2) = 1; Q(2; 1) = 0; Q(2; 2) = 1.

В этой интерпретации формулу можно записать в виде

[P (1) ! Q(f(1); 1)] ^ [P (2) ! Q(f(2); 1)] =

= [P (1) ! Q(2; 1)] ^ [P (2) ! Q(1; 1)] = (0 ! 0) ^ (1 ! 1) = 1 ^ 1 = 1,

т.е. формула истинна в заданной интерпретации. J

Как только определены интерпретации, все понятия логики высказываний можно определить и для логики первого порядка. Если формула в логике первого порядка не содержит переменных и кванторов, ее можно рассматривать как формулу в логике высказываний.

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

Формула, ложная при всех возможных интерпретациях, называется противоречивой (невыполнимой).

Формула непротиворечива (выполнима), если существует интерпретация I, в которой формула имеет значение “истина".

Определение. Формула G есть логическое следствие формул

F1; : : : ; Fn тогда и только тогда, когда для каждой интерпретации I, в которой F1 ^ ¢ ¢ ¢ ^ Fn истинна в I, G также истинна.

Теоремы 4.1 и 4.2 о логическом следствии справедливы и в логике первого порядка.

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

5.2 Предваренная нормальная форма

Определение. Говорят, что формула F представлена в предваренной нормальной форме (ПНФ), если F имеет вид

ij1x1ij2x2 : : :ijnxnM[x1; : : : ; xn],

где каждое ijxi; i = 1; n есть либо 8xi, либо 9xi, а M[x1; : : : ; xn]

– формула, не содержащая кванторов (матрица формулы F ), ij1x1ij2x2 : : :ijnxn – префикс формулы F .

Примеры 5.5.

Формулы, представленные в ПНФ.

1)8x8y[P (x; y) ^ Q(y)];

2)8x8y[:P (x; y) ! Q(y)];

3)8x8y9z[Q(x; y) ! R(z)]. J

Напомним, что две формулы F и G эквивалентны (F = G), когда истинностные значения F и G одинаковы в любой интерпретации. Основные пары эквивалентных формул (с логическими связками) логики высказываний справедливы и в логике первого порядка.

Рассмотрим эквивалентные формулы, содержащие кванторы. Это понадобится нам для преобразования формулы в предваренную нормальную форму.

Пусть F [x] формула, содержащая свободную переменную x; G – формула, в которую не входит свободная переменная x; ij – квантор 8 или 9.

Каждую пару эквивалентных формул будем называть для краткости законом:

1.a)ijxF [x] _ G =ijx(F [x] _ G); b)ijxF [x] ^ G =ijx(F [x] ^ G);

2.a):(9xF [x]) = 8x(:F [x]);

b):(8xF [x]) = 9x(:F [x]).

Законы 1a) и 1b) истинны, т.к. G не содержит переменной x и может быть внесена в область действия квантора.

Докажем 2a). Пусть I некоторая интерпретация с областью D.

Если :(9xF [x]) истинна в I, то (9xF [x]) – ложна в I. Это означает, что в D нет такого элемента, для которого F [x] истинна в I; следовательно, для любого элемента в D F [x] ложна в I, или :F [x] истинна в I, т.е. справедливо, что формула (8x:F [x]) истинна в I.

168 Глава 5. Логика предикатов

Пусть теперь :(9xF [x]) ложна в I. Тогда 9xF [x] истинна в I, т.е. 9e 2 D (в D существует некоторый элемент e), такой, что F [e] истинна в I, или :F [x] – ложна в I. Но тогда формула 8x(:F [x]) ложна в I. Таким образом, формулы принимают одни и те же истинностные значения в любой интерпретации, т.е. эквивалентны.

Докажем теперь 2b). Пусть I – произвольная интерпретация с областью D.

Если :(8xF [x]) истинна в I, то 8xF [x] ложна в I. Это значит, что существует элемент e 2 D, что F [e] ложна, т.е. :F [e] истинна. Следовательно, 9x(:F [x]) – истинна в I.

Пусть теперь :(8xF [x]) ложна в I. Тогда 8xF [x] истинна в I. Это значит, что F [x] истинна для каждого x 2 D, т.е. :F [x] ложна для каждого x 2 D, следовательно, 9x(:F [x]) ложна в I. Таким образом, формулы принимают одинаковые истинностные значения в любой интерпретации, т.е. эквивалентны.

Для конечных областей D = fa1; : : : ; akg законы 2a); 2b) можно легко доказать используя законы де Моргана.

Для закона 2a):

:(9xF [x]) = :(F [a1] _ ¢ ¢ ¢ _ F [ak]) = = :F [a1] ^ ¢ ¢ ¢ ^ :F [ak] = 8x(:F [x]).

Для закона 2b):

:(8xF [x]) = :(F [a1] ^ ¢ ¢ ¢ ^ F [ak]) = = :F [a1] _ ¢ ¢ ¢ _ :F [ak]) = 9x(:F [x]).

3. a)8xF [x] ^ 8xH[x] = 8x(F [x] ^ H[x]),

b)9xF [x] _ 9xH[x] = 9x(F [x] _ H[x]),

т.е. кванторы 8 и 9 можно распределять по ^ и _, соответственно. Однако 8 и 9 нельзя распределять по _ и ^, соответственно, т.е.

1)8xF [x] _ 8xH[x] =6 8x(F [x] _ H[x]),

2)9xF [x] ^ 9xH[x] 6= 9x(F [x] ^ H[x]),

Докажем, например, 1).

Пусть I –произвольная интерпретация с областью D и формула 8x(F [x] _ 8xH[x]) истинна в I. Выберем конкретный элемент e1 2 D и предположим, что F [e1] истинна, а H[e1] – ложна. Далее, выберем элемент e2 2 D и предположим, что F [e2] – ложна, а H[e2] – истинна в I. Оба этих варианта не нарушают предположения об истинности 8x(F [x] _ H[x]) в I.

Но тогда 8xH[x] ложна (т.к. H[e1] ложна) в I, и 8xF [x] ложна (т.к. F [e2] ложна) в I.

Таким образом, мы нашли интерпретацию, в которой 8x(F [x]_ H[x]) истинна, а 8xF [x]_8xH[x] ложна, т.е. формулы неэквивлентны.

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

Каждую связанную переменную в формуле можно рассматривать лишь как место для подстановки какой угодно переменной (связанная переменная – “немая"). Это значит, что каждую связанную переменную можно переименовать. Заменим, например, x на z и формула 8xH[x] преобразуется в 8zH[z]. Предположим, что мы выбрали z, которая не встречается в F [x]. Тогда

8xF [x] _ 8xH[x] = 8xF [x] _ 8zH[z]

А теперь применим к каждой переменной правило 1. вынесения квантора за скобки. Получим

4.8xF [x] _ 8xH[x] = 8x8z(F [x] _ H[z]). Аналогично,

5.9xF [x] ^ 9xH[x] = 9xF [x] ^ 9zH[z] =

=9x9z(F [x] ^ H[z]).

В общем случае

6.ij1xF [x]_ij2xH[x] =ij1xij2z(F [x] _ H[z]).

7.ij3xF [x]^ij4xH[x] =ij3xij4z(F [x] ^ H[z]).

5.2.1Приведение формул к предваренной нормальной форме.

Любую формулу можно преобразовать в ПНФ, если использовать следующую последовательность эквивалентных преобразований.

1. Для исключения связок $ и ! применяем законы

F$ G = (F ! G) ^ (G ! F ),

F! G = :F _ G.

2.Для того, чтобы отрицание относилось непосредственно

катому, применяем законы

:(:F ) = F (двойное отрицание);

:(F _ G) = :F ^ :G ¾ (законы де Моргана);

:(F ^ G) = :F _ :G

:(8xF [x]) = 9x(:F [x]) ¾ [2a); 2b)]. :(9xF [x]) = 8x(:F [x])

3.Переименовываем связанные переменные, если это необходимо.

4.Используем законы вынесения кванторов в префикс.

ijxF [x] _ G =ijx(F [x] _ G), ijxF [x] ^ G =ijx(F [x] ^ G),

8xF [x] ^ 8xH[x] = 8x(F [x] ^ H[x]),

9xF [x] _ 9xH[x] = 9x(F [x] _ H[x]),

ij1xF [x] _ ij2xH[x] =ij1xij2z(F [x] _ H[z]), ij3xF [x] ^ ij4xH[x] =ij3xij4z(F [x] ^ H[z]).

З а м е ч а н и я. 1. Описанный процесс приведения к ПНФ одновременно служит конструктивным способом доказательства существования ПНФ.

2. Напомним, что в процессе приведения к ПНФ мы выполняли эквивалентные преобразования, поэтому формула, представленная в ПНФ, эквивалентна исходной формуле.