2.3.2 Правила построения формул в исчислении предикатов

Определение 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(Конфуций).

2.3.3 Интерпретация формул в логике предикатов первого порядка.

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

Для исчисления высказываний существует метод построения таблиц истинности. Для исчисления предикатов этот метод либо затруднён, либо невозможен, так как область интерпретации может быть бесконечной. Если область интерпретации D={a₁, a₂,…,a_n}конечна, то

"x P(x)≡P(a₁) Ù P(a₂) Ù…Ù P(a_n);

$x P(x)≡P(a₁) Ú P(a₂) Ú …Ú P(a_n).

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

И семантический и синтаксический метод приводят к одному и тому же результату.

Терема Гёделя о полноте исчисления предикатов.

Исчисление предикатов первого порядка – полная формальная теория.

Теорема Чёрча.

Исчисление предикатов неразрешимо.

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

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

1. Каждой константе мы ставим в соответствие некоторый определенный элемент из D.

2. Каждой n- местной функции мы ставим в соответствие отображение изDⁿвD(заметим, чтоDⁿ = {(x₁, x₂,…,x_n)ç x₁Î D, x₂Î D,…, x_nÎ D}).

3. Каждому n- местному предикату мы ставим в соответствие отображениеDⁿ в {И, Л}.

Для каждой интерпретации формулы из области 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) есть И в данной интерпретации.

Пример 6. Рассмотрим формулы ("x)($y) P(x, y).

Пусть интерпретации такова: область - D={1,2};

Оценка для P: P(1,1) =И, P(1,2) =Л, P(2,1) =Л, P(2,2) =И.

При x=1 существует y=1, что P(x, y) =И.

При x=2 существует y=2, что P(x, y) =И.

Следовательно, в указанной интерпретации, для каждого x из D существует такой y, что P(x, y)=И, то есть ("x)($y) P(x, y) есть И в данной интерпретации.

Определение 12: ФормулаGназываетсянепротиворечивой (выполнимой) в данной интерпретации, если при некоторой подстановке констант вG, она превращается в истинное высказывание. В противном случае она называетсяневыполнимой (противоречивой, ложной) в данной интерпретации.

Определение 13: ФормулаG называетсяистинной в данной интерпретации, если она превращается в истинное высказывание при любой подстановке констант.

Определение 14: ФормулаGистинная в любой интерпретации, называетсятождественноистинной, общезначимой или тавтологией.

Определение 15: ФормулаGложная в любой интерпретации, называетсятождественноложной, противоречивой или невыполнимой.

Определение 16: ФормулаGестьлогическое следствиеформулF₁, F₂,…, F_n тогда и только тогда, когда для каждой интерпретации I, если F₁ ÙF₂ Ù…F_n истинна в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) ложна.

Таким образом, эти формулы эквивалентны.