Логика предикатов. Понятие формулы логики предикатов

В логике предикатов используется следующая символика:

1. Символы р, q, r,... – переменные высказывания, принимающие два значения: 1 – истина, 0 – ложь.

2. Предметные переменные – х, у, z,..., которые пробегают значения из некоторого множества М: х0, у0, z0,... – предметные константы, то есть значения предметных переменных.

3. Р(·), F(·) – одноместные предикатные переменные; Q(·,·,...,·), R(·,·,...,·) – n-местные предикатные переменные. Р0(·), Q0(·,·,…,·) – символы постоянных предикатов.

4. Символы логических операций:.

5. Символы кванторных операций:.

6. Вспомогательные символы: скобки, запятые.

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

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

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

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

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

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

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

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

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

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