《离散数学》题库

1离散数学题库一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式1QQP2QPQ3PPQ4PPQP2、下列公式中哪些是永真式1PQQR2PQQ3PQP4PPQ3、设有下列公式，请问哪几个是永真蕴涵式1PPQ2PQP3PQPQ4PPQQ5PQP6PPQP4、公式XAXBY，XZCY，ZDX中，自由变元是，约束变元是。5、判断下列语句是不是命题。若是，给出命题的真值。1北京是中华人民共和国的首都。2陕西师大是一座工厂。3你喜欢唱歌吗4若7818，则三角形有4条边。5前进6给我一杯水吧6、命题“存在一些人是大学生”的否定是，而命题“所有的人都是要死的”的否定是。7、设P我生病，Q我去学校，则下列命题可符号化为。1只有在生病时，我才不去学校2若我生病，则我不去学校3当且仅当我生病时，我才不去学校4若我不生病，则我一定去学校8、设个体域为整数集，则下列公式的意义是。1XYXY02YXXY09、设全体域D是正整数集合，确定下列命题的真值1XYXYY2XYXYY23XYXYX4XYY2X10、设谓词PXX是奇数，QXX是偶数，谓词公式XPXQX在哪个个体域中为真1自然数2实数3复数413均成立11、命题“2是偶数或3是负数”的否定是（）。12、永真式的否定是（）1永真式2永假式3可满足式413均有可能13、公式PQPQ化简为（），公式QPPQ可化简为（）。14、谓词公式XPXYRYQX中量词X的辖域是（）。15、令RXX是实数，QXX是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。（集合论部分）16、设AA,A，下列命题错误的是（）。1APA2APA3APA4APA17、在0（）之间写上正确的符号。123418、若集合S的基数|S|5，则S的幂集的基数|PS|（）。19、设PX|X14且XR,QX|5X16且XR,则下列命题哪个正22确（）1QP2QP3PQ4PQ20、下列各集合中，哪几个分别相等。1A1A,B2A2B,A3A3A,B,A4A4A,B,C5A5X|XAXBXC06A6X|X2ABXAB021、若AB，则下列哪个结论不可能正确31A2B3AB4BA22、判断下列命题哪个为真1ABBAAB2空集是任何集合的真子集3空集只是非空集合的子集4若A的一个元素属于B，则AB23、判断下列命题哪几个为正确1,2,345A,BA,B,A,B24、判断下列命题哪几个正确1所有空集都不相等24若A为非空集，则AA成立。25、设ABAC，BC，则BC。A26、判断下列命题哪几个正确1若ABAC，则BC2A,BB,A3PABPAPB（PS表示S的幂集）4若A为非空集，则AAA成立。27、，是三个集合，则下列哪几个推理正确1AB，BCAC2AB，BCAB3AB，BCAC（二元关系部分）28、设1,2,3,4,5,6，B1,2,3，从到B的关系X,Y|XY2，求1R2R1。29、举出集合A上的既是等价关系又是偏序关系的一个例子。30、集合A上的等价关系的三个性质是什么31、集合A上的偏序关系的三个性质是什么32、设A,，上的关系1,2，2,1，2,3，3,4求1RR2R1433、设1，2，3，4，5，6，是A上的整除关系，求R。34、设1,2,3,4,5,6，B1,2,3，从到B的关系X,Y|X2Y，求1R2R1。35、设1,2,3,4,5,6，B1,2,3，从到B的关系X,Y|XY2，求R和R1的关系矩阵。36、集合A1,2,10上的关系R|XY10,X,YA，则R的性质为（）。1自反的2对称的3传递的，对称的4传递的（代数结构部分）37、设A2,4,6，A上的二元运算定义为ABMAXA,B，则在独异点中，单位元是，零元是。38、设A3,6,9，A上的二元运算定义为ABMINA,B，则在独异点中，单位元是，零元是；（半群与群部分）39、设G,是一个群，则1若A,B,XG，AXB，则X；2若A,B,XG，AXAB，则X。40、设A是12阶群的生成元，则A2是阶元素，A3是阶元素。41、代数系统是一个群，则G的等幂元是。42、设A是10阶群的生成元，则A4是阶元素，A3是阶元素。43、群的等幂元是，有个。44、素数阶群一定是群,它的生成元是。45、设G,是一个群，A,B,CG，则51若CAB，则C；2若CABA，则C。46、是的子群的充分必要条件是。47、群A,的等幂元有个，是，零元有个。48、在一个群G,中，若G中的元素A的阶是K，则A1的阶是。49、在自然数集N上，下列哪种运算是可结合的（）1ABAB2ABMAXA,B3ABA2B4AB|AB|50、任意一个具有2个或以上元的半群，它（）。1不可能是群2不一定是群3一定是群4是交换群51、6阶有限群的任何子群一定不是（）。12阶23阶34阶46阶（格与布尔代数部分）52、下列哪个偏序集构成有界格（）1（N,）2（Z,）3（2,3,4,6,12,|（整除关系）4PA,53、有限布尔代数的元素的个数一定等于（）。1偶数2奇数34的倍数42的正整数次幂（图论部分）54、设G是一个哈密尔顿图，则G一定是。1欧拉图2树3平面图4连通图55、下面给出的集合中，哪一个是前缀码10，10，110，101111201，001，000，13B，C，AA，AB，ABA41，11，101，001，0011656、一个图的哈密尔顿路是一条通过图中的路。57、在有向图中，结点V的出度DEGV表示，入度DEGV表示。58、设G是一棵树，则G的生成树有棵。1021324不能确定59、N阶无向完全图KN的边数是，每个结点的度数是。60、一棵无向树的顶点数N与边数M关系是。61、一个图的欧拉回路是一条通过图中的回路。62、有N个结点的树，其结点度数之和是。63、下面给出的集合中，哪一个不是前缀码。1A，AB，110，A1B11201，001，000，131，2，00，01，0210412，11，101，002，001164、N个结点的有向完全图边数是，每个结点的度数是。65、一个无向图有生成树的充分必要条件是。66、设G是一棵树，N,M分别表示顶点数和边数，则1NM2MN13NM14不能确定。67、设TV,E是一棵树，若|V|1，则T中至少存在片树叶。68、任何连通无向图G至少有棵生成树，当且仅当G是，G的生成树只有一棵。69、设G是有N个结点M条边的连通平面图，且有K个面，则K等于1MN22NM23NM24MN2。70、设T是一棵树，则T是一个连通且图。71、设无向图G有16条边且每个顶点的度数都是2，则图G有个顶点。110243841672、设无向图G有18条边且每个顶点的度数都是3，则图G有个顶点。7110243841273、设图G，VA，B，C，D，E，E,则G是有向图还是无向图74、任一有向图中，度数为奇数的结点有个。75、具有6个顶点，12条边的连通简单平面图中，每个面都是由条边围成1224334576、在有N个顶点的连通图中，其边数（）。1最多有N1条2至少有N1条3最多有N条4至少有N条77、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为（）。1527384978、若一棵完全二元（叉）树有2N1个顶点，则它（）片树叶。1N22N3N14279、下列哪一种图不一定是树（）。1无简单回路的连通图2有N个顶点N1条边的连通图3每对顶点间都有通路的图4连通但删去一条边便不连通的图80、连通图G是一棵树当且仅当G中（）。1有些边是割边2每条边都是割边3所有边都不是割边4图中存在一条欧拉路径（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式1、PQR82、PRQRP3、PQRP4、QPR5、PPQP6、PQRP7、PPQ8、RQP9、PQ10、PQ11、PQ12、（PR）Q13、（PQ）R14、PQRPQR15、PPQQR16、PQPR三、证明1、PQ，QR，R，SPS2、ABC，CDE，FDE,ABF3、PQ，PR,QSRS4、PQRS，QWSX，WX，PRP5、UVMN,UP,PQS，QSM6、BD，EFD，EB7、PQR，RQSPQS8、PQ，PR，RSSQ9、PQRPQPR910、PQR，QP,SR,PS11、A，AB，AC，BDCD12、ACB，BA，DCAD13、PQRQ（PR）Q14、PQPPPQ15、（PQ）（PR），QR，SPS16、PQ，QR，RSP17、用真值表法证明18、PQPPQ19、用先求主范式的方法证明PQPRP（QR）20、PQQRP21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效前提1若A队得第一，则B队或C队获亚军2若C队获亚军，则A队不能获冠军3若D队获亚军，则B队不能获亚军4A队获第一结论5D队不是亚军。22、用推理规则证明PQ,QR,PR不能同时为真。集合论部分四、设，是三个集合，证明1、ABCABAC2、ABACABC3、ABAC，BC，则CBA4、ABABA5、ABAB6、ABAC，ABAC，则CB107、ABAC，BC，则CBA8、ABCABC9、ABACABC10、ABB，则AB11、AABACABC12、ABACABC13、ABBAAB14、ABCABC15、PAPBPAB（PS表示S的幂集）16、PAPBPAB（PS表示S的幂集）17、（AB）B（AB）B当且仅当B。N，则C的阶整除M与N的最大公因子M,N。五、证明或解答（数理逻辑、集合论与二元关系部分）1、设个体域是自然数，将下列各式翻译成自然语言1XY（XY1）2XYXY13XYXY04XY（XY0）5XYXYX6XY（XYX）7XYZXYZ2、设AX,Y,ZXYZ,M（X,Y,Z）XYZ,LX,YXY，个体域为自然数。将下列命题符号化（1）没有小于0的自然数（2）XYZ（4）存在X，对任意Y使得XYY（5）对任意X，存在Y使XYX。3、列出下列二元关系的所有元素（1）A0,1,2,B0,2,4,R|X,YBA（2）A1,2,3,4,5,B1,2,R|2XY4且X且YB（3）A1,2,3,B3,2,1,0,1,R|X|Y|且X且YB114、对任意集合A,B，证明若AABB，则BB。5、对任意集合A,B，证明若A，ABAC，则BC。故BC。6、设AA,B,BC。求下列集合1A0,1B；2B2A；3AB24PAA。7、设全集UA,B,C,D,E,AA,D,BA,B,C,CB,D。求下列各集合（1）AB；（2）；（3）ACCC（4）PAPB（5）ABBC（6）ABC8、设A,B,C是任意集合，证明或否定下列断言（1）若AB，且BC，则AC；（2）若AB，且BC，则AC（3）若AB，且BC，则AC；（4）若AB，且BC，则AC；9、A上的任一良序关系一定是A上的全序关系。10、若R和S都是非空集A上的等价关系，则RS是A上的等价关系。11、设RAA，则R自反IAR。12、设A是集合，RAA，则R是对称的RR1。13、设A，B，C和D均是集合，RAB，SBC，TCD，则1RSTRSRT；2RSTRSRT；14、设A,为偏序集，BA，若B有最大小元、上下确界，则它们是惟一的。15、设A1,2,3,写出下列图示关系的关系矩阵，并讨论它们的性质11123232316、设A1,2,10。下列哪个是A的划分若是划分，则它们诱导的等价关系是什么（1）B1,3,6,2,8,10,4,5,712（2）C1,5,7,2,4,8,9,3,5,6,10（3）D1,2,7,3,5,10,4,6,8,917、R是A1,2,3,4,5,6上的等价关系，RI,A求R诱导的划分。18、A上的偏序关系的HASSE图如下。1下列哪些关系式成立AB,BA,CE,EF,DF,CF；2分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）AABB,DCB,EDB,D,EAEFBDC（半群与群部分）19、求循环群C12E,A,A2,A11中HE,A4,A8的所有右陪集。20、求下列置换的运算21、试求出8阶循环群的所有生成元和所有子群。22、I上的二元运算定义为A,BI，ABAB2。试问是循环群吗23、设是群，AG。令HXG|AXXA。试证H是G的子群。24、证明偶数阶群中阶为2的元素的个数一定是奇数。25、证明有限群中阶大于2的元素的个数一定是偶数。26、试求中每个元素的阶。27、设是群，A,BG，AE，且A4BBA5。试证ABBA。28、I上的二元运算定义为A,BI，ABAB2。试证为群。29、设为半群，AS。令SAAI|II。试证是的子半群。30、单位元有惟一逆元。1331、设E和0是关于A上二元运算的单位元和零元，如果|A|1，则E0。32、证明在元素不少于两个的群中不存在零元。33、证明在一个群中单位元是惟一的。34、设A是一个群G,的生成元，则A1也是它的生成元。35、在一个偶数阶群中一定存在一个2阶元素。36、代数系统是一个群，则G除单位元以外无其它等幂元。37、设是一个群，则对于A,BG，必有唯一的XG，使得AXB。38、设半群中消去律成立，则是可交换半群当且仅当A,BS，（AB）2A2B2。39、设群除单位元外每个元素的阶均为2，则是交换群。40、设是集合A上可结合的二元运算，且A,BA,若ABBA，则AB。试证明（1）AA,AAA，即A是等幂元；（2）A,BA,ABAA（3）A,B,CA,ABCAC。41、设是群，作FGG,AA1。证明F是G的自同构G是交换群。42、若群的子群满足|G|2|H|，则一定是群的正规子群。43、设H和K都是G的不变子群。证明HK也是G的不变子群。44、设群G的中心为C（G）AG|XG,AXXA。证明C（G）是G的不变子群。45、设是没有非平凡子群的有限群。试证G是平凡群或质数阶的循环群。46、设H和K都是G的有限子群，且|H|与|K|互质。试证HKE。47、素数阶循环群的每个非单位元都是生成元。48、若是可交换独异点，T为S中所有等幂元的集合，则是的子独异点。1449、设是群，且AG的阶为N，KI，则|AK|，其中K,N为K和,NN的最大公因子。50、设是有限群，|G|N，则AG，|A|N。51、设GA，若G为无限群，则G只有两个生成元A和A1；52、设GA，EHG，AM是H中A的最小正幂，则（1）HAM；（2）若G为无限群，则H也是无限群；53、设GA，|G|N，则对于N的每一正因子D，有且仅有一个D阶子群。因此N阶循环群的子群的个数恰为N的正因子数。54、设H是从群到的群同态，G和G2的单位元分别为E1和1E2，则（1）HE1E2；（2）AG1，HA1HA1；（3）若HG1，则HHG2；（4）若H为单一同态，则AG1，|HA|A|。55、有限群G的每个元素的阶均能整除G的阶。56、证明在同构意义下，只有两个四阶群，且都是循环群。57、在一个群G,中，若G中的元素A的阶是K，即|A|K，则A1的阶也是K。58、在一个群中，若A和B都是G的子群。若ABG，则AG或BG。59、设E是奇数阶交换群的单位元，则G的所有元素之积为E。60、设SQQ，Q为有理数集合，为S上的二元运算对任意A,B,C,DS,有A,BC,DAC,ADB,求出S关于二元运算的单位元，以及当A0时，A,B关于的逆元。1561、设是一个群，H、K是其子群。定义G上的关系R对任意A,BG，ARB存在HH,KK,使得BHAK，则R是G上的等价关系。62、设H是G的子群，则下列条件等价（1）H是G的不变子群；（2）AG，AHA1H；（3）AG，A1HAH；（4）AG，HG，AHA1H。63、在半群中，若对A,BG，方程AXB和YAB都有惟一解，则是一个群。64、设是群，H和K都是G的子群，令HKHS|SK，HH,KHSH|SK,HH,，是G的子群的充分必要条件是HKKH。65、设H和K都是G的不变子群。证明HK也是G的不变子群。66、设为群，A,B,CG。若ABCBA,ACCA,BCCB，且A,B的阶分别为M,（格与布尔代数）67、当N分别是24，36，110时，是布尔代数吗若是，则求出其原子集。68、设L是有界格，且|L|1。证明01。证明69、设是格，若A,B,CL，ABC，则ABBC,ABBCABAC70、在布尔代数中，证明恒等式ABAB71、设是格，A1,A2,ANL。试证A1A2ANA1A2AN当且仅当A1A2AN。72、在布尔代数中，证明恒等式ACBBCACB73、在布尔代数中，证明恒等式ABCCABCB74、设是格，A,B,C,DL。试证若AB且CD，则ACBD75、当N分别是10,45时，画出的哈斯图。1676、在布尔代数中，证明恒等式ABCBCABCABC77、设是格，A,BL，且AB，记IA,BXL|AXB则是的子格。78、设AA,B,C，求的子格（PA表示A的幂集）。79、证明在同构意义下，4阶格只有2个。80、设是有界格，是A上的全序关系。若|A|2，则AA0,1，A无补元。81、格是模格A,B,CL，有ABACABAC82、设是分配格，A,B,CL。若ABAC且ABAC，则BC。83、证明在有补分配格中，每个元素的补元一定惟一。84、设是格，则L是分配格当且仅当A,B,CL，有ABCABC85、设是一布尔代数，则是一个交换群，其中定义为ABABAB。86、设是一布尔代数，则R|ABB是S上的偏序关系。87、设是一布尔代数，则关系|ABA是S上的偏序关系。（图论部分）88、证明在有N个结点的树中，其结点度数之和是2N2。88、任一图中度数为奇数的结点是偶数个。89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗17若是对的请证明之，否则请举例说明。90、设T是一棵树，若|V|1，则T中至少存在两片树叶。91、画一个使它分别满足1有欧拉回路和哈密尔顿回路；2有欧拉回路，但无条哈密尔顿回路；3无欧拉回路，但有哈密尔顿回路；4既无欧拉回路，又无哈密尔顿回路。92、设无向图G，|E|12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点93、设图G，|V|N，|E|M。K度顶点有NK个，且每个顶点或是K度顶点或是K1度顶点。证明NKK12M。94、设G是一个连通且|V|E|1的图，则G中有一个度为1的结点。95、若N阶连通图中恰有N1条边，则图中至少有一个结点度数为1。96、若G