离散结构
2007-a
一、填空（每空2分，共30分）
1、设P：2+2=4，Q：3是奇数 将命题“2+2=4，当且仅当3是奇数”符号化__(1)___，其真值为__(2)___。 2、在公式
?x(F(x,y))中，自由出现的变元为___(3)____。
3、若关系R具有自反性，当且仅当在关系矩阵中，主对角上元素__(4)___，若关系R具有对称性，当且仅当关系矩阵是__(5)___。 4、若关系R?1?R，则关系R一定具有__(6)___性。
5、有向图的连通性可分为弱连通、强连通、__(7)___。 6、前缀表达式 + * 2 / 8 4 3 的值是__(8)___。
7、设G是完全二元树，G有15个顶点，其中有8个叶子，则G有__(9)___条边，G的总度数是__(10)___。 8、十进制3位数的数字中恰好有一个8和一个9，共有__(11)___个这样的3位数。
9、设集合S?{a,b,c,d,e}，S上的运算?定义为：
*abcde则代数系统?10、设?aabcdebbdaadccabcaddcadceedbce S,??中单位元是__(12)___，b的左逆元是__(13)___，无左逆元的元素是__(14)___。
S,??是由元素a?S生成的循环群，且S的阶为4，则集合S=__(15)___。
二、选择题（每题2分，共30分） 1、下列语句中，_____是命题。
A、地球上的人真多 B、把门关上 C、下午有会吗？ D、x?5?6
1
2、一个公式在等价意义下，下面哪个写法是唯一的_____。
A、析取范式 B、合取范式 C、主析取范式 D、以上都不唯一
3、设命题公式
G??(P?Q)?Q，则G是_____。
A、永真式 B、矛盾式 C、可满足式 D、以上都不是 4、设I是如下一个解释，D?{a,b}，其中解释I下取真值的公式是______
A、?x?yp(x,y) B、?x?yp(x,y) C、?xp(x,x) D、?x?yp(x,y) 5、下列哪个表达式错误_____。。
A、 B、 C、 D、
p(a,a)，p(b,a)为真，p(a,b)，p(b,b)为假，则在
?x(P(x)?Q(x))??xP(x)??xQ(x)
?xP(x)??xQ(x)??x(P(x)?Q(x)) ?x(P(x)?Q(x))??xP(x)??xQ(x) ?x(P(x)?Q(x))??xP(x)??xQ(x)
6、设R，S是集合
A?{1,2,3,4}上的两个关系，其中R?{?1,1?,?2,2?,?2,3?,?4,4?}，
S?{?1,1?,?2,2?,?2,3?,?3,2?,?4,4?}，则S是R的____闭包。
A、自反 B、反对称 C、对称 D、传递 7、设R和S是非空集合A上的等价关系，下列各式是A上等价关系的是_____。
A、
A?A?R B、R?S C、R?S D、R?S的对称闭包
A,??）关系R的哈斯图如右所示，若A的子集B?{2,3,4,5}，则元素6为B的_____。
8、设偏序集（?A、下界 B、上界 C、最小上界 D、以上都不对 9、以下整数序列，能成为一个简单图的顶点度数序列的是_____。
A、1，2，2，3，4，5 B、2，3，3，4，4，5 C、1，1，1，2，3 D、2，3，3，4，5，6
10、设图G是有6个顶点的连通图，总度数为20，则从G中至少删去_____条边后使之成为树。
A、10 B、5 C、3 D、2 11、在下列关于图论的命题中，正确的是_____。
A、哈密顿图一定是欧拉图
B、无向完全图Kn(n?3)都是欧拉图
2
C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出 D、哈密顿图是平面图 12、下面编码_____不是前缀码。
A、11，00，10，01 B、01，11，011，1001 C、101，11，001，011，010
D、010，11，011，1011，1001，10101 13、5阶非同构的无向树有_____棵。
A、1 B、2 C、3 D、4 14、由0、1、2、3这四个数字能构成_____个3位数
A、64 B、48 C、24 D、18 15、在下列选项中，不是群的是_____。
A、(Q,?)，Q为有理数，+为加法运算 B、(R?,?)，R?为非零实数集，?为乘法运算
C、全体实对称矩阵集合，对于矩阵的加法运算 D、(Q,?)，Q为有理数，*为乘法运算
三、计算题（5分+5分+8分，共18分）
1、设有5个城市v1,v2,v3,v4,v5，任意两城市之间的铁路造价如下：
W(v1,v2)?4，W(v1,v3)?7，W(v1,v4)?16，W(v1,v5)?10，W(v2,v3)?13， W(v2,v4)?8，W(v2,v5)?7，W(v3,v4)?3，W(v3,v5)?5，W(v4,v5)?12
试求出连接5个城市的且造价最低的铁路网
2、构造前序遍历为a，b，f，c，g，h，i，d，e，j，k，p的有序树，其中a有4个子结点，c有3个子结点，j有2个子结点，b和e都有一个子结点，所有其它结点都是树叶。
34、设集合A?{1,2,3,4,5}，A上的关于等价关系R的商集A/R={{1,2,3},{4,5}}，试求： （1）等价关系R （2）写出关系矩阵MR （3）画出关系图 （4）写出R的传递闭包
3
四、证明题（5分+5分+6分，共16分）
1、设R是A上的等价关系，S是B上的等价关系，且A和B非空，关系T满足：
??x,a?,?y,b???T??x,y??R且?a,b??S，证明T是A?B上的等价关系。
2、设G为n阶无向简单图，证明：若G为自补图（若一个图的补图为本身则称为自补图），则n?4k或
n?4k?1，其中k为正整数。
3、若?G,??是群，u?G，定义G中的运算“?”为：a?b?a?u证明?G,?
五、应用题（6分）
?1?b，对?a,b?G
?为群。
p,q,r的意义如下：p：张群是大学生，q：张群心情愉快，r：张群唱歌
试用日常语言说明下列复合命题：
(1) (2) (3) 2007-b
一、填空（每空2分，共30分）
1、表达式?xF(x)??xG(x)中谓词的个体域是{a,b,c}，将其中的量词消去，写成与之等价的命题公式为__(1)__。
2、设R是集合A上的二元关系，如果关系R同时具有__(2)__、__(3)__和传递，则称R是A上的偏序关系。 3、已知集合
p?(q?r) p??(q?r) ?p?(q?r)
A?{1,2,3,4,5}上的二元关系
R?{?1,2?,?3,4?,?2,2?}，
S?{?4,2?,?2,5?,?3,1?,?1,3?}，则R?S=__(4)__，S2=__(5)__。
4、若有限集
A关系R具有自反性，则其对应的关系矩阵主对角元素全为__(6)__。
5、若某个简单图不是欧拉图但具有欧拉通路，则图中顶点度数为奇数的顶点个数一定为__(7)__。 6、设G??V,E?是图，如果G是__(8)__并且__(9)__则G是树。
7、一个无向图的欧拉回路要求经过图中__(10)__一次且仅一次，哈密顿回路要求经过图中__(11)__一次且仅一次。
4
8、树是平面图，它有__(12)__个面。
9、在群、半群、独异点中，__(13)__满足消去律。 10、设Q为有理数集，笛卡尔积S?Q?Q，?是S上的二元运算，??a,b?,?x,y??S，有
（a，则?0）
?a,b???x,y???ax,y?b?，则?运算的单位元为__(14)__，??a,b??S?a,b?的逆元为__(15)__。
二、选择题（每题2分，共30分） 1、下列语句中_____是命题。
A、把门关上
B、地球外的星球上也有人 C、x?5?6 D、下午有会吗
2、已知命题
G??(P?(Q?R))，则所有使G取真值的解释是_____。
A、000，001，100 B、100，101，110 C、010，101，001 D、001，101，111 3、命题公式A和B是等价的是指
A、A和B由相同的原子变元 B、A和B都是可满足的
C、当A的真值为真时，B的真值也为真 D、A和B有相同的真值 4、对P、
Q、R而言，下列是极小项的是_____。
A、?P B、P?Q C、P??Q?5、设集合
R D、?P?Q?R
都是A上的关系，
A?{1,2,3}，R、S、TR?{?1,2?,?2,1?,?3,3?}，
S?{?1,3?,?2,2?,?3,2?}，T?{?1,3?,?2,1?,?3,1?}，则T=_____。
A、R?S B、S?R C、R?R D、S?S
6、若T为树，以下叙述不正确的是_____。
A、T是连通的且不含回路
B、T的每对顶点之间有唯一的一条路径 C、T是连通的且每条边都是割边 D、T是连通的且每个点都是割点
5