离散数学习题集十五套.doc

《离散数学习题集十五套.doc》由会员分享，可在线阅读，更多相关《离散数学习题集十五套.doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学试题与答案试卷一一、填空 20% 每题2分1设 N：自然数集，E+ 正偶数 那么 。2A，B，C表示三个集合，文图中阴影局部集合表达式为 A B C 。3设P，Q 真值为0，R，S真值为1，那么真值= 。4公式主合取范式为 。5假设解释I论域D仅包含一个元素，那么 在I下真值为 。6设A=1，2，3，4，A上关系图为那么 R2 = 。7设A=a，b，c，d，其上偏序关系R哈斯图为那么 R= 。8图补图为 。9设A=a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统幺元是 ，有逆元元素为 ，它们逆元分别为 。1

2、0以下图所示偏序集中，是格为 。 二、选择 20% 每题 2分1、以下是真命题有A ； B；C ； D 。2、以下集合中相等有 A4，3；B，3，4；C4，3，3；D 3，4。3、设A=1，2，3，那么A上二元关系有 个。 A 23 ； B 32 ； C ； D 。4、设R，S是集合A上关系，那么以下说法正确是 A假设R，S 是自反， 那么是自反； B假设R，S 是反自反， 那么是反自反； C假设R，S 是对称， 那么是对称； D假设R，S 是传递， 那么是传递。5、设A=1，2，3，4，PAA幂集上规定二元系如下那么PA/ R= AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4

3、；D，2，2，3，2，3，4，A6、设A=，1，1，3，1，2，3那么A上包含关系“哈斯图为 7、以下函数是双射为 Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。注：I整数集，E偶数集， N自然数集，R实数集8、图 中 从v1到v3长度为3 通路有 条。A 0；B 1；C 2；D 3。9、以下图中既不是Eular图，也不是Hamilton图图是 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点那么该树有 个4度结点。A1；B2；C3；D4 。三、证明 26%

4、、 R是集合X上一个自反关系，求证：R是对称和传递，当且仅当 和在R中有在R中。8分、 f和g都是群到同态映射，证明是一个子群。其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一个面至少由kk3条边围成连通平面图，那么， 由此证明彼得森图Peterson图是非平面图。11分四、逻辑推演 16%用CP规那么证明下题每题 8分1、2、五、计算 18%1、设集合A=a，b，c，d上关系R= , , , 用矩阵运算求出R传递闭包t (R)。 9分2、如以下图所示赋权图表示某七个城市及预先算出它们之间一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。分试卷

5、一答案：一、填空 20% 每题2分1、0，1，2，3，4，6； 2、；3、1； 4、； 5、1；6、, , , ；7、, IA ；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% 每题 2分题目12345678910答案C DB、CCADCADBA三、证明 26%1、 证：“ 假设由R对称性知，由R传递性得 “ 假设，有 任意 ，因假设 所以R是对称。假设， 那么 即R是传递。2、 证，有 ，又 是 子群。3、 证：设G有r个面，那么，即 。而 故即得 。8分彼得森图为，这样不成立，所以彼得森图非平面图。3分 一、 逻辑推演 16%1、 证明

6、：P附加前提TIPTITITIPTICP2、证明 P附加前提USPUSTIUGCP二、 计算 18%1、 解： ， ，t (R)= , , , , , , , , 2、 解： 用库斯克Kruskal算法求产生最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。试卷二试题与答案一、填空 20% 每题2分1、 P：你努力，Q：你失败。“除非你努力，否那么你将失败翻译为 ；“虽然你努力了，但还是失败了翻译为 。2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF那么公式真值为 。2、 设S=a1 ，a2 ，a8，Bi是S子集，

7、那么由B31所表达子集是 。3、 设A=2，3，4，5，6上二元关系，那么R= 列举法。R关系矩阵MR= 。5、设A=1，2，3，那么A上既不是对称又不是反对称关系R= ；A上既是对称又是反对称关系R= 。*a b cabca b cb b cc c b6、设代数系统，其中A=a，b，c,那么幺元是 ；是否有幂等 性 ；是否有对称性 。7、4阶群必是 群或 群。8、下面偏序格是分配格是 。9、n个结点无向完全图Kn边数为 ，欧拉图充要条件是 。10、公式根树表示为 。二、选择 20% 每题2分1、在下述公式中是重言式为 A；B；C； D。2、命题公式 中极小项个数为 ，成真赋值个数为 。A0；

8、 B1； C2； D3 。3、设，那么 有 个元素。A3； B6； C7； D8 。4、 设，定义上等价关系那么由 R产 生上一个划分共有 个分块。A4； B5； C6； D9 。5、设，S上关系R关系图为那么R具有 性质。A自反性、对称性、传递性； B反自反性、反对称性；C反自反性、反对称性、传递性； D自反性 。6、设 为普通加法和乘法，那么 是域。A BC D= N 。7、下面偏序集 能构成格。8、在如下有向图中，从V1到V4长度为3 道路有 条。A1； B2； C3； D4 。9、在如下各图中 欧拉图。10、设R是实数集合，“为普通乘法，那么代数系统 是 。A群； B独异点； C半群

9、。三、证明 46%1、 设R是A上一个二元关系，试证明假设R是A上一个等价关系，那么S也是A上一个等价关系。9分2、 用逻辑推理证明：所有舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。11分3、 假设是从A到B函数，定义一个函数对任意有，证明：假设f是A到B满射，那么g是从B到 单射。10分4、 假设无向图G中只有两个奇数度结点，那么这两个结点一定连通。8分5、 设G是具有n个结点无向简单图，其边数，那么G是Hamilton图8分四、计算 14%1、 设是一个群，这里+6是模6加法，Z6=0 ，1，2，3，4，5，试求出所有子群及其相应左陪集。7分2、 权数1，4，9，16

10、，25，36，49，64，81，100构造一棵最优二叉树。7分试卷二答案：一、 填空 20%每题2分1、；2、T 3、4、R=,； 5、R=,；R=, 6、a ；否；有 7、Klein四元群；循环群 8、 B 9、；图中无奇度结点且连通 10 、二、 选择 20%每题 2分题目12345678910答案B、DD；DDBDABBBB、C三、 证明 46%1、9分（1） S自反，由R自反，（2） S对称（3） S传递由1、2、3得；S是等价关系。2、11分证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华上述句子符号化为：前提：、 结论： 3分PPUST

11、I TITITIEG11分、0分证明 ：。4、8分证明：设G中两奇数度结点分别为u 和v，假设 u，v不连通，那么G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论根本定理矛盾，因而u，v一定连通。5、8分证明： 证G中任何两结点之和不小于n。反证法：假设存在两结点u，v 不相邻且,令，那么G-V1是具有n-2个结点简单图，它边数,可得，这与G1=G-V1为n-2个结点为简单图题设矛盾，因而G中任何两个相邻结点度数和不少于n。所以G为Hamilton图.四、 计算 14%1、 7分解：子群有；0左陪集：0，1；2，3；4，50，3左陪

12、集：0，3；1，4；2，50，2，4左陪集：0，2，4；1，3，5Z6左陪集：Z6 。2、 7分试卷三试题与答案一、 填空 20% 每空 2分1、 设 f，g是自然数集N上函数，那么 。2、 设A=a，b，c，A上二元关系R= , , , 那么sR= 。3、 A=1，2，3，4，5，6，A上二元关系，那么用列举法 T= ；T关系图为 ；T具有 性质。4、 集合幂集= 。5、 P，Q真值为0 ；R，S真值为1。那么真值为 。6、 主合取范式为 。7、 设 Px：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。那么谓词自然语言是 。8、 谓词前束范式为 。二、

13、选择 20% 每题 2分1、 下述命题公式中，是重言式为 。A、； B、；C、； D、。2、 主析取范式中含极小项个数为 。A 、2； B、 3； C、5； D、0； E、 8 。3、 给定推理PUSPESTIUG推理过程中错在 。A、-; B、-; C、-; D、-; E、-4、 设S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在条件下X与 集合相等。A、 X=S2或S5 ； B、X=S4或S5；C、X=S1，S2或S4； D、X与S1，S5中任何集合都不等。5、 设R和S是P上关系，P是所有人集合，那么表示关系 。A、；B、；C、 ；

14、 D、。6、 下面函数 是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。7、 设S=1，2，3，R为S上关系，其关系图为 那么R具有 性质。A、 自反、对称、传递； B、什么性质也没有；C、反自反、反对称、传递； D、自反、对称、反对称、传递。8、 设，那么有 。A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 设A=1 ,2 ,3 ，那么A上有 个二元关系。A、23 ； B、32 ； C、； D、。10、全体小项合取式为 。A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。三、 用CP规那么证明 16% 每题

15、 8分1、2、四、14% 集合X=, , , ，R=,|x1+y2 = x2+y1 。1、 证明R是X上等价关系。 10分2、 求出X关于R商集。4分五、10%设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R关系矩阵和关系图。4分 2、用矩阵运算求出R传递闭包。6分六、20%1、10分设f和g是函数，证明也是函数。2、10分设函数，证明 有一左逆函数当且仅当f是入射函数。答案：五、 填空 20%每空2分1、2(x+1)；2、；3、；4、反对称性、反自反性；4、；5、1；6、；7、任意x，如果x是素数那么存在一个y，y是奇数且y整除x ；8、。六、 选择 20%每题

16、 2分题目12345678910答案CCCCABDADC七、 证明 16%(每题8分)1、P附加前提TIPTITITIPTICP2、 P附加前提TEESPUSTIEGCP八、 14%（1） 证明：1、 自反性： 2、 对称性： 3、 传递性：即由123知：R是X上先等价关系。2、X/R=九、 10%1、； 关系图2、 t (R)= , , , , , , , , 。 六、 20%1、12。2、证明：。试卷四试题与答案一、 填空 10% 每题 2分1、 假设P，Q，为二命题，真值为0 当且仅当 。2、 命题“对于任意给定正实数，都存在比它大实数令F(x)：x为实数，那么命题逻辑谓词公式为 。3、

17、 谓词合式公式前束范式为 。4、 将量词辖域中出现 和指导变元交换为另一变元符号，公式其余局部不变，这种方法称为换名规那么。5、 设x是谓词合式公式A一个客体变元，A论域为D，A(x)关于y是自由，那么 被称为存在量词消去规那么，记为ES。二、 选择 25% 每题分1、 以下语句是命题有 。A、 明年中秋节晚上是晴天； B、；C、当且仅当x和y都大于0； D、我正在说谎。2、 以下各命题中真值为真命题有 。A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；C、2+24当且仅当3是奇数； D、2+24当且仅当3不是奇数；3、 以下符号串是合式公式有 A、；B、；C、；D、。4、

18、 以下等价式成立有 。A、；B、；C、 ； D、。5、 假设和B为wff，且那么 。A、称为B前件； B、称B为有效结论C、当且仅当；D、当且仅当。6、 A，B为二合式公式，且，那么 。A、为重言式； B、；C、； D、； E、为重言式。7、 “人总是要死谓词公式表示为 。论域为全总个体域M(x)：x是人；Mortal(x)：x是要死。A、； B、C、；D、8、 公式解释I为：个体域D=2，P(x)：x3, Q(x)：x=4那么A真值为 。A、1； B、0； C、可满足式； D、无法判定。9、 以下等价关系正确是 。A、；B、；C、；D、。10、 以下推理步骤错在 。PUSPESTIEGA、；

19、B、；C、；D、三、 逻辑判断30% 1、 用等值演算法和真值表法判断公式类型。10分2、 以下问题，假设成立请证明，假设不成立请举出反例：10分（1） ，问成立吗？（2） ，问成立吗？3、 如果厂方拒绝增加工资，那么罢工就不会停顿，除非罢工超过一年并且工厂撤换了厂长。问：假设厂方拒绝增加工资，面罢工刚开场，罢工是否能够停顿。10分四、计算10%1、 设命题A1，A2真值为1，A3，A4真值为0，求命题真值。5分2、 利用主析取范式，求公式类型。5分五、谓词逻辑推理 15%符号化语句：“有些人喜欢所有花，但是人们不喜欢杂草，那么花不是杂草。并推证其结论。六、证明：10%设论域D=a , b ,

20、 c，求证：。答案：十、 填空 10%每题2分1、P真值为1，Q真值为0；2、；3、；4、约束变元；5、，y为D某些元素。十一、 选择 25%每题分题目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)十二、 逻辑判断 30%1、1等值演算法2真值表法P QA1 1111111 0010010 1100010 011111所以A为重言式。2、1不成立。假设取但A与B不一定等价，可为任意不等价公式。2成立。 证明：即：所以故 。3、解：设P：厂方拒绝增加工资；Q：罢工停顿；R罢工超壶过一年；R：撤换厂长前提： 结论：PPTIPTITETI罢工不会停顿是有效结论。四、计算 10%（1） 解：（2）它无成真赋值，所以为矛盾式。五、谓词逻辑推理 15%解： 证明：P