第一篇:离散数学练习题及答案
离散数学试题
一、单项选择题
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.设P:天下大雨,Q:他在室内运动,命题“如果天下大雨,他就在室内运动”可符合化为.(B)A.P∧Q C.Q→P
B.P→Q D.P∨Q
2.设G=(V , E)为任意一图(无向或有向的),顶点个数为n,边的条数为m,则各顶点的度数之和等于(D)。
A.nB.mC.2nD.2m
3.下列命题为假命题的是(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且xA
B.{x}{x}-{{x}}D.A-B=A=B B.yx(x+y=0)D.xy(x+y=0)
7.设P={x|(x+1)2≤4},Q={x|x2+16≥5x},则下列选项正确的是(C)A.PQ C.QP
8.下列表达式中不成立的是(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.PQ D.Q=P
C.{独异点}{群}{半群} D.{半群}{群}{独异点}
10.下列集合对所给的二元运算封闭的是(C)A.正整数集上的减法运算
B.在正实数的集R+上规定为ab=ab-a-b
+
a,b∈R
C.正整数集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-1
513.设集合A={a,b, c}上的关系如下,具有传递性的是(D)A.R={,
14.设有限集合A的元素个数为n个,则A上共有(C)个不同的二元关系。
A. nB.C.D.以上都不对
15.设D的结点数大于1,D=
C.D中有通过每个结点至少一次的通路
B.D中至少有一条回路
D.D中有通过每个结点至少一次的回路
15-1.下列公式中,(C)是含有3个命题变项p,q,r的极小项。
A.pqB.(pqr)C.pqrD.pq r
二、填空题
请在每小题的空格中填上正确答案。错填、不填均无分。
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)=_____________。0
123.设图G
11
10100100
11,则deg-(v1)=_ ________, 00
deg+(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={,,
_____,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∨m
129.设A={a, b, c, d, e},R为A上的关系,R={,,, , ,
解:
四、证明题
32.设R是A上的自反和传递关系,如下定义A上的关系T,使得x, y∈A,
第二篇:离散数学练习题1
1、下列句子是简单命题的是()
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-b B)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)半群、独异点C)半群D)二元运算
上有○
A)138B)120C)68D)1246、设A, C, B, D为任意集合,以下命题一定为真的是()
A)A∪B= A∪C =>B=C B)A×C= A×B =>B= C
C)A∪(B×C)=(A∪B)×(A∪C)D)存在集合A,使得A A ×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、设A,B为任意命题公式,C为重言式,若A∧C<=>B∧C,那么A<->B是重言式(重言式、矛盾式或可满足式)。
3、f:N->N×N,f(x)=
其中,x=y(mod 3)叫做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)有n
8、设 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)=_____。
n
n
n
五、设A={1,2,3,4},在A×A上定义二元关系R,,
(1)证明R是A×A上的等价关系
(2)确定由R引起的对A×A的划分。(5分)
三、利用公式的主合取范式判断下列公式是否等值。(5分)
p→(q→r)与(p∧q)∨r p→(q→r)
<=>p∨(q∨r)<=>p∨q∨r <=>M6
(p∧q)∨r
<=>(p∨q)∨r <=>p∨q)∨r <=>M6
(1)证明:
=> x+v+u+n=y+u+v+m => x+n=y+m =>
解:{{<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))),x F(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)证明:① x F(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)
第三篇:离散数学练习题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)。
五、证明:连通图中任意两条最长的简单路必有公共点。
第四篇:离散数学习题及答案
离散数学考试试题(A卷及答案)
一、(10分)某项工作需要派A、B、C和D 4个人中的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>}=R
t(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-ii
1(2)设平面图G=
证明设G=
离散数学考试试题(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和
i1
3A3产生的小项。试证由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*RR,则对任意的x、y、z∈A,如果xRz且zRy,则
六、(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使
对任意的x∈A,若存在y1、y2∈C,使得
综上可知,fg是A到C的函数。
(2)对任意的x∈A,由g:A→B是函数,有
八、(15分)设
一个等价关系,且[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)x6x 627、设R、R、Z分别为实数集、非负实数集、正整数集,下列函数为单射而非满射的是(B)f(x)x7x1 B、f:ZR,f(x)lnx; f(x)xD、f:RR,f(x)7x
18、设Z、N、E分别为整数集,自然数集,偶数集,则下列函数是双射的为(A)
A、f : ZE , f(x)2xB、f : ZE , f(x)8x
C、f: ZZ,f(x)8D、f : NNN,f(n)n,n1
9、设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,3,12,4,4,4,12},则R的关系图为:
R的关系矩阵为MR
100
000
1
1 1
关系R不是A到B的函数,因为元素2,4的象不唯一
逆关系R1也不是B到A的函数 因为元素7的象不存在.
2、设Z为整数集,函数f:ZZZ,且f(x,y)xy,问f是单射还是满射? 为什么?并求f(x,x),f(x,x).
解:xZ, 0,xZZ,总有f(0,x)x,则f是满射;
对于1,2,2,1ZZ,,有f(1,2)3f(2,1),而1,22,1,则f非单射;
f(x,x)2x,f(x,x)0.
3、设A{1,2},A上所有函数的集合记为AA, “”是函数的复合运算,试给出AA上运算“”的运算表,并指出AA中是否有幺元,哪些元素有逆元? 解:因为A2,所以A上共有224个不同函数,令A
f
1(1)1,f(2)2;
A
{f1,f2,f3,f4},其中:
f(1)1,f(2)1;f(1)2,f(2)2;f(1)2,f4(2)1
A
f1为A中的幺元,f1和f4有逆元.
4、设R为实数集,函数f:RRRR,且f(x,y)xy,xy,问f是双射吗?为什么?并求其逆函数f
1(x,y)及ff(x,y).
解: x1,y1,x2,y2RR,若f(x1,y1)f(x2,y2),有x1y1,x1y1x2y2,x2y2,则x1,y1x2,y2,故f是单射;
2且f(x,y)xy,xyu,v,则f是满射,故为双射; xyxy, ; 22
ff(x,y)f(xy,xy)f(2x,2y). f
1
u,vRR,令x
uv,y
uv,则x,yRR,(x,y)
四、证明题(每题10分)
1、设函数f:AB,g:BC,g和f的复合函数gf:AC,试证明:如果gf是双射,那么f是单射,g是满射. 证明:x1,x2A且f(x1)f(x2)B,则gf(x1)g[f(x1)]g[f(x2)]gf(x2),因gf是单射,有x1x2,故f是单射;
cC,因gf是满射,aA,使cgfa()g[fa()],而f(a)B,故g是满射.
注:如果gf是单射,那么f是单射;如果gf是满射,那么g是满射.
2、设f是A上的满射,且fff,证明:fIA.
证明:因f是满射,则对aA,存在a1A,使得f(a1)a,则ff(a1)f[f(a1)]f(a),由 fff,知a1a,于是f(a)a,由a的任意性知fIA.
3、设函数f:AB,g:BA,证明:若f证明: 因f
11
g,fg
1,则gfIA,fgIB.
g,则yB,g(y)f
1
(y)xA,有g(y)x,f(x)y,于是,对yB,有fg(y)f[g(y)]f(x)yIB(y),知fgIB;
1
又fg1,则对xA,f(x)g(x)y,有f(x)y,g(y)x,于是,对xA,有gf(x)g[f(x)]g(y)xIA(x),知gfIA.
4、设函数f:AB,g:BA,证明:若gfIA,fgIB,则f
1g,fg
1
.
证明:因恒等函数IA是双射,则gf是A上的双射,有f是单射,g是满射; 同样,恒等函数IB是双射,则gf是B上的双射,有f是满射,g是单射; 所以,f和g都是双射函数,其反函数都存在,故有f注:设函数f:AB,g:BA,证明: f
1
1
g,fg
1
1
.
g,fg
gfIA,fgIB.
5、设函数f:AB,g:B(A),对于bB,g(b){xxAf(x)b},(A)为A的幂集,证明:如果f是A到B的满射,则g是B到(A)的单射.
证明:x1x2B,因f是满射,y1,y2A,使f(y1)x1x2f(y2),则y1y2; 又由g的定义知,y1g(x1),y2g(x2),故有g(x1)g(x2),则g是B到(A)的单射.