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 propositionsFudan 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