离散数学考试题及答案

离散数学考试题及答案

一、单项选择题（每题2分，共10题）1.设集合A={1,2,3}，则A的幂集P(A)的元素个数为（）A.3B.6C.8D.9答案：C2.设命题公式P→Q的真值为假，则P和Q的真值为（）A.P=0,Q=0B.P=0,Q=1C.P=1,Q=0D.P=1,Q=1答案：C3.设图G是有n个顶点的无向连通图，则其边数（）A.至少为n-1B.至多为n-1C.恰好为n-1D.至少为n答案：A4.设A={a,b,c}，关系R={(a,a),(a,b)}在A上，则R是（）A.自反的B.对称的C.传递的D.反自反的答案：C5.下列代数系统<G,>中，（）不是群。A.G={1,-1},为普通乘法B.G={0,1,2},为模3加法C.G=Q(有理数集),为普通加法D.G=Z(整数集),为普通减法答案：D6.在自然数集N上，下列（）运算是可结合的。A.ab=a-bB.ab=max(a,b)C.ab=a+2bD.ab=\|a-b\|答案：B7.设谓词公式∀x(P(x)→Q(x,y))，则该公式的自由变元是（）A.xB.yC.x和yD.既不是x也不是y答案：B8.设A={1,2,3,4}，则A上不同的等价关系的个数为（）A.15B.16C.17D.18答案：A9.具有6个顶点的无向树的边数为（）A.4B.5C.6D.7答案：B10.设布尔表达式E=(x+y)(x'+z)，则E的对偶式为（）A.(x'y)+(xz')B.(x'y)+(x'z)C.(x+y')(x'+z')D.(x+y')(x+z')答案：A二、多项选择题（每题2分，共10题）1.以下哪些是集合A={1,2,3}上的关系（）A.{(1,1)}B.{(1,2),(2,3)}C.{(1,3),(3,1)}D.{(1,2,3)}E.A×A答案：ABCE2.下列命题公式中，哪些是永真式（）A.P→(P∨Q)B.(P∧Q)→PC.(P→Q)→(¬Q→¬P)D.¬(P→Q)∧QE.(P∨¬P)→(Q∧¬Q)答案：ABC3.下列图中，哪些是欧拉图（）A.无向完全图K3B.无向完全图K4C.有向完全图D3D.有向完全图D4E.一个圈图C5答案：AE4.设<G,>是群，a,b∈G，则以下等式成立的有（）A.(ab)⁻¹=a⁻¹b⁻¹B.(a⁻¹)⁻¹=aC.ae=ea=a，其中e是单位元D.ab=baE.如果aa=e，则a=e答案：BC5.以下关于格的说法正确的有（）A.任何一个偏序集都能构成格B.在格<L,≤>中，a∧b=min(a,b)，a∨b=max(a,b)C.格<L,≤>中，a≤b当且仅当a∧b=aD.分配格一定是模格E.有补格一定是分配格答案：BCD6.在自然数集N上定义的二元运算，如果满足（）则<N,>是半群。A.对任意a,b∈N，ab=a+bB.对任意a,b∈N，ab=a-bC.对任意a,b∈N，ab=a×bD.对任意a,b∈N，ab=max(a,b)E.对任意a,b∈N，ab=min(a,b)答案：ACDE7.设个体域为整数集Z，下列公式中哪些是真命题（）A.∀x∃y(x+y=0)B.∃x∀y(x+y=0)C.∀x∀y(xy=yx)D.∃x∃y(xy=2)E.∀x(x²≥0)答案：ACDE8.设A={a,b,c,d}，A上的划分π1={{a,b},{c,d}}，π2={{a,c},{b,d}}，则（）A.π1和π2的并是{{a,b,c,d}}B.π1和π2的交是∅C.由π1生成的等价关系R1={(a,a),(b,b),(a,b),(b,a),(c,c),(d,d),(c,d),(d,c)}D.由π2生成的等价关系R2={(a,a),(c,c),(a,c),(c,a),(b,b),(d,d),(b,d),(d,b)}E.由π1和π2生成的最大划分是{{a,b,c,d}}答案：ABCDE9.对于一个简单无向图G，若其顶点数n和边数m满足m=(n(n-1))/2，则（）A.G是完全图B.G的每个顶点的度为n-1C.G是连通图D.G是欧拉图E.G是哈密顿图答案：AB10.设布尔代数<B,∧,∨,',0,1>，则（）A.0'=1B.1'=0C.a∧a'=0D.a∨a'=1E.(a∧b)'=a'∨b'答案：ABCDE三、判断题（每题2分，共10题）1.空集是任何集合的真子集。（）答案：错2.若命题公式A→B为真，则¬A→¬B也为真。（）答案：错3.有n个顶点的无向完全图Kn的边数为n(n-1)。（）答案：错4.设R是集合A上的关系，若R是对称的和传递的，则R是自反的。（）答案：错5.在群<G,>中，对于任意a,b∈G，方程ax=b和ya=b都有唯一解。（）答案：对6.设<L,≤>是格，a,b∈L，则a∨(b∧c)=(a∨b)∧(a∨c)。（）答案：错7.谓词公式∀x(P(x)∧Q(x))和∀xP(x)∧∀xQ(x)是等价的。（）答案：对8.设A={1,2,3}，B={2,3,4}，则A-B={1}。（）答案：对9.具有n个顶点的无向树的所有顶点度数之和为2n-2。（）答案：对10.在布尔代数中，a∧(a∨b)=a。（）答案：对四、简答题（每题5分，共4题）1.简述集合A上的等价关系的定义。答案：集合A上的关系R如果是自反的、对称的和传递的，则称R是A上的等价关系。2.什么是群的单位元？答案：在群<G,>中，存在元素e∈G，对于任意a∈G，都有ae=ea=a，这个元素e称为群的单位元。3.简述哈密顿图的定义。答案：如果无向图G中存在一条经过图中每个顶点一次且仅一次的回路，则称G为哈密顿图。4.什么是布尔表达式？答案：布尔表达式是由布尔变量、布尔常量（0和1）以及布尔运算（∧、∨、'）按一定规则组成的表达式。五、讨论题（每题5分，共4题）1.讨论偏序集构成格的条件。答案：偏序集<L,≤>构成格，需要对于L中的任意两个元素a,b，都存在最小上界（上确界）a∨b和最大下界（下确界）a∧b。2.讨论有向图是强连通图的条件。答案：有向图G是强连通图当且仅当对于G中的任意两个顶点u和v，都存在从u到v和从v到u的有向路径。3.讨论