湖北大学2004—2005学年度第二学期课程考试试题参考谷案及评分标准 北:还课程雩试题参考苍案及评分标准 课程名称 数理逻辑 (A卷) 考试方式: (闭卷) 任课教师:宋伟 专业年级:哲学2003级 注:参考答案需写清题号、每小题分值、参考答案要点、评分标准等 Complete the following blanks.(each 2 points, total 20 points) 4. IfA is a wf. of L and A is a tautology, then HA. (彐x)(N(x)∧~(O(x)VE(x) 6. symbols, formation rules(or well-formed formulas 7. decidable 8. scope 10.(Vx)(x)A3(x,h1(x)x3) =. Solve the following problems.(each 10 points, total 50 points 1.DNF:(p∧q)V(~p)∧(~q)(spts.) CNF:(~p)∨q)∧(pV(~q)(5pts.) 2.(p→g) is logically equivalent to(~p)∨q) ((q)Va) so to (~p)↓q) (5 pts.) p↓p)↓q and so to(p↓p)↓q)↓(plp)lq)(5pts.) 3. Attempt to assign truth values to demonstrate the invalidity of the argument form. To make(c g)(p)) take value F we require q to have value F and value T. We also require r to be F (5 pts.) Under this assignment of truth values, the other premises, (p(qVr)) takes value F. So it is impossible to assign values so that the premises are true and the conclusion is false, and this 第1页共2页)
湖北大学 2004——2005 学年度第二学期课程考试试题 参考答案及评分标准 （第 1 页 共 2 页） 课程考试试题参考答案及评分标准 课程名称： 数理逻辑 （ A 卷） 考试方式： （闭卷） 任课教师： 宋 伟 学 院： 哲 学 系 专业年级： 哲学 2003 级 注：参考答案需写清题号、每小题分值、参考答案要点、评分标准等 一. Complete the following blanks. (each 2 points, total 20 points) 1. 2 2 n 2. logically equivalent 3. {～,∧},{～,→} 4. If A is a wf. of L and A is a tautology, then ├A. 5. ( x)(N(x) →(O(x)∨E(x))) or ～( x)(N(x) ∧～(O(x) ∨E(x))) 6. symbols, formation rules (or well-formed formulas) 7. decidable 8. scope 9. countable (or denumerable) 10. ( x1)( x3)A 3 1 (x1,h 1 1 (x1),x3) 二. Solve the following problems. (each 10 points, total 50 points) 1. DNF: (p∧q) ∨(～p) ∧(～q)) (5 pts.) CNF: ((～p) ∨q) ∧(p∨(～q)) (5 pts.) 2. (p→q) is logically equivalent to ((～p) ∨q) and so to ～((～q) ∨q) and so to ～((～p)↓q) (5 pts.) and so to ～((p↓p)↓q) and so to ((p↓p)↓q)↓((p↓p)↓q) (5 pts.) 3. Attempt to assign truth values to demonstrate the invalidity of the argument form. To make (c～ q)→(～p)) take value F we require q to have value F and value T. We also require r to be F. (5 pts.) Under this assignment of truth values, the other premises, (p→ (q∨r)) takes value F. So it is impossible to assign values so that the premises are true and the conclusion is false, and this L
湖北大学2004—2005学年度第二学期课程考试试题参考谷案及评分标准 argument is valid. (5 pts. 4.(1)(A→B) (3)A (4)B (1),(3)MP (5)(~(B→C)→(~A)→(A→(B→C)(La (2),(SMP (8)C (4)(7)MP(5pts) What we have demonstrated (A→B(~(B→C)→~AA}C So by the deduction Theorem, we have (A→B)→((~(B→C)→~A)→(A→C)) 5. We can define an interpretation I as follows DI=N, and A,(x, y) Stands for x<y, (5 pts. So the wf.(v Xi)(AF(x1, X2)-AF(x2, xi) has the interpretation for all x and yE D if x <y then Obviously, this is false (5pts) = Proof (each 10 points, total 30 points) 1. Proof. Suppose first that Al,…,An;∴ a is a valid argument form and that(A1∧…∧,An)→A is not a tautology, Then there is an assignment of truth values to the statement variables occurring such that(A1A., )takes value T, and A takes value F (5 pts. For this assignment, then, each Ai takes value T(lsis), and A takes value F. This contradicts the validity of the argument form and so(A1∧.∧An)→A) must be a tautology.(Spts.) 2. Proof. Suppose that L is not consistent, i.e. that there is a wf. A such that FA and +(A).Then by Proposition 2. 14(The Soundness Theorem), both A and(A)are tautologies. (5 pts. )This is impossible since if A is a tautology then(A) is a contradiction and if(A)is a tautology then a is a contradiction. Thus L must be consistent. (5 pts. 3. Proof. Let v be a valuation in I. Then v satisfies A and v satisfies(A-B). By the definition satisfaction, then, either v satisfies( A)or v satisfies B. But v cannot satisfy(A),so v must satisfy B (5 pts. It follows that is satisfied by every valuation in I, so B is true in I (5 pts.) 第2页共2页)
湖北大学 2004——2005 学年度第二学期课程考试试题 参考答案及评分标准 （第 2 页 共 2 页） argument is valid. (5 pts.) 4. (1) (A→B) as. (2)～(B→C)→(～A) as. (3)A as. (4)B (1),(3)MP (5)(～(B→C)→(～A))→(A→(B→C)) (L3) (6)A→(B→C) (2),(5)MP (7)(B→C) (3),(6)MP (8)C (4)(7)MP (5pts.) What we have demonstrated is {(A→B),(～(B→C)→～A),A} ├ C So by the Deduction Theorem, we have ((A→B)→((～(B→C)→～A)→(A→C))) 5. We can define an interpretation I as follows. DI = N, and 2 A1 (x,y) Stands for x＜y, (5 pts.) So the wf. ( x1) ( 2 A1 (x1,x2)→ 2 A1 (x2,x1)) has the interpretation for all x and y DI, if x＜y then y＜x. Obviously, this is false. (5pts.) 三. Proof. (each 10 points, total 30 points) 1. Proof. Suppose first that A1,…,An; ∴A is a valid argument form and that ((A1∧…∧,An)→A) is not a tautology, Then there is an assignment of truth values to the statement variables occurring such that (A1∧…∧An)takes value T, and A takes value F. (5 pts.) For this assignment, then, each Ai takes value T(1≤i≤n), and A takes value F. This contradicts the validity of the argument form, and so ((A1∧…∧An)→A) must be a tautology. (5 pts.) 2. Proof. Suppose that L is not consistent, i.e. that there is a wf. A such that ├ A and ├ (～A). Then by Proposition 2.14 (The Soundness Theorem), both A and (～A) are tautologies.(5 pts.) This is impossible since if A is a tautology then (～A) is a contradiction and if (～A) is a tautology then A is a contradiction. Thus L must be consistent. (5 pts.) 3. Proof. Let v be a valuation in I. Then v satisfies A and v satisfies (A→B). By the definition of satisfaction, then ,either v satisfies (～A)or v satisfies B. But v cannot satisfy (～A), so v must satisfy B. (5 pts.) It follows that is satisfied by every valuation in I, so B is true in I. (5 pts.) L L L
