装订线 1.5CM
华南农业大学期末考试试卷（A卷）
2009-2010学年第二学期 考试科目： 离散数学 考试类型：（闭卷）考试 考试时间： 120 分钟
学号 姓名 年级专业
题号 一 二 三 四 五 六 总分 得分 评阅人
一、判断题（本大题共10小题，每小题1分，共10分）
得分 1、“如果天气好，那么我去散步”是命题。 2、“我正在说谎话”是命题。 3、p?q既是合取范式也是析取范式。 4、?xF(x)?G(x)是前束范式。
5、A，B，C都是集合，如果A∪B=A∪C，则B=C。
6、R1和R2是集合A上的具有自反性的关系，则R1?R2也一定具有自反性。 7、顶点数目相同，边数也相同的两个无向图一定同构。 8、每个顶点的度数都是偶数的无向图一定是欧拉图。 9、奇数阶完全图K2n?1(n?0)一定是欧拉图。 10、二阶以上连通没有回路的无向图是二部图。
二、选择题（本大题共15小题，每小题2分，共30分）
得分 1、下面语句是简单命题的为_____。
A、3不是偶数。
B、李平既聪明又用功。 C、李平学过英语或日语。 D、李平和张三是同学。
2、下列命题公式中是矛盾式的有_____。
A、(p??p)??p B、?(q?p)?p
1
C、(?p?q)?(q??p) D、(p?q)?r 3、下列集合不是连接词极小全功能集的为_____。
A、{?,∧,∨} B、{?,→} C、{↓} D、{↑}
4、下列谓词公式不是命题公式P→Q的代换实例的是______
A、F(x)?G(y)
B、?xF(x,y)??yG(x,y) D、?xF(x)?G(x)
C、?x(F(x)?G(x))
5、设个体域为整数集，下列公式中其值为1的是_____。
A、?x?y(x?y?0) B、?y?x(x?y?0) C、?x?y(x?y?0) D、??x?y(x?y?0) 6、下列哪个表达式错误_____。
A、 ?x(A(x)?B)??xA(x)?B B、 ?x(A(x)?B)??xA(x)?B C、 ?x(B?A(x))?B??xA(x) D、 ?x(A(x)?B)??xA(x)?B
7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是____。
A、1?A B、{{4,5}}?A C、{1,2,3}?A D、??A 8、设集合A?{2,4,6,8,10,12}，集合B?{3,6,9,12,15,18}，则B?A? ____。
A、{1,2,3,4,5,6} B、{3,9,15,18} C、 {2,4,8,10} D、{6,9}
9、设集合A?{1,2,3,4}上的两个关系R?{?1,1?,?2,3?,?2,4?,?3,4?}，则R具有____。
A、对称性 B、传递性 C、自反性 D、反自反性 10、下述结论错误的是____。
A、存在这样的关系，它可以既满足对称性，又满足反对称性。 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。 C、存在这样的关系，它可以既满足自反性，又满足反自反性。 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。 11、集合A上的关系R为一个等价关系，当且仅当R具有_____。
A、自反性、对称性和传递性 B、自反性、反对称性和传递性 C、反自反性、对称性和传递性 D、反自反性、反对称性和传递性 12、以下整数序列，能成为一个简单图的顶点度数序列的是_____。
A、1，2，2，3，4，5 B、2，3，3，4，4，5
2
C、2，2，3，4，5，6 D、1，2，2，3，3，5 ?1?1100??装订线 1.5CM 13、设无向图G的关联矩阵为?01110 ?0012?，则G的顶点数与边数分别为_____。?1??00000??(A)4, 5 (B)4, 10 (C)5, 4 (D)5, 10
14、以下无向图中，不是二部图的是_____。
A、 B、
C、 D、
15、以下无向图中，不是欧拉图的是_____。
A、
B、
C、 D、
三、填空题（本大题共10小题，每小题2分，共20分）
得分 1、设 p:天冷，q:小王穿羽绒服，将命题“除非天冷，小王才穿羽绒服”符号化 (1)___。
2、命题公式?p?(q?r)的对偶式是 (2)___。 3、p→q 的主合取范式是 (3)___。
3
4、设G(x)：x爱美，F(x)：x为人，在全总个体域中将命题“人都爱美”符号化 (4)___。 5、设F(x)：x是兔子， G(y)：y是乌龟，H(x,y)：x比y跑得快，在全总个体域中将命题“有的兔子比所有的乌龟跑得快”符号化 (5)___。
6、设集合A?{6,8,10,12}，集合B?{3,6,9,12}，则B?A? (6)___。 7、设集合A?{a}，则P(P(A))? (7)___。
8、设集合A={1, 2, 3, 4}，R=={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}和S={<1,2>, <1,4>, <2,2>, <2,3>}是集合A上关系，则R○S= (8)___。
9、设无向图G有12条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (9)___个悬挂顶点。 10、完全二部图K3,3的匹配数是 (10)___。
四、计算题（本大题共2小题，每小题6分，共12分）
1、求1到1000之间的整数（包含1和1000在内）既不能被 6 和7 整除，也不能被 8 整除的数有多少个？
2、有向图D如图4-1所示，试求：
(1) 长为4的通路共有多少条?其中有多少条回路?
(2) 长度小于等于4的通路共有多少条?其中有多少条回路? (3) 写出D的可达矩阵, 并问D是强连通的吗?
得分 v1
v4
v2
图4-1
v3
五、应用题（本大题共2小题，每小题8分，共12分）
1、给出集合A?{1,2,3,4,5,6,7,8,9,10,11,12}，分别求出： (1)画出集合A的整除偏序关系的哈斯图；
(2)集合A的最大元，最小元，极大元，极小元；
(3)集合B?{2,4,6}的上界，下界，最小上界，最大下界。
得分 4
装订1.5CM 线
2、设集合X?{a,b,c,d,e}，X上的关系R如图5-1所示，试求：
a b c d e
图5-1
（1）写出关系R的关系矩阵MR；
（2）画出关系R的自反闭包r(R)的关系图； （3）画出关系R的对称闭包s(R)的关系图； （4）画出关系R的传递闭包t(R)的关系图。
六、证明题（本大题共2小题，每小题6分，共12分）
得分 1、公安人员审查一件盗窃案，已知的事实如下：
① 甲或乙盗窃了录音机；
② 若甲盗窃了录音机，则作案时间不能发生在午夜前； ③ 若乙的证词正确，则午夜时屋里灯光未灭；
④ 若乙的证词不正确，则作案时间发生在午夜之前； ⑤ 午夜时屋里灯光灭了。
试问谁盗窃了录音机？将命题符号化，即将命题的前提符号化；然后在自然推理系统中构造命题的推理证明过程。
2、求下列谓词公式的前束范式，要求使用自由变项换名规则，请写出推理过程： ?x(F(x)??yG(x,y,z))??zH(x,y,z)
5
华南农业大学离散数学(2009-2-A)期末考试试卷
