二、（8分）个体域为{1，2}，求xy（x+y=4）的真值。
解：xy（x+y=4）x（（x+1=4）∨（x+2=4））
（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））
（0∨0）∧（0∨1）
1∧10
四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。
解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}
s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>}
t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}
五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。
解设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/＝140。
由容斥原理，得
|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C|
所以
|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10
没有乘坐过其中任何一种的儿童共10人。
九、（10分）已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。
解：D的邻接距阵A和可达距阵P如下：
010*******
0010011111
A=00011P=11111
0000000000
1000011111
一、（10分）求命题公式(P∧Q)(PR)的主合取范式。
解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）
（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）
(P∧Q)∨(P∧R)
(P∨R)∧（Q∨P）∧（Q∨R）
(P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）
M1∧M3∧M4∧M5
五、(10分) 设A ＝{a ，b ，c ，d }，R 是A 上的二元关系，且R ＝{，，，}，求r (R )、s (R )和t (R )。
解 r (R )＝R ∪I A ＝{，，，，，，，} s (R )＝R ∪R -1＝{，，，，，} R 2＝{，，，} R 3＝{，，，} R 4＝{，，，}＝R 2
t (R )＝i i R ∞
=1Y ＝{，，，，，，，，}
十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。
解：最优二叉树为
权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148
3、（5分）树T 有2个4度顶点，2个3度顶点，其余顶点全是树叶。问T 有几片树叶
解、设T 有x 片树叶, n 个顶点，m 条边
n=2+2+x ，m=n-1= 4+x-1 ，由握手定理2(4+x-1)=24+23+x ×1 解得x =8，故T 有8片树叶.
2、（5分）设有向简单图D 的度数序列为2、2、
3、3,入度序列为0、0、2、3，试求D 的出度序列和该图的边数，并在图4中画出该有向图。
解：出度序列为 2、2、1、0
边数m=（2+2+3+3）/2=5
2、写出对应下面推理的证明：
如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会。所以进行离散数学考试。（其中p ：今天是星期一；q ：进行英语考试；r ：进行离散数学考试；s ：英语老师有会。）
前提：p →（q ∨r ），s →┐q ，p ，s 结论：r
证明：①p →（q ∨r ） 前提引入 ②p 前提引入
③q ∨r ①②假言推理 ④s →┐q 前提引入 ⑤s 前提引入 ⑥┐q ④⑤假言推理 ⑦r ③⑥析取三段论
1、={}b a ,，B={}2,1,0，求笛卡尔乘积A ×B 和A 的幂集P(A)。
解 A ×B={,,,,,} P(A)={,{a},{b},{}} 设A={1,2,3,4},A 上的关系R={1,1,1,2,2,4,3,1,4,3},求domR 、ranR 、R –1。 解 domR={1,2,3,4}, ranR={1,2,3,4}, R –1 ={1,1,2,1,4,2,1,3,3,4}
2、集合{2, 3, 4, 8, 9, 10, 11}上整除关系的哈斯图，并求它的最大元、最小元、极大元、极小元。 解 它的最大元、最小元都不存在；极大元为8, 9, 10, 11；极小元为2, 3, 11。
3、：N N N →⨯（N 为自然数集合），22),(y x y x f +=><，说明f 是否为单射、满射的计算})0({1-f 。 解 })0({1-f ={<0,0>}
不是单射 ,是满射的
五、有向图G 如图3-1所示。
（1）求G 的邻接矩阵A ； （2分）
（2）G 中1v 到4v 长度为4的路径有几条 （2分） （3）G 中1v 到自身长度为3的回路有几条 （2分） （4）G 是哪类连通图 （2分） 解：
（1）⎥⎥⎥⎥⎦⎤⎢⎢⎢
⎢⎣⎡=010*********
0121A ⎥⎥⎥⎥⎦⎤⎢
⎢⎢
⎢⎣⎡=1000
0100
10001321
2A ⎥⎥⎥⎥⎦⎤⎢
⎢⎢
⎢⎣⎡=01001000
01003421
3A ⎥
⎥
⎥⎥
⎦
⎤
⎢
⎢⎢
⎢⎣⎡=10000100
10004621
4A
（2）由4
A 中44
14=a 可知，1v 到4v 长度为4的路径有条（6411e e e e ，6764e e e e ，6521e e e e ，6531e e e e ）。
2
4 8 3 9
11
10
7 4 v v 3
e 3
