离散数学试题及答案

1设集合A,B，其中A＝{1,2,3},B={1,2},则A- (A)-＝ 设有限集合A,|A|=n,则|(A×A)|= 设集合A={a,b},B={1,2},则从A到B的所有映射 ,其中双射的 设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数 6设A、B为两个集合,A={1,2,4},B={3,4},则从 ;A－B＝ 设R是集合A上的等价关系，则R所具有的关系的三个特性 , A＝{1,2,3,4}AR1{(1,4),(2,3),(3,2)},R1{(2,1),(3,2),(4,3)},则R1R2 ,R2R1 设有限集A,B，|A|=m,|B|=n,则||(AB)|= 11设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,xR},B={x|0≤x<2,xR},则A-B= ,B-A= A∩B ,设集合A＝{2,3,4,5,6}，R是A上的整除，则R以集合形式(列举法)记 设一阶逻辑公式G=xP(x)xQ(x)，则G的前束范式 设G是具有8个顶点的树，则G中增 条边才能把G变成完全图第1页共17 A＝{12,34}，AR＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)} 设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是( 设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B {2,3,4,5},则6521素6为B的65213 (C)最小上 (D)以 (C)x+5>6

4

P(a,a)

第2页共17 设A,B为集合，当 设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有 (A)对任意x，G(x)都取真值1. (C)有某些x，使G(x0)取真值1. 设G是连通平面图，有5个顶点，6个面，则G的边数是 (A)9 (B)5条(C)6 (D)11条设G是5个顶点的完全图，则从G中删去( 0110G的相邻矩阵为1111 010

10 111 1(A)4, (B)5, (C)4, (D)5,A＝{1,23,4,6,89,12}，RA＝{1,23,4}，AR＝{(x,y)|x,yAxy},第3页共17R是实数集合，,,R上的三个映射，(x)x+3,(x2x,(x)＝x/4,试求复合映射•，•,•,•，••.I是如下一个解释：D{2,abffP(2,P(2,P(3,P(3,32320011(1)P(a,f(a))∧P(bf(2)xyP(y,A＝{1,24,6,8,12}，RAAB{4,6,8,12}的上界，下界，最小上界，最大下界G(P→Q)∨(Q∧(P→R)),GRA{a,b,c,d}.RA上的二元关系Ra,bb,a),(b,cr(Rs(RG=H=RSA＝{abcd}R＝{(aa),(ac),(bc),(cS＝{(a,b),(b,c),(b,d),(d,第4页共17RSR•SR∪SR－1, (10分)ABA－(A∩B)=(A∪B)－B

2n21={(a,1),(b,1)},2={(a,2),(b,2)},3={(a,1),(b,2)},4={(a,2),(b,1)};3,12,{4},{1,2,3,4},{1,(1,0,0),(1,0,1),(1,1,{x|-1≤x<0,xR};{x|1<x<2,xR};{x|0≤x≤1,12;{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,第5页共17{(1,3),(2,2)};{(1,1),(1,2),(1, 15. 464623 1B1,3;A18,12,90+;2.R=141423(2)MR01100111(4)•＝((x))＝(x)/4＝2x/4=x/2,第6页共17(1)P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f=P(3,2)∧P(2,==xyP(y,x)=x(P(2,x)∨P(3,=(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,=485.48

==21684621(2)无最 元，最小元1，极大元8,21684621B 上界，无最小上界。下界1,2;最大下界G=======m3∨m4∨m5∨m6∨m7=(3,4,5,6,第7页共17G=====(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；

dc dc

dababc＝(3,6,H=第8页共17＝(3,6,G,HGR R00

0 0 00

1 1 01 01 (2)R•S＝{(a,b),(c,R∪S＝{(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R－1＝{(a,a),(c,a),(c,b),(d,c)},S－1•R－1＝{(b,a),(d,证明：{P→QR→SP∨R}(1)P(2)(3)P(4)(5)(6)P(7)(8)证明：(A-B)-C第9页共17 所以 (A∪B)－B===第10页共17所以：A－(A∩B（10分）A、B、CD423个ACD1BCCD(A∨(C∧D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧

∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧F∨F∨(A∧C)∨F∨F∨(C∧第11页共17解：论域：所有人的集合。Sx)x是专家；Wx)xYx)x是青年人；x(S(x)∧W(x))，xY(x x(S(x)∧Y(xxY(x Y x(S(x)∧W(x S(c)∧W( S( S(c)∧Y x(S(x)∧Y(x T(6)

解 第12页共17（10分）RARr(Rt(R)是对称x、y∈Axr(R)yr(R)＝R∪IA得，xRyxIAyRyRxyIAxyr(R)xr(R)是对称的。n，Rn对称。xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1xRn1对称。因此，对任意正整数nRn对称。证明f：A→Bf－1BAf－1是双射。x∈Ay∈Bf(x)＝yf－1(y)＝xf－1是满射。 y、y∈Bf－1(y)＝f－1(y)＝xf(x)＝y，f(x)＝yf： 证明因为<S，*>是一个半群，对任意的b∈S，由*的封闭性可知，b2＝b*b∈S，b3q≥i，有bq＝bp*bqp≥1k≥1∈S＝…＝bkp*bkpa＝bkpa∈Sa*a＝a（1）第13页共17

m≤ lrrGr2m＝dfi≥lr。由欧拉公式得，n－m＋r＝2≤ lG*＝<V*，E*G＝<V，E，FG*G，于是第14页共17一、（10分）证明(P∨Q)∧(PR)∧(QS)证明S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS 设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人 第15页共17 （10分）2514人会打篮球，12人会打排球，6人会打篮球和排球，526个会打网球的人都会打另外一种球，求不会解A、B、C35人。3（10分）A1、A2A3U的子集，则形如Ai(AiAiAi)A1A2A3A1、A2A3U的一个划分。证明小项共8rs1、s2、…、sr(r≤8)。 AiasiUsi。又显然有siUU＝si

综上可知，{s1，s2，…，sr}U（15分）RA上的二元关系，则：R是传递的R*RR证明(5)R是传递的，则<x，y>∈R*Rz(xRz∧zSy)xRc∧cSyRxRy，即有<x，y>∈RR*RR。R*RRx、y、z∈AxRzzRy，则<x，y>∈R*R，于是有<x，y>∈RxRyR是传递的。（15分）Gn－m＋r＝2，其中，n、m、rG的结点数、边证明Gmm＝0GGn＝1，r＝1，结论自然成立。mGm的情况。eGGeG，并设其结点数、边数和面数分别为n、mre分为下列情况来讨论：第16页共17－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4n－m＋r＝2。1)＋r－1＝2n－m＋r＝2。（10分）g：A→B，f：B→C(1)f∘gAC(1)x∈Ag：A→By∈B使<x，y>∈gy∈B，因f：B→Cz∈C使<y，z>∈f。根据复合关系的定义，由<x，y>∈g和<y，z>∈f∈g且<t1y1>∈ft2使得<x，t2>∈g且<t2，y2>∈fg：A→Bt1＝t2。又f：B→Cy1＝y2AC中惟一的元素。综上