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

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

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

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

2. если P⁽ⁿ⁾Σ ‑ предикатный символ,t₁,t₂,…,t_nT(Σ), то Р(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. Выписать все подформулы формулыφ, определить все свободные и связанные переменные этой формулы:

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

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

1. x<y+z,

2. y(x<y+z),

3. zy(x<y+z),

4. xzy(x<y+z),

5. z2=u,

6. u=x+z,

7. u(u=x+z),

8. (z2=u)→u(u=x+z),

9. φ.

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

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

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