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

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

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

2. Предметные переменные – x, y, z, …, которые пробегают значения из некоторого множества М;

x⁰, y⁰, z⁰ – предметные константы, т. е. значения предметных переменных.

3. P(·), Q(·), F(·), … - одноместные предикатные переменные;

Q(·, ·, …, ·), R(·, ·, …, ·) – n-местные предикатные переменные.

P⁰(·), Q⁰(·, ·, …, ·) – символы постоянных предикатов.

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

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

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

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

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

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

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

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

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

6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.

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

.

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

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