广州大学离散数学期末总复习

1习题第十八周2填空P：天下雪，Q：我有时间，R：我进城，将以下语句翻译成命题公式。a)天没有下雪b)如果天不下雪且我有时间，那么我就进城。c)除非下雪，否则我不进城。d)我进城的必要条件是我有时间。e)我进城当且仅当我有时间且天不下雪。PPQRRPRQRPQ3填空无向连通图有100个结点、100条边，则图中有条回路。有n个结点，每个结点的度是4的连通图一定是(欧拉图/哈密顿图)。结点总数为11的完全二叉树共有个叶结点。由k棵树组成的森林，要添加条边，才能使G成为一棵树；1欧拉图6k-14填空数集,“*”为普通乘法，群R-{0},*的单位元是，零元是，4的逆元是。R为实数集,+为普通加法,代数系统R,+的单位元是，3的逆元是，零元(是0/不确定/不存在)。1不存在1/40-3不存在5填空已知|X|=m,|Y|=n，X到Y有个不同的关系，其中个是函数。个是入射，个是双射。若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有______个非零元素2mnnmm！Amn2(n-1)6填空子图个数：只有1个结点的子图有个；2个结点的子图有个；3个结点的子图有个；所以共有3＋6＋8＝17个子图.1787313622382333具有3个结点的完全图，有子图，个生成子图，个不同构的子图。7判断()无奇数度结点的无向图一定是欧拉图。()有割点的图一定不是哈密顿图。()(1,1,2,2,3)可构成无向简单图的结点度数序列。()笛卡尔乘积满足结合律。()若AB,BC,CA,则A=B=C。()若A,B,C为任意集合，且A∪B=A∪C,则B=C。×√××√×8判断()任何群都必有幺元和零元。()幺元是群中唯一的等幂元。()设*是自然数集合N上的二元运算，*定义为：对任意a,bN，a*b=a，则*是可结合的。()联结词满足交换律。()联结词↑是可交换的。×√√×√9单项选择设A={a,{a}},下式哪一个是错的()(A){a}∈P(A)(B){a}P(A)(C){{a}}∈P(A)(D){{a}}P(A)B下面哪个联结词运算不可交换()(A)(B)(C)∨(D)B下面哪个命题公式是重言式()(A)(PQ)(QP)(B)(PQ)P(C)(P∨Q)(PQ)(D)(P∨Q)B10单项选择设集合A={1,2,3,…,10},下面定义的哪种运算关于集合A不是封闭的()对于任意x,y∈A(A)x*y=max(x,y)(B)x*y=min(x,y)(C)x*y=GCD(x,y)(x,y最大公约数)(D)x*y=LCM(x,y)(x,y最小公倍数)D集合A={1,2,3,…,10}上的关系R={(x,y)|x+y=10且x,y∈A},则R的性质为()(A)自反的(B)对称的(C)传递的,对称的(D)反自反的,对称的B11单项选择图G＝V,E中，结点总度数与边数的关系是()(A)deg(vi)=2E(B)deg(vi)=E(C)(D)CVvEv2)deg(VvEv)deg(设G＝V,E为无向简单图，V=n，(G)为G的最大度数，则有()(A)(G)n(B)(G)n(C)(G)n(D)(G)nA简单有向图的可达性矩阵刻画下列哪种关系()(A)点与点(B)点与边(C)边与点(D)边与边A12单项选择有向图的邻接矩阵中，行元素之和是对应结点的()，列元素之和是对应结点的()(A)度数(B)出度(C)最大度数(D)入度给定无向图如下图所示，不是点割集的是()(A){b,d}(B){d}(C){e}(D){f,h}BDAbadcefgh13简答题设G(x):x是金子，F(x):x闪光，将命题“是金子都闪光,但闪光的不都是金子”翻译成谓词公式。(x)(G(x)→F(x))(y)(F(y)G(y))或(x)(G(x)→F(x))(y)(F(y)→G(y))14简答题解A＝{1,2,3,6,9,18}，整除关系：＝{1,11,2,1,3,1,6,1,9,1,18,2,2,2,6,2,18,3,3,3,6,3,9,3,18,6,6,6,18,9,9,9,18,18,18}•A,的关系图和哈斯图如下：•设集合A＝{18的正整数因子}，为整除关系，画出偏序集A，∝的哈斯图。15简答题一个群能否同构于自己的一个真子群？解：有可能。例如，I、E分别表示整数集和偶数集，I;+和E;+都是群，且E;+是I;+的真子群，设f:I→E，f(x)=2x，则f是I;+到E;+的同构映射，即I;+E;+。16简答题•设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图。设图G有x个结点，有握手定理21+22+34+3(x223)＝122x＝917简答题•在有21条边的无向图中，有多少个结点，其中3个4度结点，其余均为3度结点。解：13个结点。设有x个3度结点，边数m=21,有42＝3×4＋3x。18证明题如果他是计算机系本科生或者是计算机系研究生，那么他一定学过Java语言而且学过C++语言。只要他学过Java语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理有效。解答：令p：他是计算机系本科生,q：他是计算机系研究生,r：他学过Java语言,s:他学过C++语言,t:他会编程序前提：(p∨q)→(r∧s),(r∨s)→t结论：p→t19证明题•前提：(p∨q)→(r∧s),(r∨s)→t结论：p→t•①pP(附加前提)•②p∨qT①I•③(p∨q)→(r∧s)P(前提引入)•④r∧sT②③I•⑤rT④I•⑥r∨sT⑤I•⑦(r∨s)→tP(前提引入)•⑧tT⑤⑥I20证明题设图G＝V,E,是简单图，则)(2)(GnmG证明：对G中任何结点v，由最大度和最小度的定义知图有n个结点，又由握手定理，，得到)()deg()(GvGmvnii2)deg(1)()deg()(1GnvGnnii)(2)()(2)(GnmGGnmGn。分别是最大度和最小度，)()(GG21证明题•试证A－(B－C)＝(A－B)(AC)•A－(B－C)＝=(A－B)(AC))~(~CBA)()~()~~(~CABACBA)()()()()()~()(CABAxCxAxBxAxCxBxAxCBxAxCBAx或定义法：22证明题设A;*和B;△是两个群，在AB上定义运算：a1,b1★a2,b2=a1*a2,b1△b2，证明：AB;★是一个群。解(1)A≠φ,B≠φ,因此AB≠φ,且★在AB上封闭；(2)因*和△是可结合的，故★也是可结合的(3)设e1和e2分别是A;*和B;△的幺元，则可以证明e1,e2是AB;★的幺元；(4)aA,bB，逆元分别为a-1、b-1，则a-1,b-1AB，且a,b★a-1,b-1=a-1,b-1★a,b=e1,e2，从而a,b-1=a-1,b-1。23A,B,C,D四人参加考试后，有人问它们，谁的成绩最好。A说“不是我”，B说“是D”，C说“是B”，D说“不是我”。四人的回答只有一人符合实际，问是谁的成绩最好？只有一人成绩最好的是谁？解：设A:A成绩最好,B:B成绩最好,C:C成绩最好,D:D成绩最好。四人的回答只有一人符合实际(讲真话),故1(A∧D∧B∧D)∨(A∧D∧B∧D)∨(A∧D∧B∧D)∨(A∧D∧B∧D)补充题241(A∧D∧B∧D)∨(A∧D∧B∧D)∨(A∧D∧B∧D)∨(A∧D∧B∧D)(A∧B∧(C∨C)∧D)∨(A∧B∧(C∨C)∧D)(A∧B∧C∧D)∨(A∧B∧C∧D)∨(A∧B∧C∧D)∨(A∧B∧C∧D)所以,(1)A,C,D并列成绩最好；(2)A,D并列成绩最好；(3)A,C并列成绩最好；(4)A成绩最好；只有一人成绩最好的是A。