离散复习题及参考解答

复习题一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共18分。）1设为真命题，为假命题，则复合命题的真值为 。2令是人，喜欢吃米饭。在一阶逻辑中，命题“不是所有的人都喜欢吃米饭.”的符号化形式为 。3已知命题公式A中含三个命题变项，则极大项M4的公式是 。4在1到500之间的整数（包含1与500）中，既不被5整除、也不被6整除的数有 个。5. 设,则的传递闭包= 。6设是一个连通的平面图，共有个结点，条边和个面，则结点、边和面的关系为（欧拉定理） 。7在整数加群中， 。8设为整数集，的逆元 。9300与168的最大公约数是 。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共20分。）【第 3 页 共 3 页】1. 下列命题公式中，是永真公式的是( )。A B C D2关于谓词公式，下面的描述中错误的是( )。A的辖域是 B的辖域是C是该谓词公式的约束变元 D是该谓词公式的约束变元35阶无向完全图的边数为( )。A5 B10 C15 D204有向图G如右图所示，在G中，从V1到V3长度为3的通路有( )条。A0 B1 C2 D35下列图中，( )是强连通图。 A B C D6在一棵树中有7片树叶，3个3度结点，其余都是4度结点，则该树有( )个4度结点。A1 B2 C3 D47对于集合，不封闭的二元运算是( )。A BC D8下列各图中( )是欧拉图。A B C D9设是12阶循环群，则的生成元有( )个。A2 B3 C4 D5103的模5逆等于( )。A1 B2 C3 D4三、计算题（每小题各8分，共40分。）1求命题公式的主析取范式。2设集合上二元关系定义为 ，验证是偏序集，并画出哈斯图。3求下列带权图的最小生成树，画出最小生成树，并求其权值。 4求树叶的权分别为2，3，9，18，23和29的最优2叉树T，并求树权W（T）。5求解递推方程： 。四、证明题（12分。）设，在上定义二元关系，（1）证明是上的等价关系；（2）求商集。五、应用题（10分）符号化下列命题，并在自然推理系统P中用逻辑推理确定谁是作案者。 营业员A或B盗窃了金项链。 若A作案，则作案时间不在营业时间。 若B提供的证据正确，则货柜未上锁。 若B提供的证据不正确，则作案时间发生在营业时间。 货柜上了锁。参考答案一、填空题 10（或F） 2(或) 34333 5 6 7-6 8 912二、单项选择题1C 2D 3B 4D 5A 6A 7D 8B 9C 10B三、计算题（每小题各8分，共40分。）1解：主析取范式为： 2解： R所对应的关系矩阵为 由关系矩阵可知，对角线上所有元素全为1，故自反；，故反对称；由此可计算出对应的矩阵。由以上矩阵可知传递。所以，是偏序关系。 对应的哈斯图如下图所示。 3解：所求该图的最小生成树如下图所示。 该最小生成树的权值之和W（t）=2+1+1+2+3+4=13 4解：所求的最优2叉树如下图所示。该最优2叉树的权为W(t)=24+34+93+182+232+292=1875解：其特征方程为：，其特征根是：通解为： 代入初值得到：解得： 所以，原递推方程的解为：。四、证明题（12分。）证明：（1）由于 自反性：，有，即是上的自反关系； 对称性: ，有，即是上的对称关系； 传递性：，有故是上的传递关系。 由(1)、(2)、(3)可知是上的等价关系。（2）上的等价类为： 所以，五、应用题（10分）解：设简单命题p：A作案盗窃金项链。 q：B作案盗窃金项链。 r：作案发生在营业时间。s：B提供的证据正确。 t：货柜上了锁 前提：结论：（或写为：推理形式为 ）证明： 前提引入 前提引入 （1）（2）拒取式 前提引入 （3）（4）假言推理 前提引入 （5）（6）拒取式 前提引入 （7）（8）析取三段论