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

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, так как формулу переменная х входит связанно, а в формулу Р(х) переменная х входит свободно.