离散数学复习题及参考解答
复习题 一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1谓词公式中的辖域是 。2命题公式的成真赋值为 。3在1和1000之间（包括1和1000在内）不能被4和5整除的数有 个。4设是定义在集合上的二元关系，则的对称闭包 。5,则代数系统中的零元是 。6具有10个结点的无向完全图的边数= 。7一次同余方程的最小正整数解是 。884与198的最大公约数是 。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）1. 设: 是有理数，：能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为( )。A. B. C. D. 2. 设个体域是整数集，则下列命题的真值为真的是( )。A BC D3. 集合上的关系，则的性质为( )。A、自反的 B、传递的、对称的C、对称的 D、反自反的、传递的4对自然数集合，下列定义的运算中( )是不可结合的。 A. B. C. D. 5下列各图中既是欧拉图，又是汉密尔顿图的是( )。A B C D6对于下列度数序列，可画成简单无向图的是( )。A(1，1，1，2，3) B(1，2，2，3，4，5)C(1，2，3，4，5，5) D(2，3，3，4，5，6)7. 含有5个结点、3条边的不同构的简单图有( )个。【第 1 页 共 2 页】 A. 2 B. 3 C. 4 D. 5 85的模6逆等于( )。A1 B3 C4 D5三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1求命题公式的主析取范式和主合取范式。2设为偏序集，其中，是上的整除关系。（1）画出的哈斯图；（2）求中的极大元；（3）令，求的上确界和下确界。3求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。4求解递推方程： 。5有向图D如图2所示，求：（1）D中到长度为3的通路有几条？（2）D中到长度为3的回路有几条？（3）D是哪类连通图？ 图1 图2 6在通讯中要传输字母，它们出现的频率为：，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。四、证明题（每小题8分，共16分。）1设为自然数集上的关系，定义上的关系R如下：是偶数。（1）证明为等价关系；（2）求商集。2设为整数集合，在上定义二元运算如下：，证明：是群。五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。【第 2 页 共 2 页】参考答案一、填空题 （请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1 210，11，00 36004 51645 73 86二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）1C 2C 3C 4B 5C 6A 7C 8D三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1解：主合取范式为： （5分） 主析取范式为： （2分）2解：（1）的哈斯图如下图所示。 （3分） （2）中的极大元是：24，54； ( 2分)（3）的上确界：无；的下确界：1。 ( 2分)3解：所求该图的最小生成树如下图所示。 （5分）【第 1 页 共 3 页】该最小生成树的权值之和W（t）=2+1+1+2+3+4=13 （2分）4解：其特征方程为：，其特征根是： （2分）通解为： （2分）代入初值得到：解得： （2分）所以，原方程的解为：。 （1分）5解：先求图D的邻接矩阵及、。，（1分） ,（2分）（2分）(1) D中到长度为3的通路有3条。 （1分）(2) D中到长度为3的回路有5条。 （1分）(3) D是强连通图。 （1分）6解：按字母顺序，令为传输第个字母的频率，则传输100个字母，各字母出现的频数为，得。将它们按照从小到大顺序排列，得 。 （2分）以为权求最优2叉树如下图所示。 （4分）传输的前缀码分别为：。传100个所需二进制数字个数为：W(t)=15+30+60+100+40+20=265。 （2分）四、证明题（每小题8分，共16分。）1（1）证明：因为，且是偶数，于是【第 2 页 共 3 页】因此在上是自反的； （1分）若则是偶数，即是偶数，于是因此在上是对称的； （1分）若且则，于是，进而因此在上是传递的； （2分）综上所述，是上的等价关系。 （1分）（2）关于等价关系的所有等价类为和，则。 （3分） 2证明：显然，关于是封闭的。 （1分）对于任意，由于， 而，于是，即满足结合律。 （2分），因为，因此2是关于的单位元。（2分），由于且，于是关于存在逆元。 （2分） 所以，是群。 （1分）五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）解：设简单命题p：小张喜欢数学。 q：小李喜欢数学。r：小赵喜欢数学。 s：小李喜欢物理。 （2分）前提：结论：（或写为：推理形式为 ） （1分）证明： 前提引入 前提引入 （1）（2）拒取式 （2分） 前提引入 前提引入 （4）（5）假言推理 （2分） （3）（6）析取三段论 （1分）【第 3页 共 3 页】
