《离散数学》复习题专升本.doc

离散数学复习题（专升本） 一、填空题1、设 （N：自然数集，E+ 正偶数） 则 。2、A，B，C表示三个集合，文图中阴影部分的集合表达式为 A B C 。3、设P，Q 的真值为0，R，S的真值为1，则的真值= 。4、公式的主合取范式为 。5、若解释I的论域D仅包含一个元素，则 在I下真值为 。6、设A=1，2，3，4，A上关系图为则 R2 = 。7、设A=a，b，c，d，其上偏序关系R的哈斯图为则 R= 。8、图的补图为 。9、设A=a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。10、下图所示的偏序集中，是格的为 。 11、选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。12、集合A=,的幂集P(A) = 。13、设A=1，2，3，4，A上二元关系R=，画出R的关系图 。14、设A=, , B=,则= 。= 。15、设|A|=3，则A上有 个二元关系。16、A=1，2，3上关系R= 时，R既是对称的又是反对称的。17、偏序集的哈斯图为，则= 。18、设|X|=n，|Y|=m则（1）从X到Y有 个不同的函数。（2）当n , m满足 时，存在双射有 个不同的双射。19、是有理数的真值为 。20、Q：我将去上海，R：我有时间，公式的自然语言为 。21、公式的主合取范式是 。22、若是集合A的一个分划，则它应满足 。二、选择题1、下列是真命题的有（）A ； B；C ； D 。2、下列集合中相等的有（ ） A4，3；B，3，4；C4，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=（ ）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、设A=，1，1，3，1，2，3则A上包含关系“”的哈斯图为（ ）7、下列函数是双射的为（ ）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :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度结点。A1；B2；C3；D4 。11、设全集为I，下列相等的集合是（ ）。A、； B、；C、； D、。12、设S=N，Q，R，下列命题正确的是（ ）。A、； B、；C、； D、。13、设C=a,b,a,b，则分别为（ ）。A、C和a,b；B、a,b与；C、a,b与a,b；D、C与C14、下列语句不是命题的有（ ）。A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚；D、太阳系以外的星球上有生物； E、你打算考硕士研究生吗？15、的合取范式为（ ）。A、 ；B、 ；C、 D、。16、设|A|=n，则A上有（）二元关系。A、2n ； B、n2 ； C、； D、nn ； E、。17、设r为集合A上的相容关系，其简化关系图（如图），则 I r产生的最大相容类为（ ）；A、； B、； C、； D、 II A的完全覆盖为（ ）。A、； B、；C、； D、 。18、集合A=1，2，3，4上的偏序关系图为 则它的哈斯图为（ ）。19、下列关系中能构成函数的是（ ）。A、；B、；C、； D、。20、N是自然数集，定义（即x除以3的余数），则f是（ ）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。三、证明题、 R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R中有在R中。、 f和g都是群到的同态映射，证明是的一个子群。其中C= 、 G= (|V| = v，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，则， 由此证明彼得森图（Peterson）图是非平面图。、 1、每一有限全序集必是良序集。、 2、设是复合函数，如果满射，则也是满射。四、逻辑推演一、用CP规则证明下题1、2、二、或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，如果许多学生喜欢逻辑，那么数学并不难学。3、五、计算题1、设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。六、解答题设X=1,2,3,4,5，X上的关系R= , , , , ，用Warshall方法，求R的传递闭包t (R)。七、简答题1、设S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?2、设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？参考答案一、填空题1、2(x+1)；2、 ；3、；4、反对称性、反自反性；5、；6、1；7、；8、任意x，如果x是素数则存在一个y，y是奇数且y整除x ；9、10、；11、；12、见右图； 13、 , , , ， ,、 , ；14、29； 15、 , , ；16、,；17、mn 、n=m、n!；18、假；1