离散数学全部试卷

.离散数学试题与答案试卷一一、填空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=。8．图的补图为。二、选择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}}7、下列函数是双射的为（）A．f:IE,f(x)=2x；B．f:NNN,f(n)=<n,n+1>；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。五、计算18%2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计，使得各城市之间能够通信而且总造价最小。　　（９分）试卷二一、填空20%（每小题2分）1、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。2、论域D={1，2}，指定谓词P P(1,1) P(1,2) P(2,1) P(2,2) T T F F则公式真值为。2、设S={a1，a2，…，a8}，Bi是S的子集，则由B31所表达的子集是。3、设A={2，3，4，5，6}上的二元关系，则R=（列举法）。R的关系矩阵MR=。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。4、设，定义上的等价关系则由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、在如下各图中（）欧拉图。四、计算14%1、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）试卷三试题与答案填空20%（每空2分）1、设f，g是自然数集N上的函数，则。2、设A={a，b，c}，A上二元关系R={<a,a>,<a,b>,<a,c>,<c,c>},则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、谓词的前束式为。2、选择20%（每小题2分）1、的主析取式中含极小项的个数为（）。A、2；B、3；C、5；D、0；E、8。2、给定推理①P②US①③P④ES③⑤T②④I⑥UG⑤推理过程中错在（）。A、①->②;B、②->③;C、③->④;D、④->⑤;E、⑤->⑥3、设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中任何集合都不等。4、设R和S是P上的关系，P是所有人的集合，，则表示关系（）。A、；B、；C、；D、。5、下面函数（）是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。6、设S={1，2，3}，R为S上的关系，其关系图为则R具有（）的性质。A、自反、对称、传递；B、什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。7、设，则有（）。A、{{1,2}}；B、{1,2}；C、{1}；D、{2}。8、设A={1,2,3}，则A上有（）个二元关系。A、23；B、32；C、；D、。10、全体小项合取式为（）。A、可满足式；B、矛盾式；C、永真式；D、A，B，C都有可能。3、用CP规则证明16%（每小题8分）1、2、四、（14%）集合X={<1,2>,<3,4>,<5,6>,…}，R={<<x1,y1>,<x2,y2>>|x1+y2=x2+y1}。1、证明R是X上的等价关系。（10分）2、求出X关于R的商集。（4分）五、（10%）设集合A={a,b,c,d}上关系R={<a,b>,<b,a>,<b,c>,<c,d>}要求1、写出R的关系矩阵和关系图。（4分）2、用矩阵运算求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明也是函数。2、（10分）设函数，证明有一左逆函数当且仅当f是入射函数。试卷四试题与答案1填空10%（每小题2分）1、若P，Q，为二命题，真值为0当且仅当。2、命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，则命题的逻辑谓词公式为。3、谓词合式公式的前束式为。4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。5、设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则被称为存在量词消去规则，记为ES。2选择25%（每小题2.5分）6、下列语句是命题的有（）。A、明年中秋节的晚上是晴天；B、；C、当且仅当x和y都大于0；D、我正在说谎。7、下列各命题中真值为真的命题有（）。A、2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；C、2+2≠4当且仅当3是奇数；D、2+2≠4当且仅当3不是奇数；8、下列符号串是合式公式的有（）A、；B、；C、；D、。9、下列等价式成立的有（）。A、；B、；C、；D、。10、若和B为wff，且则（）。A、称为B的前件；B、称B为的有效结论C、当且仅当；D、当且仅当。11、A，B为二合式公式，且，则（）。A、为重言式；B、；C、；D、；E、为重言式。12、“人总是要死的”谓词公式表示为（）。（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。A、；B、C、；D、13、公式的解释I为：个体域D={2}，P(x)：x>3,Q(x)：x=4则A的真值为（）。A、1；B、0；C、可满足式；D、无法判定。14、下列等价关系正确的是（）。A、；B、；C、；D、。15、下列推理步骤错在（）。①P②US①③P④ES③⑤T②④I⑥EG⑤A、②；B、④；C、⑤；D、⑥3逻辑判断30%16、用等值演算法和真值表法判断公式的类型。（10分）17、下列问题，若成立请证明，若不成立请举出反例：（10分）（1）已知，问成立吗？（2）已知，问成立吗？18、如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分）四、计算10%1、设命题A1，A2的真值为1，A3，A4真值为0，求命题的真值。（5分）2、利用主析取式，求公式的类型。（5分）五、谓词逻辑推理15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。六、证明：（10%）设论域D={a,b,c}，求证：。试卷五试题与答案一、填空15%（每空3分）1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有个5度结点。2、n阶完全图，Kn的点数X(Kn)=。3、有向图中从v1到v2长度为2的通路有条。4、设[R，+，·]是代数系统，如果①[R，+]是交换群②[R，·]是半群③则称[R，+，·]为环。5、设是代数系统，则满足幂等律，即对有。二、选择15%（每小题3分）1、下面四组数能构成无向简单图的度数列的有（）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；C、（1，1，2，2，2）；D、（0，1，3，3，3）。2、下图中是哈密顿图的为（）。3、如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（）A、真；B、假。4、下列偏序集（）能构成格。5、设，*为普通乘法，则[S，*]是（）。A、代数系统；B、半群；C、群；D、都不是。三、证明48%1、（10%）在至少有2个人的人群中，至少有2个人，他们有相同的朋友数。2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。4、（10%）证明循环群的同态像必是循环群。5、（12%）设是布尔代数，定义运算*为，求证[B，*]是阿贝尔群。四、计算22%1、在二叉树中1）求带权为2，3，5，7，8的最优二叉树T。（5分）2）求T对应的二元前缀码。（5分）2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。试卷六试题与答案一填空15%（每小题3分）1、n阶完全图结点v的度数d(v)=。2、设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk=。3、算式的二叉树表示为。4、如图给出格L，则e的补元是。5、一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是。二、选择15%（每小题3分）1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（）。A、群；B、环；C、域；D、格。2、设[{a,b,c}，*]为代数系统，*运算如下： * a b c a a b c b b a c c c c c则零元为（）。A、a；B、b；C、c；D、没有。3、如右图相对于完全图K5的补图为（）。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（）4度结点。A、1；B、2；C、3；D、4。5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（）时，[A，+，·]是整环。A、；B、；C、；D、。三、证明50%1、设G是（n,m）简单二部图，则。（10分）2、设G为具有n个结点的简单图，且，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下： + 0 1 · 0 1 0 0 1 0 0 0 1 1 0 1 0 1证明它是一个环，并且是一个域。（14分）4、是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）四、10%设是布尔代数上的一个布尔表达式，试写出的析取式和合取式（10分）五、10%如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。试卷七试题与答案1、填空15%（每小题3分）1.任何(n,m)图G=(V,E),边与顶点数的关系是。2.当n为时,非平凡无向完全图Kn是欧拉图。3.已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有个1度顶点。4.n阶完全图Kn的点色数X(KN)=。5.一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是。2、选择15%（每小题3分）1、下面四组数能构成无向图的度数列的有()。　A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。2、图的邻接矩阵为()。A、；B、；C、；D、。3、下列几个图是简单图的有()。A.G1=(V1,E1),其中V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；B.G2=(V2,E2)其中V2=V1,E2={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}；C.G=(V3,E3),其中V3=V1,E3={ab,be,ed,cc}；D.G=(V4,E4),其中V4=V1,E4={（a,a）,（a,b）,（b,c）,（e,c）,（e,d）}。4、下列图中是欧拉图的有()。5、，其中，为集合对称差运算，则方程的解为（）。A、；B、；C、；D、。3、证明34%1、证明：在至少有2个人的人群中，至少有2个人，他的有相同的朋友数。（8分）2、若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）3、证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。（8分）4、证明循环群的同态像必是循环群。（10分）4、中国邮递员问题13%求带权图G中的最优投递路线。邮局在v1​点。根树的应用13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。10%设B4={e,a,b,ab}，运算*如下表， * 证明<B4,*>是一个群（称作Klein四元群试卷八试题与答案1、填空15%（每小题3分）1、n阶完全图Kn​的边数为。2、右图的邻接矩阵A=。3、图的对偶图为：4、完全二叉树中，叶数为nt，则边数m=。5、设<{a,b,c},*>为代数系统，*运算如下： * a b c a a b c b b a c c c c c则它的幺元为；零元为；a、b、c的逆元分别为。2、选择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=（）时<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的最小公倍数）。3、证明45%1、设G是（n,m）简单二部图，则。（8分）2、设G为具有n个结点的简单图，且则G是连通图。（8分）3、设G是阶数不小于11的简单图，则G或中至少有一个是非平图。（14分）4、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下： + 0 1 · 0 1 0 0 1 0 0 0 1 1 0 1 0 1证明它是一个环，并且是一个域。（15分）4、生成树及应用10%1、（10分）如下图所示的赋权图表示某七个城市及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。　　2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。5、5%对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。 Max Min + 可结合性 可交换性 存在幺元 存在零元 试卷九试题与答案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的一个分划，则它应满足。2、选择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、不是单射也不是满射。3、简答题15%1、(10分)设S={1,2,3,4,6,8,12,24}，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?2、（5分）设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？4、逻辑推理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、填空10%（每小题2分）1、若P，Q为二命题，真值为1，当且仅当。2、对公式中自由变元进行代入的公式为。3、的前束式为。4、设x是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y的自由的，则被称为全称量词消去规则，记为US。5、与非门的逻辑网络为。2、选择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、④→⑤。3、逻辑判断28%1、（8分）下列命题相容吗？2、（10分）用式方法判断公式是否等价。3、（10分）下列前提下结论是否有效？今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看。故我在看书时，说明今天下雨。4、计算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,求谓词合式公式的真值。5、逻辑推理20%1、（10分）所有有理数是实数，某些有理数是整数，因此某些实数是整数。2、（10分）符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。试卷十一试题与答案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满足。2、选择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、。3、命题演绎28%1、（10分）用反证法证明。2、（8分）用CP规则证明。3、（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。4、8%将化为与其等价的前束式。五、8%A={a,b,c,d}，R={<a,b>,<b,c>,<b,d>,<c,b>}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的关系图。六、证明16%1、（8分）设A={1，2，3，4}，在P（A）上规定二元关系如下：P（A）证明R是P（A）上的等价关系并写出商集P（A）/R。2、（8分）设f是A到A的满射，且，证明f=IA。试卷十二试题与答案5、填空20%（每空2分）1、设集合A={1，2，3，4，5，6，7，8，9，10}，定义A上的二元关系“≤”为x≤y=x|y,则=。2、设，定义A上的二元运算为普通乘法、除法和加法，则代数系统<A,*>中运算*关于运算具有封闭性。3、设集合S={α，β，γ，δ，ζ}，S上的运算*定义为 * α β γ δ ζ α α β γ δ ζ β β δ α γ δ γ γ α β α β δ δ α γ δ γ ζ ζ δ α γ ζ则代数系统<S，*>中幺元是，β左逆元是，无左逆元的元素是。4、在群坯、半群、独异点、群中满足消去律。5、设<G,*>是由元素生成的循环群，且|G|=n，则G=。6、拉格朗日定理说明若<H,*>是群<G,*>的子群，则可建立G中的等价关系R=。若|G|=n,|H|=m则m和n关系为。7、设f是由群<G,☆>到群<,*>的同态映射，是中的幺元，则f的同态核Ker(f)=。6、选择20%（每小题2分）1、设f是由群<G,☆>到群<,*>的同态映射，则ker(f)是（）。A、的子群；B、G的子群；C、包含；D、包含G。2、设<A，+，·>是环，，a·b的关于“+”的逆元是（）。A、(-a)·(-b)；B、(-a)·b；C、a·(-b)；D、a·b。3、设<A，+，·>是一代数系统且<A，+>是Abel群，如果还满足（）<A，+，·>是域。A、<A，·>是独异点且·对+可分配；B、<A-{}，·>是独异点，无零因子且·对+可分配；C、<A-{}，·>是Abel群且无零因子；D、<A-{}，·>是Abel且·对+可分配。4、设<A，+，·>是一代数系统，+、·为普通加法和乘法运算，当A为（）时，<A，+，·>是域。A、；B、；C、；D、。5、设<A,>是一个格，由格诱导的代数系统为，则（）成立。A、；B、；C、；D、。6、设<A,>是偏序集，“”定义为：，则当A=（）时，<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,>诱导的代数系统，若对，当时，有（）<A,>是模格。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,*>是一个代数系统，*是R上二元运算，，则0是幺元且<R,*>是独异点。（8分）2、设<G,*>是n阶循环群，G=(a)，设b=ak，则元素b的阶为，这里d=GCD(n,k)。（10分）3、证明如果f是由<A,☆>到<B,*>的同态映射，g是由<B,*>到<C,△>的同态映射，则是由<A,☆>到<C,△>的同态映射。（6分）4、设<A，+，·>是一个含幺环，且任意都有a·a=a，若|A|≥3则<A，+，·>不可能是整环。（8分）5、K={1,2,5,10,11,22,55,110}是110的所有整因子的集合，证明：具有全上界110和全下界1的代数系统<K,LCM,GCD,ˊ>是一个布尔代数。（）。（10分）五、布尔表达式10%设是布尔代数上的一个布尔表达式，试写出其析取式和合取式。（10分）试卷十三试题与答案7、填空10%（每小题2分）1、，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*运算的幺元是，零元是。2、代数系统<A,*>中，|A|>1，如果分别为<A,*>的幺元和零元，则的关系为。3、设<G,*>是一个群，<G,*>是阿贝尔群的充要条件是。4、图的完全关联矩阵为。5、一个图是平面图的充要条件是。8、选择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}，“≤”为整除关系，则代数系统<S,≤>是（）。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中任意原子a，和另一非零元b，在或中有且仅有一个成立。3、（）设，+,·为普通加法和乘法，则<S，+，·>是域。4、（）一条回路和任何一棵生成树至少有一条公共边。5、（）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i=t-1。四、证明38%1、（8分）对代数系统<A,*>，*是A上二元运算，e为A中幺元，如果*是可结合的且每个元素都有右逆元，则（1）<A,*>中的每个元素在右逆元必定也是左逆元。（2）每个元素的逆元是唯一的。2、（12分）设是一个布尔代数，如果在A上定义二元运算☆，为，则<A,☆>是一阿贝尔群。3、（10分）证明任一环的同态象也是一环。4、（8分）若是每一个面至少由k(k≥3)条边围成的连通平面图，则。五、应用32%1、（8分）某共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？2、用washall方法求图的可达矩阵，并判断图的连通性。（8分）3、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分）4、用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、设是由有限布尔格诱导的代数系统，S是布尔格，中所有原子的集合，则～。2、集合S={α，β，γ，δ}上的二元运算*为 * α β γ δ α δ α β γ β α β γ δ γ β γ γ γ δ α δ γ δ那么，代数系统<S,*>中的幺元是,α的逆元是　　　　。3、设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，则+3的运算表为；<Z+,+3>是否构成群。4、设G是n阶完全图，则G的边数m=。5、如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行次这个加法指令。2、选择20%（每小题2分）1、在有理数集Q上定义的二元运算*，有，则Q中满足（）。A、所有元素都有逆元；B、只有唯一逆元；C、时有逆元；D、所有元素都无逆元。2、设S={0，1}，*为普通乘法，则<S,*>是（）。B、半群，但不是独异点；B、只是独异点，但不是群；C、群；D、环，但不是群。3、图给出一个格L，则L是（）。A、分配格；B、有补格；C、布尔格；D、A,B,C都不对。3、有向图D=<V,E>，则长度为2的通路有（）条。A、0；B、1；C、2；D、3。4、在Peterson图中，至少填加（）条边才能构成Euler图。A、1；B、2；C、4；D、5。3、判断10%（每小题2分）1、在代数系统<A,*>中如果元素的左逆元存在，则它一定唯一且。（）2、设<S,*>是群<G,*>的子群，则<G,*>中幺元e是<S,*>中幺元。（）3、设，+,·为普通加法和乘法，则代数系统<A，+，·>是域。（）4、设G=<V,E>是平面图，|V|=v,|E|=e，r为其面数，则v-e+r=2。（）5、如果一个有向图D是欧拉图，则D是强连通图。（）四、证明46%1、设<A,*>，是半群，e是左幺元且，使得，则<A,*>是群。（10分）2、循环群的任何非平凡子群也是循环群。（10分）3、设aH和bH是子群H在群G中的两个左陪集，证明：要末，要末。（8分）4、设<A,+,·>，是一个含幺环，|A|>3，且对任意，都有，则<A,+,·>不可能是整环（这时称<A，+，·>是布尔环）。（8分）5、若图G不连通，则G的补图是连通的。（10分）五、布尔表达式8%设是布尔代数上的一个布尔表达式，试写出其的析取式和合取式。六、图的应用16%1、构造一个结点v与边数e奇偶性相反的欧拉图。（6分）2、假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happynewyear的编码信息。（10分）试卷十五试题与答案1、填空20%（每空2分）1、如果有限集合A有n个元素，则|2A|=。2、某集合有101个元素，则有个子集的元素为奇数。3、设S={a1，a2,…，a8}，Bi是S的子集，由B17表达的子集为，子集{a2,a6,a7}规定为。4、由A1，A2,…，An，生成的最小集的形式为，它们的并为集，它们的交为集。5、某人有三个儿子，组成集合A={S1,S2,S3}，在A上的兄弟关系具有性质。6、每一个良序集必为全序集，而全序集必为良序集。7、若是函数，则当f是的，是f的逆函数。2、选择15%（每小题3分）6、集合的幂集为（）。A、；B、；C、；D、7、下列结果正确的是（）。A、；B、；C、；D、；E、；F、A⊕A=A。8、集合的最小集式为（）（由A、B、C生成）。A、；B、；C、；D、。9、在（）下有。A、；B、；C、；D、10、下列二元关系中是函数的有（）。A、；B、；C、。三、15%用Warshall算法，对集合A={1，2，3，4，5}上二元关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}求t（R）。四、15%集合，C*上定义关系，则R是C*上的一个等价关系，并给出R等价类的几何说明。五、计算15%1、设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关系。（4分）2、设Ｚ为整数集，关系为Z上等价关系，求R的模K等价关系的商集Z/R，并指出R有秩。（5分）3、设A={1，2，3，4，5}，A上的偏序关系为求A的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。（6分）六、证明20%1、假定，且是一个满射，g是个入射，则f是满射。（10分）2、设f，g是A到B的函数，，证明。（10分）试卷十六试题与答案1、判断正误20%（每小题2分）1、设A，B，C是任意三个集合。（1）若AB且BC，则AC。（）（2）若AB且BC，则AC。（）（3）若AB且BC，则AC。（）（4）A。（）（5）(AB)C=(AC)(BC)。（）2、可能有某种关系，既是对称的，又是反对称的。（　　）３、若平面图共有v个结点，e条边和r个面，则v-e+r=2。（）４、任何有向图中各结点入度之和等于边数。（）５、代数系统中一个元素若有左逆元，则该元素一定也有右逆元。（）６、任何一个循环群必定是阿贝尔群。（）2、8%将谓词公式化为前束析取式与前束合取式。3、8%设集合Ａ＝{a,b,c,d,e}上的关系Ｒ＝{<a,b>,<b,c>,<b,d>,<d,e>}写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。四、10%设<G,*>是一个群，证明：若对任意的，都有，,,则<G,*>是一个阿贝尔群。五、8%根据库拉托夫斯基定理，证明下图为非平面图，要求用两种证法。法（1）是找出与K3，3在2度结点同构的子图。法（2）是找出与K5在2度结点同构的子图。六、10%证明：每个结点的度数至少为2的图必包含一个回路。七、12%用ＣＰ规则证明：　　１、　　２、　八、12%用推理规则证明下式：前提:结论：九、12%若集合Ｘ＝｛（0，2），（１，２），（2，4），（３，４），（５，６），……｝1、证明R是X上的等价关系。2、求出X关于R的商集。试卷十七试题与答案1、判断正误20%（每小题2分）1、设A.B.C是任意三个集合。（1）若AB且BC，则AC。（）（2）若AB且BC，则AC。（）（3）若AB且BC，则AC。（）（4）A。（）（5）(A–B)C=(AC)-(BC)。（）2、可能有某种关系，既不是自反的，也不是反自反的。（　　）３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（）４、一个图是平面图，当且仅当它包含与Ｋ3，3或Ｋ5在２度结点同构的子图。（）５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（）６、群是每个元素都有逆元的半群。（）2、8%将谓词公式化为前束析取式与前束合取式。3、8%设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{<a,b>,<b,a>,<b,c>,<c,d>}写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。四、9%１、画一个有一条欧拉回路和一条汉密尔顿回路的图。２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。３、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。五、10%证明：若图Ｇ是不连通的，则Ｇ的补图是连通的。六、10%证明：循环群的任何子群必定也是循环群。七、12%用ＣＰ规则证明：　　１．。　　２．。八、10%用推理规则证明下式：前提:结论：S九、13%若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝1、证明R是X上的等价关系。2、求出X关于R的商集。试卷十八试题与答案1、选择：（满分20分，每小题2分）1．下列语句中不是命题的有（）⑴9+512；⑵x+3=5；⑶我用的计算机CPU主频是1G吗？；⑷我要努力学习。2．命题“我不能一边听课，一边看小说”的符号化为（）⑴；⑵；⑶；⑷。3．下列表达式正确的有（）⑴；⑵；⑶；⑷。4．n个命题变元可产生（）个互不等价的小项。⑴n；⑵n2；⑶2n；⑷2n。5．若公式的主析取式为则它的主合取式为（）⑴；⑵；⑶；⑷。6．命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x是聪明的，M(x)：x是人）（）⑴⑵⑶⑷7．设A={}，B=Р(Р(A))下列（）表达式成立。⑴；⑵；⑶；⑷。8．A是素数集合，B是奇数集合，则A-B=（）⑴素数集合；⑵奇数集合；⑶；⑷{2}。9．集合A={2，3，6，12，24，36}上偏序关系R的Hass图为则集合B={2，3，6，12}的上确界。B={2，3，6，12}的下界。B={6，12，24，36}的下确界。B={6，12，24，36}的上界。⑴2；⑵3；⑶6；⑷12；⑸无。10．若函数g和f的复合函数gf是双射，则（）一定是正确的。⑴g是入射；⑵f是入射；⑶g是满射；⑷f是满射。2、填空：（满分20，每小题2分）1．设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为。2．设A，B是两命题公式，当且仅当。3．要证为前提的有效结论，运用CP规则是。4．对谓词公式的自由变元代入得。5．设S={a1,a2,…,a8},Bi是S的子集，则B31=。6．设I为整数集合，R={<x,y>∣xy(mod3)则[1]=。7．偏序集〈Ρ（{a,b}），〉的Hass图为。8．对集合X和Y，设|X|=m，|Y|=n，则从X到Y的函数有个。9．设R为实数集，S={x|0<x<1}，f：RS，则f(x)=为双射。10．设K[N]=0，K[(0,1)]=，则K[N×(0,1)]=。3、证明：（48分）1．不构造真值表证明蕴涵式（7分）2．用逻辑推演下式，，（7分）3．用CP规则证明（7分）4．符号化并证明其结论：“所有有理数是实数，某些有理数是整数，因此某些实数是整数”（设R(x)：x是实数，Q(x)：x是有理数，I(x)：x是整数）（7分）5．设R是集合X上的一个自反关系，求证：R是对称的和传递的当且仅当＜a,b＞和＜a,c＞在R中，则有＜b,c＞在R中(8分)。6．设f和g是函数，则f∩g也是函数。（6分）7．证明[0，1]～（0，1）（6分）四、（6分）集合S={1，2，3，4，5}，找出S上的等价关系，此关系能产生划分{{1，2}，{3}，{4，5}}，并画出关系图。五、（6分）求的主合取式。试卷十九试题与答案一、填空20%（每空2分）：1．若对命题P赋值1，Q赋值0，则命题的真值为。2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为。3．公式的对偶公式为。4．图的对偶图为。5．若关系R是等价关系，则R满足性质。6．关系R的传递闭包t(R)=。7．代数系统是群，则它满足。8．设是两代数系统，f是从的同态映射，则f具有性质。9．若连通平面图共有r个面，其中，则它满足的Euler公式为。10．树T的边数e与点数v有关系。二、选择10%（每小题2分）：1．如果解释I使公式A为真，且使公式也为真，则解释I使公式B为（）。A、真；B、假；C、可满足；D、与解释I无关。2．设，则P（A）×A=（）。A、A；B、P（A）；C、；D、。3．设集合A，B是有穷集合，且，则从A到B有（）个不同的双射函数。A、；B、；C、；D、。4．设K={e,a,b,c}，是Klein四元群，则元素a的逆元为（）。A、e；B、a；C、b；D、c。5．一个割边集与任何生成树之间（）。A、没有关系；B、割边集诱导子图是生成树；C、有一条公共边；D、至少有一条公共边。三、逻辑推理12%：符号化命题“每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家”；并用演绎方法证明上面推理。（F(x)：x是学术会成员；H(x)：x是工人；G(x)：x是专家；R(x)：x是青年人）四、8%：求集合的并与交。五、12%：在实数平面上，画出关系，并判定关系的特殊性质。六、8%：问代数系统是否是布尔代数，为什么？（其中为能整除24的所有正整数，LCM为最小公倍数，GCD为最大公约数，）七、10%：求图中的一棵最小生成树。八、10%：