2021年离散数学题库

试题总汇数理逻辑某些1、判断下列句子中哪些是命题（1）2是素数（2）血是黑色（3）2+3=5（4）来年10月1日是晴天（5）3能被2整除（6）这朵花多好看呀！（7）明天下午有会吗？（8）请关上门！（9）X+y>5（10）地球外星球上也有人2、将下列命题符号化（1）3不是偶数（2）2是素数和偶数（3）李芳学过英语或日语（4）如果角A和角B是对顶角，则角A等于角B（5）李平虽然聪颖，但不用功（6）李平不但聪颖，并且用功（7）小王是游泳冠军或者百米赛跑冠军（8）小王当前在宿舍或者在图书馆（9）选小王或者小李中一人当班长（10）如果我上街，我就去书店看看，除非我很累（11）如果明每天气好，咱们去郊游。否则，不去郊游（12）你爱我，我就嫁给你3、判断下列命题公式与否等值（1）（p∨q）与p∨q（2）（p∨q）与p∧q4、验证下列等值式（1）p→（q→r）（p∧q）→r（2）p（p∧q）∨（p∧q）5、用等值演算法解决下面问题：A、B、C、D4人百米竞赛。观众甲、乙、丙预报比赛名次为，（1）甲：C第一，B第二。（2）乙：C第二，D第三。（3）丙：A第二，D第四。比赛结束后发现甲、乙、丙每人报告状况都是给对一半。试问，实际名次如何？6、求下面命题公式主析取范式和主合取范式（1）（（p∨q）→r）→p7、运用真值表求主析取范式和主合取范式（1）（p∧q）∨r8、逻辑推理证明（1）前提：p→r，q→s，p∨q。结论：r∨s。（2）前提：p∨q，p→r，s→t，s→r，t。结论：q（3）前提：p→（q→r），s→p，q。结论：s→r。（4）前提：p→（（r∧s）→q），p，s。结论：q9、给定语句如下：（1）15是素数（2）10能被2整除，3是偶数（3）你下午有会吗？（4）2x+3>0（5）2是素数或是合数（6）这个男孩真勇敢呀！（7）如果2+2=6，则5是奇数（8）只有4是偶数，3才干被2整除（9）来年5月1日是晴天（10）圆面积等于半径平方与乘积以上10个语句中，是简朴命题为A，是复合命题为B，是真命题为C，是假命题为D，真值待定（真值客观存在，只是当前不懂得）命题为E。A：①（1）、（4）、（8）②（4）、（6）、（9）、（10）③（1）、（9）、（10）B：①（3）、（10）②（2）、（5）、（7）、（8）③（7）、（8）C：①（2）、（5）、（9）、（10）②（7）、（8）、（10）③（2）、（9）、（10）④（5）、（7）、（8）、（10）D：①（1）、（2）、（8）②（1）、（2）③（1）、（5）E：①（4）、（9）②（9）③（7）、（8）10、判断公式类型（1）（p∧q）→（p∨q）（2）（pq）（（p→q）∧（q→p））（3）（p→q）∧q（4）（p∧p）q（5）p→（p∨q）（6）（p∨p）→（（q∧q）∧r）（7）（（p→q）→p）p（8）（p∧q）∨（p∧q）（9）（p∨q∨r）（p∧q∧r）（10）（p∧q）∧r11、给定命题公式如下：（p→q）→（p∨q）该命题公式主析取范式中含极小项个数为A，主合取范式中含极大项个数为B，成真赋值个数为C，成假赋值个数为D。A、B、C、D：（1）0,（2）1,(3)2,(4)3,(5)412、一公安人员审查一件盗窃案，已知事实如下：（1）甲或乙盗窃了录音机（2）若甲盗窃了录音机，则作案时间不能发生在半夜前（3）若乙证词对的，则半夜时屋里灯光未灭（4）若乙证词不对的，则作案时间发生在半夜前（5）半夜时屋里灯光灭了推理证明，谁盗窃了录音机。13、设p=1，q=0，r=1，s=0，有下列命题公式（1）（p∧q）→（s∧r）（2）（p∧q∧r∧s）∨(s→q)（3）（p∧q∧r）（p∨s）那么，（1）真值为；（2）真值为；（3）真值为；14、对于下面语句，（1）只要4＜3，就有3＞2（2）只要4＜3，就有3≤2（3）只有4＜3，才有3＞2（4）只有4＜3，才有3≤2（5）除非4＜3，否则3＞2（6）4≥3仅当3≤2（7）4＜3当且仅当3＞2则，她们真值是（1）（2）（3）（4）（5）（6）（7）。15、设A是含n个命题变项公式，下面4个结论中，哪个是错误？（1）若A主析取范式中含2n个极小项，则A是重言式（2）若A主合取范式中含2n个极大项，则A是矛盾式（3）若A主析取范式中不含任何极小项，则A主析取范式为0（4）若A主合取范式中不含任何极大项，则A主合取范式为016、已知命题公式A具有3个命题变项，其成真赋值为000，010，100，110。则A主析取范式为，主合取范式为。17、判断下列语句与否为命题，如是命题请指出是简朴命题还是复合命题，并讨论真值（1）是无理数（2）5能被2整除（3）当前开会吗？（4）x+5＞0（5）这朵花真好看呀！（6）2是素数当且仅当三角形有3条边（7）血是黑色当且仅当太阳从东方升起（8）10月1日天气晴朗（9）太阳系以外星球上有生物（10）小李在宿舍里（11）全体起立（12）4是2倍数或是3倍数（13）4是偶数且是奇数（14）李明与王华是同窗（15）蓝色和黄色可以调配成绿色18、将下列命题符号化，并讨论其真值（1）如果今天是1号，则明天是2号（2）如果今天是1号，则明天是3号19、设A、B、C为任意命题公式（1）已知A∨CB∨C，问AB吗？（2）已知A∧CB∧C，问AB吗？（3）已知AB，问AB吗？20、设计一种符合如下规定室内照明控制线路：在房间门外、门内及床头分别装有控制同一种电灯F3个开关A、B、C。当且仅当一种开核心向上或3个开核心都向上时电灯亮。则F逻辑关系式可化简为。（1）A∨B∨C（2）A∨B∨C∨（A∧B∧C）（3）A∨B∨（A∧C）（4）C∨（A∧B）21、将下列语句用谓词表达式符号化（1）2是素数且是偶数（2）如果2不不大于3，则2不不大于4（3）凡是有理数均可表成分数（4）有有理数是整数（5）没有不吃饭人（6）素数不全是奇数（7）一切人都不同样高（8）有自然数无先驱数（9）有人喜欢所有花（10）任何金属都可以溶解在某种液体中（11）凡是对顶角都相等22、指出下列各合式公式中指引变项、量词辖域、个体变项自由浮现和约束浮现（1）x（F（x）→yH（x，y））（2）xF（x）∧G（x，y）（3）xy（R（x，y）∨L（x，y））∧xH（x，y）23、给定解释I如下：1）DI={2，3}2）DI中特定元素a=23）函数f（x）为f（2）=3，f（3）=24）谓词F（x）为F（2）=0，F（3）=1；G（x，y）为G（i，j）=1，i，j=2，3；L（x，y）为L（2，2）=L（3，3）=1；L（2，3）=L（3，2）=0在解释I下，求下列各式值。（1）x（F（x）∧G（x，a））（2）x（F（f（x））∧G（x，f（x）））（3）xyL（x，y）24、求下列公式前束范式（1）xF（x）∧xG（x）（2）xF（x）∨xG（x）（3）xF（x）→xG（x）（4）xF（x）→xG（x）25、设F（x）：x是人，G（x）：x爱吃糖。有人给出语句“不是所有人都爱吃糖”4种谓词表达式：（1）x（F（x）∧G（x））（2）x（F（x）→G（x））（3）x（F（x）∧G（x））（4）x（F（x）∧G（x））对的答案是。26、给出解释I，使下面两个公式在解释I下均为假，从而阐明这两个公式都不是永真式（1）x（F（x）∨G（x））→（xF（x）∨xG（x））（2）（xF（x）∧xG（x））→x（F（x）∧G（x））27、取个体域为整数集，给定下列公式（1）xy（x*y=0）（2）xy（x*y=1）（3）yx（x*y=2）（4）xyz（x–y=z）（5）x–y=-y+x（6）xy（x*y=y）（7）x（x*y=x）（8）xy（x+y=2y）在上面公式中，真命题为A，假命题为B。A：①（1）、（3）、（4）、（6）；②（3）、（4）、（5）；③（1）、（3）、（4）、（5）；④（3）、（4）、（6）、（7）B：①（2）、（3）、（6）；②（2）、（6）、（8）；③（1）、（2）、（6）、（7）；④（2）、（6）、（8）、（7）集合某些1、下列命题（1）；（2）；（3）｛｝；（4）｛｝对的是；错误是。2、计算一下幂集（1）P（）；（2）P（｛｝）；（3）P（｛，｛｝｝）；（4）P（｛1，｛2，3｝｝）3、证明（1）（A-B）∪B=A∪B；4、化简（（A∪B∪C）∩（A∪B））-（（A∪（B-C））∩A5、已知：AB=AC，证明：A=B6、求在1到1000之间不能被5和6，也不能被8整除数个数7、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，尚有2人会打这三种球。而6个会打网球人都会打另一种球（指篮球或排球），求不会打这三种球人数。8、设F表达一年级大学生集合，S表达二年级大学生集合，R表达计算机科学系学生集合，M表达数学系学生集合，T表达选修离散数学学生集合，L表达兴趣文学学生集合，P表达兴趣体育运动学生集合，则下列各句子所相应集合表达式分别是：（1）所有计算机科学系二年级学生都选修离散数学。A（2）数学系学生或者兴趣文学或者兴趣体育运动。B（3）数学系一年级学生都没有选修离散数学。C（4）只有一、二年级学生才兴趣体育运动。D（5）除去数学系和计算机科学系二年级学生外都不选修离散数学。EA、B、C、D、E：①T（M∪R）∩S；②R∩ST；③（M∩F）∩T=；④ML∪P；⑤PF∪S；⑥S-（M∪R）P9、设S1=｛1，2，…，8，9｝，S2=｛2，4，6，8｝，S3=｛1，3，5，7，9｝，S4=｛3，4，5｝，S5=｛3，5｝。拟定在如下条件下X也许与S1,…,S5中哪个集合相等。（1）若X∩S5=，则A（2）若XS4但X∩S2=，则B（3）若XS1但XS3，则C（4）若X-S3=，则D（5）若XS3但XS1，则EA、B、C、D、E：①X=S2或者S3；②X=S4或者S5；③X=S1，S2或者S4；④X与其中任何集合都不等；⑤X=S2；⑥X=S5；⑦X=S3或者S5；⑧X=S2或者S4；10、设A、B、C为任意集合，判断下述命题与否恒真，如果恒真给出证明，否则举出反例。（1）A∪B=A∪CB=C（2）AB=AB=（3）A∩（B-C）=（A∩B）-（A∩C）（4）（A∩B）∪（B-A）=B11、设A、B为集合，试拟定下列各式成立充分必要条件：（1）A–B=B（2）A–B=B-A（3）A∪B=A∩B12、求使得如下集合等式成立时，a，b，c，d应当满足条件：（1）｛a，b｝=｛a，b，c｝（2）｛a，b，a｝=｛a，b｝（3）｛a，｛b，c｝｝=｛a，｛d｝｝（4）｛｛a，b｝，｛c｝｝=｛｛b｝｝（5）｛｛a，｝，b，｛c｝｝=｛｛｝｝13、计算A∩B、A∪B、A-B、AB（1）A=｛｛a，b｝，c｝，B=｛c，d｝（2）A={{a，{b}}，c，｛c｝，｛a，b｝}，B=｛｛a，b｝，c，｛b｝｝（3）A=｛x|x∈N∧x<3｝，B=｛x|x∈N∧x≥2｝（4）A=｛x|x∈R∧x<1｝，B=｛x|x∈Z∧x<1｝（5）A=｛x|x∈Z∧x<0｝，B=｛x|x∈Z∧x≥2｝14、设|A|=3，|P（A）|=64，|P（A∪B）|=256，求：|B|，|A∩B|，|A-B|，|AB|15、设A=｛1，2｝，求：P（A）×A16、设A、B、C、D为任意集合，判断如下等式与否成立，若成立给与证明，否则，举出反例。（1）（A∩B）×（C∩D）=（A∩C）×（B∩D）（2）（A∪B）×（C∪D）=（A∪C）×（B∪D）（3）（A-B）×（C-D）=（A-C）×（B-D）（4）（AB）×（CD）=（AC）×（BD）17、设F、G是N上关系，其定义为：F=｛<x，y>|x，y∈N∧y=x2｝；G=｛<x，y>|x，y∈N∧y=x+1｝；求：G-1、FG、GF、F↑｛1，2｝、F[｛1，2｝]18、设F=｛<a，｛a｝>，<｛a｝，｛a，｛a｝｝>｝，求：FF，F↑｛a｝，F[｛a｝]。19、设A=｛a，b，c，d｝，R=｛<a，b>，<b，a>，<b，c>，<c，d>｝。给出R、r（R）、s（R）、t（R）关系图。20、设A=｛1，2，3｝，求出A上所有等价关系21、设A=｛1，2，3，…，11，12｝，R为A上整除关系，画出哈斯图。22、画出<P（｛a，b，c｝），R>哈斯图。23、R是X上二元关系，对于x∈X定义集合：R（x）={y|xRy}显然R（x）X。如果X={-4，-3，-2，-1，0，1，2，3，4}，且令R1=｛<x，y>|x，y∈X∧x<y｝，R2=｛<x，y>|x，y∈X∧y-1<x<y+2｝，R3=｛<x，y>|x，y∈X∧x2≤y｝，则下列集合满足（1）R1（0）=A（2）R2（0）=B（3）R3（3）=C（4）R1（1）=D（5）R2（-1）=EA、B、C、D、E：①；②｛-4，-3，-2，-1｝；③｛-2，-1｝；④｛-1，0，1｝；⑤｛-1，0｝；⑥｛1，2，3｝；⑦｛2，3，4｝；⑧｛0，1，2，3｝；⑨｛1，2，3，4｝；⑩以上成果都不对24、设S=｛1，2，3｝，定义S×S上等价关系R，<a，b>，<c，d>∈S×S有：<a，b>～<c，d>a+d=b+c则由R产生了S×S一种划分。在该划分中共有A个划分块，其中最大块有B个元素，并且具有元素C。最小划分块有D块，每块具有E个元素。A、B、D、E：①1；②2；③3；④4；⑤5；⑥6；⑦9；C：⑧1；⑨<1，2>；⑩<2，2>25、设S=｛0，1｝，F是S中字符构成长度不超过4串集合，即F=｛，0，1，00，01，…，1111｝，其中表达空串。在F上定义偏序关系R：x，y∈F，有<x，y>∈Rx是y前缀。例如，00是001前缀，但01不是001前缀。（1）偏序集<F，R>哈斯图是A；（2）<F，R>极小元是B；（3）<F，R>最大元是C；（4）GF，G=｛101，1001｝，则G最小上界是D，最大下届是E。A：①链；②树；③既不是链，也不是树；B、C、D、E：④；⑤0；⑥0、1和；⑦不存在；⑧10；⑨1；⑩111126、设S=｛1，2｝，则S上可定义A个不同二元关系，其中B个等价关系，C个偏序关系，Is是D，是E。A、B、C：①1；②2；③3；④4；⑤8；⑥16；D、E：⑦等价关系但不是偏序关系；⑧偏序关系但不是等价关系；⑨等价关系和偏序关系；⑩既不是等价关系也不是偏序关系；27、下面给定5个函数，其中单射而非满射有A，满射而非单射有B，双射有C，既不单射，又不满射有D。设R为实数集合，Z为整数集合，R+、Z+分别表达正实数和正整数集合。①f：R→R，f（x）=-x2+2x-1；②f：R→Z+，f（x）=lnx；③f：R→Z，f（x）=，表达不不不大于x最大整数；④f：R→R，f（x）=2x+1；⑤f：R+→R+，f（x）=28、对于给定集合A和B，构造从A到B双射函数。（1）A=Z，B=N，其中Z，N分别表达整数集和自然数集；（2）A=[，2]，B=[-1，1]实数区间29、（1）设S=｛1，2｝，R为S上二元关系，且xRy。如果R=Is，则A；如果R是数不大于等于关系，则B；如果R=Es，则C。（2）设有序对<x+2，4>与有序对<5，2x+y>相等，则x=D，y=E。A、B、C：①x与y可任意选取1或2；②x=1，y=1；③x=1，y=1或2；x=y=2；④x=2，y=2；⑤x=y=1或x=y=2；⑥x=1，y=2；⑦x=2，y=1；D、E：⑧3；⑨9；⑩-230、设S=<1，2，3，4>，R为S上关系，其关系矩阵是，则（1）R关系表达式是A；（2）domR=B；ranR=C；（3）RR中有D个有序对；（4）R-1关系图中有E个环。A：①｛<1，1>，<1，2>，<1，4>，<4，1>，<4，3>｝；②｛<1，1>，<1，4>，<2，1>，<4，1>，<3，4>｝；B、C：③｛1，2，3，4｝；④｛1，2，4｝；⑤｛1，4｝；⑥｛1，3，4｝；D、E：⑦1；⑧3；⑨6；⑩731、设S=｛1，2，…，9，10｝，是S上整除关系，则<S，>哈斯图是A，其中最大元是B，最小元是C，最小上界是D，最大下界是E。A：①一棵树；②一条链；③以上都不对；B、C、D、E：④；⑤1；⑥10；⑦6，7，8，9，10；⑧6；⑨0；⑩不存在32、设R关系图如所示，试给出r（R）、s（R）、t（R）关系图。33、画出下列集合关于整除关系哈斯图。（1）｛1，2，3，4，6，8，12，24｝（2）｛1，2，…，8，9｝34、设A=｛a，b｝，B=｛0，1｝，（1）求P（A）和BA；（2）构造一种从P（A）到BA双射函数。代数系统某些1、设Z+=｛x|x∈Z∧x>0｝，*表达求两个数最小公倍数运算，则（1）4*6=A；（2）*在Z+上B；（3）对于*运算幺元是C，零元是D；（4）在Z+中E；A：①24；②12；B：③只满足互换率；④只满足结合律；⑤满足互换率、结合律和幂等律；C、D：⑥0；⑦1；⑧不存在；E：⑨不存在逆元；⑩只有唯一逆元2、在有理数集合Q上定义二元运算*，x，y∈Q有x*y=x+y-xy则（1）2*（-5）=A，7*1/2=B。（2）*在Q上是C；（3）关于*幺元是D；（4）Q中满足E；A、B：①4；②7；③-13；C：④可结合；⑤不可结合；D：⑥1；⑦0；E：⑧所有元素均有逆元；⑨只有唯一逆元；⑩x∈Q，x1时，有逆元x-1。3、设V1=<S1，>，V2=<S2，*>，其中S1=｛a，b，c，d｝，S2={0，1，2，3}。和*由运算表1和表2给出。定义同态：S1→S2，且（a）=0，（b）=1，（c）=0，（d）=1，则（1）V1中运算A，其幺元是B，V2中运算*C；（2）是D，V1在下同态像是E；A、C：①满足互换律，不满足结合律；②不满足互换律，满足结合律；③满足互换律，满足结合律；B：④a；⑤d；D：⑥单同态；⑦满同态；⑧以上两者都不是；E：⑨<S2，*>；⑩<｛0，1｝，*>4、设V1=<｛1，2，3｝，，1>，其中xy表达取x和y之中较大数，V2=<｛5，6｝，*，6>，其中x*y表达取x和y之中较小数。（1）V1具有A个子代数，其中平凡真子代数有B个；V2具有C个平凡子代数。（2）积代数V1×V2中有D个元素，其幺元是E。A、B、C、D：①0；②1；③2；④3；⑤4；⑥5；⑦6；E：⑧<1，5>；⑨<1，6>；⑩<3，6>5、设S=｛a，b｝，则S上可以定义A个二元运算，其中有4个运算f1，f2，f3，f4，其运算表如下：则只有B满足互换律，C满足幂等律，D有幺元，E有零元。A：①4；②8；③16；④2；B、C、D、E：⑤f1和f2；⑥f1、f2和f3；⑦f3和f4；⑧f4；⑨f1；⑩f2；6、设S=｛1，2，…，9，10｝，问下面定义二元运算*与否为S上二元运算？（1）x*y=gcd（x，y），x与y最大公约数；（2）x*y=lcm（x，y），x与y最小公倍数；（3）x*y=不不大于等于xy最小整数；（4）x*y=max（x，y）；（5）x*y=质数P个数，其中x≤p≤y。7、设V=<R*，>是代数系统，其中R*为非零实数集合。分别对下述小题讨论运算与否可互换、可结合，并求幺元和所有可逆元素逆元。8、某二进制通信编码由4个数据位x1、x2、x3、x4和3个校验位x5、x6、x7构成，它们关系如下：x5=x1x2x3；x6=x1x2x4；x7=x1x3x4；其中为异或运算。（1）设S为所有满足上述关系码字集合，且x，y∈S，有xy=(x1y1,x2y2，…,x7y7)，那么<S，>是一种A。（2）设x，y∈S，定义H（x，y）=，那么当x≠y时，H（x，y）≥B。（3）使用该种码可查出接受码中包括所有k≤C位错误。（4）使用该种码可纠正接受码中包括所有k≤D位错误。（5）如果接受到1000011，且知有一位出错，那么出错位是第E位。A：①半群，但不是群；②群；③环，但不是域；④域；⑤前4种都不对；B、C、D、E：①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧0；9、对如下定义集合和运算判断它们是不是代数系统。如果是，是哪一种？（1）S1=｛1，1/2，2，1/3，3，1/4，4｝，*为普通乘法，则S1是A；（2）S2=｛a1，a2，…，an｝，n≥2，ai∈R，i=1，2，…，n，ai，aj∈S2，有aiaj=ai，则S2是B；（3）S3=｛0，1｝，*为普通乘法，则S3是C；（4）S4=｛1，2，3，6｝，为整除关系，则S4是D；（5）S5=｛0，1｝，+、*分别为模2加法和乘法，则S5是E。A、B、C、D、E：①半群，但不是独异点；②是独异点，但不是群；③群；④环，但不是域；⑤域；⑥格，但不是布尔代数；⑦布尔代数；⑧代数系统，但不是以上7种；⑨不是代数系统；10、图6-5给出一种格L，则（1）L是A元格；（2）L是B；（3）b补元是C，a补元是D，1补元是E。A：①5；②6；B：③分派格；④有补格；⑤布尔格；⑥以上都不对；C、D、E：⑦不存在；⑧c和d；⑨0；⑩c；11、设<B，∧，∨，′，0，1>是布尔代数，（1）a，b∈B，公式f为b∧（a∨（a′∧（b∨b′）））,在B中化简f；（2）在B中档式（a∧b′）∨（a′∧b）=0成立条件是什么？12、对如下定义集合和运算判断它们能否构成代数系统？如果能，请阐明是构成哪一种代数系统？（1）S1=｛0，1，2，…，n｝，+为普通加法，则S1是A；（2）S2=｛1/2，0，2｝，*为普通乘法，则S2是B；（3）S3=｛0，1，2，…，n-1｝，n为任意给定正整数，且n≥2，*为模n乘法，为模n加法，则S3是C；（4）S4=｛0，1，2，3｝，≤为不大于等于关系，则S4是D；（5）S5=Mn（R），+为矩阵加法，则S5是E；A、B、C、D、E：①半群，不是独异点；②独异点，不是群；③群；④环，不一定是域；⑤域；⑥格，不是布尔代数；⑦布尔代数；⑧代数系统，不是以上7种；⑨不是代数系统；13、（1）设G=｛0，1，2，3｝，若为模4乘法，则<G，>构成A；（2）若为模4加法，则<G，>是B阶群，且是C。G中2阶元是D，4阶元是E。A：①群；②半群，不是群；B：③有限；④无限；C：⑤Klein群；⑥置换群；⑦循环群；D、E：⑧0；⑨1和3；⑩2；14、（1）设<L，∧，∨，′，0，1>是布尔代数，则L中运算∧和∨A，运算∨幺元是B，零元是C，最小子布尔代数是由集合D构成；（2）在布尔代数L中表达式（a∧b）∨（a∧b∧c）∨（b∧c）等价式是E；A：①适合德.摩根律、幂等律、消去律和结合律；②适合德.摩根律、幂等律、分派律和结合律；③适合结合律、互换律、消去律和分派律；B、C：④0；⑤1；D：⑥｛1｝；⑦｛0，1｝；E：⑧b∧（a∨c）；⑨（a∧c）∨（a∧b′）；⑩（a∨b）∧（a∨b∨c）∧（b∨c）；15、下列各集合对于整除关系都构成偏序集，判断哪些偏序集是格？（1）L=｛1，2，3，4，5｝；（2）L=｛1，2，3，6，12｝；（3）L=｛1，2，3，4，6，9，12，18，36｝；（4）L=｛1，2，22，…，2n｝；16、设A=｛1，2，3，4，5｝，<P（A），>构成群，其中为集合对称差。（1）求解方程｛1，3｝X=｛3，4，5｝；（2）令B=｛1，4，5｝，求由B生成循环子群<B>；17、设A=｛1，2，5，10，11，22，55，110｝是110正因子集，<A，≤>构成偏序集，其中≤为整除关系。（1）画出偏序集<A，≤>哈斯图；（2）阐明该偏序集与否构成布尔代数，为什么？18、在图6-7所示3个有界格中哪些元素有补元？如果有，请指出该元素所有补元。P154图论某些1、（1）（3，3，2，3）、（5，2，3，1，4）能成为图度数序列吗？为什么？（2）已知图G有10条边，4个3度顶点，别的顶点度数均不大于等于2，问G中至少有多少个顶点？为什么？2、（1）画出4个顶点3条边所有也许非同构无向简朴图；（2）画出3个顶点3条边所有也许非同构有向简朴图；3、给定下列各图：（1）G1=<V1，E1>，其中，V1=（a，b，c，d，e），E1={（a，b），（b，c），（c，d），（a，e）}；（2）G2=<V2，E2>，其中，V2=V1，E2={（a，b），（b，e），（e，b），（a，e），（d，e）}；（3）G3=<V3，E3>，其中，V3=V1，E3={（a，b），（b，e），（e，d），（c，c）}；（4）G4=<V4，E4>，其中，V4=V1，E4={<a，b>，<b，c>，<c，a>，<a，d>，<d，a>，<d，e>}；（5）G5=<V5，E5>，其中，V5=V1，E5={<a，b>，<a，b>，<b，c>，<c，d>，<d，e>}；（6）G6=<V6，E6>，其中，V6=V1，E6={<a，a>，<a，b>，<b，c>，<e，c>，<e，d>}；在以上6个图中，A为简朴图，B为多重图。A：①（1），（3），（6）；②（3），（4），（5）；③（1），（2），（4）；④（1），（4）B：①（2），（4），（5）；②（2），（5）；③（4），（5）4、给定下列各顶点度数序列：（1）（2，2，2，2，2）；（2）（1，1，2，2，3）；（3）（1，1，2，2，2）；（4）（0，1，3，3，3）；（5）（1，3，4，4，5）；以上5组数中，A可以构成无向简朴图度数序列。A：①（1），（3），（4）；②（1），（2）；③（1），（3）；④（3），（4），（5）；5、完全图K4所有非同构生成子图中，0条边有A个；1条边有B个；2条边有C个；3条边有D个；4条边有E个；5条边有F个；6条边有G个；A、B、C、D、E、F、G：①0；②1；③2；④3；⑤4；⑥5；6、设G为9阶无向图，每个顶点度数不是5就是6，证明：G中至少有5个6度顶点或者至少6个5度顶点。7、画出5阶7条边所有非同构无向简朴图。8、下列各组数中，哪些能构成无向图度数列？哪些能构成无向简朴图度数列？（1）1，1，1，2，3；（2）2，2，2，2，2；（3）3，3，3，3；（4）1，2，3，4，5；（5）1，3，3，3；9、设有向简朴图D度数列为2，2，3，3，其中入度列为0，0，2，3，出度列为。10、设D是4阶有向简朴图，度数列为3，3，3，3，它入度列能为1，1，1，1吗？（能或者不能）11、下面各无向图中有几种顶点？（1）16条边，每个顶点都是2度顶点；（2）21条边，3个4度顶点，别的都是3度顶点；（3）24条边，各顶点度数是相似；12、一种n（n≥2）阶无向简朴图G中，n为奇数，已知G中有r个奇数度顶点，问G补图中有几种奇数度顶点？13、画出K4所有非同构字图，其中有几种是生成子图？生成子图中有几种是连通图？14、画出3阶有向完全图所有非同构子图，问其中有几种是生成子图？生成子图中又有几种是自补图？15、设G1、G2、G3均为4阶无向简朴图，它们均有两条边，它们能彼此均非同构吗？为什么？16、在K6边上涂上红色或蓝色。证明对于任意一种随意涂法，总存在红色K3或者蓝色K3。17、（1）非同构无向4阶自补图有A个；（2）非同构无向5阶自补图有B个；A、B：①0；②1；③2；④3；18、给定有向带权图如图所示，P175图中b到a最短途径权为A；b到d最短途径权为B；b到e最短途径权为C；b到g最短途径权为D；A、B、C、D：①4；②5；③6；④7；⑤8；⑥9；⑦10；19、某中学有3个课外小组：物理组、化学组、生物组。今有张、王、李、赵、陈5名同窗。若已知：（1）张、王为物理构成员，张、李、赵为化学构成员，李、赵、陈为生物构成员；（2）张为物理构成员，王、李、赵为化学构成员，王、李、赵、陈为生物构成员；（3）张为物理组和化学构成员，王、李、赵、陈为生物构成员；问在以上3中状况下能否各选出3名不兼职组长？20、在图8-17所示各图中，A为欧拉图，B为哈密顿图。P185A、B：①（a），（b），（c）；②（d），（e），（f）；③（c），（e）；④（b），（c），（d），（e），（f）；⑤（b），（c），（d），（e）；21、在图8-18所示各图中，是二部图为A，在二部图中存在完美匹配是B，它匹配数是C。P186A、B：①（a）；②（b）；③（c）；④（d）；⑤（e）；⑥（f）；⑦（a），（b）；⑧（b），（f）；⑨（c），（d），（e）；⑩（d），（e）；C：①1；②2；③3；④4；22、图8-19所示平面嵌入中，面数为A，次数最高面次数为B，次数最低面次数为C，总次数为D。A、B、C：①5；②6；③7；④8；⑤9；⑥10；⑦11；⑧1；D：①24；②26；③28；23、画出完全二部图K13，K24，K22。24、完全二部图Krs中，边数为，匹配数1为。25、今有工人甲、乙、丙去完毕三项任务a、b、c。已知甲能胜任a、b、c三项任务；乙能胜任a、b两项任务；丙能胜任b、c两项任务。你能给出一种安排方案，使每个工人各去完毕一项她们能胜任任务吗？26、画一种无向欧拉图，使它具备：（1）偶数个顶点，偶数条边；（2）奇数个顶点，奇数条边；（3）偶数个顶点，奇数条边；（4）奇数个顶点，偶数条边；27、画一种无向图，使它是：（1）是欧拉图，是哈密顿图；（2）是欧拉图，不是哈密顿图；（3）不是欧拉图，是哈密顿图；（4）不是欧拉图，不是哈密顿图；28、今有a、b、c、d、e、f、g7个人，已知如下事实：a：会讲英语；b：会讲英语和汉语；c：会讲英语、意大利语和俄语；d：会讲日语和汉语；e：会讲德语和意大利语；f：会讲法语、日语和俄语；g：会讲法语和德语；试问：这7个人要围成一圈，应如何排座位，才干使每个人都能和她身边（相邻）人交谈？29、彼得森图如图8-23所示。证明它不是二部图，也不是欧拉图，更不是平面图。P18930、证明图8-24所示图G是哈密顿图，但不是平面图。P18931、图8-25