华南农业大学期末考试试卷（A卷）
2009-2010学年第二学期 考试科目： 离散数学
考试类型：（闭卷）考试 考试时间： 120 分钟
学号 姓名 年级专业
一、判断题（本大题共10小题，每小题1分，共10分）
2、“我正在说谎话”是命题。
3、既是合取范式也是析取范式。
4、是前束范式。
5、A，B，C都是集合，如果A∪B=A∪C，则B=C。
6、和是集合A上的具有自反性的关系，则也一定具有自反性。 7、顶点数目相同，边数也相同的两个无向图一定同构。
8、每个顶点的度数都是偶数的无向图一定是欧拉图。
9、奇数阶完全图一定是欧拉图。
10、二阶以上连通没有回路的无向图是二部图。
二、选择题（本大题共15小题，每小题2分，共30分）
1、下面语句是简单命题的为_____。
A、3不是偶数。
B、李平既聪明又用功。
C、李平学过英语或日语。
D、李平和张三是同学。
A、 B、
C、 D、
3、下列集合不是连接词极小全功能集的为_____。
A、{¬,∧,∨} B、{¬,→} C、{↓} D、{↑}
4、下列谓词公式不是命题公式P→Q的代换实例的是______
A、 B、
C、 D、
5、设个体域为整数集，下列公式中其值为1的是_____。
A、 B、
C、 D、
6、下列哪个表达式错误_____。
A、
B、
C、
D、
7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是____。
A、1A B、{{4,5}}A C、{1,2,3}A D、A
8、设集合，集合，则 ____。
A、毫秒 B、 C、 D、
9、设集合上的两个关系，则R具有____。
A、对称性 B、传递性 C、自反性 D、反自反性
10、下述结论错误的是____。
A、存在这样的关系，它可以既满足对称性，又满足反对称性。
B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。
C、存在这样的关系，它可以既满足自反性，又满足反自反性。
D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。
11、集合A上的关系R为一个等价关系，当且仅当R具有_____。
北京2008油画A、自反性、对称性和传递性 B、自反性、反对称性和传递性
C、反自反性、对称性和传递性 D、反自反性、反对称性和传递性
12、以下整数序列，能成为一个简单图的顶点度数序列的是_____。
A、1，2，2，3，4，5
B、2，3，3，4，4，5
C、2，2，3，4，5，6
D、1，2，2，3，3，5
13、设无向图G的关联矩阵为，则G的顶点数与边数分别为_____。
(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、命题公式的对偶式是 (2)___。
3、p→q 的主合取范式是 (3)___。
4、设G(x)：x爱美，F(x)：x为人，在全总个体域中将命题“人都爱美”符号化 (4)___。
5、设F(x)：x是兔子， G(y)：y是乌龟，H(x,y)：x比y跑得快，在全总个体域中将命题“有的兔子比所有的乌龟跑得快”符号化 (5)___。
6、设集合，集合，则 (6)___。
7、设集合，则 (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、完全二部图的匹配数是 (10)___。
四、计算题（本大题共2小题，每小题6分，共1987年诺贝尔化学奖12分）
1、求1到1000之间的整数（包含1和1000在内）既不能被 6 和7 整除，也不能被 8 整除的数有多少个？
2、有向图D如图4-1所示，试求：
(1) 长为4的通路共有多少条?其中有多少条回路?
(2) 长度小于等于4的通路共有多少条?其中有多少条回路?
(3) 写出D的可达矩阵, 并问D是强连通的吗?
图4-1
五、应用题（本大题共2小题，每小题8分，共12分）
1、给出集合，分别求出：
(1)画出集合的整除偏序关系的哈斯图；
(2)集合的最大元，最小元，极大元，极小元；
(3)集合的上界，下界，最小上界，最大下界。
2、设集合，X上的关系R如图5-1所示，试求：王带狗肉上节目
图5-1
（1）写出关系R的关系矩阵；
（2）画出关系R的自反闭包r(R)的关系图；
（3）画出关系R的对称闭包s(R)的关系图；
（4）画出关系R的传递闭包t(R)的关系图。
六、证明题（本大题共2小题，每小题6分，共12分）
中脑边缘系统1、公安人员审查一件盗窃案，已知的事实如下：
① 甲或乙盗窃了录音机；
② 若甲盗窃了录音机，则作案时间不能发生在午夜前；
③ 若乙的证词正确，则午夜时屋里灯光未灭；
④ 若乙的证词不正确，则作案时间发生在午夜之前；
⑤ 午夜时屋里灯光灭了。
试问谁盗窃了录音机？将命题符号化，即将命题的前提符号化；然后在自然推理系统中构造命题的推理证明过程。
2、求下列谓词公式的前束范式，要求使用自由变项换名规则，请写出推理过程：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议