На этом шаге мы рассмотрим формулы логики предикатов первого порядка.
Формулы логики предикатов первого порядка рекурсивно определяются следующим образом:
- атом есть формула;
- если A и B - формулы, то ~A, AÙB, AÚB, A® B, A«B - тоже формулы;
- если A(x) - есть формула, а x - свободная переменная в A(x) , то ("x)A(x) и ($x)A(x) - тоже формулы;
- других формул, кроме составленных с помощью правил (1) - (3), нет.
Язык изучают с помощью языка исследователя - метаязыка. В нем могут использоваться различные знаки, не входящие в алфавит изучаемого языка - метасимволы. Мы будем использовать различные метасимволы, в том числе A, B, C, ..., E, A1, A2, A3, ... (большие буквы латинского алфавита с индексами или без них) - для обозначения произвольных формул, x,y,z - для обозначения произвольных предметных переменных, t, t0, t1,. .. - произвольных термов и так далее.
Для упрощения записи формул в метаязыке используют те или иные соглашения. Будем считать, что можно опустить все те скобки, которые будут восстановлены при выполнении следующей процедуры: запись просматриваем слева направо и вокруг каждого очередного вхождения знака Ù расставляем пару скобок так, чтобы подслово, в котором эти скобки служат началом и концом соответственно, являлось формулой, причем возможно более длинной; затем ту же операцию повторяем для связок Ú, ® (именно в этом порядке!).
Под интерпретацией формул в логике высказываний понимают операцию приписывания входящим в формулу атомам значений И ("истина") и Л ("ложь").
Интерпретация формулы в логике предикатов первого порядка - это задание области значений переменных и присвоение значений всех констант, функциональных и предикатных символов, встречающихся в этой формуле, в соответствии со следующими правилами:
- каждой константе ставится в соответствие некоторый элемент из области значений переменных D;
- каждому n-местному функциональному символу ставится в соответствие отображение элемента из Dn в D, где Dn ={(x1, x2, ..., xn) | x1Î D, ..., xnÎD};
- каждому n-местному предикатному символу ставится в соответствие отображение элемента из Dn в {И,Л}.
Когда мы определяем истинностное значение формулы на области D, то "x и $x интерпретируются как "для всех элементов x из Dn" и "существует элемент x из Dn" соответственно.
Формула, интерпретируемая на области D, принимает значение И или Л согласно следующим правилам:
- если заданы значения формул A и B, то истинностные значения формул ~A, AÙB, AÚB, A®B, A«B получают по таблице истинности, которая справедлива так же и для логики предикатов первого порядка;
- формула ("x)A(x) получает значение "истина", если A(x) - "истина" для каждого x из D; в противном случае (("x)A(x)) получает значение Л;
- формула ($x)A(x) получает значение И, если A(x) - И хотя бы для одного x из D; в противном случае (($x)A(x)) получает значение Л.
Приписывая формуле истинностные значения, предполагают, что она либо не содержит свободных переменных, либо свободные переменные рассматриваются как константы.
Семантическая классификация формул. В логике предикатов первого порядка, как и в логике высказываний, используются понятия общезначимости, противоречивости, выполнимости формул, а так же логического следствия, поэтому ее можно рассматривать как расширение логики высказываний, а формулу в логике предикатов первого порядка, не содержащую переменных и кванторов - как формулу в логике высказываний.
В логике предикатов первого порядка формула является:
- общезначимой тогда и только тогда, когда не существует никакой интерпретации, при которой формула принимает значение "ложь";
- противоречивой тогда и только тогда, когда не существует никакой интерпретации, при которой формула принимает значение "истина";
- выполнимой тогда и только тогда, когда существует хотя бы одна такая интерпретация, что формула принимает значение "истина".
Формула A есть логическое следствие формул B1, B2, ..., Bn тогда и только тогда, когда для любой интерпретации, если B1ÙB2Ù ...Ù Bn истинна при этой интерпретации, то A так же истинна.
На следующем шаге мы рассмотрим предваренную нормальную форму формулы.
