二、（8分）个体域为{1，2}，求?x?y（x+y=4）的真值。
解：?x?y（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∧1?0
四、（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人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。
解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝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=
解：D的邻接距阵A和可达距阵P如下：
A=
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
1 0 1 0 0
0 0 1 0 0
P=
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
一、（10分）求命题公式?(P∧Q)??(?P?R)的主合取范式。
解：?(P∧Q)??(?P?R)?（?(P∧Q)??(?P?R)）∧（?(?P?R)??(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
1
五、(10分) 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{，
解 r(R)＝R∪IA＝{，
t(R)＝?R＝{，
i?1?i4
2
32
-1
十、(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)=2?4+2?3+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
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、=?a,b?，B=?0,1,2?，求笛卡尔乘积A×B和A的幂集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。
8 4 2
3 10
9
11
3、：（N为自然数集合），f(?x,y?)?x2?y2，说明f是否为单射、满射的？计算f?1({0})。 N?N?N解
五、有向图G如图3-1所示。
（1）求G的邻接矩阵A； （2分）
（2）G中v1到v4长度为4的路径有几条？ （2分）
f?1({0})={<0,0>}
不是单射 ,是满射的
e1 v1 （3）G中v1到自身长度为3的回路有几条？ （2分） e3 （4）G是哪类连通图？ （2分） 解：
e4 e2 e6 v4 e7 v3
3??1?00?4? A??1??0??0??0200060104?1?? 0??1?3
v2 200030101??1?01?3? A??0??0??1??0e5 20004101?1?0（1）A???0??0
200011010??1?00?2? A??1??0??0??04（2）由A中a14。 ?4可知，v1到v4长度为4的路径有条（e1e1e4e6，e4e6e7e6，e1e2e5e6，e1e3e5e6）3（3）由A中a11。 ?1可知，v1到自身长度为3的回路有1条（e1e1e1）
34（4）G是单向连通图。
9. 设A?{a,b,c}，则集合S1?{{a,b},{b,c}}，S2?{{a},{a,b},{a,c}}，S3?{{a},{b,c}}，
S4?{{a,b,c}}，S5?{{a},{b},{c}}和S6?{{a},{a,c}}中是A的覆盖的有 ，是A的
划分的有 .
答案：s1, s2, s3, s4, s5 s3, s4, s5
10. A={1，2，3，4，5，6，7，8，9，10，11，12}，R是A上的整除关系。子集B={2，4，6}，那么B的最
大元是 ；B的最小元是 . 答案：不存在；2 14．命题公式P?(Q??R)的成真赋值为 ，成假赋值为 。 答案：010，100，101，110，111； 000，001，011
17．设简单图G有n个顶点m条边，v是G中度数为k的顶点，则G–{v}中有 个顶点， 条边. 答案：n-1；m-k
19．求下式的主析取范式与主合取范式。
?((P?Q)?(R?P))??((R??Q)??P)
答案：主析取范式为
(?p??q?r)?(?p?q?r)?(p??q??r)?(p??q?r)?(p?q??r)
主合取范式为
(?p??q??r)?(p??q?r)?(p?q?r)
21． 推理题（写出详细推理过程）
航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明推理：这个人一定不是航海家。
证明：
设个体域为人的集合。谓词s（x）：x是航海家；E（x）：x教育他的孩子成为航海家。
前提：?x(s(x)?E(x)), ?x(?E(x)) 结论：?x(?E(x)??S(x)) 推理过程为：
（1）?x(?E(x)) 条件引入
4
（2）?E(c) 存在规定ES （3）?x(s(x)?E(x)) 条件引入 （4）s(c)?E(c) 全称规定US （5）?S(c) （2）（4） （6）?E(c)??S(c) （2）（5） （7）?x(?E(x)??S(x)) 存在推广EG
1. 构造下面推理的证明：（10分）
前提：p→(q?r)，?s→?r，p??s； 结论：q.
证明：① p??s 前提引入 ② p ①化简 ③ p→(q?r) 前提引入 ④ q?r ②③假言推理 ⑤ ?s→?r 前提引入
⑥ ?s ①化简 ⑦ ?r ⑤⑥假言推理 ⑧ q ④⑦析取三段论
2. 求公式(p→q) ?(q→r)的主析取范式、主合取范式、成真赋值。（10分）解： (p→q) ?(q→r)
?(?p? q) ?(?q? r)
?((?p ? q) ? (r ? ?r)) ? ((p??p) (?q?r))
?(?p ? q ? r) ? (?p ? q ? ?r) ? (p ? ?q ? r) ? (?p ? ?q ? r) ?M4 ? M5 ? M2 ? M6 ?∏(2, 4, 5,6) ?∑(0, 1, 3,7)
公式(p→q) ?(q→r)的主析取范式为：∑(0, 1, 3,7)
主合取范式为：∏(2, 4, 5,6)
5