广东海洋大学2008-2009学年第二学期--《离散数学》课程试题--B卷

广东海洋大学2008——2009学年第二学期《离散数学》课程试题B卷一、填空题（每空1分，共20分）1、命题是具有真值的。2、{,{}}A，则()PA；3、{1,2,,9}E，{1,2,3,4,5},{4,5,6,7}AB，则,AB；而,BA。4、设p：这门课让人喜欢；q：这本书有趣；r：这本书习题很难；则下列语句：1）若这本书有趣，习题也不很难，则这门课就不会让人喜欢。2）这本书没趣，习题也不很难，并且这门课不让人喜欢。3）这门课让人喜欢当且仅当这本书有趣且这本书习题不很难。符号化为1）；2）；3）。5、ppp。6、{,{},{},{,}}Aabab上的包含关系为，则子集{{},{}}Cab的极大元为，最大元为，上界为；7、若非空集合上的关系是、和的，则称为等价关系；8、(,)Gnm无向图，则G有生成树当且仅当，要确定G的一棵生成树，必删去G的条边；9、实数集R上定义如下二元运算：1）2abab；2）ababab；3）abb；4）abab其中可结合的有，可交换的有，既不可结合也不交换的有；10、无向图中所有顶点度数之和等于边数的倍。二、单项选择题（每题1分，共10分）1、下列语句中，真命题是；A、我正在说谎；B、这句话是错的；C、若1+2=3则雪是黑的；D、若1+2=5则1=2；2、下列哪个公式是永真式；A、()()pqqp；B、pqp；C、()()pqpq；D、()pq3、对任意集合,,ABC，下列结论正确的是；A、ABBCAC；B、ABBCAC；C、ABBCAC；D、ABBCAC；4、{1,2,3}A上关系{1,1,1,2,1,3,3,3}R，则R具有；A、传递性和反对称性；B、传递性和对称性；C、自反性和对称性；D、反自反性和对称性；5、下列代数系统，是独异点（R为实数集，I为整数集，I为正整数集）；A、22(,),Rabab；B、333(,),Rabab；C、(,max),maxI为求两数中较大数；D、(,gcd),gcdI为求最大公约数；6、任何一个有限群在同构意义下可看作是；A、循环群；B、置换群；C、变换群；D、Abel群；7、具有6个顶点的非同构无向树的数目为；A、4；B、5；C、6；D、8；8、若3,2,:ABfAB，则不同的映射个数为；A、23个；B、32个；C、23个；D、23个；9、{1,2,1,3,2,4,4,3}R则domR；A、{1,2,3,4}；B、{1,2,3}；C、{2,3,4}；D、{1,2,4}10、无向图,GVE是哈密顿图，11VVV，均有1()pGV1V；A、；B、；C、；D、。三、判断题（每题1分，共15分）1、语句“爱美之心人皆有之”可以用命题逻辑中的简单命题来描述（）2、所谓的“推理是有效的”是指该推理的前提和结论都是正确的（）3、由于引入了论域的概念，在一阶逻辑中，不存在永真或永假的公式（）4、在一阶逻辑（谓词逻辑）中，量词也存在分配律，全称量词对合取存在分配律，存在量词对析取存在分配律（）5、空集是一切集合的子集（）6、ABAB（）7、R为二元关系，A是集合，R在A上的限制RA还是一个关系，并且是R的子关系（）8、一个关系如果不是自反的，就一定是反自反的。（）9、不存在一种关系，即是等价关系，同时也是偏序关系（）10、Abel群肯定是独异点（）11、平凡图是连通图（）12、在有向图的可达矩阵中，对角线元素可能是0（）13、完全图Kn(n≥1)都是哈密顿图（）14、Kruskal算法构造最小生成树的过程中，按照权从大到小添加边，避免回路的出现即可（）15、在后续课程《编译原理》中有重要应用的逆波兰式是指：运算符号在他的两个运算对象之后（）三、计算题（10+10+5+10=35分）1、求()pqr的主析取范式和成真赋值；2、有向图D为1）求邻接矩阵A；2）计算A3；3）D中v3到v4的长度为3的通路有几条？说明理由。3、6,Z为群，其中{0,1,2,3,4,5}nZ，为模6加法；1）求幺元（单位元）e；2）nxZ求1x；3）计算20084；4、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，求其树叶数。四、证明题（每题10分，共20分）1、前提：(()()),(()())xFxHxxGxHx结论：(()())xGxFx证明：2、设N是自然数集，定义N上的二元关系{,,}RxyxyNxy是偶数，则R是等价关系。广东海洋大学2008——2009学年第二学期《离散数学》评分细则一、填空题（每空1分，共20分）1、唯一，陈述句；2、{,{},{{}},}A；3、{4,5},{1,2,3,6,7}；4、1）()qrp，2）qrp，3）pqr；5、p；6、{}{}ab和，无，{,}ab；7、自反，对称和传递的；8、G连通，1mn；9、2）和3），2）和4），1）；10、2。二、单项选择题（每题1分，共10分）1~5题：DCAAB；6～10题：BCBDC三、判断题（每题1分，共15分）对的有：4、5、7、10、11、15错的有：1、2、3、6、8、9、12、13、14四、计算题（10+10+5+10=35分）1、()()()()pqrpqrprqr2分13prmm2分37qrmm2分1347()pqrmmmm2分成真赋值：001、011、100、1112分2、解：1）A=3分2）A3=3分3）二条；2分因为(3)342a2分3、解：1）0e；1分2）16xx；2分3）20084(42008)mod643分4、解：设树叶数为x，2分树枝数为(213)1x，2分由握手定理有：2213342(5)xx4分故10x2分五、证明题（每题10分，共20分）1、证明：①(()())xFxHx前提引入1分②(()())xFxHx①置换1分③(()())xHxFx②置换1分④()()HxFx③UI规则1分⑤(()())xGxHx前提引入1分⑥()()GxHx⑤UI规则1分⑦()()GxFx⑥④假言三段论2分⑧(()())xGxFx⑦UG规则2分2、证：①,xNxx是偶数，,xxR，故R自反；3分②若,,xyR即xy是偶数，则yx也是偶数，,yxR，故R对称；3分③若,,,xyRyzR，即xy，yz是偶数，则()()2xzxyyzy是偶数，,xzR，故R传递；4分综上所述，R是等价关系