Đề thi cuối kỳ môn Luận lý toán học năm 2008 - Mã đề 0101
LUẬN LÝ TOÁN HỌC
49,51,56Thời gian làm bài : 90 phút.
0101
Mã số đề
Thí sinh được sử dụng tài liệu và giữ lại đề thi.
1*. = <R, F, C> với R = {p(_)}, F = {s(_), m(_,_)}, C = {}.
Diễn dịch I : D = {word | word là từ trên tập ký tự {0, 1}}, I() = 10.
I(s) là hàm endcut bỏ ký tự cuối của từ, thí dụ endcut(111001) = 11100.
I(m) là hàm mix kết nối xen kẻ 2 từ, thí dụ mix(000, 11111) = 01010111.
I(p) là vị từ cir, cir(x) đúng nếu x là tuần hoàn có chiều dài chẵn, thí dụ 10, 01,
1010, 0101, ... Nếu x = 0011 thì I(m(s() + s(x))) = ?, I(p(m(s() + s(x))) = ?.
a. 0101, đúng.
c. 1010, đúng.
@b. 1001, sai.
d. 0011, sai.
2*. <R, F, C> có các thành phần như sau :
R = {ptrên(_,_), ptròn(_), pvuông(_), pthoi(_)}, F = {fnón(_)}.C = {cMinh}.
Cho 1 diễn dịch I : D = {▲, , , },
cMinh =▲.
ptrên = {(, ▲), (, )}, ptròn = {}, pvuông = {}, pthoi = {, }.
fnón = {(▲, ), (, ), (, ), (▲, )}
E = x (pvuông(x) ptròn(x)), F = x y (ptrên(x, y) ptrên(y, x)).
Đánh giá E, F trong diễn dịch I.
a. E đúng, F đúng.
@c. E sai, F đúng.
b. E đúng, F sai.
d. E sai, F sai.
3*. Chọn phát biểu đúng và bao quát nếu có thể :
a. {p(f(x)) r(z)} ở dạng chuẩn Skolem.
b. ╞/═ (xH) H[a/x] , với H là công thức, a là hằng.
c. x y(p(x) q(b,y)) ở dạng chuẩn Prenex.
@d. Các câu a, b, c đều đúng.
4*. F= ((P (Q R)) (Q R)) P,và G = ((P Q) R) (R (Q P))
Các từ viết tắt hđ = hằng đúng, kđ = khả đúng, hs = hằng sai, ks = khả sai.
a. F hđ, G hđ.
b. F kđks, G kđks.
@c. F hđ, G kđks.
d. F hs, G hs.
5*. Câu nào ở dạng chuẩn Skolem :
a. {p(x) q(y), p(f(x)) r(z)}
b. {p(a) xq(x)}
1
c. {p(x) q(b) x y}
@d. Các câu a, b, c đều sai.
6*. A = p(f(x)) r(a), B = p(f(a)) r(x), C = p(f(x)) r(z), D = p(x) r(z),
pgb(A, B) = K, pgb (C, D) = H. (Ghi chú : không phân giải nhị phân được = kpgđ)
a. K = , H = r(z)
b. K = , H =kpgđ
@c. K = hằng đúng, H = kpgđ d. K = hằng đúng, H = r(z)
7*. Chọn phát biểu sai :
s. Hệ thống là một công thức gồm hội các thành phần của hệ thống.
d. Có thể dùng thuật toán hằng sai để kiểm tra tính hằng đúng của 1công thức.
d. ╞═ x (H H[a/x]), H là công thức, a là hằng.
d. Có câu sai trong 3 câu a, b, c.
8*. Chọn phát biểu đúng :
d. Dạng chuẩn Skolem S của F còn tương đương với F theo nghĩa hằng sai.
d. mgu của {p(x, f(x, g(x)), y), p(a, z, g(w))} là = a/x, f(a, g(a))/z, , g(w)/y
d. Hai công thức tương đương nếu có cùng tập các mô hình.
d. Câu a, b, c đều đúng.
9*. Chọn phát biểu đúng và bao quát nếu có thể :
s. (F ├─ H) là công thức hằng đúng với F, H là công thức LLMĐ.
s. Luận lý vị từ chấp nhận dạng hội, giao vô hạn các công thức.
s. Phạm vi của (x) là p(x) trong công thức (y)(r(y)) (x)(p(x) q(z)).
d. Có câu sai trong 3 câu a, b, c.
10*. Chọn phát biểu đúng và bao quát nếu có thể :
s. Qui tắc (i) còn gọi là Modus ponens.
s. Công thức hằng sai có ít nhất một mô hình.
s. Một dạng chuẩn Skolem của F : SF = {p(a, b, f(y)) q(y), h(y, z)}.
d. Công thức F (G F) là khả đúng khả sai, với F, G là công thức.
11*. Chọn phát biểu đúng và bao quát nếu có thể :
d. Định lý (soundness). Nếu F├─ H thì F╞═ H.
s. Hợp nối 2 thay thế có tính phối hợp.
s. Dạng chuẩn Skolem S của F còn tương đương với F.
s. Câu a, b, c đều đúng.
12*. Chọn phát biểu đúng và bao quát nếu có thể :
s. Thuật toán hằng sai cho kết quả yes với F và yes với F. Vậy Fhằng sai.
s. DC Prenex của x(y(p(x) r(y)) z q(z)) là xyz ((p(x) r(y))
q(z))
s. Hệ thống mâu thuẫn là khả sai, khả đúng.
2
d. Có câu sai trong 3 câu a, b, c.
13*. Chọn phát biểu sai :
d. Qui tắc (i) : dòng 1: if F, dòng 1+k : nif FG, dòng 2+k : FG.
d. Một công thức hằng sai nếu phân giải ra được mệnh đề hằng sai ().
d. xy (p(x) q(y)) = yx (p(x) q(y)).
d. Hàm là ánh xạ từ Dn vào D của miền đối tượng D, với n 0.
14*. Chọn phát biểu sai :
d. Dạng chuẩn Prenex vẫn tương đương với công thức ban đầu.
d. Đoạn chứng minh sau : dòng 1 : if x0, dòng n : nif q(x0), dòng n+1 : x q(x)
sử dụng qui tắc i.
d. (P Q R) ở dạng chuẩn hội.
d. Có câu sai trong 3 câu a, b, c.
15*. Chọn phát biểu đúng và bao quát nếu có thể :
d. Dòng A=0, B=1, F= 1 của bảng thực trị được biểu diễn ở dạng {A, B, F}.
d. Công thức A hằng đúng nên A khả sai.
d. Thừa số của 1 công thức là kết quả của công thức qua tác động của 1 mgu.
d. Unifier là mgu của {E1, ..., Ek} nếu ( unifier )( thay thế ) ( = ).
16*. Chọn phát biểu đúng và bao quát nếu có thể :
d. Công thức khả sai nếu có ít nhất một mô hình.
d. Mệnh đề rỗng là công thức vừa hằng sai vừa hằng đúng.
d. Định lý completeness. Nếu F├─ H thì F╞═ H.
d. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
17*. Chọn phát biểu đúng và bao quát nếu có thể :
d. pg(F, G) ╞═ F G.
d. Công thức đóng là công thức có ít nhất 1 biến có tất cả hiện hữu ràng buộc.
d. Biểu thức vị từ là giá trị đúng sai của vị từ trong thế giới thật.
d. Luận lý mệnh đề không chấp nhận dạng hội, giao vô hạn các công thức.
18*. Chọn phát biểu đúng và bao quát nếu có thể :
d. Từ dòng m : F, viết ra dòng m+k : F (G H) là áp dụng qui tắc i.
d. ├─ F F còn gọi là qui tắc suy luận triệt tam (LEM).
d. p(x) r(f(a)) có f(a) là một nguyên từ.
d. Câu a, b, c đều đúng.
19*. Chọn phát biểu đúng và bao quát nếu có thể :
d. G = p(x) p(f(y)) là một thừa số của T = p(x) r(y) p(f(y)) r(y).
d. Mô hình của 1 công thức là diễn dịch mà công thức được đánh giá trong đó.
d. Công thức hoàn hảo chỉ là công thức nguyên.
3
d. Qui tắc e, dòng 1 : F G, dòng 2 : if F, dòng 2+m : nif H, dòng 3+m : if
G, dòng nif 3+m+n : H, dòng 4+m+n : H.
20*. Chọn phát biểu đúng và bao quát nếu có thể :
d. F ╞═ H nếu tập mô hình của H là tập con của tập mô hình của F.
d. Hằng không là nguyên từ.
d. Công thức G = (xy (p(x) q(y))) ở dạng chuẩn Prenex.
d. y x K ╞/═ x y K.
21*. Chọn phát biểu đúng và bao quát nếu có thể :
d. F và dạng chuẩn Skolem của F tương đương nhau.
d. Mệnh đề trong LLVT là giao các lưỡng nguyên.
d. pg(p(x) q(f(y)), q(a) r(x)) = p(x) r(x).
@d. Có câu sai trong 3 câu a, b, c.
22*. Chọn phát biểu đúng và bao quát nếu có thể :
d. (F G) F là công thức hằng sai.
d. Biểu thức vị từ là nguyên từ.
d. DC Prenex của x ( z r(x,z) x p(x) ) là x z t (r(x,z) p(t))
d. Các câu a, b, c đều sai.
23*. Chọn phát biểu sai :
d. Hệ thống mâu thuẫn là hằng sai.
d. Từ dòng m : F, viết ra dòng m+k : F (G H) là áp dụng qui tắc i.
d. Công thức hằng đúng nếu mọi diễn dịch là mô hình.
d. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
24*. Chọn phát biểu sai :
d. Luận lý mệnh đề là logic ở cấp độ câu. Vị từ là logic ở cấp độ đối tượng.
d. Chứng minh là 1chuỗi công thức được tạo từ tiền đề hoặc qui tắc suy luận.
d. Công thức nguyên cũng là công thức.
d. p(x) r(f(a)) là một nguyên từ.
25*. Chọn phát biểu sai :
d. Công thức của LLMĐ biểu diễn được 1 câu khai báo.
d. Vị từ là quan hệ trên tập Dn của miền đối tượng D, với n 0.
d. Biểu thức hàm là nguyên từ.
d. Chứng minh eq(t1, t2)├─ eq(t2, t1). Đặt F = eq(x, t1). Dòng 1: eq(t1, t2),
dòng 2: eq(t1, t1), dòng 3: eq(t2, t1). Dòng 3 sử dụng qui tắc (=i) 1, 2.
26*. Chọn phát biểu sai :
d. Các dòng của bảng thực trị đại diện cho tất cả diễn dịch của 1 công thức LLMĐ.
d. Qui tắc (e) có dạng : dòng n FG, dòng n+k F, dòng n+k+1 G.
4
d. Mệnh đề rỗng của LLVT là công thức hằng sai.
d. (p(x, r(y)) yq(y)) yr(f(y)) là công thức và tự do của LLVT.
27*. Chọn phát biểu sai :
d. Công thức (F (G F)) là định lý, với F, G là công thức.
d. Nguyên tắc phân giải dựa trên qui tắc truyền.
d. ((x) p(x,y) q(t,y)) (y)(r(x,y,z)) có tất cả 5 hiện hữu tự do.
d. Đoạn chứng minh sau : dòng 3 : if x0 p(x0), dòng 4 : p(x0) q(x0), dòng 5 :
nif q(x0), dòng 6 q(x0), không có lỗi.
28*. Chọn phát biểu sai :
d. “Nếu hàm f khả vi thì f liên tục”, và “f không liên tục”, vậy “f không khả
vi”. Lập luận sử dụng qui tắc modus tolens.
d. Thuật toán hằng sai cho kết quả no với F và yes với F. Vậy Fhằng đúng.
d. = {f(t)/x, z/t} và = {a/x, b/t, t/z}. = {f(b)/x, t/z}.
d. Lưỡng nguyên là công thức nguyên hoặc công thức.
29*. Chọn phát biểu sai :
d. H là hệ quả luận lý của F thì tập các mô hình của H chứa tập mô hình của F.
d. {A, B, C, F} là 1 dòng của bảng thực trị của F = (A B) C.
d. Dạng chuẩn Skolem bảo toàn tính hằng sai.
d. Qui tắc (e) : dòng m : F F, dòng k : .
30*. Chọn phát biểu sai :
d. Công thức nguyên là vị từ có thông số được thay bằng các nguyên từ.
d. Định nghĩa của khái niệm phân giải là định nghĩa đệ qui.
d. Có thể dùng thuật toán hằng đúng để kiểm tra tính khả sai của 1công thức.
d. P Q R không ở dạng chuẩn giao.
31*. Chứng minh
1. F (q1q2) tiền đề
2. If F
F (q1q2) ├─ (Fq1) (Fq2) (trong LLMĐ)
4. q1 e 3
7. Fq2
8. nif (Fq1)(Fq2) i 6,7
9. (Fq1) (Fq2) e 2,6,7,8
i 2,5
5. q2 e 3
3. q1q2
e 1,2
6. Fq1 i 2,4
@a. CM sai từ dòng 6
c. CM sai từ dòng 8
b. CM sai từ dòng 7
d. Chứng minh đúng.
32*. Chứng minh F x q(x) ├─ x (F q(x)) với x không tự do trong F.
1. F x q(x) tđề 4. if xo 7. If x (F q(x)) i 4,6
2. if F 5. q(xo) e 3,4-7
e 3
8. x (F q(x))
3. x q(x) e 1,2 6. nif F q(xo) i 2,5
@a. áp dụng sai qui tắc i, if
b. áp dụng sai qui tắc i, e
5
c. áp dụng sai qui tắc if, e
d. Chứng minh đúng.
33*. M1 = r(y) q(a), M2 = p(x) r(y), M3 = q(a) p(x), M4= q(a) r(y),
M5= r(y), bằng phân giải chứng minh {M1, M2, M3, M4, M5} hằng sai :
a. pg(M2, M3) = F, pg(M2, M1) = G, pg(F, G) = .
b. pg(M3, M2) = F, pg(M4, F) = G, pg(M1, G) = .
c. pg(M2, M1) = F, pg(M4, F) = G, pg(M5, G) = .
@d. Câu a, b, c đều sai.
34*. Tập khả đồng nhất thế :
a. {p(a, x) r(x), p(a, h(x)) r(b), p(z, t) r(y)}.
@c. {p(a, x) r(x), p(a, h(y)) r(w), p(z, t) r(w)}.
b. Câu a và c đúng.
d. Câu a và c sai.
35*. F = x ( (p(x) y q(x, y)) z t q(z, t) ) có dạng chuẩn Skolem :
a. {p(x) q(x, y) q(f(x), g(x, y))}. b. {p(x) q(x, y) q(f(x, y), g(x, y))}.
@c. Câu a, b đều sai.
d. Câu a, b đều đúng.
36*. Công thức x (p(x) y (q(f(x)) r(y)) ) với D = {1, 2} có mô hình là :
@a. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q( 2), r(1), r(2)}.
b. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q(2), r (1), r(2)}.
c. Câu a, b đều sai.
d. Câu a, b đều đúng.
37*. Nếu nhiệt độ và áp suất không đổi thì trời không mưa. Nhiệt độ vẫn không đổi.
Vì vậy nếu trời mưa thì áp suất thay đổi.
A = nhiệt độ không đổi, B = áp suất không đổi, C = trời mưa.
Vị từ ch(x) : x không thay đổi và p() : trời mưa, hằng a, b.
a. (A B) C, A ╞═ C B
b. (ch(a) ch(b)) p(), ch(a) ╞═ p() ch(b),
c. Câu a, b đều sai.
Tổng cộng : 40 câu.
@d. Câu a, b đều đúng.
Hình (photo) có 2 dạng : tròn và vuông. Có loại màu và trắng đen. Hôm qua tìm thấy
một tấm hình. Nếu tấm hình này vuông thì là hình trắng đen. Nếu nó tròn thì nó là
hình màu kỹ thuật số. Nếu hình là kỹ thuật số hoặc trắng đen thì nó là hình chân dung.
Nếu nó là hình chân dung thì nó là hình của bạn tôi. Vậy tấm hình tìm thấy có phải là
hình của bạn tôi phải không ?
Color(x) = hình có màu x, shape(x) = hình có dạng x, digital (x) = hình x, portrait(x)
= hình chân dung.
shape(a)
6
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 đ.
Đáp án được để trên trang web sau khi thi (chậm nhất) … vài ngày.
Một số ý về logic.
Propositional logic là logic ở cấp độ sentences.
Predicate logic là logic ở cấp độ objects.
Chứng minh công thức vẫn còn hằng sai qua một phép thay thế.
-----------------------
@d. Có ít nhất 1 câu sai trong 3 câu a, b, c.
LUẬN LÝ TOÁN HỌC
Mã đề 1001
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.
Qui ước : a, b, c, … là hằng, x, y, z ... là biến.
9. = f(z)/x, x/y, y/t và = a/x, z/y, g(x)/z.
a. = a/y, f(g(a))/x, z/t
@b. = f(g(x))/x, a/y, z/t
c. = a/y, f(g(a))/x, g(a)/t d. Câu a, b, c đều đúng.
2. { p(x) q(x, y), r(y) q(x, b), p(x) r(a) } ╞═ H :
a. H = q(x, y) p(x)
c. H = r(a) q(a, b)
@b. H = q(x, b) p(x)
d. Câu a, b, c đều đúng.
13. M = p(x) q(x, b) và N = p(y) r(x) q(x, y), pg(N, M) :
a. p(x) r(x) p(b)
@c. Câu a, b đều đúng
b. p(b) r(b)
d. Câu a, b đều sai.
16. Nguyên từ t nào tự do đối với x trong công thức F = x (p(x, b) z y (q(x, y)
r(z))) :
a. t = f(x, y).
c. t = z.
b. t = a.
@d. Các câu a, b, c đều sai.
17. Dùng phân giải chứng minh {q(y) p(x), q(z) r(x), p(x) t(y), r(x)}╞═
t(y).
Ký hiệu : D = q(y) p(x), E = q(z) r(x), K = p(x) t(y), L = r(x) t(y), M =
r(x), N = t(y).
@a. pg(D, E) = A, pg(M, A) = B, pg(K, B) = C, pg(N, C) = .
7
b. pg(D, K) = A, pg(L, A) = B, pg(E, L) = C, pg(N, C) = .
c. pg(L, M) = A, pg(N, A) = .
đúng.
d. Câu a, b, c đều
19. Mệnh đề E = p(x, y) q(f(x)) q(a) p(x, f(y)) và thay thế = g(y)/x, a/y,
f(x)/z :
a. E = p(g(a), a) q(f(g(a))) q(a) p(g(a), f(a)).
@b. E = p(g(y), a) q(f(g(y))) q(a) p(g(y), f(a)).
c. E = p(g(y), f(a)) q(f(g(y))) q(a).
sai.
d. Câu a, b, c đều
21. Diễn dịch D = {1, 2, 3}, I = { p(1), p(2), p(3), q(1), q(2), q(3)} là mô hình
của công thức nào :
@a. x t (p(x) q(t)) x p(x).
b. t x (p(x) q(t)) x p(x).
c. x t (p(x) q(t)) x p(x). d. Câu a, b, c đều sai.
23. q(x) p(f(x), a) là thừa số của :
a. p(x, x) q(x) p(f(x), a).
c. q(x) p(f(x), a) p(x, a).
@b. q(x) p(f(x), a) p(y, a).
d. Câu a, b, c đều đúng.
26. (q(f(a)) p(t(z)) q(y) p(v) q(h(x)) p(u) ) có thừa số là :
@a. q(h(x)) p(t(z)) p(z) q(f(a)) q(y)
b. p(t(v)) q(y) p(v)
q(h(x))
c. p(t(z)) q(h(x)) q(z) q(f(a)).
d. Câu a, b, c đều đúng.
28. F = x p(x, x), G = x y (p(x, y) q(x)), H = x y (q(y) p(x, y) )
@a. {F, G}╞═ H.
c. {G, H}╞═ F.
b. {F, H}╞═ G.
d. Các câu a, b, c đều sai.
30. Chọn phát biểu đúng :
a. ├─ x(q(x)p(x)) xq(x) xp(x).
x(q(x)p(x)) x(q(x)p(x)).
c. ├─ xq(x) xp(x) x(q(x) p(x)).
@b. ├─
d. Các câu a, b, c đều sai.
34. F = x ( r(x, b) (p(x, x) t q(t, a)) ) có dạng chuẩn Skolem :
a. {r(x, b) (p(x, x) q(f(x), a))}. @b. {p(x, x) r(x, b) q(g(x), a)}.
c. {r(x, b) p(x, x) q(t, a)}.
d. Câu a, b, c đều đúng.
37. M = p(f(y)) q(z) p(a) và N = p(a) p(f(x)) q(y) q(f(y)), pg(M, N)
là :
a. p(f(x)) q(f(z)) p(f(z))
b. q(f(z))
8
@c. p(f(x)) p(a) q(f(z)) p(f(z)) p(a) d. Câu a, b, c đều sai.
39. mgu của {r(y, z, h(u)), r(y, v, x), r(f(u), v, w) là :
a. = f(u)/y, v/z, x/w, h(u)/x . b. = f(u)/y, v/z, h(u)/w, u/x.
c. = f(u)/y, v/z, u/w, h(u)/x. @d. Câu a, b, c đều sai.
40. Công thức x ( z p(x, z) (y q(y) t q(t)) ) với D = {0, 1} có mô hình là :
a. { p(0, 0), p(0, 1), p(1, 0), p(1, 1), q(0), q(1)}.
b. {p(0, 0), p(0, 1), p(1, 0), p(1, 1), q(0), q(1)}.
@c. { p(0, 0), p(0, 1), p(1, 0), p(1, 1), q(0), q(1)}.
c đều đúng.
d. Câu a, b,
Tổng cộng : 40 câu.
*. Chọn phát biểu đúng và bao quát nếu có thể :
*. Chọn phát biểu đúng và bao quát nếu có thể :
*. Chọn phát biểu đúng và bao quát nếu có thể :
*. Chọn phát biểu sai :
*. Chọn phát biểu sai :
*. Chọn phát biểu sai :
*. Chọn phát biểu sai :
9
9 trang
25800
Free
Bạn đang xem tài liệu "Đề thi cuối kỳ môn Luận lý toán học năm 2008 - Mã đề 0101", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_thi_cuoi_ky_mon_luan_ly_toan_hoc_nam_2008_ma_de_0101.doc
- FIN_LOGIC_MT2k08_DA.DOC
