Упражнения. 1. Что соответствует в естественном языке терму ЯЛП?

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)

Договоренность Пусть a1, a2,…,an – какие-то предметные переменные (х, х1, у, у2, у1 и т.п.) и А – какая-то формула. Вместо "a1"a2…"an А будем писать "a1, a2,…, an А. Вместо $a1$a2…$an А будем писать $a1, a2,…, an А. Например, вместо "x"x4"y (Р(x,y) Ú S(х4,у) É Q(х,х4)) будем писать "x,x4,y(Р(x,y) Ú S(х4,у) É Q(х,х4)).

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

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