课程考试试题参考答案及评分标准 课程名称：  数理逻辑 （ A 卷）  考试方式：  （闭卷） 任课教师：  宋 伟  学 院：  哲 学 系 专业年级：  哲学2003级   注：参考答案需写清题号、每小题分值、参考答案要点、评分标准等   一. Complete the following blanks. (each 2 points, total 20 points) 1. 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(x1,h(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 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 (x,y) Stands for x＜y, (5 pts.) So the wf. (x1) ((x1,x2)→(x2,x1)) has the interpretation for all x and yDI, 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.)