离散模拟题(自己总结版)

一.单项选择题1. 永真命题公式( ) 只存在主析取范式;只存在主合取范式;既存在主析取范式也存在主合取范式;都不对.2. 下列代数系统中消去侓不成立的是( ).群;含幺半群;整环;分配格.3.在4个元素的集合上可定义的满射有( )个 4;12; 16 244. 在整环和格的定义中对运算都要求满足的性质是( ) 及收律; 幂等律; 交换律; 分配律.5. 下面对于群、环、格中运算都要求的性质是( ) 结合性; 交换性; 幂等性; 分配性6. 下面说法中正确的是( ) 半群都有幂等元;.剩余类环中没有零因子;.整数加法群不是循环群;每个群都有正规子群.7.下面正确的说法是( ) 5点格都不是分配格;剩余类环中没有零因子; 数加群不是循环群;群中一定有等幂元8.Z5为模5剩余类集,定义f: Z5Z5如下:f(x)=2x+1,则f0f( ).不是函数;不是单射;是置换;不是满射(0:1;1:3;2:0;3:2;4:4)9.下面关于集合基数正确的说法是( ) 没有最大的基数集;.任何集合都存在与它等势的真子集; 有最小的基数;有理数集合与实数集合等势10. 下面图中,可以割边的图是( )K10,10; 欧拉图;平面图;哈密顿图.11. 在4个元素的集合上可定义的等价关系有( )个 4;8;12 15.12.群没有平凡子群,则G( ) 没有平凡子群;是循环群;是置换群;不存在.13. 设R是A上的二元关系,且R0R=R,则( ) r（ R）=R;S( R )=R;t( R )=R;R=IA.14.谓词合适公式同时又是命题合适公式时,公式中必无( ) 自由变量;约束变量;个体常量;函数.15.设T是G的生成树,则( )G的回路必含T的边;G的回路必不含T的边;G的割边必含T的边;G的割边必不含T的边.16. 设18阶简单连通平面图G有35条边,则最多能为它增加( )条边使其仍能保持是简单平面图. 13;.18;.20;.25.(35+133*18-6=48)17.下式中( )是永真的.(PQ) (PQ)；(PQ)(PQ)；(PQ) (PQ)；(PQ)(PQ).18. 下面在集合论和逻辑学中正确的公式有( ) PPPP;2AU2B=2AUB;x(A(x) B(x) $xA(x)xB(x);AB=ACB=C;19. 下面可由拉格朗日定理推出的结论是( )每个群都有循环子群;素数阶的群是循环群;群中方程有解;群的同态核是群的正规子群.20. 下面能够符合既无割点也无割边的图类是( ).树; 欧拉图;哈密顿图;二部图.21. 设R是A上的二元关系,且R0R=R可以肯定R应是( ) 自反关系;传递关系;反对称关系;等价关系22.一个格中每个元都有补元,则该格必是( ) 有限格; 分配格; 有界格; 布尔格23.如果图G存在完备匹配M,下面叙述正确的是( ) G中无割边;G中无割点;不存在M非饱和点;存在M增广道路24. 下面哪个是有限半群必然具备的? ( ) 有等幂元; 有零元; 有幺元; 方程有解25.循环群之间的满同态映射( ) 是单射; 是双射; 把生成元映成生成元; 把零元映成零元二.多项选择题 1.下面各图中必存在生成树的有( )哈密顿图;欧拉图;平面图;平面图的对偶图;K6,82. 下面可由拉格朗日定理推出的结论是( )每个群都有循环子群;素数阶的群是循环群;群中消去律成立;元素的周期可整除群的阶;子群的阶是群的阶的因子3.下面集合中基数为阿列夫零的有( )100的倍数集;区间（2，4）;素数集合;偶数集合的幂集合；分子为5的真分数所成之集4.下列代数系统中消去律成立的有( )2A，;2A，U;置换群Sn，0;环;分配格5.下面含有生成元的群有( ) 整数加法群;非零实数乘群;置换群; 素数阶群剩余类乘群6.如果一个格中消去律成立,那么这个格( )是有补格;是分配格;是有界格;满足吸收律;满足幂等律7.下面各图中边数必不小于结点数的图有( )哈密顿图;欧拉图;平面图;二部图;树三.计算题1.求剩余类环Z12, ,上方程2x2+3x-3=0的全部解。2.如果一个n阶简单平面图又是自补图时,求n的可能值。3.写出(PR) (QR)的主析取范式。4.设A=a,b,c,d,e,求该集合元素a和b在同一个等价类中的等价关系数目。5.设G是n阶3度正则平面图,求要给它新加多少边才可能使它成为自对偶图。6.写出置换群中关于置换子群的全部左陪集。7.决定幂集代数系统2A，中有无幺元、零元、幂等元，如果有，写出它们。8.当n阶K度正则图是平面图时，求n和k满足的关系式。9.写出5个元素的集合上可以定义的含2个等价类的全部等价关系。10. 设T是一个n阶的完全3叉树，求最少要给它新加多少边才能使它成为欧拉图。11.画出元素个数为6的全部有补格对应的Hasse图。12.设a和b是交换群中周期分别为4和6的两个元素,求a*b的周期。13.求一个20阶的、非连通的、简单平面图的最大边数。14设A=a,b,c,计算A上可以定义多少个二元关系,等价关系和双射。15. 设n阶简单连通图G既是自补图又是平面图,求它的面数表达式。16求的全部生成元。四.证明题1.1设R是集A上的等价关系，证明：对任何正整数n,Rn也是等价关系。1.2设R是集A上一个自反二元关系，且（a，b）R（a，c）R（b，c）R。证明：R是等价关系。1.3设R是集A上一个自反、对称二元关系，且RoR-1=IA，证明：R是等价关系。2.1证明：连通图G其对偶图是平面二部图当且仅当G是平面欧拉图。2.2证明：如果图G中存在两个不同的完备匹配,证明G中必有回路。3.1证明：Q(PR)，(RS)B,A (SB)QPA。3.2证明：x(P(x)(Q(x)R(x)，xQ(x)$y(R