离散数学试卷及答案(19)

离散数学试卷（十九）123一、填空20%（每空2分）：1．若对命题P赋值1，Q赋值0，则命题QP的真值为。2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为。3．公式))(()(SQPQP的对偶公式为。4．图的对偶图为。5．若关系R是等价关系，则R满足性质。6．关系R的传递闭包t(R)=。7．代数系统,A是群，则它满足。8．设,,,,BA和是两代数系统，f是从,,,,BA到的同态映射，则f具有性质。9．若连通平面图EVG,共有r个面，其中eEvV,，则它满足的Euler公式为。10．树T的边数e与点数v有关系。二、选择10%（每小题2分）：1．如果解释I使公式A为真，且使公式BA也为真，则解释I使公式B为（）。A、真；B、假；C、可满足；D、与解释I无关。2．设baA,，则P（A）×A=（）。A、A；B、P（A）；C、bAaAbbabbaaaba,,,,},{,},{,},{,},{,,,,；离散数学试卷（十九）124D、AbAabbbaabaaba,,,,}{,,}{,,}{,,}{,,,,,。3．设集合A，B是有穷集合，且nBmA,，则从A到B有（）个不同的双射函数。A、n；B、m；C、!n；D、!m。4．设K={e,a,b,c}，,K是Klein四元群，则元素a的逆元为（）。A、e；B、a；C、b；D、c。5．一个割边集与任何生成树之间（）。A、没有关系；B、割边集诱导子图是生成树；C、有一条公共边；D、至少有一条公共边。三、逻辑推理12%：符号化命题“每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家”；并用演绎方法证明上面推理。（F(x)：x是学术会成员；H(x)：x是工人；G(x)：x是专家；R(x)：x是青年人）四、8%：求集合),3,2,1(10nnxxAn的并与交。五、12%：在实数平面上，画出关系0202,yxyxyxR，并判定关系的特殊性质。六、8%：问代数系统,,,24GCDLCMS是否是布尔代数，为什么？（其中24S为能整除24的所有正整数，LCM为最小公倍数，GCD为最大公约数，xx24）七、10%：求图中的一棵最小生成树。离散数学试卷（十九）125八、10%：求图的邻接矩阵和可达矩阵。九、10%：证明：如果G是无向简单图且2，则G包含一条长度不小于1的基本回路。一、填空20%（每空2分）1、0；2、QP；3、))(()(SQPQP；4、5、自反性、对称性、传递性；6、RRii1；7、①运算*在A上封闭，②*在A上可结合，③*在A上存在幺元，④A中每个元素都有逆元；8、)()()(,)()()(,,bfafbafbfafbafAba9、2rev；10、1ve。二、选择题10%（每小题2分）1、A；2、C；3、D；4、B；5、D。三、解：符号化：前提))()((,))()()((xRxFxxHxGxFx结论))()()((xGxRxFx推理演绎：（1）))()((xRxFxP（2）)()(cRcFES(1)(3)))()()((xHxGxFxP(4)))()()((cHcGcFUS(3)离散数学试卷（十九）126(5)F(c)T(2)I(6))()(cHcGT(5)(4)I(7)R(c)T(2)I(8)G(c)T(6)I(9))()()(cGcRcFT(5)(7)(8)I(10)))()()((xGxRxFxEG(9)四、解：（1）132110nnxxAAA（2）13211010nxxnxxAAA五、解：（1）关系图为x-y+2=0与x-y-2=0两直线将实平面划分为三个区域x-y+20，x-y-20为包含原点的狭长区域。（2）①R自反任意实数x，x-x+20，x-x-20,所以直线y=x上的点在区域内，即x,xR,故R自反；②R对称若Ryx,有0202yxyx得0)2(20)2(2yxxyyxxy即Rxy,所以R对称；③因R自反且结点集非空，故R非反自反；④因R对称且结点集非空，并非全是孤立点，故R不是反对称；（0，2）（2，0）（0，-2）（0，0）（-2，0）离散数学试卷（十九）127⑤由0202yxyx得22xyx所以R41,1而R1,1所以R4不是传递的。六、解：不是布尔代数。因S24的最小元为1，最大元为24，但122242，LCM(2,12)=1224，vb且12)24,2()2,2(GCDGCD。七、解：用Kruskal算法，选一条权最小的边，逐一选取剩余的边中与已知边未构成回路且权数最小的边),(21vv，每次选出的边记入T,其权加入T的成本。T的边T的成本),(21vv2),(83vv2+2),(74vv2+2+2),(65vv2+2+2+2),(76vv2+2+2+2+3),(41vv2+2+2+2+3+3八、解：0000000100000010110100000)(GA，0000000001000000010100000)(2GA，0000000000000000000100000)(3GA，554)(OGA。离散数学试卷（十九）128所以可达矩阵0000000101000010110100000432AAAAP。九、解：设G中最长的基本路l为（点不同）：kvvvv210，则0v的所有邻接点均在l上，否则它与l是最长的基本道路矛盾。将0v的所有邻接点中下标最大者记为m，显然m，取l中子基本通路为mvvvv210，连接0v与mv之间的边便得G的一条长度不小于1的基本回路：1210vvvvvQm