Fudan University 复旦大学 2012-2013学年第二学期考试试卷 课程名称:离散数学(I) 课程代码:SOFT130040.01 开课院系:软件学院 考试形式:开卷 姓名 学号 专业 得分 DIRECTION: There are totally two pages of examination paper. You must write all your answers, include your name and student number clearly, on a specific answersheet. You have 2 to se 1. Given a poset 1, 2, 4, 5, 10, 20 with the relation defined by Figure 1 (a) Verify it is a lattice? (5 points) (b)Is (1, 4, 10, 20] a sublattice of (1, 2, 4, 5,10, 201? Give your reasons. (5 points 2 2. If P and Q are posets, let Q be the poset of order-preserving maps from P to Q, where forf,g∈ Q we define f≤giff(a)≤g(a) for all a∈P. If Q is a lattice show that Q is also a lattice. (5 points) 3. Prove or disprove the following statements. If a statement is false, give a counterexample (15 marks (a) Let a be a well-defined proposition. a has arbitrary length when length k > 4.3 (b)B is satisfiable if and only if (B)is not valid. (3 marks) (c) If a proposition a is satisfiable, then it has infinite models. 3 marks) (d)The number of tautologies is the same as the number of unsatisfiable propositions
Fudan University 复旦大学 2012-2013 学年第二学期考试试卷 课程名称: 离散数学 (II) 课程代码: SOFT130040.01 开课院系: 软件学院 考试形式: 开卷 姓名: 学号: 专业: 题目 1 2 3 4 5 6 7 8 9 10 总分 得分 Direction: There are totally two pages of examination paper. You must write all your answers, include your name and student number clearly, on a specific answersheet. You have 2 hours to solve all the questions. 1. Given a poset {1, 2, 4, 5, 10, 20} with the relation defined by Figure 1, (a) Verify it is a lattice? (5 points) (b) Is {1, 4, 10, 20} a sublattice of {1, 2, 4, 5, 10, 20} ? Give your reasons. (5 points) 1 2 5 4 10 20 Figure 1: Lattice 2. If P and Q are posets, let QP be the poset of order-preserving maps from P to Q, where for f, g ∈ QP we define f ≤ g iff f(a) ≤ g(a) for all a ∈ P. If Q is a lattice show that QP is also a lattice. (5 points) 3. Prove or disprove the following statements. If a statement is false, give a counterexample. (15 marks) (a) Let α be a well-defined proposition. α has arbitrary length when length k ≥ 4. (3 marks) (b) B is satisfiable if and only if (¬B) is not valid. (3 marks) (c) If a proposition α is satisfiable, then it has infinite models. (3 marks) (d) The number of tautologies is the same as the number of unsatisfiable propositions. (3 marks) 1
(e) Given two sets of propositions∑1and∑2,∑1∑2→M(∑2)sM(∑1) 4. Let F be the constant false and M be the ternary minority connectives (m(, B, C)is true if and only if at most one of A, B, C is true). Show that (F, M is complete. (5 marks marks) every proposition can be represented in CNF(Conjunctive Normal Form).(8 5. Prove that 6. Prove or disprove the following statements. If it is false, a counterexample is needed: (10 na (a){(-(6→7)→-a),3}F(a→?).(4 marks (b)Ip*(qVr), -g, r) H =p 3 marks) (c)(P→(Q→R)→(P→Q)→(P→B).(3 marks) 7. Given the following deduction: If the equatorial rain forests produce oxygen used by Americans, then either Americans ought to pay for the oxygen, or they ought to stop complaining about the destruction of the rain forests. But either it is false that americans ought to pay for the oxygen, or it is false that Americans ought to stop complaining about the destruction of the rain forests. Therefore, it is false that the equatorial rain forests produce oxygen used by Ameri cans Answer the following questions:(9 marks) (a) Formalize the deduction with propositional logic. (5 marks) (b) Prove or disprove the conclusion formally.(4 marks) 8. Given a set 2=a1,., an) of finite propositions, prove that 2 a if and only if (a1A…∧an)→ a is valid(8 marks) 9. In 1977 it was proved that every planar map can be colored with four colors(Of course there are only finite countries on map). Suppose we have an infinite(but countable) planar map with countries C1,C2,C3,……(10 marks) (a) Formalize this problem with propositional logic.(5 marks) (b)Prove that an infinite map can be still colored with four colors. (5 marks)
(e) Given two sets of propositions Σ1 and Σ2, Σ1 ⊆ Σ2 ⇒ M(Σ2) ⊆ M(Σ1). 4. Let F be the constant false and M be the ternary minority connectives(M(A, B, C) is true if and only if at most one of A, B, C is true). Show that {F, M} is complete. (5 marks) 5. Prove that every proposition can be represented in CNF(Conjunctive Normal Form).(8 marks) 6. Prove or disprove the following statements. If it is false, a counterexample is needed:(10 marks) (a) {(¬(β → γ) → ¬α), β} |= (α → γ).(4 marks) (b) {p → (q ∨ r), ¬q, ¬r} ⊢ ¬p.(3 marks) (c) ((P → (Q → R)) → ((P → Q) → (P → R))). (3 marks) 7. Given the following deduction: If the equatorial rain forests produce oxygen used by Americans, then either Americans ought to pay for the oxygen, or they ought to stop complaining about the destruction of the rain forests. But either it is false that Americans ought to pay for the oxygen, or it is false that Americans ought to stop complaining about the destruction of the rain forests. Therefore, it is false that the equatorial rain forests produce oxygen used by Americans. Answer the following questions: (9 marks) (a) Formalize the deduction with propositional logic. (5 marks) (b) Prove or disprove the conclusion formally. (4 marks) 8. Given a set Σ = {α1, . . . , αn} of finite propositions, prove that Σ |= α if and only if (α1 ∧ · · · ∧ αn) → α is valid.(8 marks) 9. In 1977 it was proved that every planar map can be colored with four colors(Of course there are only finite countries on map). Suppose we have an infinite(but countable) planar map with countries C1, C2, C3, . . .. (10 marks) (a) Formalize this problem with propositional logic. (5 marks) (b) Prove that an infinite map can be still colored with four colors. (5 marks) 2