离散数学考试试题及答案

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）110四、（10分）已知A=1,2,3,4,5和R=,，求r(R)、s(R)和t(R)。解：r(R)=,s(R)=,t(R)=,五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。解 设、分别表

2、示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|20，|2|55，|70/0.5140。由容斥原理，得|所以|75|75(|)(|2|)|75140552010没有乘坐过其中任何一种的儿童共10人。九、（10分）已知：D=，V=1,2,3,4,5，E=,，求D的邻接距阵A和可达距阵P。解：D的邻接距阵A和可达距阵P如下：01010111110010011111A=00011P=1111100000000001000011111一、（10分）求命题公式(PQ)(PR)的主合取范式。解：(PQ)(PR)（(PQ)(PR)）（(PR)(PQ)）（(PQ)(PR)）（(PR)(PQ)）(PQ)

3、(PR)(PR)（QP）（QR）(PQR)(PQR)（PQR）（PQR）M1M3M4M5五、(10分) 设Aa，b，c，d，R是A上的二元关系，且R，求r(R)、s(R)和t(R)。解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。解：最优二叉树为权(2+4)4+63+122+(8+10)3+1421483、（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

4、+23+x1解得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：英语老师有会。） 前提：p（qr），sq，p，s 结论：r 证明：p（qr） 前提引入 p 前提引入qr 假言推理sq 前提引入s 前提引入q

5、 假言推理r 析取三段论1、=，B=，求笛卡尔乘积AB和A的幂集P(A)。解 AB=, 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,3,3,42、集合2, 3, 4, 8, 9, 10, 11上整除关系的哈斯图，并求它的最大元、最小元、极大元、极小元。解 它的最大元、最小元都不存在；极大元为8, 9, 10, 11；极小元为2, 3, 11。2483911103、：（N为自然数集合），说明f是否为单射、满射的？计

6、算。解 = 不是单射 ,是满射的五、有向图如图3-1所示。27441231365（1）求的邻接矩阵； （2分）（2）中到长度为4的路径有几条？ （2分）（3）中到自身长度为3的回路有几条？ （2分）（4）是哪类连通图？ （2分）解：（1） （2）由中可知，到长度为4的路径有条（，）。（3）由中可知，到自身长度为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的最大元是

7、；B的最小元是 .答案：不存在；214命题公式的成真赋值为 ，成假赋值为 。答案：010，100，101，110，111； 000，001，01117设简单图G有n个顶点m条边，v是G中度数为k的顶点，则Gv中有 个顶点， 条边.答案：n-1；m-k19求下式的主析取范式与主合取范式。答案：主析取范式为 主合取范式为21 推理题（写出详细推理过程）航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明推理：这个人一定不是航海家。证明：设个体域为人的集合。谓词s（x）：x是航海家；E（x）：x教育他的孩子成为航海家。前提：结论：推理过程为：（1） 条件引入（2） 存在规定ES（3

8、） 条件引入（4） 全称规定US（5） （2）（4）（6） （2）（5）（7） 存在推广EG1. 构造下面推理的证明：（10分）前提：p(qr)，sr，ps；结论：q.证明： ps 前提引入 p 化简 p(qr) 前提引入 qr 假言推理 sr 前提引入 s 化简 r 假言推理 q 析取三段论2. 求公式(pq) (qr)的主析取范式、主合取范式、成真赋值。（10分）解： (pq) (qr)(p q) (q r)(p q) (r r) (pp) (qr)(p q r) (p q r) (p q r) (p q r)M4 M5 M2 M6 (2, 4, 5,6)(0, 1, 3,7)公式(pq)

9、 (qr)的主析取范式为：(0, 1, 3,7)主合取范式为：(2, 4, 5,6)公式(pq) (qr)的成真赋值为：000，001，011，1113. 设集合A=a,b,c,d，R是A上的二元关系，R= , , , ；(8分)（1）画出R的关系图；（2）求R2； （3）求出R的自反闭包r(R)、对称闭包s(R)。 2） R2 = ， （3）r(R)= RIA=,s(R)=RR1=, 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的边数和面数。解：设平面图G的边数为m，面数为r。由于图G顶点个数为8，由连通平面图欧拉公式可知： 8 m