Формулы логики предикатовБольшинство определений этого параграфа будут индуктивными. Введем понятие атомарной формулы сигнатуры Σ: 1) если t1, t2, T( Σ ), то t1=t2 ‑ атомарная формула; 2) если P(n) Σ ‑ предикатный символ, t1, t2, …, tn T( Σ ), то Р(t1, t2, …, tn) ‑ атомарная формула; 3) никаких атомарных формул, кроме построенных по пп. 1, 2, нет. Формула сигнатуры Σ определяется следующим образом: 1) атомарная формула сигнатуры Σ есть формула сигнатуры Σ; 2) если φ, ψ – формулы сигнатуры Σ, то φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), xφ, xφ – формулы сигнатуры Σ; 3) никаких формул сигнатуры Σ, кроме построенных по пп. 1, 2, нет. Символы , , использованные в определении, называются соответственно квантором всеобщности и квантором существования и читаются " для любого" и " существует". Все соглашения относительно расстановок скобок, принятые в алгебре высказываний, остаются в силе и для формул логики предикатов. Кроме того, вместо записей x1… xnφ и x1… xnφ будем часто использовать записи x1, …, xnφ и x1, …, xnφ;. Определим подформулы формулы φ сигнатуры Σ: 1) если φ ‑ атомарная формула, то φ ‑ ее единственная подформула; 2) если φ имеет вид φ 1, или xφ 1, или xφ 1, то подформула формулы φ – это либо φ, либо подформула формулы φ 1; 3) если φ имеет вид φ 1∧ φ 2, или φ 1∨ φ 2, или φ 1→ φ 2, то подформула формулы φ ‑ это либо φ, либо подформула формулы φ 1, либо подформула формулы φ 2; 4) других подформул формулы φ, кроме построенных по пп. 1, 2, 3, нет. Пример 4. Пусть Σ = { F(2), P(1) }, φ = 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={P1(1), P2(2)}. Рассмотрим формулы: 1) P1(x); 2) Р2(x, y)→ xP1(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 связанная. Предложением или замкнутой формулой сигнатуры Σ называется формула сигнатуры Σ, не имеющая свободных переменных. Запись φ (x1, …, xn) будет означать, что все свободные переменные формулы φ содержатся в множестве {x1, …, xn}.
|