2005离散数学ii1补考试卷a答案

《2005离散数学ii1补考试卷a答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3页共3页班级：姓名：准考证号：任课教师考场教室――――――――――――――――――――――――――装订线――――――――――――――――――――――――――――――－姓名中国民航学院2004－2005学年第1学期《离散数学》期末考试试卷A课程编号：试卷类型：考试形式：闭卷考试日期：2005-4-28题号一二三四五六总分得分注意事项：1.试卷后两页为草稿纸，可以撕下；2.不准携带任何书籍、资料、纸张等。1．（20分)1）求命题公式(p®q)Ú(pÙr)的析取范式和合取范式【解答】求(p®q)Ú(pÙr)的合取范式：(p®q)Ú(pÙr)Û(ØpÚq)Ú(pÙr)Û(ØpÚ

2、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)，按极小项所对应的二

3、进制数的大小重新排列为(Ø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)

4、Ú(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分)每个大学生不是文科生就是理工科生，有的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生。3第3页共3页设A(x):x是大学生,B(x):x是文科生,C(x):x是理工科生，D(x):x

5、是优等生,a:小张试用逻辑表示式表示，并利用逻辑推理规则证明之。【解答】"x(A(x)→(ØB(x)→C(x))),$x(A(x)∧D(x))，ØC(a)∧D(a)Þ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)CP4．(25分)R和S都在A上是自反、对称、传递的，求证R∩S在A上是等价关系。【证明】一.证明R∩S的自反性任取x∈A,因R和S都自反，所以有

6、x>∈R，∈S，于是有∈R∩S，所以R∩S也自反。二.证明R∩S的对称性：任取x,y∈A,设∈R∩S,则∈R，∈S，因为R和S对称，所以有∈R，∈S，于是∈R∩S。∴R∩S对称。3第3页共3页三.证明R∩S的传递性：任取x,y,z∈A,设∈R∩S,∈R∩S,∈R∩S∧∈R∩SÛ∈R∧∈S∧∈R∧∈SÛ(∈R∧∈R)∧(∈S∧∈S)Þ∈R∧∈S（因为R、S传递

7、）Û∈R∩S所以R∩S传递。5.(20分)设A¹f，RÍA´A，则：1.r(R)=RÈIA；2.s(R)=RÈR-1；【证明】1.首先RÈIA是自反的，且RÍRÈIA，若又有自反关系R’满足RÍR’，则因为R’是自反的有IAÍR’，即有RÍR’ÙIAÍR’，从而有RÈIAÍR’，命题得证。2.首先RÈR-1是对称的，因为(RÈR-1)-1=RÈR-1。若又有对称关系RÍR’，则对任意的ÎA´A，有：ÎRÈR-1Û(ÎR)Ú(ÎR-1)Þ(ÎR’)Ú(