Определение 10. Правильно построенные формулы логики первого порядка рекурсивно определяются следующим образом:
1. Атом есть формула.
2. Если F и G – формулы, то Ш(F), (F Ъ G) , (F Щ G), (F®G), (F «G) – формулы.
3. Если F – формула, а x – свободная переменная в F, то ("x) F и ($x) F –формулы.
4. Формулы порождаются только конечным числом применений правил 1-3.
Определение 11. Терм t называется свободным для переменной x в формуле F, если ни x, ни другая произвольная переменная из t не находится в области действия никакого квантора "x или $x в F.
Пример3. Если термом является переменная y, а формула имеет вид (("y)P(y)) Щ Q(x), то y свободно для x, так как x не находится в области действия квантора по y, чего нельзя сказать в случае, если формула имеет вид ("y)(P(y) Щ Q(x)).
При этом выполняются следующие правила:
· любой терм, не содержащий переменных, свободен для любой переменной в данной формуле;
· терм свободен для любой переменной в формуле, если никакая переменная терма не является связанной в этой формуле;
· переменная x свободна для x в любой формуле;
· любой терм свободен для переменной в формуле, не содержащей свободных вхождений этой переменной.
В аксиомах ("x)F(x) ® F(t) и F(t) ®($x)F(x) t свободен для x в формуле F, F(t) получена из F(x)заменой всех свободных вхождений x на t.
Пример4: переведем в формулу утверждение «Каждый человек смертен. Конфуций – человек, следовательно, Конфуций смертен».
Обозначим «x есть человек» через P(x), а «x смертен» через Q(x). Тогда утверждение «Каждый человек смертен» может быть представлено формулой ("x) (P(x)® Q(x)), утверждение «Конфуций – человек» формулой P(Конфуций) и «Конфуций смертен» формулой Q(Конфуций).
Утверждение в целом может быть представлено формулой
("x) (P(x)® Q(x))Щ P(Конфуций) ® Q(Конфуций).
Как в логике высказываний, так и в логике предикатов, существуют два метода получения общезначимых формул: семантический, на основе интерпретации формул, и синтаксический, на основе формального вывода из аксиом и правил вывода и вспомогательных теорем.
Для исчисления высказываний существует метод построения таблиц истинности. Для исчисления предикатов этот метод либо затруднён, либо невозможен, так как область интерпретации может быть бесконечной. Если область интерпретации D={a1, a2,…,an} конечна, то
"x P(x)≡P(a1) Щ P(a2) Щ…Щ P(an);
$x P(x)≡P(a1) Ъ P(a2) Ъ …Ъ P(an).
Заменив все формулы содержащие кванторы, с помощью этих соотношений, получим формулу, не содержащую кванторы. Истинность такой формулы на конечной области проверяется с помощью конечного числа подстановок и вычислений значений истинности. Для бесконечной области этот метод непригоден.
И семантический и синтаксический метод приводят к одному и тому же результату.
Терема Гёделя о полноте исчисления предикатов.
Исчисление предикатов первого порядка – полная формальная теория.
Теорема Чёрча.
Исчисление предикатов неразрешимо.
Чтобы определить интерпретацию для формулы логики первого порядка, мы должны указать предметную область, значения констант, функций и предикатов, встречающихся в формуле.
Определение 12. Интерпретация формулы F логики первого порядка состоит из непустой (предметной) области D и указания значения всех констант, функций и предикатов, встречающихся в F.
1. Каждой константе мы ставим в соответствие некоторый определенный элемент из D.
2. Каждой n- местной функции мы ставим в соответствие отображение из Dn в D (заметим, что Dn = {(x1, x2,…,xn)з x1О D, x2О D,…, xnО D}).
3. Каждому n- местному предикату мы ставим в соответствие отображение Dnв {И, Л}.
Для каждой интерпретации формулы из области D формула может получить значение И или Л согласно следующим правилам:
1. Если заданы значения формул F и G, то истинностные значения формул Ш(F), (F Ъ G) , (F Щ G), (F®G), (F «G) получаются с помощью таблиц истинности соответствующих логических связок.
2. ("x) F получает значение И, если F получает значение И для каждого x из D , в противном случае она получает значение Л.
3. ($x) F получает значение И, если F получает значение И хотя бы для одного x из D , в противном случае она получает значение Л.
Отметим, что формула, содержащая свободные переменные, не может получить истинностное значение. Поэтому, в дальнейшем, будем считать, что формула либо не содержит свободных переменных, либо свободные переменные рассматриваются как константы.
Пример 5. Рассмотрим формулы ("x) P(x) и ($x) ШP(x).
Пусть интерпретации такова: область - D={1,2};
Оценка для P :P(1) =И, P(2) =Л.
В таком случае ("x) P(x) есть Л, а ($x) ШP(x) есть И в данной интерпретации.
Следовательно, в указанной интерпретации, для каждого x из D существует такой y, что P(x, y)=И, то есть ("x) ($y) P(x, y) есть И в данной интерпретации.
Определение 12: Формула G называется непротиворечивой (выполнимой) в данной интерпретации, если при некоторой подстановке констант в G, она превращается в истинное высказывание. В противном случае она называется невыполнимой (противоречивой, ложной) в данной интерпретации.
Определение 13: Формула G называется истинной в данной интерпретации, если она превращается в истинное высказывание при любой подстановке констант.
Определение 14: Формула G истинная в любой интерпретации, называется тождественно истинной, общезначимой или тавтологией.
Определение 15: Формула G ложная в любой интерпретации, называется тождественно ложной, противоречивой или невыполнимой.
Определение 16: Формула G есть логическое следствие формул F1, F2,…, Fnтогда и только тогда, когда для каждой интерпретации I, если F1Щ F2Щ…Fnистинна в I, то G также истинна в I.
Пример 7. Рассмотрим формулы:
F1: ("x) (P(x)® Q(x)),
F2: P(a).
Докажем, что Q(a) есть логическое следствие формул F1 и F2.
Рассмотрим любую интерпретацию I, в которой "x(P(x)® Q(x))Щ P(a) является истинной. Конечно, в этой интерпретации P(a) есть И. Пусть Q(a) есть Л в данной интерпретации, тогда P(a)® Q(a) есть Л в данной интерпретации по определению операции импликации. Это значит, что "x (P(x)® Q(x)) есть Л в I, что невозможно. Следовательно, Q(a) должна быть И в каждой интерпретации, которая удовлетворяет "x (P(x)® Q(x))Щ P(a). Это означает, что Q(a) есть логическое следствие из F1 и F2.
Определение 17: Формулы называются эквивалентными, если при всех подстановках констант (при всех интерпретациях) они принимают одинаковые значения. В частности, все общезначимые (тождественно истинные) и все противоречивые (тождественно ложные формулы) эквивалентны.
Утверждение 8. Докажем эквивалентность следующих формул:
Ш(($x) P(x))º("x) (ШP(x)).
Доказательство:
Если правая часть истинна, то для любого x истинна ШP(x), то есть ложна P(x), а значит, не найдётся x, при котором истинна P(x), следовательно, истинно высказывание Ш$x P(x).
Если правая часть ложна, то найдётся x=a такое, что P(a) истина, следовательно, существует x, при котором истинна P(x), и значит, Ш$x P(x) ложна.
