.一、选择题：（每题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，111 B．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)∧Q D．P →(P∧Q)7、命题公式(⌝P→Q) →(⌝Q∨P)中极小项的个数为（），成真赋值的个数为（）。

A．0 B．1 C．2 D．38、若公式(P∧Q)∨(⌝P∧R) 的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为（）。

A．m001∧m011∧m110∧m111B．M000∧M010∧M100∧M101C．M001∧M011∧M110∧M111D．m000∧m010∧m100∧m1019、下列公式中正确的等价式是（）。

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) → Q D．∃x ( P(x) →Q ) ⇔∃x P(x) → Q11、设个体域为整数集，下列真值为真的公式是（）。

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．3 B．6 C．7 D．815、已知幂集的基数|ρ( A)|=2048，则集合A 的基数|A|为（ ）。

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

A ． 23B ． 32C ．23⨯3D ．32⨯217、设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．每一个有限整环一定是域，反之也对。