离散数学考试试题及答案-1

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））（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=V,E，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如下：01010111110010011111A=00011P=1111100000000001000011111一、（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∧M52五、(10分)设A＝{a，b，c，d}，R是A上的二元关系，且R＝{a，b，b，a，b，c，c，d}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{a，b，b，a，b，c，c，d，a，a，b，b，c，c，d，d}s(R)＝R∪R-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，b，b，d}＝R2t(R)＝iiR1＝{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×2＝1483、（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=532、写出对应下面推理的证明：如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会。所以进行离散数学考试。（其中p：今天是星期一；q：进行英语考试；r：进行离散数学考试；s：英语老师有会。）前提：p→（q∨r），s→┐q，p，s结论：r证明：①p→（q∨r）前提引入②p前提引入③q∨r①②假言推理④s→┐q前提引入⑤s前提引入⑥┐q④⑤假言推理⑦r③⑥析取三段论1、=ba,，B=2,1,0，求笛卡尔乘积A×B和A的幂集P(A)。解A×B={a,0,a,1,a,2,b,0,b,1,b,2.}P(A)={,{a},{b},{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、：NNN（N为自然数集合），22),(yxyxf，说明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）0100100001000121A10000100100013212A01001000010034213A10000100100046214A248391110e2e7v4e4v1v2v3e1e3e6e54（2）由4A中4414a可知，1v到4v长度为4的路径有条（6411eeee，6764eeee，6521eeee，6531eeee）。（3）由3A中1311a可知，1v到自身长度为3的回路有1条（111eee）。（4）G是单向连通图。9.设},,{cbaA，则集合}},{},,{{1cbbaS，}},{},,{},{{2cabaaS，}},{},{{3cbaS，}},,{{4cbaS，}}{},{},{{5cbaS和}},{},{{6caaS中是A的覆盖的有，是A的划分的有.答案：s1,s2,s3,s4,s5s3,s4,s510.A={1，2，3，4，5，6，7，8，9，10，11，12}，R是A上的整除关系。子集B={2，4，6}，那么B的最大元是；B的最小元是.答案：不存在；214．命题公式)(RQP的成真赋值为，成假赋值为。答案：010，100，101，110，111；000，001，01117．设简单图G有n个顶点m条边，v是G中度数为k的顶点，则G–{v}中有个顶点，条边.答案：n-1；m-k19．求下式的主析取范式与主合取范式。))(())()((PQRPRQP答案：主析取范式为)()()()()(rqprqprqprqprqp主合取范式为)()()(rqprqprqp21．推理题（写出详细推理过程）航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明推理：这个人一定不是航海家。证明：设个体域为人的集合。谓词s（x）：x是航海家；E（x）：x教育他的孩子成为航海家。前提：E(x))x()),()((xExsx结论：))()((xSxEx推理过程为：（1）))((xEx条件引入5（2）)(cE存在规定ES（3）))()((xExsx条件引入（4）)()(cEcs全称规定US（5）)(cS（2）（4）（6）)()(cScE（2）（5）（7）))()((xSxEx存在推广EG1.构造下面推理的证明：（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)6公式(p→q)(q→r)的成真赋值为：000，001，011，1113.设集合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)。a••bd••c2）,0000100001010010M,00000000101001012MMMR2={a,a，a,c，b,b，b,d}（3）r(R)=R∪IA={a,b,b,a,b,c,c,d,a,a,b,b,c,c,d,d}s(R)=R∪R–1={a,b,b,a,b,c,c,d,c,b,d,c}5.已知某有向图G的邻接矩阵如下：（8分）12341210001001010010vvAvv问：（1）画出图G。（2）试用邻接矩阵求G中长度小于等于2的通路的条数，其中回路有几条？（3）该图是为强连通图还是弱连通图？解：（1）有向图G如右图：7vv11vv33vv22vv44（2）,0100101001000121A10100200101013312AAAG中长度小于等于2的通路的条数为：8+14=24，其中，回路为1+5=6条。（3）该图为弱连通图。7.图G是一个简单的连通平面图，顶点数为8，其无限面的次数为5，其余面都为三角形（次数为3），计算平面图G的边数和面数。解：设平面图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,2,5,2,4,3,4,4,4,5,2,5,4}R4={2,2,2,4,3,4,4,4,5,1,5,5