Fudan University 复旦大学 2012-2013学年第二学期考试试卷 课程名称:离散数学(I) 课程代码:SOFT130040 开课院系:软件学院 考试形式:开卷 姓名 学号 专业 题 89—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 questi REMARK: All solutions are only for reference. Because there may be more than one method to solve a problem 1. Define a binary connective A e B whose truth table is given in Table 1. Answer the ABAb TTF Table 1: Truth table of e following questions (7 marks) (a)Prove or disprove that (,e) is adequate (2 marks (b)Add the atomic tableau of e into atomic tableaux (2 marks) ()Discuss the validity of (Ae B)+(Av-B by using tableau proof. 3 marks) Solution.(a) First A V B can be represented as A e-B.(1 mark) Hence (V, is adequate. , e) is also adequate. (1 mark (b)The tableau is shown in Figure 1. F and T each has 1 mark (c)The tableau is shown in Figure 2 It is a tableau proof. So the sentence/proposition valid 2. Give the following statementsFudan 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. Remark: All solutions are only for reference. Because there may be more than one method to solve a problem. 1. Define a binary connective A ⊖ B whose truth table is given in Table 1. Answer the A B A ⊖ B T T T T F T F T F F F T Table 1: Truth table of ⊖ following questions. (7 marks) (a) Prove or disprove that {¬, ⊖} is adequate. (2 marks) (b) Add the atomic tableau of ⊖ into atomic tableaux. (2 marks) (c) Discuss the validity of (A ⊖ B) → (A ∨ ¬B) by using tableau proof. (3 marks) Solution. (a) First A ∨ B can be represented as A ⊖ ¬B. (1 mark) Hence {∨, ¬} is adequate. {¬, ⊖} is also adequate. (1 mark) (b) The tableau is shown in Figure 1. F and T each has 1 mark. (c) The tableau is shown in Figure 2 It is a tableau proof. So the sentence/proposition is valid. 2. Give the following statements: 1