Упражнения. Примеры неправильно построенных выражений (не термы и не формулы)

Примеры неправильно построенных выражений (не термы и не формулы)

Примеры составных формул

Примеры атомарных формул

^

P¹(a) (читается «Р от а»; подразумевается объект а обладает свойством Р)

P¹(x)

P¹(f¹(а)) (читается «Р от f от а»; подразумевается объект, сопоставленный объекту а функцией f, обладает свойством Р)

R²(x,a) (читается «R от х, а»; подразумевается свойство находится в отношении R с объектом а)

R²(y,y)

R²(y₁₁,y)

R³(f¹(c), f¹(a), a)

R³(f¹(c), f¹(a), h²(y,z))

a=b

f¹(a)= h¹(h¹(с))

f¹(a)= h¹(g²(y,z))

Примеры термов и формул

$xP(x)

$x(P(x)&Q(x)) (главный знак - $)

$xP(x)&Q(x) (главный знак - &)

"y"zQ(z,f¹(y)) (главный знак – квантор "y)

Ø"y"zQ(z,y) (главный знак - Ø)

"x$yR(x,y)Ú"y"zQ(z,y) (главный знак - Ú)

"x($yR(x,y)Ú"zQ(z,x)) (главный знак - квантор "x)

ØR(x,y)ÚQ(z,x) (главный знак - Ú)

Ø (a=b Ú c=b) Éa ¹b (главный знак - É)

1. х&у. Ошибка: х и у – термы, а связка & (так же, как Ú, É, º), могут связывать только формулы.

2. f¹(Q¹(a)). Ошибка: после одноместного функционального символа (f¹) должен стоять один терм, а в нашем случае в скобках стоит формула - Q¹(a).

3. Øх & Øу. В этой записи два неправильно построенных выражения – Øх, Øу – соединены конъюнкцией. Øх – неосмысленная запись, поскольку в нашем языке отрицание может относится к структуре предложения (формуле), а не к терму (х - терм). То же с Øу.

4. P²(Q¹(a),S¹(a)). Ошибка: после символа двухместного предиката (P²) в скобках должны находиться два терма, а в нашей записи стоят две формулы (Q¹(a) и S¹(a)).

5. ∀x. Кванторы используются только при построении формулы, но в составе формулы в обязательном порядке должны присутствовать а) предикатные символы(Pⁿ, Qⁿ, Rⁿ, Sⁿ, P₁ⁿ и т.д.), либо б) выделенный предикатный символ равенства, либо в) логические константы (^, Т). В нашей записи их нет.

6. ∀x É ∃y. Слева и справа от импликации должны стоять формулы, а в примере 6 слева и справа от знака É стоят не формулы, а неправильно построенные выражения (см. предыдущий пример).

7. ∀xР¹(х) É ∃yР¹(∃х). Плохое место: Р¹(∃х). В скобках после одноместного предиката Р¹ должен стоять аналог имени – терм, а ∃х - не терм (в состав термов не входят кванторы). Если убрать из примера 7 символ квантора существования, тогда получим формулу ∀xР¹(х)É∃yР¹(х).

8. Р(а)=Р(с). Ошибка: символ равенства связывает термы, а в этом примере слева и справа от равенства стоят формулы.

9. $x"yR(x,y)ÉØ$y"аØR(x,а). Ошибка: запись "а невозможна, после квантора сразу должна идти переменная (x, y, z, x₁, y₁, z₁, x₂ и т.д.), а не константа (а – индивидная константа)[2].

10. Ø$y"ØR(x,у). Ошибка: после квантора общности (") нет переменной.

1. Что соответствует в естественном языке терму ЯЛП? Что формуле?

2.Определите, являются ли следующие последовательности символов осмысленными (правильно построенными) выражениями ЯЛП¹ (то есть термами или формулами). Там, где не указана местность функтора или предиката, считайте, что она та, которая и требуется записью (Например, в Р(х) Р – одноместный предикат, а в Р(а,у) - двухместный).

1. ⁺ xy

2. ⁺ (x,y)

3. ⁺ P²(x&y)

4. ⁺ Øа

5. ⁺ h³(g¹(f²(a,b)))

6. ⁺ ∀x(R(x)⊃∃y(P(y)&Q(x,y)))

7. a

8. x

9. f²(x,x)

10. x₁₈₂₄

11. f²(h²(a,b))

12. h¹(f²(a, h¹(z)))

13. f²h¹(a)

14. f¹(P¹(a))

15. f¹(a)& f¹(c)

16. P(z₁)

17. $P(x)

18. P(x,х)

19. "х f¹(x)

20. "х f¹(x)=h¹(h¹(x))

21. "aP(a)

22. P(a)

23. y¹(x)

24. Q²

25. Q¹("х)

26. ØR(x,y)

27. $xP(a)

28. Ø"xØ"y R(x,y)

29. $y(Q¹ É Р¹)

30. P¹(Q¹(a))

31. Ø $x"yÉ "хØ$y

32. $x"yR(x,y)ÉØ$y"xØR(x,y)

3. Укажите граф, соответствующий процедуре построения данного терма / формулы.

а) g(a, f(b))

б) Ø$x "y R(x,y) É"х$уØR(x,y)

в) $x(R(x) & "у(ØR(x,y)Ú ØR(x,y))

4. Укажите логические и нелогические константы, входящие в состав данных формул.

(а) P (x,c)

(б) "x P (x,c)

(в) "x P (x,c)É^

(г) Ø (Т º (∀x∃y((R(x) & R(y)) É Q(x,y)))

(д) $x("yQ(b,c,y) º R(x,y))Ú("z (Q (z) º R(z,b)))

Область действия кванторов. Свободные и связанные вхождения переменных в формулу. – см. лекцию

5. Укажите область действия каждого квантора в следующих формулах.

(а) "x P (x,c) ÉR(x)

(б) "x (P (x,c) ÉR(x))

(в) $x("yQ(y)ÉR(x,y))Ú("zQ(z)ÚR(z,x))

(г) ⁺ "x(P(x,y₁)º$yQ(y,x))&"z(R(x,y)ºR₁(y, x))

Зачем различать свободные и связанные вхождения переменных в формулу? Свободные вхождения переменных можно заменять на имена объектов, а для связанных вхождений такая замена – незаконна, бессмысленна. Пример Рассмотрим два выражения (записанные в прикладном языке арифметики) (1) x+y=7 (2) $х$у x+y=7.   Выражение (1) ни истинно, ни ложно. Все зависит от того, что мы припишем в качестве значений переменным х и у (какими числами их заменим, точнее – именами каких чисел). Выражение (2) уже есть (истинное) предложение (оно утверждает, что есть такие 2 (допустим, натуральных) числа, сумма которых есть число 7). Замена переменных на имена конкретных объектов в этом случае бессмысленна.

6. Определить, какие вхождения переменных являются свободными, а какие связанными в следующих формулах:

а. "x P (x,c)

б."x (P(x)ÉQ(y))

в. $x("yQ(y)ÉR(x,y))Ú("z Q (z)ÚR(z,x))

г. "x(P(x,y)É$yQ(y,z,x))

д. ⁺ "x(P(x,y)ºQ(y,x))&"z(R(x,y)ºR₁(y, x))

е. ⁺ $x(P(x)ºQ(y))

ж. ⁺ "x$y(P(x,y)ºQ(y,x))&"x"y(R(x,y)ºR₁(y, x))

Формула ЯКЛП называется замкнутой или предложением, е.т.е. она не содержит свободных переменных.

Термин предложение употребляется, таким образом, в двух смыслах: предложение естественного языка и предложение (формального) языка логики предикатов (= формула без свободных переменных)

7. Какие из следующих формул являются предложениями ЯКЛП?

a. P¹(x)

b. P¹(a)

c. $xP¹(x)

d. Q²(c,y)

e. Q³(a₂,a₂,c)

f. $x(P¹(x)& Q²(c,y))

g. $y(P¹(y)& Q²(c,y))É ($yR¹(y)& Q²(c,y))

h. "x"x₄"y((R(x₄)& R(x)& R(y))ÉØQ³(x,y,x₄))

i. "x"x₄"y(R(x₄)& R(x)& R(y))ÉØQ³(x,y,x₄)

j.⁺ $z"x(R²(x,z)ºQ²(x,x))ÉØQ³(x,z,z)

Договоренность Пусть a₁, a₂,…,a_n – какие-то предметные переменные (х, х₁, у, у₂, у₁ и т.п.) и А – какая-то формула. Вместо "a₁"a₂…"a_n А будем писать "a₁, a₂,…, a_n А. Вместо $a₁$a₂…$a_n А будем писать $a₁, a₂,…, a_n А. Например, вместо "x"x₄"y (Р(x,y) Ú S(х₄,у) É Q(х,х₄)) будем писать "x,x_4,y(Р(x,y) Ú S(х₄,у) É Q(х,х₄)).

Тема 2: От выражений естественного языка к их структуре: перевод выражений естественного языка на ЯКЛП

Перевод выражений естественного языка на ЯКЛП:

Дата добавления: 2014-12-27