离散数学试题与答案试卷一一、填空20%（每小题2分）1．设（N：自然数集，E+正偶数）则。2．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上二元运算如下：*abcdabcdabcdbcdacdabdabc那么代数系统
的幺元是，有逆元的元素为，它们的逆元分别为。10．下图所示的偏序集中，是格的为。二、选择20%（每小题2分）1、下列是真命题的有（ ）A．；B．；C．；D．。2、下列集合中相等的有（）A．{4，3}；B．{，3，4}；C．{4，，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}，P（A）（A的幂集）上规定二元系如下则P（A）/R=（）A．A；B．P(A)；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（）7、下列函数是双射的为（）A．f:IE,f(x)=2x；B．f:NNN,f(n)=；C．f:RI,f(x)=[x]；D．f: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度结点。A．1；B．2；C．3；D．4。三、
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
26%1、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当和在R中有<.b,c>在R中。（8分）1、f和g都是群到的同态映射，证明是的一个子群。其中C=(8分)1、G=(|V|=v，|E|=e)是每一个面至少由k（k3）条边围成的连通平面图，则，由此证明彼得森图（Peterson）图是非平面图。（11分）四、逻辑推演16%用CP
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
证明下题（每小题8分）1、2、五、计算18%1、设集合A={a，b，c，d}上的关系R={,,,}用矩阵运算求出R的传递闭包t(R)。（9分）2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，使得各城市之间能够通信而且总造价最小。 （９分）试卷一答案：一、填空20%（每小题2分）1、{0，1，2，3，4，6}；2、；3、1；4、；5、1；6、{<1,1>,<1,3>,<2,2>,<2,4>}；7、{,,,,}IA；8、9、a；a,b,c,d；a,d,c,d；10、c;二、选择20%（每小题2分）题目12345678910答案CDB、CCADCADBA三、证明26%1、证：“”若由R对称性知，由R传递性得“”若，有任意，因若所以R是对称的。若，则即R是传递的。2、证，有，又★★★是的子群。3、证：①设G有r个面，则，即。而故即得。（8分）②彼得森图为，这样不成立，所以彼得森图非平面图。（3分）1、逻辑推演16%1、证明：①P（附加前提）②T①I③P④T②③I⑤T④I⑥T⑤I⑦P⑧T⑥⑦I⑨CP2、证明①P（附加前提）②US①③P④US③⑤T②④I⑥UG⑤⑦CP1、计算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则公式真值为。1、设S={a1，a2，…，a8}，Bi是S的子集，则由B31所表达的子集是。1、设A={2，3，4，5，6}上的二元关系，则R=（列举法）。R的关系矩阵MR=。5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R=；A上既是对称的又是反对称的关系R=。*abcabcabcbbcccb6、设代数系统，其中A={a，b，c},则幺元是；是否有幂等性；是否有对称性。7、4阶群必是群或群。8、下面偏序格是分配格的是。9、n个结点的无向完全图Kn的边数为，欧拉图的充要条件是。10、公式的根树表示为。二、选择20%（每小题2分）1、在下述公式中是重言式为（）A．；B．；C．；D．。2、命题公式中极小项的个数为（），成真赋值的个数为（）。A．0；B．1；C．2；D．3。3、设，则有（）个元素。A．3；B．6；C．7；D．8。1、设，定义上的等价关系则由R产生的上一个划分共有（）个分块。A．4；B．5；C．6；D．9。5、设，S上关系R的关系图为则R具有（）性质。A．自反性、对称性、传递性；B．反自反性、反对称性；C．反自反性、反对称性、传递性；D．自反性。6、设为普通加法和乘法，则（）是域。A．B．C．D．=N。7、下面偏序集（）能构成格。8、在如下的有向图中，从V1到V4长度为3的道路有（）条。A．1；B．2；C．3；D．4。9、在如下各图中（）欧拉图。10、设R是实数集合，“”为普通乘法，则代数系统是（）。A．群；B．独异点；C．半群。三、证明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，25，36，49，64，81，100构造一棵最优二叉树。（7分）试卷二答案：1、填空20%（每小题2分）1、；2、T3、4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}6、a；否；有7、Klein四元群；循环群8、B9、；图中无奇度结点且连通10、1、选择20%（每小题2分）题目12345678910答案B、DD；DDBDABBBB、C1、证明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分①P②P③US②④T①I⑤T③④I⑥T①I⑦T⑤⑥I⑧EG⑦……11分３、１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图.1、计算14%1、7分解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>{[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]}{[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]}{[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]}Z6的左陪集：Z6。2、7分试卷三试题与答案1、填空20%（每空2分）1、设f，g是自然数集N上的函数，则。2、设A={a，b，c}，A上二元关系R={,,,},则s（R）=。3、A={1，2，3，4，5，6}，A上二元关系，则用列举法T=；T的关系图为；T具有性质。4、集合的幂集=。5、P，Q真值为0；R，S真值为1。则的真值为。6、的主合取范式为。7、设P（x）：x是素数，E(x)：x是偶数，O(x)：x是奇数N(x,y)：x可以整数y。则谓词的自然语言是。8、谓词的前束范式为。1、选择20%（每小题2分）1、下述命题公式中，是重言式的为（）。A、；B、；C、；D、。2、的主析取范式中含极小项的个数为（）。A、2；B、3；C、5；D、0；E、8。3、给定推理①P②US①③P④ES③⑤T②④I⑥UG⑤推理过程中错在（）。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、；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都有可能。1、用CP规则证明16%（每小题8分）1、2、四、（14%）集合X={<1,2>,<3,4>,<5,6>,…}，R={<,>|x1+y2=x2+y1}。1、证明R是X上的等价关系。（10分）1、求出X关于R的商集。（4分）五、（10%）设集合A={a,b,c,d}上关系R={,,,}要求1、写出R的关系矩阵和关系图。（4分）2、用矩阵运算求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明也是函数。2、（10分）设函数，证明有一左逆函数当且仅当f是入射函数。答案：1、填空20%（每空2分）1、2(x+1)；2、；3、；4、反对称性、反自反性；4、；5、1；6、；7、任意x，如果x是素数则存在一个y，y是奇数且y整除x；8、。1、选择20%（每小题2分）题目12345678910答案CCCCABDADC1、证明16%(每小题8分)1、①P（附加前提）②T①I③P④T②③I⑤T④I⑥T⑤I⑦P⑧T⑥⑦I⑨CP2、①P（附加前提）②T①E③ES②④P⑤US④⑥T③⑤I⑦EG⑥⑧CP1、14%（1）证明：1、自反性：2、对称性：3、传递性：即由（1）（2）（3）知：R是X上的先等价关系。2、X/R=1、10%1、；关系图2、t(R)={,,,,,,,,}。六、20%1、（1）（2）。2、证明：。。*则是一个群（称作Klein四元群答案：1、填空15%（每小题3分）1、；2、奇数；3、5；4、n；5、臂力小者1、选择15%（每小题3分）题目12345答案BCBBA1、证明34%1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集V={v1，…，vn}，设，无向图G=（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2）若G中有一个孤立点，则G中的至少有3个顶点，现不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中顶点数到值只能是1，2，…，n-1这n-1个数，因而取n-1个值的n个顶点的度数至少有两个结点度数是相同的。2、（8分）证：设G中两个奇数度结点分别为u，v。若u，v不连通，即它们中无任何通路，则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。3、（8分）证：n=6,m=12欧拉公式n-m+f=2知f=2-n+m=2-6-12=8由图论基本定理知：，而，所以必有，即每个面用3条边围成。4、（10分）证：设循环群[A，·]的生成元为a，同态映射为f，同态像为，于是都有对n=1有n=2,有若n=k-1时有对n=k时，这表明，f(A)中每一个元素均可表示为，所以是以f(a)生成元的循环群。1、中国邮递员问题14%解：图中有4个奇数结点，（1）求任两结点的最短路再找两条道路使得它们没有相同的起点和终点，且长度总和最短：（2）在原图中复制出，设图G‘，则图G‘中每个结点度数均为偶数的图G‘存在欧拉回路，欧拉回路C权长为43。1、根树的应用13%解：用100乘各频率并由小到大排列得权数（1）用Huffman算法求最优二叉树：（2）前缀码用00000传送5；00001传送6；0001传送7；100传送3；101传送4；001传送2；11传送1；01传送0（频率越高传送的前缀码越短）。1、10%证明：（1）乘：由运算表可知运算*是封闭的。（1）群：即要证明，这里有43=64个等式需要验证但：①e是幺元，含e的等式一定成立。②ab=a*b=b*a，如果对含a，b的等式成立，则对含a、b、ab的等式也都成立。③剩下只需验证含a、b等式，共有23=8个等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b；(a*b)*b=ab*b=a=a*(b*b)=a*e=a；(a*a)*a=e*a=a=a*(a*a)=a*e=a；(a*a)*b=e*b=b=a*(a*b)=a*ab=b；(b*b)*a=e*a=a=b*(b*a)=b*ab=a；(b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b；(b*a)*b=ab*b=a=b*(a*b)=b*ab=a。（1）幺：e为幺元（1）逆：e-1=e；a-1=a；b-1=b；(ab)-1=ab。所以为群。试卷八试题与答案1、填空15%（每小题3分）1、n阶完全图Kn的边数为。2、右图的邻接矩阵A=。3、图的对偶图为。4、完全二叉树中，叶数为nt，则边数m=。5、设<{a,b,c},*>为代数系统，*运算如下：*abcaabcbbaccccc则它的幺元为；零元为；a、b、c的逆元分别为。1、选择15%（每小题3分）1、图相对于完全图的补图为（）。2、对图G则分别为（）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。3、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（）片树叶。A、3；B、4；C、5；D、64、设是代数系统，其中+，·为普通的加法和乘法，则A=（）时是整环。A、；B、；C、；D、。5、设A={1，2，…，10}，则下面定义的运算*关于A封闭的有（）。A、x*y=max(x,y)；B、x*y=质数p的个数使得；C、x*y=gcd(x,y)；(gcd(x,y)表示x和y的最大公约数)；D、x*y=lcm(x,y)（lcm(x,y)表示x和y的最小公倍数）。1、证明45%1、设G是（n,m）简单二部图，则。（8分）2、设G为具有n个结点的简单图，且则G是连通图。（8分）3、设G是阶数不小于11的简单图，则G或中至少有一个是非平图。（14分）4、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：+01·01001000110101证明它是一个环，并且是一个域。（15分）1、生成树及应用10%1、（10分）如下图所示的赋权图表示某七个城市及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。 2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。1、5%对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MaxMin+可结合性可交换性存在幺元存在零元答案：1、填空15%（每小题3分）1、；2、；3、；4、；5、a，c，a、b、没有1、选择15%（每小题3分）题目12345答案AACDA，C1、证明45%1、（8分）：设G=（V，E），对完全二部图有当时，完全二部图的边数m有最大值。故对任意简单二部图有。2、（8分）反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然。与假设矛盾。所以G连通。3、（14分）（1）当n=11时，边数条，因而必有或的边数大于等于28，不妨设G的边数，设G有k个连通分支，则G中必有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则,矛盾）下面用反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3。于是G的每个面至少由g()条边围成，由点、边、面数的关系，得：而矛盾，所以G为非平面图。（2）当n>11时，考虑G的具有11个顶点的子图，则或必为非平面图。如果为非平面图，则为非平面图。如果为非平面图，则为非平面图。4、（15分）1）[{0，1}，+，·]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0……结合律成立。幺：幺元为0。逆：0，1逆元均为其本身。所以，<{0，1}，+>是Abel群。②<{0，1}，·>是半群乘：由“·”运算表知封闭群：(0·0)·0=0·（0·0）=0；（0·0）·1=0·（0·1）=1；（0·1）·0=0·（1·0）=1；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0；…③·对+的分配律对Ⅰ0·（x+y）=0=0+0=(0·x)+(0·y)Ⅱ1·（x+y）当x=y(x+y)=0则当（）则所以均有同理可证：所以·对+是可分配的。由①②③得，<{0，1}，+，·>是环。（2）<{0，1}，+，·>是域因为<{0，1}，+，·>是有限环，故只需证明是整环即可。①乘交环：由乘法运算表的对称性知，乘法可交换。②含幺环：乘法的幺元是1③无零因子：1·1=1≠0因此[{0，1}，+，·]是整环，故它是域。1、树的应用20%1、（10分）解：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价五、（10分）由二叉树知H、A、P、Y、N、E、W、R对应的编码分别为000、001、010、011、100、101、110、111。显然{000，001，010，011，100，101，110，111}为前缀码。英文短语HAPPYNEWYEAR的编码信息为000001010010011100101001001101001111六、5%MaxMin+可结合性YYY可交换性YYY存在幺元NNY存在零元NNN试卷九试题与答案1、填空30%（每空3分）1、选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A=。2、集合A={,{}}的幂集P(A)=。3、设A={1，2，3，4}，A上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图。4、设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则=。=。5、设|A|=3，则A上有个二元关系。6、A={1，2，3}上关系R=时，R既是对称的又是反对称的。7、偏序集的哈斯图为，则=。8、设|X|=n，|Y|=m则（1）从X到Y有个不同的函数。（2）当n,m满足时，存在双射有个不同的双射。9、是有理数的真值为。10、Q：我将去上海，R：我有时间，公式的自然语言为。11、公式的主合取范式是。12、若是集合A的一个分划，则它应满足。1、选择20%（每小题2分）1、设全集为I，下列相等的集合是（）。A、；B、；C、；D、。2、设S={N，Q，R}，下列命题正确的是（）。A、；B、；C、；D、。3、设C={{a},{b},{a,b}}，则分别为（）。A、C和{a,b}；B、{a,b}与；C、{a,b}与{a,b}；D、C与C4、下列语句不是命题的有（）。A、x=13；B、离散数学是计算机系的一门必修课；C、鸡有三只脚；D、太阳系以外的星球上有生物；E、你打算考硕士研究生吗？5、的合取范式为（）。A、；B、；C、D、。6、设|A|=n，则A上有（）二元关系。A、2n；B、n2；C、；D、nn；E、。7、设r为集合A上的相容关系，其简化关系图（如图），则[I]r产生的最大相容类为（）；A、；B、；C、；D、[II]A的完全覆盖为（）。A、；B、；C、；D、。8、集合A={1，2，3，4}上的偏序关系图为则它的哈斯图为（）。9、下列关系中能构成函数的是（）。A、；B、；C、；D、。10、N是自然数集，定义（即x除以3的余数），则f是（）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。1、简答题15%1、(10分)设S={1,2,3,4,6,8,12,24}，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?2、（5分）设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？1、逻辑推理10%或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，如果许多学生喜欢逻辑，那么数学并不难学。五、10%设X={1,2,3,4,5}，X上的关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}，用Warshall方法，求R的传递闭包t(R)。六、证明15%1、每一有限全序集必是良序集。（7分）2、设是复合函数，如果满射，则也是满射。（8分）答案1、填空20%（每小题2分）1、；2、；3、见右图；4、{<1,2>,<2,4>,<3,3>,<1，3>，<2,4>,<4,2>}、{<1,4>,<2,2>}；5、29；6、{<1,1>,<2,2>,<3,3>；7、{,,,,,,,,,}；8、mn、n=m、n!；9、假；10、我将去上海当且仅当我有空；11、；12、。1、选择20%（每小题2分）题目12345678910答案A、DCBA、EB、DCB、D；CABD1、简答题15%1、（10分）（1）≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>}covS={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12>,<8,24>,<12,24>}Hass图为（2）极小元、最小元是1，极大元、最大元是24。2、（5分）解：公式A涵义为：对任意的实数x,y,z，如果x,<1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>}。1、证明15%1、（7分）证明：设，全序集。若不是良序集，那么必有一子集，在B中不存在最小元素，由于B是一有限集合，故一定可找出两元素x,y是无关的，由于是全序集。所以x,y必有关系，矛盾。故必是良序集。2、（8分）证明：设，由于满射，故必有使得，由复合函数定义知，存在使得，又因为g是函数，必对任，必使，任每个z在g作用下都是Y中元素的一个映象，由Z的任意性，所以g是满射。试卷十试题与答案1、填空10%（每小题2分）1、若P，Q为二命题，真值为1，当且仅当。2、对公式中自由变元进行代入的公式为。3、的前束范式为。4、设x是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y的自由的，则被称为全称量词消去规则，记为US。5、与非门的逻辑网络为。1、选择30%（每小题3分）1、下列各符号串，不是合式公式的有（）。A、；B、；C、；D、。2、下列语句是命题的有（）。A、2是素数；B、x+5>6；C、地球外的星球上也有人；D、这朵花多好看呀！。3、下列公式是重言式的有（）。A、；B、；C、；D、4、下列问题成立的有（）。A、若，则；B、若，则；C、若，则；D、若，则。5、命题逻辑演绎的CP规则为（）。A、在推演过程中可随便使用前提；B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C、如果要演绎出的公式为形式，那么将B作为前提，设法演绎出C；D、设是含公式A的命题公式，，则可用B替换中的A。6、命题“有的人喜欢所有的花”的逻辑符号化为（）。设D：全总个体域，F（x）：x是花，M(x)：x是人，H(x,y)：x喜欢yA、；B、；C、；D、。7、公式换名（）。A、；B、；C、；D、。8、给定公式，当D={a,b}时，解释（）使该公式真值为0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=19、下面蕴涵关系成立的是（）。A、；B、；C、；D、。10、下列推理步骤错在（）。①P②US①③ES②④UG③⑤EG④A、①→②；B、②→③；C、③→④；D、④→⑤。1、逻辑判断28%1、（8分）下列命题相容吗？2、（10分）用范式方法判断公式是否等价。3、（10分）下列前提下结论是否有效？今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。1、计算12%1、（5分）给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。求复合命题：的真值。2、（7分）给定解释I：D={2，3}，L（x,y）为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,求谓词合式公式的真值。1、逻辑推理20%1、（10分）所有有理数是实数，某些有理数是整数，因此某些实数是整数。2、（10分）符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。答案1、填空15%（每小题3分）1、P，Q的真值相同；2、；3、；4、；5、。1、选择30%（每小题3分）题目12345678910答案B、CA、CBC、DCDAB、CB、DC1、逻辑判断28%1、（8分）①P②AP③BT①②I④P⑤T④E⑥T⑤I⑦FT③⑥I所以不相容。2、（10分）所以两式等价。3、设P：今天天晴，Q：今天下雨，R：我不看书，S：我看电影符号化为：①P②P③T①②I④T③I⑤P⑥T⑤E⑦T④⑥I结论有效。1、计算12%1、（5分）解：P，Q是真命题，R是假命题。2、（7分）1、逻辑推理20%1、（10分）解：设R(x)：x是实数，Q(x)：x是有理数，I(x)：x是整数符号化：前提：，结论：①P②ES①③P④US③⑤T②I⑥T④⑤I⑦T②I⑧T⑥⑦I⑨EG⑧2、解：F(x)：x是病人，G(x)：x是医生，H(x)：x是骗子，L(x,y)：x相信y符号化：前提：结论：⑴P⑵ES⑴⑶T⑵I⑷T⑵I⑸P⑹US⑸⑺T⑶⑹I⑻T⑺E⑼US⑷⑽US⑻⑾T⑼⑽I⑿UG⑾卷十一试题与答案1、填空20%（每小题2分）1、称为命题。2、命题P→Q的真值为0，当且仅当。3、一个命题含有4个原子命题，则对其所有可能赋值有种。4、所有小项的析取式为。5、令P（x）：x是质数，E（x）：x是偶数，Q（x）：x是奇数，D（x，y）：x除尽y.则的汉语翻译为。6、设S={a，b,c}则S6的集合表示为。7、P（P()）=。8、=。9、设R为集合A上的关系，则t（R）=。10、若R是集合A上的偏序关系，则R满足。1、选择20%（每小题2分）1、下列命题正确的有（）。A、若是满射，则是满射；B、若是满射，则都是满射；C、若是单射，则都是单射；D、若单射，则是单射。2、设f，g是函数，当（）时，f=g。A、；B、；C、；D、。3、下列关系，（）能构成函数。A、；B、；C、；D、。4、下列函数（）满射；（）单射；（）双射（）；一般函数（）。A、；B、（除以3的余数）；C、；D、。5、集合A={1，2，3，4}上的偏序关系为，则它的Hass图为（）。6、设集合A={1，2，3，4，5}上偏序关系的Hass图为则子集B={2，3，4}的最大元（）；最小元（）；极大元（）；极小元（）；上界（）；上确界（）；下界（）；下确界（）。A、无，4，2、3，4，1，1，4，4；B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4；D、无，4，2、3，4，1，1，4，无。7、设R，S是集合A上的关系，则下列（）断言是正确的。A、自反的，则是自反的；B、若对称的，则是对称的；C、若传递的，则是传递的；D、若反对称的，则是反对称的8、设X为集合，|X|=n，在X上有（）种不同的关系。A、n2；B、2n；C、；D、。9、下列推导错在（）。①P②US①③ES②④UG③A、②；B、③；C、④；D、无。10、“没有不犯错误的人”的逻辑符号化为（）。设H（x）：x是人，P（x）：x犯错误。A、；B、；C、；D、。1、命题演绎28%1、（10分）用反证法证明。2、（8分）用CP规则证明。3、（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。1、8%将化为与其等价的前束范式。五、8%A={a,b,c,d}，R={,,,}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的关系图。六、证明16%1、（8分）设A={1，2，3，4}，在P（A）上规定二元关系如下：P（A）证明R是P（A）上的等价关系并写出商集P（A）/R。1、（8分）设f是A到A的满射，且，证明f=IA。答案1、填空20%（每小题2分）1、能够断真假的阵述句；2、P的真值为1，Q的真值为0；3、24=16；4、永真式；5、任意两数x、y,如果x是偶数且能除尽y，则y一定是偶数；6、S110={a,b}；7、；8、；9、；10、自反性、反对称性、传递性二、选择20%（每小题2分）题目12345678910答案A、DBC、DC、D；A、D；D；BCAADCB、D三、命题演绎28%1、（10分）证明：⑴P（附加前提）⑵T⑴E⑶P⑷T⑶E⑸P⑹T⑷⑸E⑺T⑹E⑻T⑺I⑼T⑵⑻I⑽P⑾T⑽E⑿T⑾E⒀T⑼⑿I2、（8分）①P（附加前提）②P③T①②I④P⑤T③④I⑥T⑤E⑦CP3、证明：设Q（x）：x是有理数，R(x)：x是实数，N(x)：x是无理数，C(x)：x是虚数。前提：结论：⑴P⑵US⑴⑶P⑷US⑶⑸P⑹US⑸⑺T⑹E⑻T⑵⑺I⑼T⑷⑺I⑽T⑻⑼I⑾T⑽E⑿UG⑾四、8%解：五、8%解：所以t（R）={,,,,,,,,}关系图为六、证明16%1、（8分）证明：⑴P（A），由于，所以，即R自反的。⑵P（A），若，则，，R是对称的。⑶P（A），若：，即：所以R是传递的。由⑴⑵⑶知，R是等价关系。P（A）/R={[]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R}2、（8分）证明：因为f是满射，所以，存在使得，又因为f是函数，所以即由所以，又，所以由a的任意性知：f=IA。卷十二试题与答案1、填空20%（每空2分）1、设集合A={1，2，3，4，5，6，7，8，9，10}，定义A上的二元关系“≤”为x≤y=x|y,则=。2、设，定义A上的二元运算为普通乘法、除法和加法，则代数系统中运算*关于运算具有封闭性。3、设集合S={α，β，γ，δ，ζ}，S上的运算*定义为*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ则代数系统中幺元是，β左逆元是，无左逆元的元素是。4、在群坯、半群、独异点、群中满足消去律。5、设是由元素生成的循环群，且|G|=n，则G=。6、拉格朗日定理说明若是群的子群，则可建立G中的等价关系R=。若|G|=n,|H|=m则m和n关系为。7、设f是由群到群<,*>的同态映射，是中的幺元，则f的同态核Ker(f)=。1、选择20%（每小题2分）1、设f是由群到群<,*>的同态映射，则ker(f)是（）。A、的子群；B、G的子群；C、包含；D、包含G。2、设是环，，a·b的关于“+”的逆元是（）。A、(-a)·(-b)；B、(-a)·b；C、a·(-b)；D、a·b。3、设是一代数系统且是Abel群，如果还满足（）是域。A、是独异点且·对+可分配；B、是独异点，无零因子且·对+可分配；C、是Abel群且无零因子；D、是Abel且·对+可分配。4、设是一代数系统，+、·为普通加法和乘法运算，当A为（）时，是域。A、；B、；C、；D、。5、设是一个格，由格诱导的代数系统为，则（）成立。A、；B、；C、；D、。6、设是偏序集，“”定义为：，则当A=（）时，是格。A、{1,2,3,4,6,12}；B、{1,2,3,4,6,8,12,14}；C、{1,2,3,…，12}；D、{1,2,3,4}。7、设是由格诱导的代数系统，若对，当时，有（）是模格。A、；B、；C、；D、。8、在（）中，补元是唯一的。A、有界格；B、有补格；C、分配格；D、有补分配格。9、在布尔代数中，当且仅当（）。A、；B、；C、；D、。10、设是布尔代数，f是从An到A的函数，则（）。A、f是布尔代数；B、f能表示成析取范式，也能表示成合取范式；C、若A={0，1}，则f一定能表示成析取范式，也能表示成合取范式；D、若f是布尔函数，它一定能表示成析（合）取范式。三、8%设A={1，2}，A上所有函数的集合记为AA,是函数的复合运算，试给出AA上运算的运算表，并指出AA中是否有幺元，哪些元素有逆元。四、证明42%1、设是一个代数系统，*是R上二元运算，，则0是幺元且是独异点。（8分）1、设是n阶循环群，G=(a)，设b=ak，则元素b的阶为，这里d=GCD(n,k)。（10分）1、证明如果f是由到的同态映射，g是由到的同态映射，则是由到的同态映射。（6分）1、设是一个含幺环，且任意都有a·a=a，若|A|≥3则不可能是整环。（8分）1、K={1,2,5,10,11,22,55,110}是110的所有整因子的集合，证明：具有全上界110和全下界1的代数系统是一个布尔代数。（）。（10分）五、布尔表达式10%设是布尔代数上的一个布尔表达式，试写出其析取范式和合取范式。（10分）答案：一、填空20%（每空2分）1、LCM（x,y）；2、乘法；3、α、δ，γ、ζ；4、群；5、；6、、；7、二、选择20%（每小题2分）题目12345678910答案BB，CDABAADCC，D三、8%解：因为|A|=2，所以A上共有22=4个不同函数。令，其中：为AA中的幺元，和有逆元。四、证明42%1、（8分）证明：[幺]，即[乘]，由于+，·在R封闭。所以即*在R上封闭。[群]因此，〈R，*〉是独异点。2、（10分）证明：（1）（2）若b的阶不为n1，则b阶m到的同态映射。4、（8分）证明：反证法：如果是整环，且|A|≥3，则且即有且，这与整环中无零因子矛盾。所以不可能是整环。5、（10分）（1）代数系统是由格诱导的，其Hasst图为Hass图中不存在与五元素格和同构的子格。所以格是分配格。（2）即任元素都有补元，所以有补格。是布尔代数。五、布尔表达式10%解：函数表为：00000011010101111001101111011110析取范式：合取范式：试卷十三试题与答案1、填空10%（每小题2分）1、，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*运算的幺元是，零元是。2、代数系统中，|A|>1，如果分别为的幺元和零元，则的关系为。3、设是一个群，是阿贝尔群的充要条件是。4、图的完全关联矩阵为。5、一个图是平面图的充要条件是。1、选择10%（每小题2分）1、下面各集合都是N的子集，（）集合在普通加法运算下是封闭的。A、{x|x的幂可以被16整除}；B、{x|x与5互质}；C、{x|x是30的因子}；D、{x|x是30的倍数}。2、设，，其中表示模3加法，*表示模2乘法，则积代数的幺元是（）。A、<0,0>；B、<0,1>；C、<1,0>；D、<1,1>。3、设集合S={1,2,3,6}，“≤”为整除关系，则代数系统是（）。A、域；B、格，但不是布尔代数；C、布尔代数；D、不是代数系统。4、设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=（）。A、n·k；B、n(k+1)；C、n(k+1)-m；D、n(k+1)-2m。5、一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有（）个4度结点。A、1；B、2；C、3；D、4。三、判断10%（每小题2分）1、（）设S={1,2}，则S在普通加法和乘法运算下都不封闭。2、（）在布尔格中，对A中任意原子a，和另一非零元b，在或中有且仅有一个成立。3、（）设，+,·为普通加法和乘法，则是域。4、（）一条回路和任何一棵生成树至少有一条公共边。5、（）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i=t-1。四、证明38%1、（8分）对代数系统，*是A上二元运算，e为A中幺元，如果*是可结合的且每个元素都有右逆元，则（1）中的每个元素在右逆元必定也是左逆元。（2）每个元素的逆元是唯一的。2、（12分）设是一个布尔代数，如果在A上定义二元运算☆，为，则是一阿贝尔群。3、（10分）证明任一环的同态象也是一环。4、（8分）若是每一个面至少由k(k≥3)条边围成的连通平面图，则。五、应用32%1、（8分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？1、用washall方法求图的可达矩阵，并判断图的连通性。（8分）1、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分）1、用Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a，b，c，d，e，f的频率分别为2%，3%，5%，7%，8%，9%求传输它的最佳前缀码。（8分）答案：1、填空10%（每小题2分）1、1，不存在；2、；3、有；4、11100-100010-101-100-1-105、它不包含与K3,3或K5在2度结点内同构的子图。1、选择10%（每小题2分）题目12345答案A，DBCDA1、判断10%题目12345答案YYNNN1、证明38%1、（8分）证明：（1）设，b是a的右逆元，c是b的右逆元，由于，所以b是a的左逆元。（2）设元素a有两个逆元b、c，那么a的逆元是唯一的。2、（12分）证明：[乘]运算☆在A上也封闭。[群]即☆满足结合性。[幺],故全下界0是A中关于运算☆的幺元。[逆],即A中的每一个元素以其自身为逆元。[交]即运算☆具有可交换性。所以是Abel群。3、(10分)证明:设是一环,且是关于同态映射f的同态象。由是Abel群，易证也是Abel群。是半群，易证也是半群。现只需证：对是可分配的。于是同理可证因此也是环。5、（8分）证明：设G有r个面，。1、应用32%1、（8分）解：即为最少考试天数。用Welch-Powell方法对G着色：第一种颜色的点，剩余点第二种颜色的点，剩余点第三种颜色的点所以≤3任构成一圈，所以≥3故=3所以三天下午即可考完全部九门课程。2、（8分）解：1：A[2，1]=1，；2：A[4，2]=1，3：A[1，3]=A[2，3]=A[4，3]=1，4：A[k，4]=1，k=1，2，3，4，p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。3、（8分）解：用a,b,c,d,e,f,g7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为此图中的Hamilton回路即是圆桌安排座位的顺序。Hamilton回路为abdfgeca。4、（8分）解：(1)（1）用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e传输它们的最优前缀码为{0000，0001，001，01，10，11}。试卷十四试题与答案1、填空10%（每小题2分）1、设是由有限布尔格诱导的代数系统，S是布尔格，中所有原子的集合，则～。2、集合S={α，β，γ，δ}上的二元运算*为*αβγδαδαβγβαβγδγβγγγδαδγδ那么，代数系统中的幺元是,α的逆元是 。3、设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，则+3的运算表为；是否构成群。4、设G是n阶完全图，则G的边数m=。5、如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行次这个加法指令。1、选择20%（每小题2分）1、在有理数集Q上定义的二元运算*，有，则Q中满足（）。A、所有元素都有逆元；B、只有唯一逆元；C、时有逆元；D、所有元素都无逆元。2、设S={0，1}，*为普通乘法，则是（）。A、半群，但不是独异点；B、只是独异点，但不是群；C、群；D、环，但不是群。3、图给出一个格L，则L是（）。A、分配格；B、有补格；C、布尔格；D、A,B,C都不对。3、有向图D=，则长度为2的通路有（）条。A、0；B、1；C、2；D、3。4、在Peterson图中，至少填加（）条边才能构成Euler图。A、1；B、2；C、4；D、5。1、判断10%（每小题2分）1、在代数系统中如果元素的左逆元存在，则它一定唯一且。（）2、设是群的子群，则中幺元e是中幺元。（）3、设，+,·为普通加法和乘法，则代数系统是域。（）4、设G=是平面图，|V|=v,|E|=e，r为其面数，则v-e+r=2。（）5、如果一个有向图D是欧拉图，则D是强连通图。（）四、证明46%1、设，是半群，e是左幺元且，使得，则是群。（10分）1、循环群的任何非平凡子群也是循环群。（10分）1、设aH和bH是子群H在群G中的两个左陪集，证明：要末，要末。（8分）1、设，是一个含幺环，|A|>3，且对任意，都有，则不可能是整环（这时称是布尔环）。（8分）1、若图G不连通，则G的补图是连通的。（10分）五、布尔表达式8%设是布尔代数上的一个布尔表达式，试写出其的析取范式和合取范式。六、图的应用16%1、构造一个结点v与边数e奇偶性相反的欧拉图。（6分）1、假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happynewyear的编码信息。（10分）答案1、填空10%（每小题2分）+3[0][1][2][0][0][1][2][1][1][2][0][2][2][0][1]1、；2、β，γ；3、是；4、；5、91、选择10%（每小题2分）题目12345答案CBDBD1、判断10%（每小题2分）题目12345答案NYYNY1、证明46%1、（10分）证明：（1）(2)e是之幺元。事实上：由于e是左幺元，现证e是右幺元。（3）由（2），（3）知：为群。2、（10分）证明：设是循环群,G=(a)，设是的子群。且，则存在最小正整数m，使得：，对任意，必有，故：即：所以但m是使的最小正整数，且，所以r=0即：这说明S中任意元素是的乘幂。所以是以为生成元的循环群。3、（8分）证明：对集合，只有下列两种情况：（1）；（2）对于，则至少存在，使得，即有，这时任意，有，故有同理可证：所以4、（8分）证明：反证法：如果，是整环，且有三个以上元素，则
浙公网安备 33021202002483