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

离散数学试卷（23）150一、单项选择题：（每小题1分，本大题共10分）1．命题公式)(PQP是（）。A、矛盾式；B、可满足式；C、重言式；D、等价式。2．下列各式中哪个不成立（）。A、)()())()((xxQxxPxQxPx；B、)()())()((xxQxxPxQxPx；C、)()())()((xxQxxPxQxPx；D、QxxPQxPx)())((。3．谓词公式)())()((xQyyRxPx中的x是（）。A、自由变元；B、约束变元；C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。4．在0之间应填入（）符号。A、=；B、；C、；D、。5．设A，是偏序集，AB，下面结论正确的是（）。A、B的极大元Bb且唯一；B、B的极大元Ab且不唯一；C、B的上界Bb且不唯一；D、B的上确界Ab且唯一。6．在自然数集N上，下列（）运算是可结合的。（对任意Nba,）A、baba；B、),max(baba；C、baba5；D、baba。7．Q为有理数集N，Q上定义运算*为a*b=a+b–ab,则Q，*的幺元为（）。A、a；B、b；C、1；D、0。8．给定下列序列，（）可以构成无向简单图的结点次数序列。A、（1，1，2，2，3）；B、（1，1，2，2，2）；C、（0，1，3，3，3）；D、（1，3，4，4，5）。9．设G是简单有向图，可达矩阵P(G)刻划下列（）关系。离散数学试卷（23）151A、点与边；B、边与点；C、点与点；D、边与边。10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（）。A、5；B、7；C、9；D、8。二、填空：（每空1分，本大题共15分）1．在自然数集中，偶数集为1N、奇数集为2N，则21NN=；21NN=。2．设}3,34,2,2,1{,}4,3,2,1{，RX，则r(R)=；s(R)=；t(R)=。3．设R为集合A上的等价关系，对Aa，集合Ra][=，称为元素a形成的R等价类，Ra][，因为。4．任意两个不同小项的合取为，全体小项的析取式为。5．设为偶数xxQ:)(，为素数xxP:)(，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1）；（2）。6．设T为根树，若，则称T为m元树；若则称T为完全m叉树。7．含5个结点，4条边的无向连通图（不同构）有个，它们是。三、判断改正题：（每小题2分，本大题共20分）1．命题公式BBAA))((是一个矛盾式。（）2．任何循环群必定是阿贝尔群，反之亦真。（）3．根树中最长路径的端点都是叶子。（）4．若集合A上的关系R是对称的，则1R也是对称的。（）5．数集合上的不等关系（≠）可确定A的一个划分。（）6．设集合A、B、C为任意集合，若A×B=A×C，则B=C。（）离散数学试卷（23）1527．函数的复合运算“。”满足结合律。（）8．若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。（）9．图G为（n,m）图，G的生成树GT必有n个结点。（）10．使命题公式)(RQP的真值为F的真值指派的P、Q、R值分别是T、F、F。（）四、简答题（每小题5分，本大题共25分）1．设,H和,K都是群,G的子群，问,KH和,KH是否是,G的子并说明理由。2．设}9432{，，，A，}12,10742{，，，B，从A到B的关系},,,{baBbAabaR整除且，试给出R的关系图和关系矩阵，并说明此关系是否为函数？为什么？3．设,S是半群，LO是左零元，对任LOxSx,是否是左零元？为什么？4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）5．通过主合取范式，求出使公式RQP)(的值为F的真值指派。五、证明题：（共30分）1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。2．试证明若,G是群，GH，且任意的Ha，对每一个Gx，有axxa，则,H是,G的子群。离散数学试卷（23）1533．设G是每个面至少由k（3k）条边围成的连通平面图，试证明2)2(kvke，其中v为结点数，e为边数。4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。一、单项选择题：题号12345678910答案CACDDBDBCC二、填空题：1．;2N。2．}4,4,2,2,1,1,3,3,4,2,2,1{)(Rr，}2,4,1,2,3,3,4,2,2,1{)(Rs，}3,3,4,1{2RRR，}3,3{23RRR，}3,3{34RRR，所以，}4,1,3,3,4,2,2,1{)(Rt。3．},{][aRxAxxaR；Raa][。4．永假式（矛盾式），永真式（重言式）。5．（1）)))()(())()(((yxyPyQyxPxQx。（2）))()()()((yxyPyQxPxQyx。6．每个结点的出度都小于等于m；除叶子外，每个结点的出度都等于m。7．3。三、判断改正题：1．×命题公式BBAA))((是一个重言式。离散数学试卷（23）1542．×任何循环群必定是阿贝尔群，但反之不真。3．×根树中最长路径的端点不都是叶子。4．√5．×≠不能确定A的一个划分。6．√7．√8．×欧拉图其边数e和结点数v的奇偶性可以相反。9．√10．√四、简答题1．解：,KH是,G的子群，,KH不一定是,G的子群。,,,,,,,,KHKbaHbaKHba和由则都是,G的子群，,,,1,11GKHKHbaKbaHba是且的子群。如：G={1，5，7，11}，：模12乘，则,G为群。且H={1，5}，K={1，7}，,,KH和皆为,G的子群，但}7,5,1{KH，,KH不是,G的子群。因为KH1175，即运算不封闭。2．解：}12,4,4,4,12,3,12,2,10,2,4,2,2,2{R则R的关系图为：R的关系矩阵为00000100101000011011RM关系R不是A到B的函数，因为元素2，4的象不唯一（或元素9无象）。3．解：LOx仍是左零元。因为Sy，由于LO是左零元，所以，LLOyO，又,S为半群，所以*可结合。所以，LLLOxyOxyOx)()(，所以，LOx仍是左零元。4．解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图EVG,，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得A2349B2471012离散数学试卷（23）155回路。由题已知，10)deg(,10)deg(,,vuVvu，20)deg()deg(vu，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。5．解：010110100)()()()()()()()(MMMRQPRQPRQPRQPRQRPRQPRQP原式∴使公式RQP)(的值为F的真值指派为：0:0:1:RQP；0:1:1:RQP；0:1:0:RQP。五、证明题：1．证明：假设R不是反对称的，则yxRxyRyx,,,,由R的传递性，∴Rxx,此与R反自反矛盾，∴R反对称。2．证明：（1）设群,G的幺元为e，则Gx有xeex，∴He即H非空。（2）Hba,，则Gx有bxxbaxxa,，从而Hbabaxbxabxbbabbxbaxba11111111,)()()()()()(故,H是,G的子群。3．解：设连通平面图G有t个面：trrr,,,21则有2rev，又有题意，tiiiktrkr1)deg(,)deg(又ertii2)deg(1，∴kte2，ekt2。从而22ekev，∴)2(2vkke。4．解：设)(xP：x喜欢美术，)(xQ：x喜欢体育，)(xR：x喜欢音乐。论域：人。命题形式化为：前提：))()((xQxPx，))()((xRxQx，)(xRx离散数学试卷（23）156结论：)(xPx。证明：（1）)(xRxP(2))(aRES(1)(3)))()((xRxQxP(4))()(aRaQUS(4)(5))(aQT(2)(4)I(6)))()((xQxPxP(7))()(aQaPUS(6)(8))(aPT(5)(7)I(9))(xPxEG(8)∴结论有效。