离散数学考试试题及答案

1、二、（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）Û（00）（01）Û11Û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>,<

2、;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分)

3、75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。解 设、分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|20，|2|55，|70/0.5140。由容斥原理，得|所以|75|75(|)(|2|)|75140552010没有乘坐过其中任何一种的儿童共10人。九、（10分）已知：D=<V,E>，V=1,2,3,4,5，E=<1,2>,<1,4>,<2,3>,

4、<3,4>,<3,5>,<5,1>，求D的邻接距阵A和可达距阵P。解：D的邻接距阵A和可达距阵P如下：01010111110010011111A=00011P=1111100000000001000011111一、（10分）求命题公式Ø(PQ)«Ø(ØP®R)的主合取范式。解：Ø(PQ)«Ø(ØP®R)Û（Ø(PQ)®Ø(ØP®R)）（Ø(ØP®R)®Ø

5、;(PQ)）Û（(PQ)(ØPØR)）（(PR)(ØPØQ)）Û(PQ)(ØPØR)Û(PØR)（QØP）（QØR）Û(PQØR)(PØQØR)（ØPQR）（ØPQØR）ÛM1M3M4M5五、(10分) 设Aa，b，c，d，R是A上的二元关系，且R<a，b>，<b，a>，<b，c>，<c，d>，求r(R)、s(R)和t(R)。解 r(R)RIA<

6、;a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>s(R)RR-1<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>R2<a，a>，<a，c>，<b，b>，<b，d>R3<a，b>，<a，d>，<b，a>，<b，c>R4<a，a>，<a，c>，<b

7、，b>，<b，d>R2t(R)<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。解：最优二叉树为权(2+4)×4+6×3+12×2+(8+10)×3+14×21483、（5分）树T有2个4度顶点，2个3度顶点，其余顶点全是树叶。问T有几片树叶？解、设T有x片树叶, n个顶点，m条边n=2

8、+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=52、写出对应下面推理的证明：如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会。所以进行离散数学考试。（其中p：今天是星期一；q：进行英语考试；r：进行离散数学考试；s：英语老师有会。） 前提：

9、p（qr），sq，p，s 结论：r 证明：p（qr） 前提引入 p 前提引入qr 假言推理sq 前提引入s 前提引入q 假言推理r 析取三段论1、=，B=，求笛卡尔乘积A×B和A的幂集P(A)。解 A×B=<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2.> P(A)=F,a,b,a.b设A=1,2,3,4,A上的关系R=1,1,1,2,2,4,3,1,4,3,求domR、ranR、R1。解 domR=1,2,3,4, ranR=1,2,3,4, R1 =1,1,2,1,4,2,1,

10、3,3,42、集合2, 3, 4, 8, 9, 10, 11上整除关系的哈斯图，并求它的最大元、最小元、极大元、极小元。解 它的最大元、最小元都不存在；极大元为8, 9, 10, 11；极小元为2, 3, 11。2483911103、：（N为自然数集合），说明f是否为单射、满射的？计算。解 =<0,0> 不是单射 ,是满射的五、有向图如图3-1所示。27441231365（1）求的邻接矩阵； （2分）（2）中到长度为4的路径有几条？ （2分）（3）中到自身长度为3的回路有几条？ （2分）（4）是哪类连通图？ （2分）解：（1） （2）由中可知，到长度为4的路径有条（，）。（3）由中

11、可知，到自身长度为3的回路有1条（）。（4）是单向连通图。9. 设，则集合，和中是A的覆盖的有 ，是A的划分的有 . 答案：s1, s2, s3, s4, s5 s3, s4, s510. A=1，2，3，4，5，6，7，8，9，10，11，12，R是A上的整除关系。子集B=2，4，6，那么B的最大元是 ；B的最小元是 .答案：不存在；214命题公式的成真赋值为 ，成假赋值为 。答案：010，100，101，110，111； 000，001，01117设简单图G有n个顶点m条边，v是G中度数为k的顶点，则Gv中有 个顶点， 条边.答案：n-1；m-k19求下式的主析取范式与主合取范式。答案：主

12、析取范式为 主合取范式为21 推理题（写出详细推理过程）航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明推理：这个人一定不是航海家。证明：设个体域为人的集合。谓词s（x）：x是航海家；E（x）：x教育他的孩子成为航海家。前提：结论：推理过程为：（1） 条件引入（2） 存在规定ES（3） 条件引入（4） 全称规定US（5） （2）（4）（6） （2）（5）（7） 存在推广EG1. 构造下面推理的证明：（10分）前提：p(qÚr)，ØsØr，pÙØs；结论：q.证明： pÙØs 前提引入 p 化简 p(q&

13、#218;r) 前提引入 qÚr 假言推理 ØsØr 前提引入 Øs 化简 Ør 假言推理 q 析取三段论2. 求公式(pq) Ù(qr)的主析取范式、主合取范式、成真赋值。（10分）解： (pq) Ù(qr)Û(ØpÚ q) Ù(ØqÚ r)Û(Øp Ú q) Ú (r Ù Ør) Ù (pÚØp) (ØqÚr)Û(Øp Ú

14、q Ú r) Ù (Øp Ú q Ú Ør) Ù (p Ú Øq Ú r) Ù (Øp Ú Øq Ú r)ÛM4 Ù M5 Ù M2 Ù M6 Û(2, 4, 5,6)Û(0, 1, 3,7)公式(pq) Ù(qr)的主析取范式为：(0, 1, 3,7)主合取范式为：(2, 4, 5,6)公式(pq) Ù(qr)的成真赋值为：000，001，011，1113. 设集合

15、A=a,b,c,d，R是A上的二元关系，R=<a,b> ,<b,a> ,<b,c> , <c,d >；(8分)（1）画出R的关系图；（2）求R2； （3）求出R的自反闭包r(R)、对称闭包s(R)。 2） R2 = <a, a>，< a, c >，< b, b >，< b, d > （3）r(R)= RIA=<a,b>,<b,a>,<b,c>,<c,d>,<a,a >,<b,b>,<c,c>,<d,d>s

16、(R)=RR1=<a,b>,<b,a>,<b,c>,<c,d>,<c,b >,<d,c> 5. 已知某有向图G的邻接矩阵如下：（8分） 问：（1）画出图G。 （2）试用邻接矩阵求G中长度小于等于2的通路的条数，其中回路有几条？（3）该图是为强连通图还是弱连通图？ 解：（1）有向图G如右图： （2）G中长度小于等于2的通路的条数为：8+14=24，其中，回路为1+5=6条。（3）该图为弱连通图。7. 图G是一个简单的连通平面图，顶点数为8，其无限面的次数为5，其余面都为三角形（次数为3），计算平面图G的边数和面数。解：设平面

17、图G的边数为m，面数为r。由于图G顶点个数为8，由连通平面图欧拉公式可知： 8 m + r =2 由平面图握手定理可知： 5 +3(r-1) =2m 解可得：m =16，r =10，即平面图G的边数为16，面数为10。七、设R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。解：r(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>s(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>R2=R5=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>R3=<2,1>