《离散数学》综合复习资料
一、解答题
1. 将下列命题符号化：
（1）他虽聪明但不用功。

（2）除非你努力否则你将失败。

（3）我们不能既划船又跑步
（4）仅当你走我才留下。

2. 用谓词表达式符号化下列命题：
（1）所有老的国家选手都是运动员。

（2）某些教练是年老的，但是健壮的。

（3）任何自然数不是偶数就是奇数。

（4）不是所有运动员都是教练。

3. 求命题公式⌝(P →Q)的主合取范式。

4. 求命题公式P ∧(P →Q)的主析取范式。

5. 设集合A ＝{1, 2, 3}，A 上的关系R ＝{<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3, 3>},
（1）画出R 的关系图；
（2）写出R 的关系矩阵；
（2）问R 具有关系的哪几种性质(自反、反自反、对称、反对称、传递)。

6. 设S={1,2,3,4,6,12}，D 为S 上的整除关系，
（1）试写出该关系并画出哈斯图；
（2）设子集B={2,3,6}，试求B 的最大元、最小元、极大元和极小元；
（3）试求B 的上界、上确界、下界和下确界。

7. 设集合A 有3个元素，B 有4个元素，则A 到B 的关系有多少个？A 到B 的函数有多少个？
8. 判定下列代数系统是否为群，请说明原因。

（1）<R,+>，其中R 为实数集，+为普通加法；
（2）<I,⨯>，其中I 为整数集，⨯为普通乘法
9. 设G=<V ,E>，V={V1,V2,V3,V4}的邻接矩阵：
A(G)=
（1）试画出该图。

（2）V2的入度d -(V2)和出度d +(V2)是多少？
（3）从V2到V4长度为2的路有几条？
0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 0
10.（1）画一个有欧拉回路和一条汉密尔顿回路的图。

（2）画一个有欧拉回路，但没有汉密尔顿回路的图。

（3）画一个没有欧拉回路，但有汉密尔顿回路的图。

11.设有一组权3、4、13、5、6、12，求相应的最优树（要求构造的过程中，每个分支点的
左儿子的权小于右儿子的权）。

二、证明题
1.试证明命题公式(()())()
P Q Q R P R
→∧→→→为永真式。

2.试证明：(P∨Q) ∧(P→R) ∧(Q→S) ⇒S∨R
3.用推理规则证明：(∀x)(P(x)→Q(x)) ⇒(∃x) P(x)→(∃y)(P(y)∧Q(y))
4.若R和S是集合A上的等价关系，试证明R⋂S也是A上的等价关系。

5.设<G1,*>,<G2,︒>是两个群，在G1⨯G2上定义运算 为：
<a1,b1> <a2,b2>=<a1*a2,b1︒b2>，证明< G1⨯G2, >是一个群。