离散数学II补考试卷A答案.docVIP

第  PAGE 4 页 共  NUMPAGES 4 页 PAGE  PAGE 4 第  PAGE 1 页 共  NUMPAGES 4 页 班级： 姓名： 准考证号： 任课教师 考场教室 ――――――――――――――――――――――――――装 订 线――――――――――――――――――――――――――――――－ 姓名 中国民航学院2004－2005 学年第 1 学期 《离散数学》期末考试试卷A 课程编号： 试卷类型： 考试形式： 闭卷 考试日期：2005-4-28 题号一二三四五六总分得分 注意事项：1.试卷后两页为草稿纸，可以撕下；2.不准携带任何书籍、资料、纸张等。 （20分) 求命题公式(p?q)?(p?r)的析取范式和合取范式 【解答】求(p?q)?(p?r)的合取范式： (p?q)?(p?r)?(?p?q)?(p?r)? (?p?q?p)? (?p?q?r) 显然(p?q)?(p?r)的析取范式为(?p)?q?(p?r)。 2) 求命题公式(?p?q)?(p?r)的主析取范式 【解答】(1)知(?p?q)?(p?r)的一个析取范式是(p?r)?(q??p)?(q?r)，我们将其中的每个简单合取式展开为含有所有命题变元的极小项的析取： (p?r)展开为(p?q?r)?(p??q?r) (q??p)展开为(?p?q?r)?(?p?q??r) (q?r)展开为(p?q?r)?(?p?q?r) 因此(?p?q)?(p?r)的主析取范式为(p?q?r)?(p??q?r)?(?p?q?r)?(?p?q??r)，按极小项所对应的二进制数的大小重新排列为(?p?q??r)?(?p?q?r)?(p??q?r)?(p?q?r)。 (2)知(p?q)?(p?r)的一个析取范式为(?p)?q?(p?r)，将其中每个简单合取式展开为含有所有命题变元的极小项的析取： (?p)展开为(?p?q?r)?(?p??q?r)?(?p?q??r)?(?p??q??r) q展开为(p?q?r)?(?p?q?r)?(p?q??r)?(?p?q??r) (p?r)展开为(p?q?r)?(p??q?r) 因此(p?q)?(p?r)的主析取范式为： (?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r)?(p??q?r)?(p?q??r)?(p?q?r) 2.(10分) 求公式： ?xF(x, y) ?(?xG(x) ? ?yF(y, z)) 的前束范式 【解答】 ?xF(x, y) ?(?xG(x) ? ?yF(y, z)) ? ?xF(x, u) ?(?vG(v) ? ?yF(y, z)) ? ?xF(x, u) ? (?v?y(G(v) ? F(y, z))) ? ?x?v?y(F(x, u) ? (G(v) ? F(y, z))) 3. (25分)每个大学生不是文科生就是理工科生，有的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生。 设 A(x):x是大学生, B(x):x是文科生, C(x):x是理工科生，D(x):x是优等生, a:小张 试用逻辑表示式表示，并利用逻辑推理规则证明之。 【解答】 x(A(x)→(?B(x)→C(x))), $x(A(x)∧D(x)) ，?C(a)∧D(a) T A(a)→B(a) ⑴ A(a) P(附加前提) ⑵ x(A(x)→(?B(x)→C(x))) P ⑶ A(a)→(?B(a)→C(a)) US ⑵ ⑷ ?B(a)→C(a)) T ⑴⑶I ⑸ ?C(a)∧D(a) P ⑹ ?C(a) T ⑸I ⑺ ??B(a) T ⑷⑹ I ⑻ B(a) T ⑺ E ⑼ A(a)→B(a) CP 4．(25分)R和S都在A上是自反、对称、传递的，求证R∩S在A上是等价关系。 【证明】 证明R∩S的自反性 任取 x∈A, 因R和S都自反，所以有x,x∈R，x,x∈S，于是有 x,x∈R∩S，所以R∩S也自反。 二.证明R∩S的对称性： 任取 x,y∈A,设x,y∈R∩S,则x,y∈R，x,y