课程考试试题参考答案及评分标准 课程名称：  数理逻辑 （ B 卷）  考试方式：  （闭卷） 任课教师：  宋 伟  学 院：  哲 学 系 专业年级：  哲学2003级   注：参考答案需写清题号、每小题分值、参考答案要点、评分标准等   一. Complete the following blanks.(each 2 points, total 20 points) 1. 2n 2. logically implies 3. ((～A)∨(～B)) 4. Every theorem of L is a tautology. 5. ～(x)(N(x)∧O(x)∧E(x)) or (x)(N(x)→(O(x)∧E(x))) 6. formal language, deductive apparatus 7. decidable 8. free 9.Countable (or denumerable) 10. (x2)( (c1, x2)→(c1,c2)) 二. Solve the following problems. (each 10 point, total 60 points) 1. DNF: (p∧q∧r) ∨(p∧(～q) ∧r) ∨(p∧(～q) ∧(～r)) ∨((～p) ∧q∧r) ∨((～p) ∧(～q) ∧r) (5 pts) CNF: ((～p) ∨(～q) ∨r) ∧(p∨(～q) ∨r) ∧(p∨q∨r) (5pts) 2. (p→q) is logically equivalent to ～(p∧(～q)) and so to (p|(～q)) (5 pts.) and so to (p|(～q)) (5pts.) 3. Attempt to assign truth values to demonstrate the invalidity of the argument form. Let p take value F and q take value T. (5pts.) Under this assignment of truth values, the other premises, ((～p) →(～q)) takes value F. So it is impossible to assign values so that the premises ate true and the conclusion is false, and this argument is valid. (5 pts.) 4. (1) (A→(B→C)) as. (2) B as. (3) A as. (4) (B→C) (1),(3)MP (5) C (2),(4)MP (5 pts.) What we have demonstrated is {(A→(B→C),B,A)}├C so by the Deduction Theorem, We have ((A→(B→C) →(B→(A→C))) (5 pts.) 5. We can define an interpretation I as Follows. DI = Z , A(x) stands for x<0, and f(x) stands for the successor of x. (5pts.) So the wf. (x1) ((x1)→((x1))) has the interpretation for all xDI, if x＜0 then the successor of x＜0. Obviously, when x = -1 this is false. (5 pts.) 三. Proof. (each 10 points, total 30 points) 1. Proof. Now suppose, conversely, that ((A1∧…∧An) → A) is a tautology and that A1,…,An; ∴A is not a valid argument form. Then there is an assignment of truth values which makes each Ai (1≤i≤n) take value T and makes A take value F, so that ((A1∧…∧An)→A) takes value F. (5 pts.)This contradicts the assumption that this statement form is a tautology, and so A1,…, An; ∴A is a valid argument form. (5 pts.) 2. Proof. If B is a contradiction, then (～B)is obviously tautology, i.e.├(～B) (5.pts.) Suppose that B is a theorem of any consistent extension of L, then B and (～B) are both the theorems of L’, But this result contradicts that L’ is a consistent extension of L, so if B is a contradiction, then it cannot be a theorem of any consistent extension of L. (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.)