Формулы логики предикатов

Большинство определений этого параграфа будут индуктивными.

Введем понятие атомарной формулы сигнатуры Σ:

1) если t₁, t₂, T( Σ ), то t₁=t₂ ‑ атомарная формула;

2) если P⁽ⁿ⁾ Σ ‑ предикатный символ, t₁, t₂, …, t_n T( Σ ), то Р(t₁, t₂, …, t_n) ‑ атомарная формула;

3) никаких атомарных формул, кроме построенных по пп. 1, 2, нет.

Формула сигнатуры Σ определяется следующим образом:

1) атомарная формула сигнатуры Σ есть формула сигнатуры Σ;

2) если φ, ψ – формулы сигнатуры Σ, то φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), xφ, xφ – формулы сигнатуры Σ;

3) никаких формул сигнатуры Σ, кроме построенных по пп. 1, 2, нет.

Символы , , использованные в определении, называются соответственно квантором всеобщности и квантором существования и читаются " для любого" и " существует". Все соглашения относительно расстановок скобок, принятые в алгебре высказываний, остаются в силе и для формул логики предикатов. Кроме того, вместо записей x₁… x_nφ и x₁… x_nφ будем часто использовать записи x₁, …, x_nφ и x₁, …, x_nφ;.

Определим подформулы формулы φ сигнатуры Σ:

1) если φ ‑ атомарная формула, то φ ‑ ее единственная подформула;

2) если φ имеет вид φ ₁, или xφ ₁, или xφ ₁, то подформула формулы φ – это либо φ, либо подформула формулы φ ₁;

3) если φ имеет вид φ ₁∧ φ ₂, или φ ₁∨ φ ₂, или φ ₁→ φ ₂, то подформула формулы φ ‑ это либо φ, либо подформула формулы φ ₁, либо подформула формулы φ ₂;

4) других подформул формулы φ, кроме построенных по пп. 1, 2, 3, нет.

Пример 4. Пусть Σ = { F⁽²⁾, P⁽¹⁾ }, φ = x( y(x=F(z, y))∨ P(z)) ‑ формула сигнатуры Σ. Тогда x( y(x=F(z, y))∨ P(z)), y(x=F(z, y))∨ P(z),

y(x=F(z, y)), x=F(z, y)), P(z) ‑ все подформулы формулы φ;.

Говорят, что вхождение переменной х в формулу φ связано в φ, если оно находится в терме или предикате подформулы формулы φ вида xψ или xψ; в противном случае это вхождение называется свободным в φ. Переменная х называется свободной (связанной), если некоторое вхождение х в φ свободно (связано).

Пример 5. Пусть S={P₁⁽¹⁾, P₂⁽²⁾}. Рассмотрим формулы:

1) P₁(x);

2) Р₂(x, y)→ xP₁(x);
3) x(P₂(x, y)→ P₁(x)).

Переменная х в первой формуле является свободной, во второй – и свободной, и связанной, в третьей – связанной; переменная у во всех формулах свободна.

Пример 6. Выписать все подформулы формулы φ, определить все свободные и связанные переменные этой формулы:

φ x z y(x< y+z) ((z∙ 2=u)→ u(u=x+z)).

Решение. Выпишем подформулы формулы φ:

1) x< y+z,

2) y(x< y+z),

3) z y(x< y+z),

4) x z y(x< y+z),

5) z 2=u,

6) u=x+z,

7) u(u=x+z),

8) (z 2=u)→ u(u=x+z),

9) φ;.

Поскольку существуют связанные и свободные вхождения переменных х, u и z в формулу φ, то х, u и z являются связанными и свободными переменными. Переменная y связанная.

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

Запись φ (x₁, …, x_n) будет означать, что все свободные переменные формулы φ содержатся в множестве {x₁, …, x_n}.