一、选择题：（每题2’）1、下列语句中不是命题的有（ ）。

A ．离散数学是计算机专业的一门必修课。

B ．鸡有三只脚。

C ．太阳系以外的星球上有生物 。

D ．你打算考硕士研究生吗? 2、命题公式A 与B 是等价的，是指（ ）。

A ． A 与B 有相同的原子变元 B ． A 与B 都是可满足的C ． 当A 的真值为真时，B 的真值也为真D ． A 与B 有相同的真值3、所有使命题公式P∨(Q∧¬R)为真的赋值为（ ）。

A ． 010，100，101，110，111B ． 010，100，101，111C ． 全体赋值D ． 不存在 4、合式公式(P∧Q)R 的主析取范式中含极小项的个数为（ ）。

A ．2 B ．3 C ．5 D ．05、一个公式在等价意义下，下面哪个写法是唯一的（ ）。

A ．析取范式B ．合取范式C ．主析取范式D ．以上答案都不对6、下述公式中是重言式的有（ ）。

A ．(P ∧Q) (P ∨Q)B ．(P Q) (( P Q)∧(Q P))C ．(P Q)∧QD ．P (P ∧Q) 7、命题公式 (P Q) (Q ∨P) 中极小项的个数为（ ），成真赋值的个数为（ ）。

A ．0 B ．1 C ．2 D ．38、若公式 (P∧Q)∨(P∧R) 的主析取范式为 m 001∨m 011∨m 110∨m 111 则它的主合取范式为（ ）。

A ．m 001∧m 011∧m 110∧m 111B ．M 000∧M 010∧M 100∧M 101C ．M 001∧M 011∧M 110∧M 111D ．m 000∧m 010∧m 100∧m 1019、下列公式中正确的等价式是（ ）。

A ．(x)A(x) (x)A(x) B ．(x) (y)A(x, y) (y) (x) A(x, y) C ．(x)A(x) (x)A(x) D ．(x) (A(x) ∧B(x)) (x) A(x) ∨(x) B(x) 10、下列等价关系正确的是（ ）。

A ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x)B ．x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x)C ．x ( P(x) Q ) x P(x) QD ．x ( P(x) Q ) x P(x) Q 11、设个体域为整数集，下列真值为真的公式是（ ）。

A ．x y （x·y=1）B ．x y （x·y=0）C ．x y （x·y=y） D ．x y （x+y=2y ） 12、设S={,{1},{1,2}}，则有（ ）S 。

A ．{{1,2}}B ．{1,2 }C ．{1}D ．{2}13、下列是真命题的有（ ）。

A ．{a}{{a}}B ．{{}}{,{}}C ．{,{}}D ．{}{,{}}14、设S={,{1},{1,2}}，则2S有（ ）个元素。

A ．3B ．6C ．7D ．8 15、已知幂集的基数|( A)|=2048，则集合A 的基数|A|为（ ）。

A ．11 B ．12 C ．10 D ．916、设A={1，2，3}，则A 上的二元关系有（ ）个。

A ． 23B ． 32C ．233D ．32217、设A={a, b, c, d}，A 上的等价关系R={<a, b>,<b, a>,<c, d>,<d, c>}∪I A ，则对应于R 的A 的划分是（ ）。

A ．{{a}, {b, c}, {d}}B ．{{a, b}, {c}, {d}}C ．{{a}, {b}, {c},{d}} D ．{{a, b}, {c, d}}18、设R ，S 是集合A 上的关系，则下列说法正确的是（ ）。

A ．若R 、S 是自反的，则R S 是自反的B ．若R 、S 是反自反的，则R S 是反自反的C ．若R 、S 是对称的，则R S 是对称的D ．若R 、S 是传递的，则R S 是传递的19、集合A 上的相容关系R 的关系矩阵M(R)的对角线元素（ ）。

A ．全是1B ．全是0C ．有的是1，有的是0D ．有的是220、设集合 A={1，2，3}，A 上的关系R={<1,1>，<1,2>，<2,2>，<3,3>，<3,2>}，则R 不具备（）。

A ． 自反性B ． 传递性C ． 对称性D ． 反对称性21、设} 3 ,2 ,1 { S ，S 上关系R 的关系图为（如图所示），则R 具有（ ）性质。

A ．自反性、对称性、传递性B ．反自反性、反对称性C ．反自反性、反对称性、传递性D ．自反性22、设S={1，2，3}，R 为S 上的关系，其关系图为则R 具有（ ）的性质。

A ．自反、对称、传递B ．什么性质也没有C ．反自反、反对称、传递D ．自反、对称、反对称、传递23、设A={1, 2, 3}，B={a, b}，下列各二元关系中是A 到B 的函数的是（ ）。

A ．R={<1,a>,<2,a>,<3,a>}B ．R={<1,a>,<2,a>,<2,b>,<3,a>}C ．R={<1,a>,<2,b>}D ．R={<2,a>,<2,b>}24、设R 为实数集，映射f ：R R ，f (x)= -x 2+2x-1，则f 是（ ）。

A．单射而非满射B．满射而非单射C．双射D．既不是单射，也不是满射25、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（）。

A．B． C．D．26、N是自然数集合，定义f：N N，f (x) = x mod 3（即x除以3的余数），则f 是（）。

A．满射不是单射B．单射不是满射C．双射D．不是单射也不是满射27、设S={,{1},{1,2}}，则有（）S。

A．{{1,2}} B．{1,2 } C．{1} D．{2}28、集合A={x | x=2n∧n N }对（）运算封闭。

A．加法B．减法C．乘法D．|x－y|29、设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（）。

A．x A，有x*Z=Z*x=Z B．Z A，且x A有x*Z=Z*x=ZC．Z A，且x A有x*Z=Z*x=x D．Z A，且x A有x*Z=Z*x=Z30、下面偏序集（）能构成格。

31、在（）中，补元是唯一的。

A．有界格B．有补格 C．分配格D．有补分配格。

32、下面四组数能构成无向简单图的度数序列的有（）。

A．(2, 2, 2, 2, 2) B．(1, 1, 2, 2, 3) C．(1, 1, 2, 2, 2) D．(1, 1, 3, 3, 3)33、无向图结点之间的连通性，是结点集之间的一个（）。

A．连通关系B．偏序关系C．等价关系D．函数关系34、已知图G的相邻矩阵为：则G有（）。

A．5点，8边B．6点，7边C．5点，7边D．6点，8边35、下列四组数为结点度序列，能构成无向图的是（）。

A．2, 3, 4, 5, 6, 7 B．1, 2, 2, 3, 4C．2, 1, 1, 1, 2 D．3, 3, 5, 6, 036、下列几个图是简单图的有（）。

A．G1=(V1,E1)，其中 V1={a, b, c, d, e}，E1={(a,b), (b,e), (e,b), (a,e), (d,e)}B．G2=(V2,E2)，其中V2=V1，E2={<a,b>, <b,c>, <c,a>, <a,d>, <d,a>, <d,e>}C．G3=(V3,E3)，其中V3=V1，E3={(a,b), (b,e), (e,d), (c,c)}D．G4=(V4,E4)，其中V4=V1，E4={<a,a>, <a,b>, <b,c>, <e,c>, <e,d>}37、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。

A．1 B．2 C．3 D．438、一棵树有2个4度结点，3个3数度结点，其余是树叶，则该树中树叶的个数是（）。

A．8 B．9 C．10 D．1139、设图G是有6个顶点的连通图，总度数为20，则从G中删去（）边后使之变成树。

A．10 B． 5 C． 3 D． 240、下面那一个图可一笔画出（）。

41、在如下各图中（）欧拉图。

42、下图中既不是欧拉图，也不是哈密尔顿图的是（ ）。

43、在如下的有向图中，从V 1到V 4长度为3 的道路有（ ）条。

A ．1B ．2C ．3D ．444、图 中 从v 1到v 3长度为3 的通路有（ ）条。

A ．0B ．1C ．2D ．3二、判断题（每题 1分）1．)()())()((x xB x xA x B x A x ∀∧∀⇔∧∀。

（ Y ） 2．设A ，B ， C 是任意三个集合。

（1）若A B 且B C ，则A C 。

（ Y ） （2）若A B 且B C ，则A C 。

（ N ） （3）若A B 且B C ，则A C 。

（ N ） （4）(A B)⨯C=(A ×C)(B ×C)。

（ Y ）（5）A ∪(B C)= (A∪B)(A∪C)。

（ N ）3．A ，B ，C 为任意集合，若A ∪B=A ∪C ，则B = C 。

（ N ）4．可能有某种关系，既不是自反的，也不是反自反的。

（ Y ）5．可能有某种关系，既是对称的，又是反对称的。

（ Y ）6．设R 是实数集，R 上的关系S={<x , y >||x -y |＜2∧x ,y R}，S 是相容关系。

（ Y ）7．若集合A 上的关系R 是对称的，则R c 也是对称的。

（ Y ）8．数集合上的不等关系（≠）可确定A 的一个划分 （ N ）9．设集合A 、B 、C 为任意集合，若A×B = A×C，则B = C 。

（ N ）10．函数的复合运算“ ”满足结合律。

（ Y ）11．集合A 上的恒等关系是一个双射函数。

（ Y ）12．任何一个循环群必定是阿贝尔群。

（ Y ）13．任何循环群必定是阿贝尔群，反之亦真。

（ N ）14．设< A ，≤ >是偏序集，B A ，则B 的极大元b B 且唯一。

（ N ）15．群是每个元素都有逆元的半群。

（ N ）16．在代数系统< S , > 中，若一个元素的逆元是唯一的，其运算必是可结合的。

（ N） 17．每一个有限整环一定是域，反之也对。