离散数学期末试题.PAGE/NUMPAGES离散数学考试试题〔A卷及答案一、〔10分求>的主析取范式解：>>∨>∨>∧∧∧>∧∧∧∧∨∨∨∨∨二、〔10分在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是XX人,是上海人。乙说：王教授不是上海人,是XX人。丙说：王教授既不是上海人,也不是XX人。王教授听后说：你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人？解设设P：王教授是XX人；Q：王教授是上海人；R：王教授是XX人。则根据...
.PAGE/NUMPAGES离散数学考试试题〔A卷及
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
一、〔10分求
>的主析取范式解：><>∨>∨>∧∧∧>∧∧∧∧∨∨∨∨∨二、〔10分在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是XX人,是上海人。乙说：王教授不是上海人,是XX人。丙说：王教授既不是上海人,也不是XX人。王教授听后说：你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人？解设设P：王教授是XX人；Q：王教授是上海人；R：王教授是XX人。则根据题意应有：甲：P∧Q乙：Q∧P丙：Q∧R王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有Q∧P,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：<<P∧Q>∧<∨<Q∧R>>>∨<<Q∧P>∧<Q∧R>><P∧Q∧Q∧R>∨<P∧Q∧Q∧R>∨<Q∧P∧Q∧R><P∧Q∧R>∨P∧Q∧RT因此,王教授是上海人。三、〔10分证明tsr是包含R的且具有自反性、对称性和传递性的最小关系。证明设R是非空集合A上的二元关系,则tsr是包含R的且具有自反性、对称性和传递性的关系。若是包含R的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r。则srs<>＝,进而有tsrt<>＝。综上可知,tsr是包含R的且具有自反性、对称性和传递性的最小关系。四、〔15分集合A＝{a,b,c,d,e}上的二元关系R为R＝{,,,,,,,,,,,,,},<1>写出R的关系矩阵。<2>判断R是不是偏序关系,为什么？解<1>R的关系矩阵为：<2>由关系矩阵可知,对角线上所有元素全为1,故R是自反的；＋≤1,故R是反对称的；可计算对应的关系矩阵为：由以上矩阵可知R是传递的。五、〔10分设A、B、C和D为任意集合,证明×C＝－。证明：因为<,>∈×C∈∧∈C<∈A∧B>∧∈C<∈A∧∈C∧B>∨<∈A∧∈C∧C><∈A∧∈C>∧<B∨C><∈A∧∈C>∧<∈B∧∈C><,>∈∧<,><,>∈－所以,×C＝。六、〔10分设f：AB,g：BC,h：CA,证明：如果hogof＝IA,fohog＝IB,gofoh＝IC,则f、g、h均为双射,并求出f－1、g－1和h－1。解因IA恒等函数,由hogof＝IA可得f是单射,h是满射；因IB恒等函数,由fohog＝IB可得g是单射,f是满射；因IC恒等函数,由gofoh＝IC可得h是单射,g是满射。从而f、g、h均为双射。由hogof＝IA,得f－1＝hog；由fohog＝IB,得g－1＝foh；由gofoh＝IC,得h－1＝gof。七、〔15分设是一代数系统,运算*满足交换律和结合律,且a*x＝a*yx＝y,证明：若G有限,则G是一群。证明因G有限,不妨设G＝{,,…,}。由a*x＝a*yx＝y得,若x≠y,则a*x≠a*y。于是可证,对任意的a∈G,有aG＝G。又因为运算*满足交换律,所以aG＝G＝Ga。令e∈G使得a*e＝a。对任意的b∈G,令c*a＝b,则b*e＝*e＝c*＝c*a＝b,再由运算*满足交换律得e*b＝b,所以e是关于运算*的幺元。对任意a∈G,由aG＝G可知,存在b∈G使得a*b＝e,再由运算*满足交换律得b*a＝e,所以b是a的逆元。由a的任意性知,G中每个元素都存在逆元。故G是一群。八、〔20分〔1证明在n个结点的连通图G中,至少有n－1条边。证明不妨设G是无向连通图〔若G为有向图,可略去边的方向讨论对应的无向图。设G中结点为、、…、。由连通性,必存在与相邻的结点,不妨设它为〔否则可重新编号,连接和,得边,还是由连通性,在、、…、中必存在与或相邻的结点,不妨设为,将其连接得边,续行此法,必与、、…、中的某个结点相邻,得新边,由此可见G中至少有n－1条边。〔2给定简单无向图G＝,且|V|＝m,|E|＝n。试证：若n≥＋2,则G是哈密尔顿图。证明若n≥＋2,则2n≥m2－3m＋6〔1。若存在两个不相邻结点、使得d<>＋d<>＜m,则有2n＝＜m＋＋m＝m2－3m＋6,与〔1矛盾。所以,对于G中任意两个不相邻结点、都有d<>＋d<>≥m。由定理10.26可知,G是哈密尔顿图。离散数考试试题〔B卷及答案一、〔10分使用将命题公式化为主范式的方法,证明∧。证明：因为<P∨Q>∨∨∧<Q∨P>∧∨<Q∧Q>∨∨∨P∨>∨∨∨所以,∧。二、〔10分证明下述推理：如果A努力工作,那么B或C感到愉快；如果B愉快,那么A不努力工作；如果D愉快那么C不愉快。所以,如果A努力工作,则D不愉快。解设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为：AB∨C,BA,DCAD<1>A附加前提<2>AB∨CP<3>B∨CT<1><2>,I<4>BAP<5>ABT<4>,E<6>BT<1><5>,I<7>CT<3><6>,I<8>DCP<9>DT<7><8>,I<10>ADCP三、〔10分证明xyQ><xPyQ>。xyQ>xy<P∨Q>x<P∨yQ>xP∨yQxP∨yQ<xPyQ>四、〔10分设A＝{,1,{1}},B＝{0,{0}},求P、P－{0}、PB。解P＝{,{},{1},{{1}},{,1},{,{1}},{1,{1}},{,1,{1}}}P－{0}＝{,{0},{{0}},{0,{0}}－{0}＝{,{0},{{0}},{0,{0}}PB＝{,{0},{{0}},{0,{0}}{0,{0}}＝{,0,{{0}},{0,{0}}五、〔15分设X＝{1,2,3,4},R是X上的二元关系,R＝{<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}<1>画出R的关系图。<2>写出R的关系矩阵。<3>说明R是否是自反、反自反、对称、传递的。解<1>R的关系图如图所示：<2>R的关系矩阵为：<3>对于R的关系矩阵,由于对角线上不全为1,R不是自反的；由于对角线上存在非0元,R不是反自反的；由于矩阵不对称,R不是对称的；经过计算可得,所以R是传递的。六、〔15分设函数f：R×RR×R,f定义为：f<>＝。<1>证明f是单射。<2>证明f是满射。<3>求逆函数f－1。<4>求复合函数f－1of和fof。证明<1>对任意的x,y,x1,y1∈R,若f<>＝f<>,则＝,x＋y＝x1＋y1,x－y＝x1－y1,从而x＝x1,y＝y1,故f是单射。<2>对任意的∈R×R,令x＝,y＝,则f<>＝<＋,－>＝,所以f是满射。<3>f－1<>＝<,>。<4>f－1of<>＝f－1>>＝f－1<>＝<,>＝fof<>＝f>>＝f<>＝>＝<2x,2y>。七、〔15分给定群,若对G中任意元a和b,有a3*b3＝3,a4*b4＝4,a5*b5＝5,试证是Abel群。证明对G中任意元a和b。因为a3*b3＝3,所以*a3*b3*＝*3*,即得a2*b2＝2。同理,由a4*b4＝4可得,a3*b3＝3。由a5*b5＝5可得,a4*b4＝4。于是*＝4＝a4*b4,即b4*a＝a*b4。同理可得,*＝3＝a3*b3,即b3*a＝a*b3。由于*b3＝a*b4＝b4*a＝b*＝b*＝*b3,故a*b＝b*a。八、〔15分〔1证明在n个结点的连通图G中,至少有n－1条边。证明不妨设G是无向连通图〔若G为有向图,可略去边的方向讨论对应的无向图。设G中结点为、、…、。由连通性,必存在与相邻的结点,不妨设它为〔否则可重新编号,连接和,得边,还是由连通性,在、、…、中必存在与或相邻的结点,不妨设为,将其连接得边,续行此法,必与、、…、中的某个结点相邻,得新边,由此可见G中至少有n－1条边。〔2试给出|V|＝n,|E|＝的简单无向图G＝是不连通的例子。解下图满足条件但不连通。
本文档为【离散数学期末试题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483