离散数学样卷参考答案

参考答案试卷一一、选择填空1.C2.A3.D4.D5.A6.A7.B8.C9.D10.B二、填空1.主合取范式)()(qpqp.前束范式))()((xGxFx或))()((yGxFyx2.n-k,93.)(A{Φ,{1}，{2}，{1，2}}，BA={〈1,a〉,1,b,2,a,2,b}4.[b]R={1,2,3},X/R={{1,2,3},{4},{5}}.5．,,Gyx)()()(yfxfyxf。6.)(1Rr{2,1,4,2,1,1,3,3,2,2}，SR{1,4,2,2}。7.15，12.8.42134321=(132)141324321=(123)9．0,4510．2,0三1.×2.√3.√4.×5.×四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。试求其共有多少个结点？多少片叶？解:设该树其有x片叶,则顶点数为x+7,根据树的性质知,该树有x+6边,由握手定理有:3*2+2*3+2*4+x*1=2(x+6),得x=8故该树共有15个结点,8片叶.2.已知X={a,b,c},给出X上的所有等价关系。解:X的划分其有五种:S1={{a,b,c}},S2={{a,b},{c}},S3={{a,c},{b}},S4={{a},{b,c}},S5={{a},{b},{c}},因为X上划分与等价关系一一对应,故x上共有五个等价关系，它们是：R1＝{a,b,b,a,a,cc,a,b,c,c,b}XIR2＝{a,b,b,a}XI,R3＝{a,cc,a}XIR4＝{b,c,c,b}XI,R5＝XI3.．画一棵权为2，3，3，4，5，6，7，8的最优二叉树，并计算出它的树权。解:图略,W(T)=106五、1、已知偏序集〈X,R〉,其中X={a,b,c,d,e},Y={d,e},R的关系矩阵为求：(1).用集合的列举法写出R(2).画出R的哈斯图；(3).找出X的极大元、极小元、最大元、最小元；(4).找出Y的上界、下界、最小上界、最大下界。解:(1).R的关系矩阵R={a,c,b,c,d,a,〈d,b,d,cd,e,e,a,e,b,e,c}xI,(2).略1011111111001000011000101RM(3)．X的极大元c、极小元d、最大元c、最小元d；(4).Y的上界e,a,b,c、下界d、最小上界e、最大下界d。2．已知有向图G=V,E,其中v={a,b,c,d}，E={a,b,a,d,b,a,b,b,b,c,b,d,c,d,d,a,d,b}(1).求出各点的入度序列、出度序列(2).判定图G是否为欧拉图？，是否哈密顿图？并说明理由。(3).写出G的邻接矩阵；(4).找出所有长度等于3的路的条数.解:1.各点的入度序列:2,3,1,3各点的出度序列:2,4,1,22.不是欧拉图,是哈密顿图3.0011100011111010GM4.21210011313211222M,42542121638652533M所有长度等于3的路共有59条六、证明题1．构造推理证明，前题))()((xHxFx，))()((xGxHx结论)()(yyGxxF证明:(1))(xxF附加前题;(2))(aFT(1)EI规则;(3)))()((xHxFxP;(4))()(aHaFT(3)UI规则;(5))(aHT(2)(4)假言推理规则;(6)))()((xGxHxP;(7))()(aGaHT(6)UI规则;(8))(aGT(5)(7)析取三段论.(9))(yyGT(8)EG规则.2．在实数集R上定义二元运算：xyyxyx，其中的其它运算符均为R上的普通运算，证明R，是可交换独异点。证明:按下列4步进行证明(1)*是二元运算,R，*是代数系统;(2)*满足结合律,R，*是半群;(3)0是单位元,R，*是独异点;(4)*满足交换律试卷二一、选择填空1.A2.D3.C4.D5.D6.B7.C8.B9.D10.B二、填空1.主析取范式)()(qpqp.前束范式))()((yGxFyx2.2,),(yxF3.)(A{Φ,{Φ}}，BA={〈1,1〉,1,2,2,1,2,2}4.[b]R={1,2},X/R={{1,2},{3},{4,5}}.5．3,206.)(RS{1,2,2,1,4,2,2,4,3,3}，SS{4,4,2,2}。7.10，12.8.31424321=(1243)124314321=(234)9．1,-1/410．2,0三1.√2.√3.√4.√5.×四.1．一棵树具有2个2度结点，3个3度结点，4个4度结点，其余为叶。试求其共有多少个结点？多少片叶？解:设该树其有x片叶,则顶点数为x+9,根据树的性质知,该树有x+8条边,由握手定理有:2*2+3*3+4*4+x*1=2(x+8),得x=13故该树共有22个结点,13片叶.2.．已知X={a,b,c},给出X上所有的双射。答X上共有六个双射:f1＝{a,a,b,b,c,c},f2＝{a,a,b,c,c,b}f3＝{a,b,b,a,c,c},f4＝{a,b,b,c,c,a}f5＝{a,c,b,a,c,b},f6＝{a,c,b,b,c,a}3.．画一棵权为2，3，3，4，5，6，7，8的最优二叉树，并计算出它的树权。解:图略,W(T)=111五1、已知偏序集〈X,R〉,其中X={2,3,4,6,8,12},Y={3,6},R的X上的整除关系,(1).用集合的列举法写出R(2).画出R的哈斯图；(3).找出X的极大元、极小元、最大元、最小元；(4).)找出Y的上界、下界、最小上界、最大下界。解:(1).R的关系矩阵R={2,4,2,6,2,8,2,12〈3,6,2,12,4,8,4,12,6,12}xI,(2).略(3)．X的极大元12、极小元2,3、最大元12、最小元无；(4).Y的上界6,12下界3、最小上界6、最大下界3。2．已知有向图G=V,E,其中v={a,b,c,d}E={a,b,a,d,b,a,b,b,b,c,b,d,c,d,d,b,}1.画出该图;2.判定图G的连通性(强连通、单侧连通、弱连通)?3.写出G的邻接矩阵；4.找出所有从a到c的长度为3的简单路;解:解:1.图略2.强连通3.0010100011111010GM4.共有两条adbc,abbc六、证明题1．构造推理证明，前提：,,,srqppr结论：.qs证：(1)qpP;(2)pT(1)化简规则;(3)qT(1)化简规则(4)prP;(5)rT(2)(4)拒取式规则;(6)srP;(7)sT(5)(6)假言推理;(8)qsT(3)(7)合取式.2．Z11={0,1,2,3}，在Z11上定义运算：)(yxyxmod11，证明Z11,是一个循环群。证明:按下列4步进行证明(1)是二元运算,Z11,是代数系统;(2)满足结合律,Z11,是半群;(3)0是单位元,Z11,是独异点;(4)001,xx111,()0x,所以,Z11,是群;(5)1是生成元.010,111,212,313,xx1所以Z4,是循环群;试卷三一、填空题：1、给定含有4个原子命题的某命题公式，则该公式的真值表中共有16种不同的真值指派。2、公式（P∧Q）∨1的对偶公式是（P∨Q）∧0。3、在根树中，树叶的出度为_____0_____，入度为___1_____。4、X={a,b,c,d,e},X上的等价关系R={a,b,b,a,c,d,d,c,}∪Ix,则[b]R=_{a,b}_,X/R=_{{a,b},{c,d},{e}}_______.5、一个含2个变项qp,的命题公式的主析取范式是1000mm,则它的主合取范式是1101MM。6、设A={1，2，3}，则A的幂集Ρ（A）={φ,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}。7、设A={a，b}，B={0，1，2}，则A×B={〈a,0〉，〈a,1〉,〈a,2〉，〈b,0〉,〈b,1〉，〈b,2〉}，B×A={〈0,a〉，〈0,b〉,〈1,a〉，〈1,b〉,〈2,a〉，〈2,b〉}。8、已知集合A={1，2，3，4}，R和S都是A上的二元关系，且R={〈1,2〉，〈3,4〉}，S={〈2,3〉，〈4,1〉}，则RoS={〈1,3〉，〈3,1〉}，SoR={〈2,4〉，〈4,2〉}。9、设有程序集P={P1，P2，P3，P4}上的“调用”关系：R={(P1，P2)，(P1，P3)，(P2，P3)，(P2，P4)}，则其传递闭包为{(P1，P2)，(P1，P3)，(P2，P3)，(P1，P4)，(P2，P4)}。10、设集合X={a，b，c，d，e}上的偏序关系如图：则X的最大元a，最小元无，极大元a，极小元d,c。二、选择题：1、命题公式rqp)(的成真赋值为A。A．001，011，101，110，111；B.全体赋值；C．000，010，110；D.无。2、给定如图1的图，则相对于完全图的补图是(2)。3、集合A上的恒等关系IA没有的性质是B。A.对称性；B.反自反性；C.传递性；D.反对称性。4、设N是自然数集合，对下述每一种情况，运算是不可结合的有D。A．a⊙b=max(a,b)；B.a⊙b=min(a,b)；C．a⊙b=a+b+3；D.a⊙b=a+2b。5、有向图G=〈V,E〉其中V={1，2，3，4}，E={〈1,2〉，〈3,1〉，〈3,4〉，〈4,2〉}，则G是B。A．强连通图；B.弱连通图；B．单向连通图；D.非连通图。6、以下各命题中A为真。A.{a,b}{{a},a,b}；B.{}；C.ρ()=；D.P({0})={0}。7、设F={-1,1}，运算是普通乘法，则F,A。A.是群；B.是半群但不是独异点；C.不是半群；D.是独异点。8、设为集合，则A-B=C。A.BxAxx；B.BxAxx；C.BxAxx；D.BxAxx。9、A上关系的复合运算满足____C_____。A.交换律；B.幂等律；C.结合律；D.消去律。10、T是无向树，则T不具有的性质是C。A．T是最小连通图；B.T中每条边均是桥；C．T的边数等于顶点数；D.T是最大无回路图。三、判断题：1、设A、B、C为任意的命题公式，若A∨BA∨C，则BC。[╳]2、公式（P∧Q）→（P∨Q）是永真式。[√]3、一个不是自反的关系，一定是反自反的。[╳]4、设A为任意非空集合，⊙是一个二元运算，则称〈A,⊙〉为代数系统。[╳]5、一个有5个结点，4条边的无向图是树。[╳]四、将下面命题符号化：1、3是有理数当且仅当美国位于非洲。P:3是有理数Q:美国位于非洲P←→Q2、只有你陪伴我或代我叫辆车子，我才出去。P:你陪伴我,Q:你代我叫辆车子,R:我出去R→(P∨Q)五、设有一棵树T，它有2个结点次数为4，3个结点次数为3，其余的结点的次数都为1，问这棵树有多少个结点的次数为1？并请画出这棵树。解:设有x个结点的次数为1,则这棵树有5+x个结点,其边数为4+x,由握手定理知