我最好的老师-婚礼证婚人致辞

成都理工大学2007－2008学年第一学期
《离散数学》考试试卷
大题 一
得分
得分
二

三

四

五

六

七

八

九

总分

一、填空题
（本大题共10小题，每小题2分，共20分）
1. 解释（0，1）使命题公式
A(p(pq))q
的真值为 。
2. 两个重言式的析取是__________________ 式，一个重言式和一个永假式的合
取式是_________________式。
3．设p :小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符
号化形式为_____ ________________________________。
4. 设
F(x) :x
是火车，
G

y

:y
是汽车，
H( x,y):x
比
y
快，则“火车都比汽车快”
可符号化为 。
5. A上的等价关系R的定义是。
6. 设A={1，2，3}，R={<1，2>,<1，3>} 是A上的关系，则R满足下列性质的哪
几条：自反的，对称的，传递的，反自反的，反对称的。
。
7. 设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法
和乘法，则代数系统的幺元是，零元是。
8. 若h是A =〈S，〉到A
′
=〈S
′
，
′
〉的同态，则h（a b）=。
9. 〈R，+，〉是环，则〈R，+〉是交换群，〈R，〉是。
10．无向 图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均
小于3，则G至少有 个结点。
得分
二、选择题
（本大题共10小题，每小题1分，共10分）
1．下列语句中，不是命题的有（ ）。
A. 5能被2整除。
C. 现在开会吗？

B.太阳系以外的星球上有生物。
D.小李在宿舍里。

2．与谓词公式 PQ等价的公式是（ ）。
A. PQ
C. PQ
B. PQ
D. PQ
3．下述不是偏序集合的是（ ）。
A．〈I，〉 B．〈R，〉
C．〈{1，2，3，6} 整除〉 D．〈{2，4，8，16}，倍数〉
4．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ）。
A．满射函数 B．单射函数
C．双射函数 D．非单射非满
5. 设个体域为整数，下列公式中真值为1的是( )。


A．xy(x + y = 1); B．xy(x + y = 1);
C．xy(x + y = 1); D． xy(x + y = 1)。
6．设集合X为人的全体，在X上定义关系R、S为R={|a，bX∧a是b
的父亲}，S={|a，bX∧a是b的母亲}，那么关系{< a，b>|a，b X∧ a
是b的祖母}的表达式为（ ）。
A．R

S B．R
-1

S
C．S

R D．R

S
-1

7. 满足谓词P(x,y)：xy0的整数集Z上的二元关系具有（ ）性质？
A．反自反、对称 B．反对称、传递
C．反对称 D．自反、对称、传递

8. I为整数集，下列系统中不是代数系统的有（ ）。
A.
C.




B.
D. 都不是
9．任何图中必定有偶数个（ ）：
A、度数为偶数的结点 B、入度为偶数的结点
C、度数为奇数的结点 D、出度为奇数的结点

10．下列图形中为欧拉图的是（ ）

得分
三、
（本大题共10分）

求
(P∨Q)←→(P∧Q)
的主析取范式和主合取范式。


得

分

四、
（本大题共10分）

用谓词推理理论来论证下述推证：
每个有理数都是实数,有的有理数是整数.因此,有的实数是整数。
得分
五、
（本大题共10分）
设 为群，任意a,b,cA, 证明 a*b=a*c，则 b=c。

得分
六、
（本大题共10分）
设R＝{<1,2>,<3,4>,<2,2>}， S＝{<4,2>,<2,3>,<3,1>}，分别是定 义为从A
→B和从B→C的关系，其中A＝B＝C＝{1,2,3,4}。
求R•S，S•R，R•R，S•S。
得分
七、
（本大题共10分）
设A＝｛1，2，3，4，6，8，12，24｝，R为A上整除关系，试画
的哈斯图，并求A中的最大元，最小元，极大元，极小元。
得分
八、
（本大题共10分）

设无向图G=，V={v1，v2„v6}，
E={v
1
v2
,v
1
v
3
,v
1
v
4
, v
2
v
5
,v
2
v
4
,v
2v
3
,v
3
v
5
,v
4
v
5
}。

（1） 画出G的图形；（2） 求出G中各顶点的度及奇数度顶点的个数。


得分
九、
（本大题共10分）
证明：非平凡的树至少有两个叶子。

成都理工大学2007－2008学年第一学期
《离散数学》考试试卷
大题 一
得分
得分
二

三

四

五

六

七

八

九

总分

一、填空题
（本大题共10小题，每小题2分，共20分）
1. 解释（0，1）使命题公式
A(p(pq))q
的真值为 。
2. 两个重言式的析取是__________________ 式，一个重言式和一个永假式的合
取式是_________________式。
3．设p :小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符
号化形式为_____ ________________________________。
4. 设
F(x) :x
是火车，
G

y

:y
是汽车，
H( x,y):x
比
y
快，则“火车都比汽车快”
可符号化为 。
5. A上的等价关系R的定义是。
6. 设A={1，2，3}，R={<1，2>,<1，3>} 是A上的关系，则R满足下列性质的哪
几条：自反的，对称的，传递的，反自反的，反对称的。
。
7. 设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法
和乘法，则代数系统的幺元是，零元是。
8. 若h是A =〈S，〉到A
′
=〈S
′
，
′
〉的同态，则h（a b）=。
9. 〈R，+，〉是环，则〈R，+〉是交换群，〈R，〉是。
10．无向 图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均
小于3，则G至少有 个结点。
得分
二、选择题
（本大题共10小题，每小题1分，共10分）
1．下列语句中，不是命题的有（ ）。
A. 5能被2整除。
C. 现在开会吗？

B.太阳系以外的星球上有生物。
D.小李在宿舍里。

2．与谓词公式 PQ等价的公式是（ ）。
A. PQ
C. PQ
B. PQ
D. PQ
3．下述不是偏序集合的是（ ）。
A．〈I，〉 B．〈R，〉
C．〈{1，2，3，6} 整除〉 D．〈{2，4，8，16}，倍数〉
4．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ）。
A．满射函数 B．单射函数
C．双射函数 D．非单射非满
5. 设个体域为整数，下列公式中真值为1的是( )。


A．xy(x + y = 1); B．xy(x + y = 1);
C．xy(x + y = 1); D． xy(x + y = 1)。
6．设集合X为人的全体，在X上定义关系R、S为R={|a，bX∧a是b
的父亲}，S={|a，bX∧a是b的母亲}，那么关系{< a，b>|a，b X∧ a
是b的祖母}的表达式为（ ）。
A．R

S B．R
-1

S
C．S

R D．R

S
-1

7. 满足谓词P(x,y)：xy0的整数集Z上的二元关系具有（ ）性质？
A．反自反、对称 B．反对称、传递
C．反对称 D．自反、对称、传递

8. I为整数集，下列系统中不是代数系统的有（ ）。
A.
C.




B.
D. 都不是
9．任何图中必定有偶数个（ ）：
A、度数为偶数的结点 B、入度为偶数的结点
C、度数为奇数的结点 D、出度为奇数的结点

10．下列图形中为欧拉图的是（ ）

得分
三、
（本大题共10分）

求
(P∨Q)←→(P∧Q)
的主析取范式和主合取范式。


得

分

四、
（本大题共10分）

用谓词推理理论来论证下述推证：
每个有理数都是实数,有的有理数是整数.因此,有的实数是整数。
得分
五、
（本大题共10分）
设 为群，任意a,b,cA, 证明 a*b=a*c，则 b=c。

得分
六、
（本大题共10分）
设R＝{<1,2>,<3,4>,<2,2>}， S＝{<4,2>,<2,3>,<3,1>}，分别是定 义为从A
→B和从B→C的关系，其中A＝B＝C＝{1,2,3,4}。
求R•S，S•R，R•R，S•S。
得分
七、
（本大题共10分）
设A＝｛1，2，3，4，6，8，12，24｝，R为A上整除关系，试画
的哈斯图，并求A中的最大元，最小元，极大元，极小元。
得分
八、
（本大题共10分）

设无向图G=，V={v1，v2„v6}，
E={v
1
v2
,v
1
v
3
,v
1
v
4
, v
2
v
5
,v
2
v
4
,v
2v
3
,v
3
v
5
,v
4
v
5
}。

（1） 画出G的图形；（2） 求出G中各顶点的度及奇数度顶点的个数。


得分
九、
（本大题共10分）
证明：非平凡的树至少有两个叶子。