Đề thi cuối học kỳ môn Luận lý toán học năm 2009

LUẬN LÝ TOÁN HỌC

Thời gian làm bài : 90 phút.

Thí sinh được sử dụng tài liệu và giữ lại đề thi.

1. Biểu diễn công thức x(p(x) yq(y)) ở dạng mệnh đề (clausal form) :

a. {{p(x), q(f(x))}}

c. Các câu a, b đều đúng.

b. {{p(x), q(a)}}

d. Các câu a, b đều sai.

2. Cho 2 công thức F = xy(P(f(x), y)  Q(x)) và G = xQ(x).

Chọn Z = {a, b}, g : Z  Z với g(a) = a, g(b) = b;

S : Z  {1, 0} với S(a) = 1, S(b) = 0,

R : Z² {1, 0}, R(a, a) = R(b, b) = 1, R(a, b) = R(b, a) = 0.

Diễn dịch I lấy D là Z, hàm f là g, vị từ P là R và Q là S. Đánh giá F, G trong dd I.

a. F và G là 1.

b. F và G là 0.

@c. F là 1, G là 0.

d. Các câu a, b, c đều sai.

3. Chọn công thức có giá trị sai với D là tập số nguyên tự nhiên N.

a. x y (2x − y = 0).

b. yz (y + z = 100).

c. x ((x < 10)  y (y < x  y < 9)).

d. xy (y > x  z (y + z = 100)).

4. Chọn phát biểu đúng và bao quát nếu có thể :

a. x (p(x)  y (p(y)  y = x))  xy (p(x)  (p(y)  x = y)).

b. ╞═ x p(x)  x p(x)

c. x r(x, x) ╞═ xy r(x, y).

d. Các câu a, b, c đều đúng.

5. Chọn phát biểu đúng và bao quát nếu có thể :

a. Q(y,G(A,B))

b. Older(Father(y),y)

c. Knows(Father(y),y) và

và

Q(G(x,x),y)

Older(Father(x), John) có mgu.

Knows(x,x) có mgu.

có mgu.

d. Các câu a, b, c đều đúng.

6. Công thức nào hằng đúng :

a. P  (Q  (P  Q)).

b. xy r(x, y)  x r(x, x).

c. Cả 2 câu a, b đều hằng đúng.

d. Cả 2 câu a, b đều không hằng đúng.

1

7. Chọn phát biểu đúng và bao quát nếu có thể :

a. ╞═ ((x. P(x))  (y.Q(y)))  z. (P(z)  Q(z)).

b. {P(x, z, y), P(x, z, x), P(a, x, x)} có mgu.

c. “Công thức  có giá trị sai” là phát biểu thuộc phạm vi ngữ nghĩa.

d. Các câu a, b, c đều đúng.

8. Chọn phát biểu sai :

a. “Nobody loves John” có thể được dịch là “x (loves(x, a))”.

b. “Mary doesn't love anybody” có thể được dịch là “x loves(a, x)”.

c. “Everybody loves everybody” có thể được dịch là “x loves(x, x)”.

d. Có câu sai trong 3 câu a, b, c.

. Chọn phát biểu đúng và bao quát nếu có thể :

a. .

b. .

c. .

d. Các câu a, b, c đều đúng.

. Chọn phát biểu sai :

a. .

b. .

c. .

d. Có câu sai trong 3 câu a, b, c.

. Chọn phát biểu đúng và bao quát nếu có thể :

a. .

b. .

c. .

d. Các câu a, b, c đều đúng.

. Chọn phát biểu sai :

a. .

b. .

c. .

d. Có câu sai trong 3 câu a, b, c.

Tổng cộng : 40 câu.

≤ ≥

Phát biểu nào đúng ?

(1) ╞═ x p(x)  x p(x).

(2) ╞═ x p(x)  x p(x).

2

(3) ╞═ x p(x)  x p(x). khó

(4) ╞═ x p(x)  x p(x)

(5) ╞═ xy r(x, y)  x r(x, x)

(6) ╞═ xy r(x, y)  x r(x, x)

(7) ╞═ xy r(x, y)  xy r(y, x)

(8) ╞═ x r(x, x)  xy r(x, y)

(9) ╞═ x r(x, x)  xy r(x, y)

(10) ╞═ x r(x, x)  xy r(x, y)

or

(3) x r(x, x) ╞═ xy r(x, y).

(11) ╞═ xyz((r(x, y)  r(y, x))  r(x, y))

---

Exercise 4.33 Which of the following statements hold? If a statement holds, then you

should explain why. If it does not, then you should give a counterexample.

(1) x p(x) ╞═ x p(x)

(2) x p(x) ╞═ x p(x).

(5) xy r(x, y) ╞═ x r(x, x)

(6) xy r(x, y) ╞═ x r(x, x).

(7) yx r(x, y) ╞═ xy r(x, y)

(8) xy r(x, y) ╞═ yx r(x, y).

(11) x r(x, x) ╞═ xy r(x, y).

---

Exercise 4.34 Which of the following hold?

(1) xy(r(x, y)  r(y, x)), r(a, b) ╞═ r(b, a)

(2) xy(r(x, y)  r(y, x)), r(a, b) ╞═ r(a, a)

Các câu này cho dư z ?????, 4, 5, 6 chưa xét.

(3’) xyz((r(x, y)  r(y, x))  r(x, y)), r(a, b), r(a, c) ╞═ r(b, c),

(3) xyz((r(x, y)  r(y, z))  r(x, z)), r(a, b), r(a, c) ╞═ r(b, c),

(4) xyz((r(x, y)  r(y, x))  r(x, y)), r(a, b), r(a, b) ╞═ r(a, c),

(5) xyz((r(x, y)  r(y, x))  r(x, y)), r(a, b), r(a, c) ╞═ r(b, c),

(6) xyz((r(x, y)  r(y, x))  r(x, y)), xy(r(x, y)  r(y, x)), r(a, b) ╞═ r(a, a).

---

For each pair of atomic sentences, give the most general unifier if it exists (and

indicate if both are unifyable or not):

(a) P(A,B,B); P(x,y,z)

(b) Q(y,G(A,B)); Q(G(x,x),y)

(c) Older(Father(y),y), Older(Father(x), John)

(d) Knows(Father(y),y); Knows(x,x)

---

Transform each of the following formulas to clausal form:

Biểu diễn công thức ở clausal form :

(a) x(p(x) yq(x))

*(a’) x(p(x) yq(y)) : {{p(x), q(f(x))}}, {{p(x), q(a)}}

(b) xy(zp(z)  u(q(x,u) vq(y,v)))

(c) x(yp(y) z(q(z) r(x)))

3

---

(i) Use truth tables to prove that

P  (Q  (P  Q)) is a tautology.

Consider the following formula in first-order logic:

F = xy(P(f(x), y)  Q(x))

Suppose that the following structure S is given:

D = {a, b}, {g : D  D}, {R : D2  {true, false}, S : D  {true, false}}i

where g(a) = a, g(b) = b; R(a, a) = true, R(a, b) = false, R(b, b) = true, R(b, a) = false,

S(a) = true, and S(b) = false. The function g is linked to the function symbol f, and the

predicates R and S are linked to predicate symbols P and Q, respectively. Determine

the truth value of formula F for the given structure S.

*

F = xy(P(f(x), y)  Q(x)), G = xQ(x)

Chọn Z = {a, b}, {g : D  D}, {R : D² {1, 0}, S : D  {1, 0}}

với g(a) = a, g(b) = b; R(a, a) = R(b, b) = 1, R(a, b) = R(b, a) = 0, S(a) = 1, S(b) = 0.

Diễn dịch I lấy D là Z, hàm f là g, vị từ P là R và Q là S. Đánh giá F trong diễn dịch I.

-----

CNF clauses for this problem is thus as follows:

1. HOUND(x)  HOWL(x)

2. HAV E(x, y)  CAT(y)  HAV E(x, z)  MOUSE(z)

3. LS(x)  HAV E(x, y)  HOWL(y)

4.

(a) HAV E(John, a)

(b) CAT(a)  HOUND(a)

(a) LS(John)

5.

(b) HAV E(John, b)

(c) MOUSE(b)

6. CAT(a)  HOWL(a) [1, 4(b)]

7. HAV E(x, y)  CAT(y)  HAV E(x, b) [2, 5(c)]

8. HAV E(John, y)  CAT(y) [7, 5(b)]

9. HAV E(John, a)  HOWL(a) [6, 8]

10. HOWL(a) [4(a), 9]

11. LS(x)  HAV E(x, a) [3, 10]

12. LS(John) [4(a), 11]

13.  [5(a), 12]

---

For each of the following sets of expressions, determine whether or not it is unifiable.

If a given set if unifiable, then determine a most general unifier:

(ii) {P(a, x, f(x)), P(x, y, x)}

(iii) {P(x, f(y), y), P(w, z, g(a, b))}

(iv) {P(x, z, y), P(x, z, x), P(a, x, x)}

4

(v) {P(z, f(x), b), P(x, f(a), b), P(g(x), f(a), y)}

---

Convert the following first-order sentences into sets of clauses:

(i) xy(isgrandparent(x, y)  z(parent(x, z)  parent(z, y)))

{parent(x, f(x, y))  isgrandparent(x, y), parent(f(x, y), y))  isgrandparent(x, y)}

(ii) x(bird(x)  flies(x))

(iii) xyz(person(x)  ((likes(x, y)  y ≠ z)  likes(x, z)))

(iv) x((y IsDescendant(y, x))  Root(x))

(v) x(P(a, x)  y(Q(x, y)  zR(z))).

---

Determine whether the following are valid inferences in first-order logic using

resolution:

(i) x(P(x)  Q(x)) ├─ y(Q(y)  P(y))

(ii) x(P(x)  Q(x)) ├─ x(Q(x)  P(x))

(iii) x(P(x)  Q(x)), P(a) ├─ Q(a)

(iv) x(P(x)  Q(x)), xP(x) ├─ xQ(x)

(v) x(P(x)  Q(x)), x(Q(x)  R(x)) ├─ x(P(x)  R(x))

---

Consider the following set of clauses S:

S = {P(x, f(y))  Q(y, a)  R(x), Q(g(b),w)  S(d), P(c, u), R(v)  S(d), S(z)}

with x, y, z, u, v,w universally qualified variables and a, b, c, d constants. Prove by

means of binary resolution that this set of clause S is inconsistent.

---

State whether the following are true or false, where x , y and z range over the

integers.

(a) x y (2x − y = 0)

(b) yx (2x − y = 0)

(c) x y (x − 2y = 0)

(d) x ((x < 10)  y (y < x  y < 9))

(e) yz (y + z = 100)

(f) xy (y > x  z (y + z = 100)), với x, y, z  N (số nguyên tự nhiên).

---

6. Prove that the following are equivalent:

(a) x P(x)  y (P(y)  y = x)

(b) x (y P(y)  y = x)

Công thức (a), (b) không đóng ???

---

Unify (if possible) the following pairs of predicates and give the resulting substitutions. b is a

constant. a. P(x, f(x), z),  P(g(y),f(g(b)),y) b. P(x, f(x)),  P(f(y), y) c. P(x, f(z)),  P(f(y), y)

---

3..Show that the following is a tautology of first-order intuitionistic predicate logic.

(x. P(x))  (x. P(x))

5

4. Show that the following is a tautology of first-order intuitionistic predicate logic.

x. (P(x)  y. (P(y))).

5. Show that the following is a tautology of first-order intuitionistic predicate logic.

(x. P(x))  y. P(y).

6. Show that the following is a tautology of first-order intuitionistic predicate logic.

((x. P(x))  (y.Q(y)))  z. (P(z)  Q(z)).

---

Exercise 4.4 Rephrase “x ≤ y  y ≤ z” in predicate logic, using binary relations < for

“less

than” and = for “equal”.

Exercise 4.5 Rephrase “(x ≤ y  y ≤ z)” in predicate logic, using binary relations <

for “less

than” and = for “equal”.

--

Câu nào sau đây thuộc về phạm vi ngữ nghĩa (semantic) hoặc cú pháp (syntactic).

a) X, Y là công thức LLVT, khi đó X  Y cũng là công thức LLVT.

b) Công thức “” có giá trị sai trong bảng thực trị.

True

“Nobody loves John” được dịch là “x loves(x, a)” hoặc “x (loves(x, a))”

“Mary doesn't love anybody” được dịch là “x loves(a, x)”

Mary doesn't love everybody or somebody doesn't love Mary

x (loves(a, x))  y (loves (y, a))

If Mary loves everybody then somebody doesn't love Mary and Mary loves somebody

x (loves(a, x))  y (loves(y, a))  z (loves(a, z))

False

“Everybody loves everybody” được dịch là “x loves(x, x)”

Cách tính điểm.

00  01 câu = 00 đ. 02 câu = 0.5 đ.

07  09 câu = 02 đ. 10 câu = 2.5 đ.

15  17 câu = 04 đ. 18 câu = 4.5 đ.

23  25 câu = 06 đ. 26 câu = 6.5 đ.

31  33 câu = 08 đ. 34 câu = 8.5 đ.

39  40 câu = 10 đ.

03  05 câu = 01 đ. 06 câu = 1.5 đ.

11  13 câu = 03 đ. 14 câu = 3.5 đ.

19  21 câu = 05 đ. 22 câu = 5.5 đ.

27  29 câu = 07 đ. 30 câu = 7.5 đ.

35  37 câu = 09 đ. 38 câu = 9.5 đ.

6

Đề thi cuối học kỳ môn Luận lý toán học năm 2009 - Đề gốc