装订线 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)期末考试试卷
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)