离散数学复习题参考带答案

一、选择题：（每题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 ． ，100，101，110，111B ． ，100，101，111C ． 全体赋值D ． 不存在4、合式公式⌝(P ∧Q)→R 的主析取式中含极小项的个数为（ ）。

A ．2B ．3C ．5D ．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 ．0B ．1C ．2D ．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) → 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 ．3B ．6C ．7D ．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 且唯一。