离散数学练习题及答案（共五篇）

离散数学练习题及答案（共五篇）第一篇：离散数学练习题及答案离散数学试题一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就在室内运动”可符合化为．（B）A.P∧QC.Q→PB.P→QD.P∨Q2.设G=(V,E)为任意一图（无向或有向的），顶点个数为n，边的条数为m，则各顶点的度数之和等于（D）。A.nB.mC.2nD.2m3.下列命题为假命题的是（A）．A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一4.谓词公式x(P(x)∨yR(y))→Q(x)中变元x是（D）A.自由变元C.既不是自由变元也不是约束变元B.约束变元D.既是自由变元也是约束变元5.若个体域为整数域，下列公式中值为真的是（A）A.xy(x+y=0)C.xy(x+y=0)6.下列命题中不正确的是（D）．A.x∈{x}-{{x}}C.A={x}∪x,则x∈A且xAB.{x}{x}-{{x}}D.A-B=A=BB.yx(x+y=0)D.xy(x+y=0)7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C）A.PQC.QP8.下列表达式中不成立的是（A）．A.A∪(BC)=(A∪B)(A∪C)C.(AB)×C=(A×C)(B×C)9.半群、群及独异点的关系是（A）A.{群}{独异点}{半群}B.{独异点}{半群}{群}B.A∩(BC)=(A∩B)(A∩C)D.(A-B)×C=(A×C)-(B×C)B.PQD.Q=PC.{独异点}{群}{半群}D.{半群}{群}{独异点}10.下列集合对所给的二元运算封闭的是（C）A.正整数集上的减法运算B.在正实数的集R+上规定为ab=ab-a-b+a,b∈RC.正整数集Z+上的二元运算为xy=min(x,y)x,y∈Z+D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法11.设集合A={1，2，3}，下列关系R中不是等价关系的是（C）．A.R={<1,1>,<2,2>,<3,3>}B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}C.R={<1,1>,<2,2>,<3,3>,<1,2>}D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}12.下列函数中为双射的是（D）A.f：Z→Z,f(j)=j(mod)3C.f：Z→N,f(j)=|2j|+11,j是奇数B.f：N→N,f(j)=0,j是偶数D.f：R→R,f(r)=2r-1513.设集合A={a,b,c}上的关系如下，具有传递性的是（D）A.R={,,,}C.R={,,,}B.R={,}D.R={}14.设有限集合A的元素个数为n个，则A上共有（C）个不同的二元关系。A．nB.C.D.以上都不对15.设D的结点数大于1，D=是强连通图，当且仅当（D）A.D中至少有一条通路C.D中有通过每个结点至少一次的通路B.D中至少有一条回路D.D中有通过每个结点至少一次的回路15-1.下列公式中，（C）是含有3个命题变项p,q,r的极小项。A.pqB.(pqr)C.pqrD.pqr二、填空题请在每小题的空格中填上正确答案。错填、不填均无分。16.设A={1,2,3}，B={3,4,5}，则AA=___________，AB=___________。17.设A={1,2,3,4,5}，RA×A，R={<1,2>，<3,4>,<2,2>}，则R的自反闭包r(R)=__________。对称闭包t(R)=__________。18.设P、Q为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。19.对于公式x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当个体域为{1,2}时，其真值为_____________,当个体域为{0,1,2}时，其真值为_____________。__,20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数(fg)(x)__________(gf)(x)__________________。（此题两个答案颠倒一下）22.无向图G=如左所示，则G的最大度Δ(G)=_____________，G的最小度δ(G)=_____________。0123.设图G,V={v1,v2,v3,v4},若G的邻接矩阵A111010010011，则deg-(v1)=_________,00deg+(v4)=____________。25.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>}，则RS__________答案：三、计算题26.设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，画出R的关系图，并求出A中各元素的等价类。_____，SR_______________。28.求下列公式的主析取范式：P→（（Q→P）∧（P∧Q））解：原式P∨（（Q∨P）∧（P∧Q））P∨((Q∧P∧Q)∨(P∧P∧Q))P∨(0∨0)P(P∧Q)∨(P∧Q)m0∨m129.设A={a,b,c,d,e}，R为A上的关系，R={，，,,,,}∪IA，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。解：四、证明题32.设R是A上的自反和传递关系，如下定义A上的关系T，使得x,y∈A，∈T∈R∧(y,x)∈R。证明T是A上的等价关系。第二篇：离散数学练习题B离散数学练习题B一、简要回答下列问题：1．什么是消去环？请举一例。2．请给出公式R→P的真值表。3．什么是恒真公式？举一例。4.什么是子句？什么是短语？5．请给出命题xG(x)的真值规定6．什么是最优树？7．什么是群？举一例。8．给出环的定义。举一例。9．什么是整区？举一例。10．什么是半序格？请举一例。二、对任意集合A，B，证明：(1)AB当且仅当(A)(B)；(2)(A)(B)(AB)；(3)(A)(B)=(AB)；举例说明：(A)∪(B)≠(A∪B)三、证明：映射的乘法满足结合律，举例说明：映射的乘法不满足交换律。四、判断下列公式是恒真？恒假？可满足？a)(P(QR))(P(QR))；b)P(P(QP))；c)(QP)(PQ)；d)(PQ)(PQ)。五、证明：连通图中任意两条最长的简单路必有公共点。第三篇：离散数学练习题11、下列句子是简单命题的是（）A)3是素数。B)2x+3<5C)张三跟李四是同学吗？D)我在说谎。2、下列公式不是永真式的是（）．．A)((p∧q))→p)∨rB)p→(p∨q∨r)C)┓(q→r)∧rD)(p→q)→(┓q→┓p)3、设命题公式G<=>┓(p→q)，H<=>p→(q→┓p)，则G与H的关系是()。A)G<=>HB)H→GC)H=>GD)G=>H4、下列命题不为真的是（）．A)ΦΦB)Φ∈ΦC){a,b}∈{a,b,c,{a,b}}}D){a,b}{a,b,c,{a,b}}5、1到300之间（包含1和1000）不能被3、5和7整除的数有（）个。13、下列运算在指定集合上不符合交换律的是（）。A)复数C集合上的普通加法B)n阶实矩阵上的乘法C)集合S的幂集上的∪D)集合S的幂集上的14、下列集合对所给的二元运算封闭的是（）A)正实数集合R+和。运算，其中。运算定义如下：a,b∈R+，a。b=ab-a-bB)n∈Z+，nZ={nZ|z∈Z}，nZ关于普通的加法运算C)S={2x-1|x∈Z+}关于普通的加法运算D)S={x|x=2n,n∈Z+}，S关于普通的加法运算15、设V=,其中*定义如下：a，b∈Z,a*b=a+b-2,则能构成的代数系统是（）。A)半群、独异点、群B)半群、独异点C)半群D)二元运算上有○A)138B)120C)68D)1246、设A,C,B,D为任意集合，以下命题一定为真的是（）A)A∪B=A∪C=>B=CB)A×C=A×B=>B=CC)A∪(B×C)=(A∪B)×(A∪C)D)存在集合A,使得AA×A7、设A={1,2,3,4}，R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}是A上的关系，则R的性质是（）A)既是对称的也是反对称的B)既不是对称的也不是反对称的C)是对称的但不是反对称的D)不是对称的但是反对称的8、设R是A上的关系，则R在A上是传递的当且仅当（）则这4个运算中满足幂等律的是（）17、在上述四个运算中有单位元的是（）18、在上述四个运算中有零元的是（）19、与命题公式P（QR）等值的公式是()A)(PQ)RB)(PQ)RC)(PQ)RD)P(QR)20、下列集合都是N的子集，能够构成代数系统V=的子代数的是（）A)｛x|x∈N∧x与5互为素数｝B)｛x|x∈N∧x是30的因子｝C){x|x∈N∧x是30的倍数}D){x|x=2k+1,k∈N}二、填空题(1分/空，共20分。请将正确答案填在相应的横线上。)1、公式┓(p∨q)→p的成假赋值为00__,公式┓(q→p)∧p的成真赋值为。2、设Ａ，Ｂ为任意命题公式，Ｃ为重言式，若Ａ∧Ｃ<=>Ｂ∧Ｃ，那么ＡＢ是重言式（重言式、矛盾式或可满足式）。3、f：N->N×N，f(x)=,A={5},B={<2,3>,<7,8>},则f(x)是A)IARB)R=R-1C)R∩IAΦD)R。RR9、设A={1,2,3,4,5,6,7,8},R为A上的等价关系R={|x,y∈A∧x=y(mod3)}其中，x=y(mod3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。则1的等价类，即[1]，为（）A){1,4,7}B){2,5,8}C){3,6}D){1,2,3,4,5,6,7,8}10、当集合A=Φ且B≠Φ时，则BA结果为（）A)ΦB){Φ}C){Φ,{Φ}}D)错误运算11、函数f:R→R,f(x)=x2-2x+1,则f(x)是（）函数。A)单射B)满射C)双射D)不是单射，也不是满射12、设X={a,b,c,d},Y={1,2,3}，f={,,}，则以下命题正确的是()A)f是从X到Y的二元关系，但不是从X到Y的函数B)f是从X到Y的函数，但不是满射的，也不是单射的C)f是从X到Y的满射，但不是单射D)f是从X到Y的双射双射）函数，A在f下的像f(A)＝_{<5,6>}_，B在f下的完全原像f-1(B)=____。4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）__M∧_M∧_M∧_M∧_M，主析取范式为（用极小项表示）5、公式x(F(x,y)→yG(x,y,z))的前束范式为_6、列出从集合A={1,2}到B={1}的所有二元关系。7、设A为集合且∣A∣=n，则A共有nP(A)有n8、设f，g，h∈RR且f(x)=x+3,g(x)=2x+1,h(x)=x/2,则复合函数⑦x(F(x)∧G(x)→H(x))前提引入⑧F(a)∧G(a)→H(a)T⑦UI⑨F(a)∧G(a)T③⑥合取(10)H(a)T⑧⑨假言推理f。g。h(x)=__，f。g。h(x)=_____。9、含有n个命题变项的公式共有_____个不同的赋值，最多可以生成___个不同的真值表；n个命题变项共可产生___n_____个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有___2^2___种不同的情况。10、已知集合A={,{}}，则A的幂集P(A)＝_____。nnn五、设A={1,2,3,4}，在A×A上定义二元关系R，，∈A×A，R<=>u+y=x+v(1)证明R是A×A上的等价关系(2)确定由R引起的对A×A的划分。(5分)三、利用公式的主合取范式判断下列公式是否等值。（5分）p→(q→r)与(p∧q)∨rp→(q→r)<=>p∨(q∨r)<=>p∨q∨r<=>M6(p∧q)∨r<=>(p∨q)∨r<=>p∨q)∨r<=>M6(1)证明:∈A×A=>x+y=y+x=>∈R∴R是自反的∈A×A,R=>x+v=y+u=>R∴R是对称的,∈A×A,R∧R=>x+v=y+u∧u+n=v+m=>x+v+u+n=y+u+v+m=>x+n=y+m=>R∧∴R是传递的(2)解:{{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>,<4,1>},{<3,1>,<4,2>},{<2,1>,<3,2>,<4,3>}}四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（5分）每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的，所以华有为在他的事业中将获得成功。六、A={1,2,3,4,6,8,12}，R是A上的整除关系，请作出偏序集的哈斯图，给出关系矩阵，并求出A的极大元、极小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）解:首先符号化：M(x)：x是科学工作者；F(x)：x是刻苦钻研的；G(x)：x是聪明的；H(x)：x在事业中获得成功；a：华有为。前提：x(M(x)→F(x)），x(F(x)∧G(x)→H(x)),M(a)∧G(a)结论：H(a)证明：①M(a)∧G(a)前提引入②M(a)T①化简规则③G(a)T①化简规则④x(M(x)→F(x)）前提引入⑤M(a)→F(a)T④⑥F(a)T②⑤假言推理解:A的极大元为8、12,极小元为1，无最大元，最小元为1。B的上界为12，下界为1，最小上界为12，最大下界为1。七、在自然推理系统P中构造下面推理的证明。（5分）(1)前提：(p∨q)→(r∧s),(s∨t)→u结论：p→u(2)前提：x(F(x)→(G(a)∧R(x)))，xF(x).九、证明下列恒等式A-(B∪C)=(A-B)∩(A-C)。（5分）证明：A-(B∪C)结论：x(F(x)∧R(x)).(1)证明：①p附加前提引入规则②p∨q①附加规则③(p∨q)→(r∧s)前提引入④r∧s②③假言推理⑤s④化简规则⑥s∨t⑤附加规则⑦(s∨t)→u前提引入⑧u⑥⑦假言推理(2)证明：①xF(x)前提引入②F(b)①EI③x(F(x)→(G(a)∧R(x)))前提引入④F(b)→(G(a)∧R(b))③UI⑤G(a)∧R(b)②④假言推理⑥R(b)⑤化简⑦F(b)∧R(b)②⑥合取⑧x(F(x)∧R(x))⑦EG八、设有理数集合Q上的*运算定义如下：a，b∈Q,a*b=a+b-ab。请指出该运算的性质，并求出其单位元、零元及所有可能的逆元。（5分）解：(1)因为a*b=a+b-ab=b+a-ba=b*a，所以运算满足交换律。(2)因为(a*b)*c=(a+b-ab)*c=a+b-ab+c-(a+b-ab)c=a+b+c-ab-bc-ac+abca*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ab-bc-ac+abc故运算满足结合律。(3)任意x∈Q，因为x*x=x+x-xx=2x+x2≠x，故不满足幂等律(4)因为对a∈Q，有a*0=a+0-a0=a，所以0是单位元。(5)因为对a∈Q，有a*1=a+1-a=1，所以1是零元。(6)对a∈Q，令a*x=a+x-ax=0，则有x=a/(a-1)。所以当a≠1时，其逆元为a=a/(a-1)，1没有逆元。1＝A∩～(B∪C)＝A∩～B∩～C=A∩A∩～B∩～C＝(A∩～B)∩(A∩～C)=(A-B)∩(A-C)十、设A,B为任意集合，证明：AB<=>P(A)P(B)。（5分）证明：先证明充分性（=>）X∈P(A)=>XA=>XB=>X∈P(B)再证明必要性（<=）x∈A=>{x}A=>{x}∈P(A)=>{x}∈P(B)=>{x}B=>x∈B综上所述，AB<=>P(A)P(B)第四篇：离散数学习题及答案离散数学考试试题（A卷及答案）一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此(ACD)∧(B∧C)∧(CD)(A∨(C∧D)∨(C∧D))∧(B∨C)∧(C∨D)(A∨(C∧D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)F∨F∨(A∧C)∨F∨F∨(C∧D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F(A∧C)∨(B∧C∧D)∨(C∧D∧B)∨(C∧D)(A∧C)∨(B∧C∧D)∨(C∧D)T故有三种派法：B∧D，A∧C，A∧D。二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))下面给出证明：(1)xY(x)P(2)Y(c)T(1)，ES(3)x(S(x)∧W(x))P(4)S(c)∧W(c)T(3)，US(5)S(c)T(4)，I(6)S(c)∧Y(c)T(2)(5)，I(7)x(S(x)∧Y(x))T(6)，EG三、（10分）设A、B和C是三个集合，则AB(BA)。证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))(BA)。四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝Rt(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i14232－15>}。五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。下证对任意正整数n，R对称。因R对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若Rn对称，则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x，所以Rn1对称。因此，对任意正整数n，Rn对称。对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是对称的。六、（10分）若f：A→B是双射，则f：B→A是双射。证明因为f：A→B是双射，则f是B到A的函数。下证f是双射。对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。综上可得，f：B→A是双射。七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。令a＝bkp，则a∈S且a*a＝a。八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：m≤rl(n－2)。l2l证明设G有r个面，则2m＝2)。d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤l2(n－ii1（2）设平面图G＝是自对偶图，则|E|＝2(|V|－1)。证明设G＝是连通平面图G＝的对偶图，则GG，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**离散数学考试试题（B卷及答案）一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。(1)R附加前提(2)PRP(3)PT(1)(2)，I(4)P∨QP(5)QT(3)(4)，I(6)QSP(7)ST(5)(6)，I(8)RSCP(9)S∨RT(8)，E二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。(1)x(P(x)Q(x))P(2)x(P(x)∨Q(x))T(1)，E(3)x(P(x)∧Q(x))T(2)，E(4)P(a)∧Q(a)T(3)，ES(5)P(a)T(4)，I(6)Q(a)T(4)，I(7)x(P(x)(A(x)∨B(x))P(8)P(a)(A(a)∨B(a))T(7)，US(9)A(a)∨B(a)T(8)(5)，I(10)x(A(x)Q(x))P(11)A(a)Q(a)T(10)，US(12)A(a)T(11)(6)，I(13)B(a)T(12)(9)，I(14)P(a)∧B(a)T(5)(13)，I(15)x(P(x)∧B(x))T(14)，EG三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和i13A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，i13即有a∈si，于是Usi。又显然有siU，所以U＝si。i1i1i1i1rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。五、（15分）设R是A上的二元关系，则：R是传递的R*RR。证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。由数学归纳法知，结论成立。七、（10分）设函数g：A→B，f：B→C，则：(1)fg是A到C的函数；(2)对任意的x∈A，有fg(x)＝f(g(x))。证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。综上可知，fg是A到C的函数。(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，则R是G中的－一个等价关系，且[a]R＝aH。证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a1*b)*(b1*c)＝a－－－－－1*c∈H，故∈R。综上可得，R是G中的一个等价关系。对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R－＝aH。第五篇：离散数学函数复习题答案第6章函数一、选择题（每题3分）1、设A{a,b,c},B{1,2,3}，则下列关系中能构成A到B函数的是（C）A、f1{a,1,a,2,a,3}B、f2{a,1,b,1,b,2}C、f4{a,1,b,1,c,1}D、f1{a,1,a,2,b,2,c,3}2、设R、Z、N分别为实数集、整数集，自然数集，则下列关系中能构成函数的是（B）A、{x,y|(x,yN)(xy10)}B、{x,y|(x,yR)(yx2)}C、{x,y|(x,yR)(y2x)}D、{x,y|(x,yZ)(xymod3)}3、设Z为整数集，则二元关系f{a,baZbZb2a3}（B）A、不能构成Z上的函数B、能构成Z上的函数C、能构成Z上的单射D、能构成Z上的满射4、设f为自然数集N上的函数，且f(x)10若x为奇数若x为偶数，则f（D）A、为单射而非满B、为满射而非单射C、为双射D、既非单射又非满射5、设f为整数集Z上的函数，且f(x)为x除以5的余数，则f（D）A、为单射而非满B、为满射而非单射C、为双射D、既非单射又非满射6、设R、Z分别为实数集、整数集，则下列函数为满射而非单射的是（C）A、f:RR,C、f:RZ,A、f:RR,C、f:RR,f(x)x6B、f:RR,f(x)[x]D、f:RR,2f(x)(x6)f(x)x6x627、设R、R、Z分别为实数集、非负实数集、正整数集，下列函数为单射而非满射的是（B）f(x)x7x1B、f:ZR,f(x)lnx；f(x)xD、f:RR,f(x)7x18、设Z、N、E分别为整数集，自然数集，偶数集，则下列函数是双射的为（A）A、f:ZE,f(x)2xB、f:ZE,f(x)8xC、f:ZZ,f(x)8D、f:NNN,f(n)n,n19、设X3,Y4，则从X到Y可以生成不同的单射个数为（B）．A、12B、24C、64D、8110、设X3,Y2，则从X到Y可以生成不同的满射个数为（B）．A、6B、8C、9D、6411、设函数f:BC，g:AB都是单射，则fg:AC（A）A、是单射B、是满射C、是双射D、既非单射又非满射12、设函数f:BC，g:AB都是满射，则fg:AC（B）A、是单射B、是满射C、是双射D、既非单射又非满射13、设函数f:BC，g:AB都是双射，则fg:AC（C）A、是单射B、是满射C、是双射D、既非单射又非满射14、设函数f:BC，g:AB，若fg:AC是单射，则（B）A、f是单射B、g是单射C、f是满射D、g是满射15、设函数f:BC，g:AB，若fg:AC是满射，则（C）A、f是单射B、g是单射C、f是满射D、g是满射16、设函数f:BC，g:AB，若fg:AC是双射，则（D）A、f,g都是单射B、f,g都是满射C、f是单射,g是满射D、f是满射,g是单射二、填充题（每题4分）1、设Xm,Yn，则从X到Y有2mn种不同的关系，有nm种不同的函数．2、设Xm,Yn，且mn，则从X到Y有Anm种不同的单射．3、在一个有n个元素的集合上，可以有2不同的双射．1，若x为奇数4、设f为自然数集N上的函数，且f(x)x若x为偶数2，n种不同的关系，有nn种不同的函数，有n!种,则f(0)0，f[{0}]{0}，f[{1,2,3}]{1}，f[{0,2,4,6,}]N．5、设f,g是自然数集N上的函数,xN,f(x)x1,则fg(x)2x1，gf(x)2(x1)．g(x)2x，三、问答计算题（每题10分）1、设A{2，3，4}，B{2，4，7，10,12}，从A到B的关系R{a,baA,bB,且a整除b}，试给出R的关系图和关系矩阵，并说明此关系R及其逆关系R1是否为函数？为什么？解：R{2,2,2,4,2,10,2,12