复习题一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共18分。）1．设为真命题，为假命题，则复合命题的真值为。2．令是人，喜欢吃米饭。在一阶逻辑中，命题“不是所有的人都喜欢吃米饭.”的符号化形式为。3．已知命题公式A中含三个命题变项，则极大项的公式是。4．在1到500之间的整数（包含1与500）中，既不被5整除、也不被6整除的数有个。5.设,,则的传递闭包=。6．设是一个连通的平面图，共有个结点，条边和个面，则结点、边和面的关系为（欧拉定理）。7．在整数加群中，。8．设为整数集，的逆元。9．300与168的最大公约数是。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共20分。）1.下列命题公式中，是永真公式的是()。A．B．C．D．2．关于谓词公式，下面的描述中错误的是()。A．的辖域是B．的辖域是C．是该谓词公式的约束变元D．是该谓词公式的约束变元3．5阶无向完全图的边数为()。A．5B．10C．15D．204．有向图G如右图所示，在G中，从V1到V3长度为3的通路有()条。A．0B．1C．2D．35．下列图中，()是强连通图。【第3页共3页】A．B．C．D．6．在一棵树中有7片树叶，3个3度结点，其余都是4度结点，则该树有()个4度结点。A．1B．2C．3D．47．对于集合，不封闭的二元运算是()。A．B．C．D．8．下列各图中()是欧拉图。A．B．C．D．9．设是12阶循环群，则的生成元有()个。A．2B．3C．4D．510．3的模5逆等于()。A．1B．2C．3D．4三、计算题（每小题各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提供的证据不正确，则作案时间发生在营业时间。⑤货柜上了锁。参考答案一、填空题1．0（或F）2．(或)3．4．3335．6．7．-68．9．12二、单项选择题1．C2．D3．B4．D5．A6．A7．D8．B9．C10．B三、计算题（每小题各8分，共40分。）1．解：主析取范式为：2．解：R所对应的关系矩阵为由关系矩阵可知，对角线上所有元素全为1，故自反；，故反对称；由此可计算出对应的矩阵。由以上矩阵可知传递。所以，是偏序关系。对应的哈斯图如下图所示。3．解：所求该图的最小生成树如下图所示。该最小生成树的权值之和W（t）=2+1+1+2+3+4=134．解：所求的最优2叉树如下图所示。该最优2叉树的权为W(t)=2×4+3×4+9×3+18×2+23×2+29×2=1875．解：其特征方程为：，其特征根是：通解为：代入初值得到：解得：所以，原递推方程的解为：。四、证明题（12分。）证明：（1）由于①自反性：，有，即是上的自反关系；②对称性:，有，即是上的对称关系；③传递性：，有故是上的传递关系。由(1)、(2)、(3)可知是上的等价关系。（2）上的等价类为：所以，五、应用题（10分）解：设简单命题p：A作案盗窃金项链。q：B作案盗窃金项链。r：作案发生在营业时间。s：B提供的证据正确。t：货柜上了锁前提：结论：（或写为：推理形式为）证明：前提引入前提引入（1）（2）拒取式前提引入（3）（4）假言推理前提引入（5）（6）拒取式前提引入（7）（8）析取三段论