Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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





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

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

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

2) если P(n) Σ ‑ предикатный символ, t1,t2,…,tn T(Σ), то Р(t1,t2,…,tn) ‑ атомарная формула;

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

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

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

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

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

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

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

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

2) если φ имеет вид φ1, или 1, или 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ψ; в противном случае это вхождение называется свободным в φ. Переменная х называется свободной (связанной), если некоторое вхождение х в φ свободно (связано).

Пример 5. Пусть S={P1(1),P2(2)}. Рассмотрим формулы:

1) P1(x);

2) Р2(x,y)→ xP1(x);
3) x(P2(x,y)→P1(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}.






Дата добавления: 2014-11-10; просмотров: 449. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.008 сек.) русская версия | украинская версия