复习题
一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）
1．谓词公式?x?y(P(x,y)?Q(y,z))??xR(x,y)中?x的辖域是 。 2．命题公式 ( p??q)的成真赋值为 。
3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有 个。
4．设R是定义在集合A?{1,2,3,4}上的二元关系R?{?1,1?,?1,2?,?2,3?,?1,4?}，则R的对称闭包s(R)? 。
5．A?{1,2,3,4},x?y?min{x,y},则代数系统?A,??中的零元是 。 6．具有10个结点的无向完全图的边数= 。 7．一次同余方程3x??1(mod5)的最小正整数解是 。 8．84与198的最大公约数是 。
二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）
1. 设F(x): x是有理数，G(x)：x能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为( )。
A. ??x(F(x)??G(x)) B. ??x(F(x)??G(x)) C. ??x(F(x)??G(x)) D. ??x(F(x)??G(x)) 2. 设个体域是整数集，则下列命题的真值为真的是( )。
A．?y?x(x?y?1) B．?x?y(x?y?0)
C．?x?y(x?y?y2) D．?y?x(x?y?x2)
3. 集合A?{1,2,,10}上的关系R?{?x,y?|x?y?10,?x,y?A}，则R的性质为( )。
A、自反的 B、传递的、对称的 C、对称的 D、反自反的、传递的
4．对自然数集合N，下列定义的运算中( )是不可结合的。 A. a?b?a?b?3 B. a?b?a?2b
C. a?b?a?b(mod 3) D. a?b?min{a,b}
5．下列各图中既是欧拉图，又是汉密尔顿图的是( )。
A． B． C． D．
6．对于下列度数序列，可画成简单无向图的是( )。
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条边的不同构的简单图有( )个。
A. 2 B. 3 C. 4 D. 5
【第 1 页 共 2 页】
8．5的模6逆等于( )。
A．1 B．3
C．4 D．5
三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。） 1．求命题公式(p?q)?(p?r)的主析取范式和主合取范式。
2．设?A,R?为偏序集，其中A?{1,2,3,4,6,9,24,54}，R是A上的整除关系。（1）画出?A,R?的哈斯图；（2）求A中的极大元；（3）令B?{4,6,9}，求B的上确界和下确界。 3．求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。
4．求解递推方程：an?7an?1?12an?2?0,a0?4,a1?6 。 5．有向图D如图2所示，求：（1）D中v1到v3长度为3的通路有几条？（2）D中v1到v1长度为3的回路有几条？（3）D是哪类连通图？
12124536344v1v4 3 图1 图2
v2v3
6．在通讯中要传输字母a,b,c,d,e,f,g，它们出现的频率为：
a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。
四、证明题（每小题8分，共16分。）
1．设R为自然数集N上的关系，定义N上的关系R如下：?x,y??R?x?y是偶数。 （1）证明R为等价关系； （2）求商集N/R。
?x,y?Z,xy?x?y?2，?Z,?2．设Z为整数集合，在Z上定义二元运算如下：证明：
是群。
五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）
若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。
【第 2 页 共 2 页】
参考答案
一、填空题 （请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）
1．P(x,y)?Q(y,z) 2．10，11，00 3．600
4．{?1,1?,?1,2?,?2,3?,?1,4?,?2,1?,?3,2?,?4,1?} 5．1 6．45 7．3 8．6
二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）
1．C 2．C 3．C 4．B 5．C 6．A 7．C 8．D 三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）
1．解：主合取范式为： （5分）
(p?q)?(p?r)?(?p?q)?(?p?r)?((?p?q)?(r??r))?((?p?r)?(q??q)) ?(?p?q?r)?(?p?q?r)?(?p?q?r)?(?p??q?r)?(?p?q?r)?(?p?q?r)?(?p??q?r)?M4?M5?M6 主析取范式为： （2分）
(p?q)?(p?r)?m0?m1?m2?m3?m7?(?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r)?(p?q?r)2．解：（1）?A,R?的哈斯图如下图所示。 （3分）
2454
426329
1
（2）A中的极大元是：24，54； ( 2分)
（3）B的上确界：无；B的下确界：1。 ( 2分) 3．解：所求该图的最小生成树如下图所示。 （5分）
121234 【第 1 页 共 3 页】