2023年离散数学题库

常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库01卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）下列表达式对的的有()（A） （B） （C） （D）设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列()命题的真值为真。（A） （B） （C） （D）集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,yA}，则R的性质为()（A）自反的（B）对称的（C）传递的，对称的 （D）传递的设，，其中表达模3加法，*表达模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是()（A）<0，0> （B）<0，1> （C）<1，0> （D）<1，1>下图中既不是Eular图，也不是Hamilton图的图是()设为无向图，，则G一定是()（A）完全图 （B）树 （C）简朴图 （D）多重图设P：我将去镇上,Q：我有时间。命题“我将去镇上,仅当我有时间”符号化为（）。（A）PQ （B）QP （C）PQ （D）在有n个结点的连通图中,其边数（）（A）最多有n-1条（B）最多有n条（C）至少有n-1条（D）至少有n条设A－B＝,则有（）（A）B＝ （B）B （C）AB （D）AB设集合A上有3个元素,则A上的不同的等价关系的个数为（）（A）5 （B）7 （C）3 （D）6二、填空题（每题2分，共20分）n个命题变元组成的命题公式共有种不同的等价公式。设〈L，≤〉为有界格，a为L中任意元素，假如存在元素b∈L,使，则称b是a的补元。设*，Δ是定义在集合A上的两个可互换二元运算，假如对于任意的x,y∈A,都有,则称运算*和运算Δ满足吸取律。设T是一棵树，则T是一个连通且的图。一个公式的等价式称作该公式的主合取范式是指它仅由组成。量词否认等价式Ø("x)P(x)Û，Ø($x)P(x)Û。二叉树有5个度为2的结点，则它的叶子结点数为。设<G，*>是一个群，<G，*>是阿贝尔群的充要条件是。集合S={α，β，γ，δ}上的二元运算*为*αβγδαδαβγβαβγδγβγγγδαδγδ那么，代数系统<S，*>中的幺元是，α的逆元是。设A={<1，2>，<2，4>，<3，3>}，B={<1，3>，<2，4>，<4，2>}=。=。三、判断题（每题1分，共10分）命题公式是一个矛盾式。（），若，则必有。（）设S为集合X上的二元关系，则S是传递的当且仅当(SS)S。（）任何一棵二叉树的结点可相应一个前缀码。（）代数系统中一个元素的左逆元一定等于该元素的右逆元。（）一个有限平面图，面的次数之和等于该图的边数。（）A´B=B´A（）设*定义在集合A上的一个二元运算，假如A中有关于运算*的左零元θl和右零θr,则A中有零元。（）一个循环群的生成元不是唯一的。（）任何一个前缀码都相应一棵二叉树。（）四、解答题（5小题，共30分）（5分）什么是欧拉路？如何用欧拉路鉴定一个图G是否可一笔画出？（8分）求公式(P∨Q)R的主析取范式和主合取范式。（5分）已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？（7分）权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（5分）集合上的关系，，写出关系矩阵，画出关系图并讨论R的性质。五、证明（3小题，共20分）（10分）用推理P,T规则证明：PQ，P→R,Q→SRS。（5分）设Ａ，Ｂ，Ｃ是三个集合，证明：(A－B)(A－C)=A－(BC)。（5分）设<G,*>是群，aG。令H={xG|a*x=x*a}。试证：H是G的子群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库02卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）下列公式中哪些是永真式？()（A）(┐PQ)→(Q→R) （B）(PQ)→P （C）P→(Q→Q) （D）P→(PQ)下列推导错在()① P② US①③ ES②④ UG③（A）② （B）④ （C）③ （D）无集合A={1，2，3，4}上的偏序关系图为图(0)，则它的Hass图为()设R是实数集合，“”为普通乘法，则代数系统<R，×>不是()（A）群 （B）独异点 （C）半群 （D）广群连通非平凡的无向图G有一条欧拉回路当且仅当图G()（A）只有一个奇度结点 （B）只有两个奇度结点 （C）只有三个奇度结点 （D）没有奇度结点若一棵完全二元（叉）树有2n-1个顶点，则它()片树叶（A）n（B）2n （C）n-1 （D）2在谓词演算中,是的有效结论,根据是（）。（A）US规则（B）UG规则（C）ES规则（D）EG规则设在上海工作；是上海人。则命题“在上海工作的人未必都是上海人”的符号化为（）。A．（B）（C）（D）集合A上的关系R是相容关系的必要条件是（）（A）自反,反对称的 （B）反自反,对称的 （C）传递,自反的 （D）自反,对称的下列各式错误的是（）（A） （B） （C） （D）二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式：（1）┐(P∨Q)； （2）PQ；若集合A上的关系R满足的三个性质，则R是偏序关系。设A，B是两命题公式，当且仅当。给定无孤立点图G，若存在一条路满足，该条路称为欧拉路。一个称为布尔格。对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”MaxMin+可结合性可互换性存在幺元存在零元设<A,£>为偏序集，BÍA，记B­={y|yÎA且y是B的上界}，若B­有最小元，则称该最小元为B的。一个公式的等价式称作该公式的主析取范式是指它仅由组成。由集合A和B的所有共同元素组成的集合称为A和B的交集，记作AÇB，即AÇB={}。的图称为完全图。三、判断题（每题1分，共10分）“北京与天津的距离很近”是复合命题。（）假如A∨CB∨C，则有AB。（）设R1和R2是集合A上的关系，且R1R2，则有r(R1)r(R2)。（）若平面图共有v个结点，e条边和r个面，则v-e+r=2。（）任何循环群必然是阿贝尔群，反之亦真。（）命题公式是没有真假值的。（）格〈L,≤〉所诱导的代数系统为〈L,∧，∨〉，则运算∧，∨满足互换律。（）设函数f:A→B,则f的逆关系是函数当且仅当f是入射。（）群<G,*>的运算表中的每一行或每一列不一定是G的元素的一个置换。（）任何一棵二叉树可相应一个前缀码。（）四、解答题（3小题，共20分）（5分）简述二叉树的定义。如何将任何一棵有序树（m叉树）改写为相应的二叉树？（8分）求公式(P→Q)R的主析取范式和主合取范式。（7分）如下图所示的赋权图表达某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间可以通信并且总造价最小。五、证明（4小题，共30分）（10分）用推理P,T规则证明：P→Q，QR，R，SPS。（10分）若R和S都是非空集A上的等价关系，则RS是A上的等价关系。（6分）若图G不连通，则G的补图是连通的。（4分）I(整数集)上的二元运算*定义为：a,bI，a*b=a+b-2。证明<I,*>是群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库03卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）在下述公式中不是重言式为()（A） （B）（C） （D）设，则B－A是()（A） （B） （C） （D）设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的最小公倍数）设<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}在有n个顶点的连通图中，其边数()（A）最多有n-1条（B）至少有n条 （C）最多有n条 （D）至少有n-1条一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为()（A）5（B）7 （C）8 （D）9公式G=P￢P,则G是（）（A）永真的（B）永假的（C）可满足的（D）析取的设P,Q的真值为0,R,S的真值为T,则下面命题公式中真值为T的是（）.（A）RP（B）QS（C）PS（D）QRA={1,2,3}上的关系R={<1,1><1,2><1,3><3,3>},则R具有（）（A）传递性与反对称性（B）传递性与对称性（C）自反性与对称性（D）反自反性与对称性连通图G是一颗树,当且仅当满足下述条件中那一个（）（A）有些边不是割边。（B）每条边都是割边（C）每条边都不是割边（D）无割边集二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式： （1）P→Q； （2）PQ；若对命题P赋值T，Q赋值F，则命题PQ的真值为。代数系统<A，*>中，|A|>1，假如分别为<A，*>的幺元和零元，则的关系为（填相等或不相等）。设集合A={1，2，3，4，5，6，7，8，9，10}，定义A上的二元关系“≤”为x≤y=x|y，则xy=。公式的根树表达为。重言式又叫式，其定义为。给定无孤立点图G，若存在一条回路满足，该回路称为欧拉回路。设R为X到Y的关系，S为从Y到Z上的关系，R°S称为R和S的复合关系，则R°S=。设<G,*>为群，若在G中存在一个元素a,使得，则称该群为循环群。设G是一个连通平面图，一个面的称作该面的次数。三、判断题（每题1分，共10分）设命题“所有的研究生都读过大学”符号化为：。（）设P，Q是两个命题，当且仅当P，Q的真值均为T时，PQ的值为T。（）设A={a，b，c}，RA×A且R={<a，b>，<a，c>}，则R是传递的。（）在有向图中顶点间的互相可达关系是等价关系。（）代数系统中一个元素若有左逆元，则该元素一定也有右逆元。（）合式公式的定义是用一个递归形式给出的。（）格〈L,≤〉所诱导的代数系统为〈L,∧，∨〉，则运算∧，∨满足分派律。（）设函数f:A→B,则f的逆关系是函数当且仅当f是满射。（）群<G,*>的运算表中的每一行或每一列都是G的元素的一个置换。（）K3，3不是平面图。（）四、解答题（4小题，共30分）（5分）请解释谓词演算推理理论的US规则，UG规则，ES规则和EG规则。（8分）求公式(P→Q)(RP)的主析取范式和主合取范式。（10分）集合上的偏序关系R为整除关系。设，，试画出R的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。（7分）假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happynewyear的编码信息。五、证明（3小题，共20分）（8分）用推理P,T规则证明：BD，(E→F)→D，EB。（6分）证明在6个结点12条边的简朴连通平面图中，每个面的次数都是3。（6分）<I,+>是一个群,设IE＝{x|x=2n,n∈I},证明<IE,+>是<I,+>的子群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库04卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x是聪明的，M(x)：x是人）()（A） （B）（C） （D）谓词公式中的x是()（A）自由变元 （B）约束变元（C）既不是自由变元又不是约束变元 （D）既是自由变元又是约束变元集合A={1，2，3，4}上的偏序关系如图(0)，则它的哈斯图为()设是布尔代数，f是从An到A的函数，则()（A）f是布尔代数（B）f能表达成析取范式，也能表达成合取范式（C）若A={0，1}，则f一定能表达成析取范式，也能表达成合取范式（D）若f是布尔函数，它一定能表达成析（合）取范式设，*为普通乘法，则<S，*>是()（A）代数系统 （B）半群 （C）群 （D）都不是设无向图G有18条边且每个顶点的度数都是3，则图G有()个顶点（A）10 （B）4 （C）8 （D）12一个割边集与任何生成树之间()（A）没有关系 （B）至少有一条公共边 （C）有一条公共边 （D）割边集诱导子图是生成树集合A上的等价关系R,决定了A的一个划分,该划分就是（）（A）商集A/R （B）交集AR （C）差集A-R （D）并集AR公式G=P￢P,则G是（）（A）永真的（B）永假的（C）可满足的（D）析取的在有n个结点的连通图中,其边数（）（A）最多有n-1条（B）至少有n-1条（C）最多有n条（D）至少有n条二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式：（1）┐(P∧Q)； （2）PQ；n个命题变元有个互不等价的极小项。设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk=。设集合S={α，β，γ，δ，ζ}，S上的运算*定义为*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ则代数系统<S，*>中幺元是，β左逆元是。具有的图称为欧拉图。设*是定义在集合A上的一个二元运算，θ为A中的一个元素，假如对于任一x∈A,有，则称θ为A中关于运算*的零元。是存在量词消去规则，简称ES规则。R在A上是自反的ÛÍR。若偏序集A的每一个非空子集存在最小元，则称偏序集A为集。设图G=<V,E>，假如有图G’=<V’,E’>，使得，则称图G’是图G的子图。三、判断题（每题1分，共10分）命题公式是重言式。（）公式中的辖域为。（）不也许有某种关系，既是对称的，又是反对称的。（）在任何有向图中，所有结点的入度的平方和等于所有结点的出度的平方和。（）设S={1，2}，则S在普通加法和乘法运算下都封闭。（）PÚQ是一个合取范式。（）格〈L,≤〉所诱导的代数系统为〈L,∧，∨〉，则运算∧，∨满足结合律。（）设函数f:A→B,则f的逆关系是函数当且仅当f是双射。（）群<G,*>中，除幺元e外，不也许有任何别的等幂元。（）在任意图中,存在奇数个度数为奇数的结点。（）四、解答题（5小题，共30分）（5分）简述Warshall在1962年提出的求传递闭包的方法。（8分）求公式Q→(PR)的主析取范式和主合取范式。（4分）设全集U={a,b,c,d,e},A={a,d},B={a,b,c},求P(A)-P(B)。（9分）在二叉树中（1）求带权为2，3，5，7，8的最优二叉树T; （2）求T相应的二元前缀码。（4分）设S=QQ，Q为有理数集合，*为S上的二元运算：对任意<a,b>，<c,d>S,有<a,b>*<c,d>=<ac,ad+b>,求出S关于二元运算*的幺元以及当a0时，<a,b>关于*的逆元。五、证明（2小题，共20分）（10分）用推理P,T规则证明：P→(Q→R)，R→(Q→S)P→(Q→S)。（10分）设<A,*>是半群,e是左幺元且对每一个,存在,使得。①证明：对于任意的,假如a*b=b*c则b=c。②通过证明e是A中的幺元,证明<A,*>是群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库05卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）下列是真命题的有()（A） （B） （C） （D）下列集合中哪个是最小联结词集()（A） （B）{,} （C）{,} （D）设，S上关系R的关系图如下，则R具有()性质（A）自反性、对称性、传递性 （B）反自反性、反对称性 （C）反自反性、反对称性、传递性 （D）自反性设，*为普通乘法，则<S，*>是()（A）代数系统 （B）半群 （C）群 （D）都不是如右图相对于完全图K5的补图为()设G是n个结点、m条边和r个面的连通平面图，则m等于()（A）n+r-2 （B）n-r+2 （C）n-r-2 （D）n+r+2连通图G是一颗树,当且仅当满足下述条件中那一个（ ）（A）有些边不是割边。（B）每条边都是割边（C）每条边都不是割边（D）无割边集设集合A={1,2,3,,10},在集合A上定义运算,不是封闭的为（）（A） （B）（最大公约数）（C）（最小公倍数） （D）设R和S是集合A上的等价关系,则RS的对称性（）（A）一定不成立（B）一定成立 （C）不一定成立（D）不也许成立图G和G’的结点和边分别存在一一相应关系是G和G’同构的（）（A）必要条件（B）充足条件（C）充要条件（D）既不充足也不必要条件二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式： （1）P→Q； （2）PQ；任意两个不同小项的合取为，全体小项的析取式为。设S={a1，a2，…，a8}，Bi是S的子集，且设B1={a8},则由B31所表达的子集是。设集合S={α，β，γ，δ，ζ}，S上的运算*定义为*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ则代数系统<S，*>中幺元是，β左逆元是。n阶完全图Kn的点色数X(KN)=。无向图G具有一条欧拉路，当且仅当G是连通的，且。*是定义在A上的一个二元运算，e是A中关于运算*的幺元。假如对于A中的一个元素a存在着A中的某个元素b,使得，那么就称b是a的一个逆元。是存在量词引入规则，简称EG规则。设X和Y是任意两个集合，而f是X到Y的一个关系，假如，称关系f为函数。设图G的子图为G’，假如,则称该图G’为G的生成子图。三、判断题（每题1分，共10分）命题公式是重言式。（）设命题“所有的研究生都读过大学”符号化为：。（）AB当且仅当A∩B=A。（）在有向图中，所有结点的入度平方之和等于出度平方之和。（）设<S，*>是群<G，*>的子群，则<S，*>中幺元不一定是<G，*>中幺元。（）对于n个结点的完全图Kn，有X(Kn)＝n。（）AÈ(B´C)=(AÈB)´(AÈC)（）群中的运算不满足消去律。（）质数阶群必然是循环群。（）(x)(A(x)∨B(x))Û(x)A(x)∨(x)B(x)（）四、解答题（5小题，共30分）（5分）什么是集合的划分，如何根据集合A的一个划分拟定A的元素间的一个等价关系？（8分）求公式┐(P∧R)∧(P∨Q)的主析取范式和主合取范式。（4分）设A={a,d},B={a,b,c},C={b,d}。求集合(A-B)(B-C)。（7分）在通讯中，八进制数字出现的频率如下：0：20%、1：30%、2：10%、3：15%、4：10%、5：5%、6：5%、7：5%,求传输它们最佳前缀码（写出求解过程）。（6分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人天天只在下午考一门课，若以课程表达结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？五、证明（2小题，共20分）（10分）用推理P,T规则证明：P→Q，P→R，R→SS→Q。（10分）设，在上定义关系当且仅当，证明是上的等价关系，并求出[<2,5>]R。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库06卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）设是人，犯错误,命题“没有不犯错误的人”符号化为()（A） （B） （C） （D）下列公式是重言式的有()（A） （B） （C） （D）设A={}，B=Р(Р(A))下列()表达式不成立（A） （B） （C） （D）下面偏序集()能构成格6阶有限群的任何子群一定不是()（A）2阶 （B）3阶 （C）4阶 （D）6阶一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有()个4度结点（A）1 （B）2 （C）3 （D）4设G是一个哈密尔顿图，则G一定是()（A）欧拉图 （B）树 （C）平面图 （D）连通图设R和S是集合A上的等价关系,则RS的对称性（ ）（A）不一定成立（B）一定不成立（C）一定成立（D）不也许成立设G=<V,E>,|V|=n,|E|=m为连通平面图且有r个面,则r=（）（A）n-m-2 （B）m-n+2（C）n+m-2（D）m+n+2在0____之间填上对的的符号是（）（A）= （B） （C） （D）二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式：（1）┐(P∧Q)； （2）PQ；若P，Q，为二命题，真值为F当且仅当。设考虑下列子集，，，。，。则是A的覆盖的子集有，是A的划分的子集有。设<G，*>是一个群，则（A）若a，b，x∈G，ax=b，则x= 。（B）若a，b，x∈G，ax=ab，则x=。n阶无向完全图Kn的边数是，每个结点的度数是。无向图G具有一条欧拉回路，当且仅当G是连通的，且。一般来说，命题公式用联结词组表达。是反对称的ÛRÇRcÍ。设函数f:A®B，g:C®D，假如A=C，B=D，且，则称函数f和g相等，记作f=g。在无向图G中，假如结点u和v之间，则结点u和v称为是连通的。三、判断题（每题1分，共10分）若P为命题变元，P∧P为主合取范式。 （）假如AB，则有￢A￢B。（）设R1和R2是集合A上的关系，且R1R2，则有t(R1)t(R2)。（）在完全二元树中，若有片叶子，则边的总数。（）独异点的运算表中任意两行都是不相同的。（）任意平面图G最多是5-色的。（）A´B=B´A（）群中的运算不满足消去律。（）质数阶群不一定是循环群。（）("x)F(x)Þ($x)F(x)（）四、解答题（5小题，共30分）（5分）已知一个偏序关系，如何画出它的哈斯图？（8分）求公式(P→Q)(RP)的主析取范式和主合取范式。（6分）如右图给出的赋权图表达六个城市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间可以通讯且总造价最小，并计算出最小总造价。（7分）构造H、A、P、N、E、W、R、相应的前缀码，并画出与该前缀码相应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。（4分）设全集U={a,b,c,d,e},A={a,d},B={a,b,c},C={b,d}。求集合(AB)C。五、证明（2小题，共20分）（10分）用推理P,T和CP规则证明：A∨B→C∧D，D∨E→FA→F。（10分）R是实数集，<R-{-1},*>是一个代数系统，*是R-{-1}上的一个二元运算，使得对于R-{-1}中任意元素a,b都有a*b=a+b+ab，证明0是<R-{-1},*>的幺元，并且<R-{-1},*>是群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库07卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）设L(x)：x是演员，J(x)：x是老师，A(x,y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为()（A） （B） （C） （D）命题逻辑演绎的CP规则为()（A）在推演过程中可随便使用前提（B）在推演过程中可随便使用前面演绎出的某些公式的逻辑结果（C）设是含公式A的命题公式，，则可用B替换中的A（D）假如要演绎出的公式为形式，那么将B作为前提，演绎出C下列命题对的的是()（A） （B） （C） （D）设<A,>是一个有界格，假如它也是有补格，只要满足()（A）每个元素都至少有一个补元 （B）每个元素都有多个补元 （C）每个元素都无补元 （D）每个元素都有一个补元设，*为普通乘法。则代数系统的幺元为()（A）不存在 （B） （C） （D）下列图中()是根树（A） （B）（C） （D）左图(0)相对于完全图K5的补图为()集合A上的关系R是相容关系的必要条件是（）（A）自反、反对称的（B）反自反、对称的（C）传递、自反的（D）自反、对称的公式G=P￢P,则G是（）。（A）永真的（B）永假的（C）可满足的（D）析取的在图G=<V,E>中,结点总度数与边数的关系是（）（A） （B） （C） （D）二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式： （1）P→Q； （2）PQ；论域D={1，2}，指定谓词PP(1，1)P(1，2)P(2，1)P(2，2)TTFF则公式真值为。下图所示的哈斯图中，是格的为。在一个群〈G，*〉中，若G中的元素a的阶是k，则a-1的阶是。一个图的欧拉回路是一条通过图中的回路。给定图G，若存在一条路满足，这条路称作汉密尔顿路。一个代数系统<S,*>,假如运算*是和，则称代数系统<S,*>为半群。一个命题公式称为合取范式，当且仅当它具有形式。设*是定义在集合A上的二元运算，假如对于任意的x,y∈A,都有，则称该二元运算*是可互换的。若图G=〈V,E〉满足，则G称为连通图。三、判断题（每题1分，共10分）若命题合式公式A的对偶式是A*，则AA*。（）“今天你吃饭了吗？”这句话不是命题。（）设S为集合X上的二元关系，则S是传递的当且仅当SSS。（）不也许有偶数个结点，奇数条边的欧拉图。（）有最大元和最小元的偏序集并不一定是格。（）连通图的生成树是唯一的。（）在任意图中,存在奇数个度数为奇数的结点。（）群<G,*>的运算表中的每一行或每一列不一定是G的元素的一个置换。（）设<G,*>是一个群，<S,*>是<G,*>的一个子群，则<G,*>中的幺元e一定是<S,*>中的幺元。（）K5不是平面图。（）四、解答题（5小题，共30分）（5分）什么是集合的覆盖，如何根据集合A的一个覆盖拟定A元素间的一个相容关系？（3分）设A={0,1,2}，B={0,2,4}，列出二元关系R={<x,y>|x,y}的所有元素。（8分）求公式(PQ)(PR)的主析取范式和主合取范式。（10分）设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{<a,b>,<b,a>,<b,c>,<c,d>},写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。（6分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人天天只在下午考一门课，若以课程表达结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？五、证明（2小题，共20分）（10分）用规则P,T和CP推证：B∨D,(C→A)→DB→C。（10分）设I+是正整数集，A={<x,y>|x∈I+∧y∈I+}，R={<<x,y>,<u,v>>|xv=yu∧<x,y>∈A∧<u,v>∈A}，证明R是一个等价关系。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库08卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）命题“有的人喜欢所有的花”的逻辑符号化为()设D：全总个体域，F（x）：x是花，M(x)：x是人，H(x,y)：x喜欢y（A） （B）（C） （D）给定公式，当D={a,b}时，解释()使该公式真值为F。（A）P(a)=0、P(b)=0 （B）P(a)=0、P(b)=1 （C）P(a)=1、P(b)=1 （D）P(a)=1、P(b)=0下面集合()关于整除关系构成格（A）{2,3,6,12,24,36} （B）{1,2,3,4,6,8,12} （C）{1,2,3,5,6,15,30} （D）{3,6,9,12}Q为有理数集N，Q上定义运算*为a*b=a+b–ab，则<Q，*>的幺元为()（A）a （B）b （C）1 （D）0设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设G是一棵树，n,m分别表达顶点数和边数，则()（A）n=m （B）n=m+1 （C）m=n+1 （D）不能拟定集合A上的关系R是相容关系的必要条件是（）（A）自反、反对称的（B）反自反、对称的（C）传递、自反的（D）自反、对称的Z是整数集合,对于下列*运算,哪个<Z,*>代数系统是半群（）（A）（B）（C）（D）无向图G中的边e是其割边的充足必要条件是（）（A）边e是平行边 （B）边e不是平行边（C）边e不包含在G的任一简朴回路中 （D）边e不包含在G的某一回路中。设集合A={1,2,3,,10},在集合A上定义运算,不是封闭的为（）（A）（最小公倍数）（B）（最大公约数）（C）（D）二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式：（1）┐(P∨Q)； （2）PQ；若解释I的论域D仅包含一个元素，则在I下真值为。设A={a，b，c，d}，A上二元运算如下：*abcdabcdabcdbcdacdabdabc那么代数系统<A，*>的幺元是，有逆元的元素为。n个结点的有向完全图边数是，每个结点的度数是。给定图G，若存在一条回路满足，这个回路称作汉密尔顿回路。具有的半群称为独异点。要证明AÍB，必须证明。设RÍA´A且A¹Æ,则r(R)=。设*是定义在集合A上的二元运算，假如对于任意的x,y∈A,都有,则称二元运算*在A上是封闭的。简朴有向图G=〈V,E〉中，任意一对结点间，至少有一个结点到另一个结点是可达的，则称这个图为连通图。三、判断题（每题1分，共10分）关系R是对称的，当且仅当关系矩阵是对称的，或在关系图上，任两个结点间若有定向弧线，必是成对出现的。（）“这件作品多有创意！”这句话不是命题。（）设集合S={1，2，3，4}，S上的关系R={<1，1>，<2，2>，<1，3>}，则R具有自反性。（）无多重边的图是简朴图。（）循环群的任何子群必然是循环群。（）连通图的生成树是不唯一的。（）AÇ(B´C)=(AÇB)´(AÇC)（）群中可以有零元。（）假如〈L,≤〉是格，S是L的子集且〈S,≤〉是格，则〈S,≤〉一定是〈L,≤〉的子格。（）任何一棵有序树都可以改写为唯一的一棵二叉树，同样，任何一棵二叉树都对可以改回成唯一的一棵有序树。（）四、解答题（5小题，共30分）（5分）什么是商集，如何根据集合A的一个等价关系R求得A关于R的一个商集？（8分）求公式(R→Q)P的主析取范式和主合取范式。（10分）设集合Ａ＝{a,b,c,d,e}上的关系Ｒ＝{<a,b>,<b,c>,<b,d>,<d,e>}写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。（3分）设A={1,2,3,4,5}，B={1,2}，列出二元关系R={<x,y>|2x+y4且x，yB}的所有元素。（4分）设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝，求(1)RR(2)R-1。五、证明（3小题，共20分）（8分）运用规则P，T或CP推证：（P∧Q）,Q∨R,RP。（6分）求一棵带权为1,1,1,2,2,3,4,5的最优二叉树T,并计算W(T)。3．（6分）设<A,*>是半群,e是左幺元且对每一个，存在,使得。证明e是<A,*>中幺元。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库09卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）公式换名()（A） （B）；（C） （D）。下面蕴涵关系不成立的是()（A） （B）（C） （D）判断下列命题哪个为对的？()（A）{Ф}∈{Ф,{{Ф}}} （B）{Ф}{Ф,{{Ф}}}` （C）Ф∈{{Ф}} （D）{a,b}∈{a,b,{a},{b}}下列哪个偏序集构成有界格()（A）（N，）（B）（Z，） （C）（{2，3，4，6，12}，|（整除关系）） （D）(P（A），)6阶群的子群的阶数可以是()（A）1，2，5 （B）2，4 （C）3，6，7 （D）2，3一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有()个4度结点（A）1 （B）2 （C）3 （D）4设G是有n个结点m条边的连通平面图，且有k个面，则k等于()（A）m-n+2 （B）n-m-2 （C）n+m-2 （D）m+n+2设在上海工作；是上海人。则命题“在上海工作的人未必都是上海人”的符号化为（）（A）（B）（C）（D）设V={a,b,c,d},则与V构成强连通图的边集为（）（A）E1={<a,d>,<b,a>,<b,d>,<c,b>,<d,c>}（B）E2={<a,d>,<b,a>,<b,d>,<b,c>,<d,c>}（C）E3={<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}（D）E4={<a,b>,<a,c>,<a,d>,<b,d>,<c,d>}下列公式中不是合式公式的是（）（A） （B）P（RS）（C） （D）P（RS）二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式： （1）PQ； （2）PQ；一般说来，n个命题变元共有个小项（或大项）。设<G，*>是一个群，a，b，c∈G，则(1)若ca=b，则c=; (2)若ca=ba，则c=。具有的图称为汉密尔顿图。设<G,*>是一个代数系统，其中G是非空集合，假如，则称<G,*>是一个群。n个命题变元的析取式，称为布尔析取或大项，是指：。Í的传递性是指：。设RÍA´A且A¹Æ,则s(R)=。设*是定义在集合A上的二元运算，假如对于任意的x,y,z∈A都有,则称该二元运算*是可结合的。简朴有向图G=〈V,E〉中，假如对于图G中的任意两个结点两者之间是互相可达的，则称这个图为图。三、判断题（每题1分，共10分）任意两个矛盾式的合取还是矛盾式。（）假如￢A￢B，则有AB。（）任意无限集合必具有可数子集。（）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i=t-1。（）设Q为有理数集，Q上运算*定义为，则<Q,*>是群。（）ØPÚQ是一个合取范式。（）在任意图中,度数为奇数的结点不一定是偶数个。（）设*定义在集合A上的一个二元运算，假如A中有关于运算*的左幺元el和右幺er,则A中有幺元。（）任何一个循环群必然是阿贝尔群。（）简朴图除了K5和K3，3外都是平面图。（）四、解答题（5小题，共30分）（5分）<A,*>是一个代数系统，*是A上的一个二元运算，如何根据运算表看出<A,*>是否有=1\*GB3①封闭性；=2\*GB3②可互换性；=3\*GB3③等幂元；=4\*GB3④零元；=5\*GB3⑤幺元。（8分）求公式（PR）Q的主析取范式和主合取范式。（4分）设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求RR和R-1的关系矩阵。（8分）求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。（5分）图给出的赋权图表达五个城市及相应两城乡间公路的长度。试给出一个最优化的设计方案使得各城市间可以有公路连通。五、证明（2小题，共20分）（10分）用推理P,T规则证明：（PQ）,（QR）,（RS）（PS）。（10分）设集合A＝{a,b,c,d}，A上的关系R={<a,b>,<b,a>,<b,c>,<c,d>}（1）写出关系R的关系矩阵；（2）求R的自反闭包,对称闭包和传递闭包；（3）求包含R的最小的等价关系。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库10卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）下列哪个公式为永真式？()（A）QQ→P （B）QP→Q （C）PP→Q （D）P(PQ)P设，则有()（A）{{1,2}} （B）{1,2} （C）{1} （D）{2}下列结果对的的是()（A） （B） （C） （D）设I为整数集合，m是任意正整数，是由模m的同余类组成的同余类集合，在上定义运算，则代数系统最确切的性质是()（A）封闭的代数系统 （B）半群 （C）独异点 （D）群一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有()片树叶（A）3 （B）4 （C）6 （D）5设，，则有向图是()（A）强连通的 （B）单侧连通的 （C）弱连通的 （D）不连通的设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（）（A）7 （B）8 （C）9 （D）14下列代数系统<G,*>中,其中*是加法运算,（）不是群。（A）G为整数集合（B）G为偶数集合 （C）G为有理数集合 （D）G为自然数集合谓词公式中量词的辖域是（）。（A）（B） （C） （D）无向图G是欧拉图,当且仅当（）（A）G中所有结点的度数全为偶数（B）G连通且所有结点度数全为偶数（C）G的所有结点的度数全为奇数（D）G连通且所有结点度数全为奇数二、填空题（每题2分，共20分）设P、Q是命题公式，填写如下的基本等价关系式：（1）┐(P∧Q)； （2）PQ；设<{a，b，c}，*>为代数系统，*运算如下：*abcaabcbbaccccc则它的幺元为；a、b的逆元分别为。当时，群只能有阶非平凡子群，平凡子群为。树T的边数e与点数v有关系。设G＝〈V，E〉是一个无向图，假如可以在平面上把G画成，就称G是一个平面图。设<G,Δ>是群，S是G的非空子集，假如对于S中的任意元素a和b有,则<S,Δ>是<G,Δ>的子群。设P（x）：x是素数，E(x)：x是偶数，O(x)：x是奇数N(x，y)：x可以整数y。则谓词的自然语言是。设RÍA´A且A¹Æ,则t(R)=。设*，Δ是定义在集合A上的两个二元运算，假如对于任意的x,y,z∈A都有,则称运算*对于运算Δ是可分派的。简朴有向图G=〈V,E〉中，假如在图G中略去方向，将它当作是无向图，图是连通的，则称该有向图为。三、判断题（每题1分，共10分）“北京到天津的距离很近”是复合命题。（）一个有限平面图，面的次数之和等于该图的结点度数。（）有人可以证明存在一个无限集，其基数是严格介于之间的。（）一条回路和任何一棵生成树至少有一条公共边。（）循环群不一定是Abel群。（）ØPÚQ不是一个析取范式。（）K5不是平面图。（）设*定义在集合A上的一个二元运算，假如A中有关于运算*的左零元θl和右零θr,且θl=θr,则A中有零元。（）x(F(y)→G(x))F(y)→xG(x)。（）设<G,Δ>是群，S是G的非空子集，假如对于S中的任意元素a和b有aΔb-1∈S,则<S,Δ>是<G,Δ>的子群。（）四、解答题（5小题，共30分）（5分）请叙述群的定义。（8分）求公式（PQ）R的主析取范式和主合取范式。（4分）设A={a,b}，P(A)为A的幂集，求集合P(A)A。（5分）设Ａ＝｛1,2,3,4,5,6｝，B={0,1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求：(1)RR；(2)R-1。（8分）若传递a，b，c，d，e，f的频率分别为2%，3%，5%，7%，8%，9%，求传输它的最佳前缀码，规定写出具体的求解过程。五、证明（3小题，共20分）（8分）用推理P,T,CP规则证明：A→(B→C),(C∧D)→E,G→(D∧E)A→(B→G)。（8分）设<G，*>是一个群，证明<G，*>是阿贝尔群的充要条件是对于任意的a，b∈G有(a*b)*(a*b)=(a*a)*(b*b)。（4分）设A={a,b,c,d,e,f},R=IA∪{<a,b>,<b,a><f,e><e,f>},则R是A上的等价关系。(1)求a的等价类[a]R； (2)求商集A/R。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库11卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）下列等价关系对的的是()（A） （B）（C） （D）设R,S是集合A上的关系，则下列说法对的的是()（A）若R,S是自反的，则RS是自反的 （B）若R,S是反自反的，则RS是反自反的（C）若R,S是对称的，则RS是对称的 （D）若R,S是传递的，则RS是传递的设f，g是函数，当()时，f=g（A） （B）（C） （D）在Peterson图中，至少填加()条边才干构成Euler图（A）1 （B）2 （C）4 （D）5在有理数集Q上定义的二元运算*，有， 则Q中满足()（A）只有唯一逆元 （B）时有逆元 （C）所有元素都有逆元 （D）所有元素都无逆元下面给出的符号串集合中,哪一个不是前缀码（）（A）｛1,10,110,1111｝（B）｛01,001,000,1｝（C）｛b,c,aa,ac,aba,abc｝ （D）｛0011,01,101,11,100｝在自然数集合N上定义的二元运算,满足结合律的运算是（）（A）ab=a-b（B）ab=a+4b（C）ab=min{a,b}（D）ab=|a-b|设集合A={1,2,3,,10},在集合A上定义如下运算,不是封闭的有（）（A）（最小公倍数）（B）（最大公约数）（C）（D）设S={0，1}，*为普通乘法，则<S，*>是()（A）半群，但不是独异点 （B）群 （C）环，但不是群 （D）只是独异点，但不是群在0____之间填上对的的符号是（）（A）=（B）（C）（D）二、填空题（每题2分，共20分）由集合A的组成的集合,称为A的幂集，记作P(A)，即P(A)={x|xÍA}。若一个集合A的若干个非空子集S1,S2,…,Sm满足，则这些非空子集的全体叫做A的一个覆盖。设<A,£>为偏序集，BÍA，若yÎA满足，称y为B的下界。假如群<G,*>中的运算*是的，则称该群为阿贝尔群。的图称为简朴图。设G是一个连通平面图，由图中的边所包围的区域，在区域内既不包含图的，也不包含图的，这样的区域称为图G的一个面。设P、Q是命题公式，填写如下的基本等价关系式：（1）P→Q； （2）PQ；给定集合A的一个覆盖S={S1,S2,…,Sm}，若，则S称作是A的一个划分。图的补图为。n个结点的无向完全图Kn的边数为。三、判断题（每题1分，共10分）("x)(A(x)∧B(x))Û("x)A(x)∧("x)B(x)（）使命题公式的真值为F的真值指派的P、Q、R值分别是T、T、F。（）集合A上的恒等关系是一个双射函数。（）任一简朴图G的最大度数Δ（G）不一定小于G的顶点数。（）设是布尔代数，则一定为有补分派格。（）命题公式是有真假值的。（）设〈L,≤〉是一个格，那么对L中任何元素a,b,c,d,若a≤b，则a∨c≤b∨c，a∧c≤b∧c。（）存在基数严格介于其之间的无限集。（）群中的运算不满足消去律。（）K3，3不是平面图。（）四、解答题（5小题，共30分）（5分）什么是偏序关系？如何拟定偏序集〈L，≤〉中最大元，极大元。（8分）求公式(PR)(QR)P的主析取范式和主合取范式。（7分）权数1，2，3，4，5，6，7，8，9，10构造一棵最优二叉树。（5）集合上的关系，写出关系矩阵MR，画出关系图并讨论R的性质。（5分）已知一棵无向树中有3个2度顶点、1个3度顶点、2个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？五、证明（3小题，共20分）（10分）用推理P,T规则证明：PQ，P→R,Q→SRS。（5分）证明对集合A、B和C,有（A∩B）∪C=A∩(B∪C)当且仅当CA。（5分）设<G,·>是群，aG。令H={xG|a·x=x·a}。试证：H是G的子群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库12卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）下列推理环节错在()① P② US①③ P④ ES③⑤ T②④I⑥ EG⑤（A）② （B）⑤ （C）④ （D）⑥设A={1，2，3，4}，P(A)（P(A)是A的幂集）上规定二元系则P(A)/R=()（A）A （B）P（A） （C）{[]R,[{1}]R,[{1,2}]R,[{1,2,3}]R,[{1,2,3,4}]R}（D）{[]R,[2]R,[2,3]R,[2,3,4]R,[A]R}Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理对的()（A）AB，BC则AC （B）AB，BC则A∈B （C）A∈B，B∈C则A∈C （D）A∈B，B∈C则AC下图中是哈密顿图的为()在有n个顶点的连通图中，其边数()（A）最多有n-1条（B）至少有n条 （C）最多有n条 （D）至少有n-1条在自然数集合N上定义的二元运算,满足结合律的是（）（A）ab=a-b（B）ab=min{a,b}（C）ab=a+4b（D）ab=|a-b|连通图G是一棵树当且仅当G中（）（A）有些边不是割边（B）每条边都是割边（C）无割边集（D）每条边都不是割边集合A上的关系R是相容关系的必要条件是（）（A）自反,反对称的（B）反自反,对称的（C）传递,自反的（D）自反,对称的具有6个结点的树的边数为（）（A）4（B）6（C）5（D）8集合A上的一个覆盖拟定A的元素间的关系为：（）（A）相容关系（B）全序关系（C）等价关系（D）偏序关系二、填空题（每题2分，共20分）设S={a，b，c}若S1={c},则S6的集合表达为。若是集合A的一个划分，则它应满足。设S是非空有限集，代数系统＜P（S），Ç，È＞中，P（S）对Ç的幺元为，零元为。P(S）对È的幺元为，零元为。n阶完全图结点v的度数deg(v)=。设*是定义在集合A上的一个二元运算，假如对于任意的x∈A,都有,则称运算*是等幂的。集合A={，{}}的幂集P(A)=。证明AÞB，即证A®B是重言式，有两种证法：（1），（2）。R在A上被称为传递的Û。设<G,*>是一个群，<G,*>是阿贝尔群的充要条件是对任意的a,b∈G,有。设G是一个连通平面图，包围一个面的称为这个面的边界。三、判断题（每题1分，共10分）(x)(F(x)→G(y))(x)F(x)→G(y)。（）假如f是函数，则其逆关系fc也是函数。（）对任意集合A，B，C有(A－B)－C=A－(B∩C)。（）任何有向图中各结点入度之和等于边数。（）在有幺元e的代数系统<S,*>中，假如*是可结合的运算，且每个元素都有左逆元,那么这个代数系统中任何一个元素的左逆元必然也是该元素的右逆元，且每个元素的逆元是唯一的。（）一个有限平面图，面的次数之和等于该图的边数的二倍。（）(A´B)´C=A´(B´C)（）设<A,*>是一个代数系统，且集合A中元素的个数大于1。假如该代数系统中存在幺元e和零元θ,则θ≠e。（）一个循环群的生成元是唯一的。（）谓词公式的前束范式是。（）四、解答题（3小题，共20分）（5分）请简述“哥尼斯堡七桥问题”，该问题是否有解？为什么？（8分）求公式(P∧R)∧(P∨Q)的主析取范式和主合取范式。（7分）如下图所示的赋权图表达某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间可以通信并且总造价最小。五、证明（4小题，共30分）（10分）用推理P,T规则证明：P→Q，QR，R，SPS。（10分）若R和S都是非空集A上的等价关系，则RS是A上的等价关系。（4分）设Ａ，Ｂ，Ｃ是三个集合，证明：A(B－C)＝(AB)－(AC)。（6分）I(整数集)上的二元运算*定义为：a,bI，a*b=a+b-2。证明<I,*>是群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库13卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）若公式的主析取范式为则它的主合取范式为()（A） （B）；（C） （D）。下列各式中哪个不成立()（A） （B）（C） （D）设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为()设[{a，b，c}，*]为代数系统，*运算如下：*abcaabcbbaccccc则零元为()（A）a （B）b （C）没有 （D）c下面那一个图可一笔画出()在任何图中必然有偶数个()（A）度数为偶数的结点 （B）入度为奇数的结点 （C）度数为奇数的结点 （D）出度为奇数的结点下列命题对的的是（）（A）{a}{a,b,c} （B）（A） （C）{a,b,c} （D）{a,b}{a}设集合A上有四个元素,则A上的不同的划分的个数为（）（A）11 （B）14 （C）17 （D）15设<A，≤>是偏序集，，下面结论对的的是()（A）的上确界且唯一 （B）的极大元且不唯一（C）的上界且不唯一 （D）的极大元且唯一无向图G中的边e是G的割边的充要条件为（）（A）e是重边（B）e不是重边（C）e不包含在G的任一简朴回路中（D）e不包含在G的某一回路中二、填空题（每题2分，共20分）设A={a,b,c},A上二元关系R={<a,a>,<a,b>,<a,c>,<c,c>},则s（R）=。设S={a1，a2，…，a8}，Bi是S的子集，则B31=。设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，<Z+，+3>是否构成群。欧拉图的充要条件是。设A¹Æ，RÍA´A，若R是，则称R为A上的等价关系。设*是定义在集合A上的一个二元运算，e为A中的一个元素,假如对于任意x∈A,有，则称e为Ａ中关于运算*的幺元。在真值表中，一个公式的真值为T的指派所相应的小项的析取，即为此公式的范式。由所有集合A和B的所有元素组成的集合称为A和B的并集，记作AÈB，即AÈB={}。设<A,≤>是偏序集，若有x,yÎA，x≤y，且x¹y，且不存在其它元素zÎA，使得，则称元素y盖住元素x。n个结点的无向完全图Kn的边数为。三、判断题（每题1分，共10分）(x)(A→G(x))A→(x)G(x)（）设集合A，B，C都是D的子集，则AB当且仅当A∩B=A。（）整数集合上的相等关系可拟定A的一个划分。（）一个图是平面图，当且仅当它包含与Ｋ3，3或Ｋ5在２度结点内