Задачи.

1. Доказать или опровергнуть равносильность формул:

а) Ø$ х A(х) º " xØ A( x); б) " x A(х)&B º " x(A( x) & B); в) B&" x A(х) º " x(B&A( x)); г) BÚ" x A(х) º " x(BÚ A( x)); д) " x A(х)ÚB º " x(A( x)ÚB); е) $ x A(х)ÚB º $ x(A( x)Ú B);

ж) BÚ$ x A(х) º $ x(BÚA( x)); з)" x A(х)® B º $ x(A( x) ®B);

и)B®" x A(х) º"x(B®A( x)); к) $ x A(х)® B º " x(A(x)®B); л) B®$ x A(х) º $ x(B ® A( x)); м) $ x A(х) º " xA( x) .

2. Доказать неравносильность формул "x$y A(х,y) и $y"x A(x,y).

5.5 Аксиоматическое построение ЛП. Исчисление предикатов

В ИВ формальный аксиоматический подход ненамно-го расширяет возможности при анализе высказываний, по-скольку там есть такое мощное средство проверки истин-ности формул, как таблицы истинности. Поскольку в ЛП рассматриваются высказывания, применимые для произ-вольных предметных множеств и произвольных преди-катов, то такой метод проверки здесь не применим в силу того, что нельзя описать все возможные наборы перемен-ных и логических функций (предикатов), входящих в фор-мулы. Поэтому здесь значение аксиоматического метода значительно возрастает.

Как и в алгебре логики, формальное аксиоматическое построение в ЛП называется исчислением предикатов (ИП).

Принципы задания ИП те же, что и у ИВ. При выборе аксиом {A} можно принять

а) систему независимых аксиом, содержащую минимальное их количество, либо

б) расширенную систему аксиом, позволяющую упростить проверку истинности конкретных формул.

Рассмотрим наиболее известные примеры формаль-ного аксиоматического построения ИП. Обозначения пред-метных переменных, констант и функциональных перемен-ных, термов и предикатов не влияет на содержание теории, поэтому их опускаем. Поэтому перечислим только сущест-

венные признаки систем.

Рассмотрим построение ИП по Э.Мендельсону.

I.Множество логических связок {f} = {Ø, ®}.

II. В определении формул по сравнению с ЛП должно быть

учтено более узкое множество логических связок. Их вво-

дят следующим образом:

1. Если (t₁ , ..., t_k) - термы, (х₁ , ..., х_m) - множество пере-менных, входящих в них, а Р- предикатная переменная, то Р( t₁ , ..., t_k ) - назовем элементарной формулой или атомом, а (х₁ , ..., х_m ) - его свободными переменными.

2. Если А и В - формулы, то выражения вида F = А®В, F = ØА тоже являются формулами. Свободные переменные формул А и В являются свободными переменными формулы F.

3.Если А - формула со свободными переменными (х₁,...,х_m ), то выражения вида F =" х_i А(х₁ , ..., х_m ), F =$ х_i А(х₁ , ..., х_m ) - тоже являются формулами, в которых переменная х_i связана, соответственно, кванторами " и $ , а переменные (х₁ , ..., х_m ) \ х_i -свободны в F.

III.Множество аксиом А₁, А₂, А₃, А₄, А₅ = {A} следующее: