Fudan universit 复旦大学 2011-2012学年第2学期考试试卷 果程名称:离散数学(I 课程代码:SOFT130040.01 开课院系:软件学院 考试形式:开卷 姓名 专业 23 6 8910总分 得分 DIRECTION: There are totally two pages of examination paper. You must write all your answers, include your name and student number clearly, on a specifie sheet. You have 2 hours to solve all the questions 1. Given lattice(L, s) described by the Hasse diagram shown in Figure 1, answer the fol- lowing questions:( 8 marks d Figure 1: A hasse diagram of a lattice (a) Prove or disprove whether the following subsets are sublattices of L: L1=10, a, b,1] L 2=a,c, d, 13, L3=0, c, e, I or not.(5 marks) (b)If Li, i= 1, 2, 3, is a sublattice, prove or disprove whether it is an ideal of L. 3 2. Let L be a finite lattice, prove that: (10 marks) (a)If L> 2, then for any element a E L, a is not a complement of a(4 marks) (b)If Ll> 3 and L is a chain, then L is not complemented lattice.(6 marks) 3. Prove or disprove the following statements. If a statement is false, give a counterexample
Fudan University ❊➀➷ 2011-2012➷❝✶2➷Ï⑧➪➪ò ➅➜➯→: ❧Ñê➷(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 lattice hL, ≤i described by the Hasse diagram shown in Figure 1, answer the following questions: (8 marks) a b c d e 1 0 Figure 1: A Hasse Diagram of a Lattice (a) Prove or disprove whether the following subsets are sublattices of L: L1 = {0, a, b, 1}, L2 = {a, c, d, 1}, L3 = {0, c, e, 1} or not. (5 marks) (b) If Li , i = 1, 2, 3, is a sublattice, prove or disprove whether it is an ideal of L. (3 marks) 2. Let L be a finite lattice, prove that:(10 marks) (a) If |L| ≥ 2, then for any element a ∈ L, a is not a complement of a. (4 marks) (b) If |L| ≥ 3 and L is a chain, then L is not complemented lattice. (6 marks) 3. Prove or disprove the following statements. If a statement is false, give a counterexample. (15 marks) 1
(a)Let a be a well-defined proposition. a has arbitrary length when length k > 4.3 mark (b)B is satisfiable if and only if (B)is not valid. (3 marks) (c)(B)is not satisfiable if and only if B is valid. (3 marks) (d)The number of tautologies is the same as the number of unsatisfiable propositions (3 marks) (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(A, B, C)is true if and only if at most one of A, B, C is true). Show that (F, M is complete.(4 marks 5. Prove that every proposition can be represented in CNF(Conjunctive Normal Form).(6 marks 6. Prove or disprove the following statements. If it is false, a counterexample is needed: (10 mari (a){(-(→)→-a),B}=(a→7).(4 marks) (b)IR+P,SVR, S)HnP. 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 eithe 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 2=a1,..., an of finite propositions, prove that 2F a if and only if (a1A…A∧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 0 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)
(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) (¬B) is not satisfiable if and only if B is valid. (3 marks) (d) The number of tautologies is the same as the number of unsatisfiable propositions. (3 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. (4 marks) 5. Prove that every proposition can be represented in CNF(Conjunctive Normal Form).(6 marks) 6. Prove or disprove the following statements. If it is false, a counterexample is needed:(10 marks) (a) {(¬(β → γ) → ¬α), β} |= (α → γ).(4 marks) (b) {R → P, ¬S ∨ R, S} ` ¬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
