离散数学复习纲要.docVIP

201209学期《离散数学》复习纲要一 一、单项选择题 1．下列语句中是真命题的是（ ） A.我正在说谎 B.严禁吸烟 C.如果1+2=3，那么雪是黑的 D.如果1+2=5，那么雪是黑的 2．将命题“若m是奇数，则2m是偶数”符号化为（ ）是奇数，是 偶数。 A. B. C. D. 3．命题公式A与B是等价的，是指（ ） A.A与B有相同的原子变元 B.A与B是可满足的 C.当A的真值为真时，B的真值也为真 D.A与B有相同的真值 4．在公式中，的辖域是（ ） A. B. C. D. 5．在合式公式中，的辖域是（ ） A. B. C. D. 6．设A= {1,2,4},B={1,3,{2}},下列各式成立的是（ ） A. B. C. D. 7．设,则（ ） A. B. C. D. 8．前提的结论是（ ） A. B. C. D. 9．整数集合Z上的关系的传递闭包是关系（ ） A. B. C.全域关系 D. 10．设,则A上不同的等价关系总共有（ ） A.3个 B.4个 C.5个 D.6个 11．数的加法在下列集合上封闭的是（ ） A. B. C. D. 12．设,*为普通乘法，则代数系统的幺元为（ ） A.不存在 B. C. D. 13．完全图K3的不同构的生成子图的个数为（ ） A.3 B.4 C.5 D.6 14．设是一个有界格，它也是有补格，只要满足（ ） A.每个元素都有一个补元 B.每个元素都至少有一个补元 C.每个元素都无补元 D.每个元素都有多个补元 15．具有如下定义的代数系统，（ ） A.G={1，10},*是模11乘 B.G={1，3，4，5，9},*同是模11乘 C.G=Q(有理数),*是普通加法 D.G=Q(有理数),*是普通乘法 16．在自然数集合N上，下列哪种运算是可结合的？（ ） A.B. C. D. 17．连通无向图G有6个顶点9条边，T为G的一棵生成树，对应T的基本回路的数目为（ ）A.4 B.5 C.6 D.7 18．一棵树有2个4度顶点，3个3度顶点，其余是树叶，则该树中树叶的个数是（ ）A.8 B.9 C.10 D.11 19．K33是（ ） A.欧拉图 B.哈密顿图 C.平面图 D.完全图 20．给定下列序列，（ ） A.（1，1，2，2，3） B.（1，1，2，2，2） C.（0，1，3，3，3） D.（1，3，4，4，5） 二、判断题（正确填“T”，错误填“F”） 1．自然数 N = {1，2，3，．．．．．} + { 0 }。 ( ) 2．设A,B为任意命题，则。 ( ) 3．联结词集合是功能完备集。 ( ) 4．设A,B为任意集合，则。 ( ) 5．G（n，m）图的每一棵生成树都有 n-1 条树枝。 ( ) 6．设个体域是自然数集合，p 代表 xy彐z F（x－y = z），则 p 是真命题。( ) 7．自然数 N 与其上的普通加法 + 构成的代数系统 〈N，+〉 是群。 ( ) 三、填空题 1．谓词公式是______，是______。（填逻辑有效式或矛盾式） 2．公式中，x是______出现，y是______出现。 3．若函数g和f是入射，则是______；若g和f是满射的，则是______；若g和f是双射的，则是______。 四、证明题 证明：（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （2）当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。 201209学期《离散数学》复习纲要一 答案 一、单项选择题 DDDDB BCDDC CBCBD ABBCB 二、判断题（正确填“T”，错误填“F”） FFTTT FF 三、填空题 题号 答案 1 逻辑有效式 矛盾式 2 约束自由 3 入射 满射 双射 四、证明题 证明： （1）因图中结点数和边数分别为，，根据欧拉公式，