离散数学期末考试试题(配答案).doc

(每小题2分,共10分)∃x∃y¬P(x)∨Q(y)__________。∩B=__{2}__,_{4,5}____,__{1,3,4,5},则__{{c},{a,c},{b,c},{a,b,c}}__________,_____Φ_______。(N,+)中,其单位元是0,仅有1有逆元。,条边,则G有___e+2-n____个面。(每小题2分,共10分)()(A)(B)(C)(D),A上的二元关系不具备关系()性质(A)传递性(B)反对称性(C)对称性(D),结点总度数与边数的关系是()(A)(B)(C)(D),则图D的边数为()(A)(B)(C)(D),当且仅当()G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数(C)G连通且所有结点的度数都是偶数(D)G连通且G的所有结点度数都是奇数。(共43分)。(6分)解:主合取方式:p∧q∨r⇔(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨r)=∏:p∧q∨r⇔(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)∨(p∧¬q∧r)=∑,求的关系矩阵,并画出R,的关系图。(10分)3无向图G有12条边,G中有6个3度结点,其余结点的度数均小于3,问G中至少有多少个结点?(10分)解:∵G(V,E),|E|=V,d(Vi)<3,设至少有x个节点,由握手定理得:2×12=∑d(Vi)<6×3+(x-6)×32<(x-6)=>x>8故G中至少有9个节点。4求下面两个图的最小生成树。(12分)?说明理由。(5分)解:(Z,≤)是格,理由如下:对于任意a∈Z,a≤a成立,满足自反性;对于任意a∈Z,b∈Z,若a≤b且b≤a,则a=b,满足反对称性;对于任意a,b,c∈Z,若a≤b,b≤c,则a≤c,满足传递性;而对于任意a,b∈Z,a≤b,b为最小上界,a为最大下界,故(Z,≤)是格。(注:什么是格?)(共37分)。(10分)证明:编号公式依据(1) (¬B∨C)∧¬C 前提(2) ¬B∨C,¬C (1)(3) ¬B (2)(4) A→B (3)(5) ¬A (3)(4)(6) ¬(¬A∧D) 前提(7) A∨¬D (6)(8) ¬D (5)(6)