Определение формулы логики предикатов

1.Каждое высказывание как переменное, так и по­стоянное, является формулой.

2. Если F (·,·,...,·) – n -местная предикатная перемен­ная или постоянный предикат, а x ₁, х ₂,..., х_n – предмет­ные переменные или предметные постоянные, не обяза­тельно все различные, то F (x ₁, х ₂,..., х_n) есть формула. В этой формуле предметные переменные являются свобод­ными. Формулы вида 1 и 2 называются элементарными.

3. Если A и B – формулы, причем такие, что одна и та же предметная переменная не является в одной из них свя­занной, а в другой свободной, то слова есть формулы. В этих формулах те переменные, которые в ис­ходных формулах были свободными, являются свободны­ми, а те, которые были связанными, являются связанными.

4. Если А – формула, то – формула, и характер предметных переменных при переходе от формулы А к формуле не меняется.

5. Если А (х) – формула, в которую предметная пере­менная х входит свободно, то слова и являются формулами, причем предметная переменная в них входит связанно.

6. Никакая другая строка символов формулой не является.

Например, если Р (x) и Q (х,у) – одноместный и двухме­стный предикаты, а q, r – переменные высказывания, то формулами будут слова:

Не является формулой слово: . Здесь нарушено условие п.3, так как в формулу переменная х входит связано, а в формулу Р (х) переменная х входит свободно.

Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.

Пример 1. Какие из следующих выражений явля­ются формулами логики предикатов? В каждой форму­ле выделите свободные и связанные переменные.

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

Решение. Выражения 1), 2), 4), 6) являются форму­лами, так как записаны в соответствии с определением формулы логики предикатов. Выражения 3) и 5) не яв­ляются формулами. В выражении 3) операция конъюн­кции применена к формулам P (x) и ; в первой из них переменная х свободна, а во второй связана кванто­ром общности, что противоречит определению форму­лы. В выражении 5) квантор существования по перемен­ной у навешен на формулу , в которой перемен­ная у связана квантором общности, что также противо­речит определению формулы.

В формуле 1) переменная у свободна, а переменные х и z связаны. В формуле 2) нет предметных переменных. В формуле 4) переменная х связана, а переменная у свободна.