第一篇：離散數(shù)學(xué)練習(xí)題及答案
離散數(shù)學(xué)試題
一、單項選擇題
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。
1.設(shè)P：天下大雨,Q：他在室內(nèi)運動,命題“如果天下大雨，他就在室內(nèi)運動”可符合化為．（B）A.P∧Q C.Q→P
B.P→Q D.P∨Q
2.設(shè)G=(V , E)為任意一圖（無向或有向的），頂點個數(shù)為n，邊的條數(shù)為m，則各頂點的度數(shù)之和等于（D）。
A.nB.mC.2nD.2m
3.下列命題為假命題的是（A）．
A.如果2是偶數(shù)，那么一個公式的析取范式惟一 B.如果2是偶數(shù)，那么一個公式的析取范式不惟一 C.如果2是奇數(shù)，那么一個公式的析取范式惟一 D.如果2是奇數(shù)，那么一個公式的析取范式不惟一
4.謂詞公式?x(P(x)∨?yR(y))→Q(x)中變元x是（D）A.自由變元
C.既不是自由變元也不是約束變元
B.約束變元
D.既是自由變元也是約束變元
5.若個體域為整數(shù)域，下列公式中值為真的是（A）A.?x?y(x+y=0)C.?x?y(x+y=0)
6.下列命題中不正確的是（D）．A.x∈{x}-{{x}}
C.A={x}∪x,則x∈A且x?A
B.{x}?{x}-{{x}}D.A-B=??A=B B.?y?x(x+y=0)D.??x?y(x+y=0)
7.設(shè)P={x|(x+1)2≤4}，Q={x|x2+16≥5x},則下列選項正確的是（C）A.P?Q C.Q?P
8.下列表達式中不成立的是（A）．A.A∪(B?C)=(A∪B)?(A∪C)C.(A?B)×C=(A×C)?(B×C)
9.半群、群及獨異點的關(guān)系是（A）A.{群}?{獨異點}?{半群}
B.{獨異點}?{半群}?{群} B.A∩(B?C)=(A∩B)?(A∩C)D.(A-B)×C=(A×C)-(B×C)B.P?Q D.Q=P
C.{獨異點}?{群}?{半群} D.{半群}?{群}?{獨異點}
10.下列集合對所給的二元運算封閉的是（C）A.正整數(shù)集上的減法運算
B.在正實數(shù)的集R+上規(guī)定?為a?b=ab-a-b
+
?a,b∈R
C.正整數(shù)集Z+上的二元運算?為x?y=min(x,y)?x,y∈Z+ D.全體n×n實可逆矩陣集合Rn
×n
上的矩陣加法
11.設(shè)集合A={1，2，3}，下列關(guān)系R中不是等價關(guān)系的是（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.下列函數(shù)中為雙射的是（D）A.f：Z→Z,f(j)=j(mod)3C.f：Z→N,f(j)=|2j|+
1?1,j是奇數(shù)
B.f：N→N,f(j)=?
0,j是偶數(shù)?
D.f：R→R,f(r)=2r-1
513.設(shè)集合A={a,b, c}上的關(guān)系如下，具有傳遞性的是（D）A.R={
B.R={
14.設(shè)有限集合A的元素個數(shù)為n個，則A上共有（C）個不同的二元關(guān)系。
A． nB.C.D.以上都不對
15.設(shè)D的結(jié)點數(shù)大于1，D=
C.D中有通過每個結(jié)點至少一次的通路
B.D中至少有一條回路
D.D中有通過每個結(jié)點至少一次的回路
15-1.下列公式中，（C）是含有3個命題變項p,q,r的極小項。
A.p?qB.?(p?q?r)C.?p??q??rD.p?q ? r
二、填空題
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.設(shè)A={1,2,3}，B={3,4,5}，則A?A=___________，A?B=___________。
17.設(shè)A={1,2,3,4,5}，R?A×A，R={<1,2>，<3,4>,<2,2>}，則R的自反閉包r(R)=__________。
對稱閉包t(R)=__________。
18.設(shè)P、Q為兩個命題，德摩根律可表示為_____________，吸收律可表示為____________。
19.對于公式?x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,當個體域為{1,2}時，其真值為
_____________ ,當個體域為{0,1,2}時，其真值為_____________。
__, 20.設(shè)f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,則復(fù)合函數(shù)(f?g)(x)?__________
(g?f)(x)?__________________。（此題兩個答案顛倒一下）
22.無向圖G=
Δ(G)=_____________，G的最小度δ(G)=_____________。?0
?
123.設(shè)圖G
?1??1
10100100
1?1??，則deg-(v1)=_ ________, 0??0?
deg+(v4)=____________。
25.給定集合A={1,2,3,4,5}，在集合A上定義兩種關(guān)系：R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>}，則R?S?__________答案：
三、計算題
26.設(shè)A={a,b,c,d}，A上的等價關(guān)系R={
_____，S?R?_______________。
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.設(shè)A={a, b, c, d, e}，R為A上的關(guān)系，R={
解：
四、證明題
32.設(shè)R是A上的自反和傳遞關(guān)系，如下定義A上的關(guān)系T，使得?x, y∈A，
第二篇：離散數(shù)學(xué)練習(xí)題1
1、下列句子是簡單命題的是（）
A)3是素數(shù)。B)2x+3<
5C)張三跟李四是同學(xué)嗎？D)我在說謊。
2、下列公式不是永真式的是（）．．
A)((p∧q))→p)∨rB)p→(p∨q∨r)
C)┓(q→r)∧rD)(p→q)→(┓q→┓p)
3、設(shè)命題公式G<=>┓(p→q)，H<=>p→(q →┓p)，則G與H的關(guān)系是()。
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整除的數(shù)有（）個。
13、下列運算在指定集合上不符合交換律的是（）。
A)復(fù)數(shù)C集合上的普通加法B)n階實矩陣上的乘法 C)集合S的冪集上的∪D)集合S的冪集上的?
14、下列集合對所給的二元運算封閉的是（）
A)正實數(shù)集合R+和。運算，其中。運算定義如下：?a,b∈R+，a。b=ab-a-b B)n∈Z+，nZ={nZ|z∈Z}，nZ關(guān)于普通的加法運算 C)S={2x-1|x∈Z+}關(guān)于普通的加法運算
D)S={x|x=2n, n∈Z+}，S關(guān)于普通的加法運算
15、設(shè)V=
A)半群、獨異點、群B)半群、獨異點C)半群D)二元運算
上有○
A)138B)120C)68D)1246、設(shè)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、設(shè)A={1,2,3,4}，R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 是A上的關(guān)系，則R的性質(zhì)是（）
A)既是對稱的也是反對稱的 B)既不是對稱的也不是反對稱的 C)是對稱的但不是反對稱的D)不是對稱的但是反對稱的8、設(shè)R是A上的關(guān)系，則R在A上是傳遞的當且僅當（）
則這4個運算中滿足冪等律的是（）
17、在上述四個運算中有單位元的是（）
18、在上述四個運算中有零元的是（）
19、與命題公式P?（Q?R）等值的公式是()
A)(P?Q)?RB)(P?Q)?RC)(P?Q)?RD)P?(Q?R)
20、下列集合都是N的子集，能夠構(gòu)成代數(shù)系統(tǒng)V=
A)｛x| x∈N∧x與5互為素數(shù)｝B)｛x| x∈N∧x是30的因子｝ C){x| x∈N∧x是30的倍數(shù)}D){x|x=2k+1, k∈N }
二、填空題(1分/空，共20分。請將正確答案填在相應(yīng)的橫線上。)
1、公式┓(p∨q)→p的成假賦值為00__,公式┓(q→p)∧p的成真賦值為。
2、設(shè)Ａ，Ｂ為任意命題公式，Ｃ為重言式，若Ａ∧Ｃ<=>Ｂ∧Ｃ，那么Ａ<->Ｂ是重言式（重言式、矛盾式或可滿足式）。
3、f：N->N×N，f(x)=
其中，x=y(mod 3)叫做x與y模3相等，即x除以3的余數(shù)與y除以3的余數(shù)相等。則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結(jié)果為（）
A)ΦB){Φ} C){Φ, {Φ}}D)錯誤運算
11、函數(shù)f:R→R,f(x)= x2-2x+1,則f(x)是（）函數(shù)。
A)單射B)滿射C)雙射D)不是單射，也不是滿射
12、設(shè)X={a,b,c,d},Y={1,2,3}，f={
A)f是從X到Y(jié)的二元關(guān)系，但不是從X到Y(jié)的函數(shù) B)f是從X到Y(jié)的函數(shù)，但不是滿射的，也不是單射的 C)f是從X到Y(jié)的滿射，但不是單射 D)f是從X到Y(jié)的雙射
雙射）函數(shù)，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}的所有二元關(guān)系。
7、設(shè)A為集合且∣A∣=n，則A共有nP(A)有n
8、設(shè) f，g，h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 則復(fù)合函數(shù)
⑦ ?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個命題變項共可產(chǎn)生___n_____個極小項（極大項）；含n個命題變項的所有有窮多個合式公式中，與它們等值的主析取范式（主合取范式）共有___2^2___種不同的情況。
10、已知集合A={?,{?}}，則A的冪集P(A)＝_____。
n
n
n
五、設(shè)A={1,2,3,4}，在A×A上定義二元關(guān)系R，?
(1)證明R是A×A上的等價關(guān)系
(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>}}
四、符號化命題，并推理證明(給出每個符號的準確含義，及每一步推理的根據(jù))。（5分）
每個科學(xué)工作者都是刻苦鉆研的。每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。華有為是科學(xué)工作者并且是聰明的，所以華有為在他的事業(yè)中將獲得成功。
六、A= {1,2,3,4,6,8,12}，R是A上的整除關(guān)系，請作出偏序集
求出A的極大元、極小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）
解:
首先符號化：M(x)：x是科學(xué)工作者；F(x)：x是刻苦鉆研的；G(x)：x是聰明的；H(x)：x
在事業(yè)中獲得成功；a：華有為。
前提： ?x(M(x)→F(x)），?x(F(x)∧G(x)→H(x)),M(a)∧ G(a)
結(jié)論：H(a)
證明：① M(a)∧ G(a)前提引入 ② M(a)T ①化簡規(guī)則 ③ G(a)T ①化簡規(guī)則 ④ ?x(M(x)→F(x)）前提引入 ⑤ M(a)→F(a)T ④
⑥ F(a)T ② ⑤ 假言推理
解:A的極大元為8、12,極小元為1，無最大元，最小元為1。
B的上界為12，下界為1，最小上界為12，最大下界為1。
七、在自然推理系統(tǒng)P中構(gòu)造下面推理的證明。（5分）(1)前提：(p∨q)→(r∧s),(s∨t)→u
結(jié)論：p→u(2)前提：?x(F(x)→(G(a)∧ R(x)))，?x F(x).九、證明下列恒等式 A-(B∪C)=(A-B)∩(A-C)。（5分）證明：A-(B∪C)
結(jié)論： ?x(F(x)∧ R(x)).(1)證明：① p附加前提引入規(guī)則② p ∨ q①附加規(guī)則③(p ∨ q)→(r ∧ s)前提引入
④ r ∧ s②③ 假言推理⑤ s④化簡規(guī)則⑥ s ∨ t⑤附加規(guī)則⑦(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
八、設(shè)有理數(shù)集合Q上的 * 運算定義如下：?a，b∈Q, a*b=a+b-ab。請指出該運算的性質(zhì)，并求出其單位元、零元及所有可能的逆元。（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故運算滿足結(jié)合律。
(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)
十、設(shè)A,B為任意集合，證明：A?B<=>P(A)?P(B)。（5分）證明：先證明充分性（=>）
?X∈P(A)=> X?A=> X?B=> X∈P(B)再證明必要性（<=）
?x∈A=> {x}?A=> {x}∈P(A)=> {x}∈P(B)=> {x}?B=>x∈B 綜上所述，A?B<=>P(A)?P(B)
第三篇：離散數(shù)學(xué)練習(xí)題B
離散數(shù)學(xué)練習(xí)題B
一、簡要回答下列問題：
1．什么是消去環(huán)？請舉一例。
2．請給出公式R→P的真值表。
3．什么是恒真公式？舉一例。
4.什么是子句？什么是短語？
5．請給出命題?xG(x)的真值規(guī)定
6．什么是最優(yōu)樹？
7．什么是群？舉一例。
8．給出環(huán)的定義。舉一例。
9．什么是整區(qū)？舉一例。
10．什么是半序格？請舉一例。
二、對任意集合A，B，證明：
(1)A?B當且僅當?(A)? ?(B)；
(2)?(A)??(B)??(A?B)；
(3)?(A)??(B)=?(A?B)；
舉例說明：?(A)∪?(B)≠?(A∪B)
三、證明：映射的乘法滿足結(jié)合律，舉例說明：映射的乘法不滿足交換律。
四、判斷下列公式是恒真？恒假？可滿足？
a)(P?(Q?R))?(?P?(?Q??R))；
b)P?(P?(Q?P))；
c)(Q?P)?(?P?Q)；
d)(?P??Q)?(P??Q)。
五、證明：連通圖中任意兩條最長的簡單路必有公共點。
第四篇：離散數(shù)學(xué)習(xí)題及答案
離散數(shù)學(xué)考試試題（A卷及答案）
一、（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？
(1)若A去，則C和D中要去1個人；
(2)B和C不能都去；
(3)若C去，則D留下。
解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時成立。因此
(A?C?D)∧?(B∧C)∧(C??D)
?(?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分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。
解：論域：所有人的集合。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分）設(shè)A、B和C是三個集合，則A?B??(B?A)。
證明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)
???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B)
??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A))
??(B?A)。
四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且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，i?1?4232－
15>}。
五、（10分）R是非空集合A上的二元關(guān)系，若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)是對稱的。
下證對任意正整數(shù)n，R對稱。
因R對稱，則有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R對稱。若Rn對稱，則xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1對稱。因此，對任意正整數(shù)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的函數(shù)。下證f是雙射。
對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿射。
對任意的y1、y2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因為f：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。
綜上可得，f：B→A是雙射。
七、（10分）設(shè)是一個半群，如果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(luò)－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的每個面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點數(shù)n有如下關(guān)系：
m≤
rl(n－2)。l?2l證明設(shè)G有r個面，則2m＝
2)。?d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l?2(n－ii?
1（2）設(shè)平面圖G＝
證明設(shè)G＝
離散數(shù)學(xué)考試試題（B卷及答案）
一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R
證明因為S∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。
(1)?R附加前提
(2)P?RP
(3)?PT(1)(2)，I
(4)P∨QP
(5)QT(3)(4)，I
(6)Q?SP
(7)ST(5)(6)，I
(8)?R?SCP
(9)S∨RT(8)，E
二、（15分）根據(jù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。
設(shè)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名學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。
解設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則：
|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，|A?B?C|＝25－20＝5。故，不會打這三種球的共5人。
四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱為由A1、A2和
i?1
3A3產(chǎn)生的小項。試證由A1、A2和A3所產(chǎn)生的所有非空小項的集合構(gòu)成全集U的一個劃分。
證明小項共8個，設(shè)有r個非空小項s1、s2、…、sr(r≤8)。
對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，i?13即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。
i?1i?1i?1i?1rrrr
任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。綜上可知，{s1，s2，…，sr}是U的一個劃分。
五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。
證明(5)若R是傳遞的，則
反之，若R*R?R，則對任意的x、y、z∈A，如果xRz且zRy，則
六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點數(shù)、邊數(shù)和面數(shù)。證明對G的邊數(shù)m作歸納法。
當m＝0時，由于G是連通圖，所以G為平凡圖，此時n＝1，r＝1，結(jié)論自然成立。
假設(shè)對邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。
設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G?，并設(shè)其結(jié)點數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對e分為下列情況來討論：
若e為割邊，則G?有兩個連通分支G1和G2。Gi的結(jié)點數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設(shè)有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，由歸納假設(shè)有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。
由數(shù)學(xué)歸納法知，結(jié)論成立。
七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：
(1)f?g是A到C的函數(shù)；
(2)對任意的x∈A，有f?g(x)＝f(g(x))。
證明(1)對任意的x∈A，因為g：A→B是函數(shù)，則存在y∈B使
對任意的x∈A，若存在y1、y2∈C，使得
綜上可知，f?g是A到C的函數(shù)。
(2)對任意的x∈A，由g：A→B是函數(shù)，有
八、（15分）設(shè)
一個等價關(guān)系，且[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。－－－－
若
－1*c∈H，故
綜上可得，R是G中的一個等價關(guān)系。
對于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－
[a]R?aH。對任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R－
＝aH。
第五篇：離散數(shù)學(xué)函數(shù)復(fù)習(xí)題答案
第6章 函數(shù)
一、選擇題（每題3分）
1、設(shè)A?{a,b,c},B?{1,2,3}，則下列關(guān)系中能構(gòu)成A到B函數(shù)的是（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、設(shè)R、Z、N分別為實數(shù)集、整數(shù)集，自然數(shù)集，則下列關(guān)系中能構(gòu)成函數(shù)的是（B）
A、{?x,y?|(x,y?N)?(x?y?10)}B、{?x,y?|(x,y?R)?(y?x2)}
C、{?x,y?|(x,y?R)?(y2?x)}D、{?x,y?|(x,y?Z)?(x?ymod3)}
3、設(shè)Z為整數(shù)集，則二元關(guān)系f?{?a,b?a?Z?b?Z?b?2a?3}（B）
A、不能構(gòu)成Z上的函數(shù)B、能構(gòu)成Z上的函數(shù)
C、能構(gòu)成Z上的單射D、能構(gòu)成Z上的滿射
4、設(shè)f為自然數(shù)集N上的函數(shù)，且f(x)???
1?0若x為奇數(shù)若x為偶數(shù)，則f（D）
A、為單射而非滿B、為滿射而非單射C、為雙射D、既非單射又非滿射
5、設(shè)f為整數(shù)集Z上的函數(shù)，且f(x)為x除以5的余數(shù)，則f（D）
A、為單射而非滿B、為滿射而非單射C、為雙射D、既非單射又非滿射
6、設(shè)R、Z分別為實數(shù)集、整數(shù)集，則下列函數(shù)為滿射而非單射的是（C）
A、f:R?R,C、f:R?Z,A、f:R?R,C、f:R?R,f(x)?x?6B、f:R?R,f(x)?[x]D、f:R?R,2f(x)?(x?6)f(x)?x?6x 627、設(shè)R、R、Z?分別為實數(shù)集、非負實數(shù)集、正整數(shù)集，下列函數(shù)為單射而非滿射的是（B）f(x)??x?7x?1 B、f:Z??R,f(x)?lnx； f(x)?xD、f:R?R,f(x)?7x?
18、設(shè)Z、N、E分別為整數(shù)集，自然數(shù)集，偶數(shù)集，則下列函數(shù)是雙射的為（A）
A、f : Z?E , f(x)?2xB、f : Z?E , f(x)?8x
C、f: Z?Z,f(x)?8D、f : N?N?N,f(n)??n,n?1?
9、設(shè)X?3,Y?4，則從X到Y(jié)可以生成不同的單射個數(shù)為（B）．
A、12B、24C、64D、8110、設(shè)X?3,Y?2，則從X到Y(jié)可以生成不同的滿射個數(shù)為（B）．
A、6B、8C、9D、6411、設(shè)函數(shù)f:B?C，g:A?B都是單射，則f?g:A?C（A）
A、是單射B、是滿射C、是雙射D、既非單射又非滿射
12、設(shè)函數(shù)f:B?C，g:A?B都是滿射，則f?g:A?C（B）
A、是單射B、是滿射C、是雙射D、既非單射又非滿射
13、設(shè)函數(shù)f:B?C，g:A?B都是雙射，則f?g:A?C（C）
A、是單射B、是滿射C、是雙射D、既非單射又非滿射
14、設(shè)函數(shù)f:B?C，g:A?B，若f?g:A?C是單射，則（B）
A、f是單射B、g是單射C、f是滿射D、g是滿射
15、設(shè)函數(shù)f:B?C，g:A?B，若f?g:A?C是滿射，則（C）
A、f是單射B、g是單射C、f是滿射D、g是滿射
16、設(shè)函數(shù)f:B?C，g:A?B，若f?g:A?C是雙射，則（D）
A、f,g都是單射 B、f,g都是滿射 C、f是單射, g是滿射 D、f是滿射, g是單射
二、填充題（每題4分）
1、設(shè)X?m,Y?n，則從X到Y(jié)有2mn 種不同的關(guān)系，有nm 種不同的函數(shù)．
2、設(shè)X?m,Y?n，且m?n，則從X到Y(jié)有Anm 種不同的單射．
3、在一個有n個元素的集合上，可以有2不同的雙射．
?1，若x為奇數(shù)
?
4、設(shè)f為自然數(shù)集N上的函數(shù)，且f(x)??x
?若x為偶數(shù)?2，n
種不同的關(guān)系，有nn 種不同的函數(shù)，有n!種,則f(0)?0，f[{0}]?{0}，f[{1,2,3}]?{1}，f[{0,2,4,6,?}]?N．
5、設(shè)f,g是自然數(shù)集N上的函數(shù),?x?N,f(x)?x?1,則f?g(x)?2x?1，g?f(x)?2(x?1)．
g(x)?2x，三、問答計算題（每題10分）
1、設(shè)A?{2，3，4}，B?{2，4，7，10,12}，從A到B的關(guān)系
R?{?a,b?a?A,b?B,且a整除b}，試給出R的關(guān)系圖和關(guān)系矩陣，并說明此
關(guān)系R及其逆關(guān)系R?1是否為函數(shù)？為什么？
解：R?{?2,2?,?2,4?,?2,10?,?2,12?,?3,12?,?4,4?,?4,12?}，則R的關(guān)系圖為：
R的關(guān)系矩陣為MR
?
1??0???0
000
1?
?1 ?1??
關(guān)系R不是A到B的函數(shù)，因為元素2，4的象不唯一
逆關(guān)系R?1也不是B到A的函數(shù) 因為元素7的象不存在．
2、設(shè)Z為整數(shù)集，函數(shù)f：Z?Z?Z，且f(x,y)?x?y，問f是單射還是滿射？ 為什么？并求f(x,x),f(x,?x)．
解：?x?Z, ??0,x??Z?Z，總有f(0,x)?x，則f是滿射；
對于?1,2?,?2,1??Z?Z,，有f(1,2)?3?f(2,1)，而?1,2???2,1?，則f非單射；
f(x,x)?2x,f(x,?x)?0．
3、設(shè)A?{1,2}，A上所有函數(shù)的集合記為AA, “?”是函數(shù)的復(fù)合運算，試給出AA上運算“?”的運算表，并指出AA中是否有幺元，哪些元素有逆元？ 解：因為A?2，所以A上共有22?4個不同函數(shù)，令A(yù)
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、設(shè)R為實數(shù)集，函數(shù)f：R?R?R?R，且f(?x,y?)??x?y,x?y?，問f是雙射嗎？為什么？并求其逆函數(shù)f
?
1(?x,y?)及f?f(?x,y?)．
解： ??x1,y1?,?x2,y2??R?R，若f(?x1,y1?)?f(?x2,y2?)，有?x1?y1,x1?y1???x2?y2,x2?y2?，則?x1,y1???x2,y2?，故f是單射；
2且f(?x,y?)??x?y,x?y???u,v?，則f是滿射，故為雙射； x?yx?y,? ； 22
f?f(?x,y?)?f(?x?y,x?y?)?f(?2x,2y?)． f
?1
??u,v??R?R，令x?
u?v，y?
u?v，則?x,y??R?R，(?x,y?)??
四、證明題（每題10分）
1、設(shè)函數(shù)f：A?B，g：B?C，g和f的復(fù)合函數(shù)g?f：A?C，試證明：如果g?f是雙射，那么f是單射，g是滿射． 證明：?x1,x2?A且f(x1)?f(x2)?B，則g?f(x1)?g[f(x1)]?g[f(x2)]?g?f(x2)，因g?f是單射，有x1?x2，故f是單射；
?c?C，因g?f是滿射，?a?A，使c?g?fa()?g[fa()]，而f(a)?B，故g是滿射．
注：如果g?f是單射，那么f是單射；如果g?f是滿射，那么g是滿射．
2、設(shè)f是A上的滿射，且f?f?f，證明：f?IA．
證明：因f是滿射，則對?a?A，存在a1?A，使得f(a1)?a，則f?f(a1)?f[f(a1)]?f(a)，由 f?f?f，知a1?a，于是f(a)?a，由a的任意性知f?IA．
3、設(shè)函數(shù)f：A?B，g：B?A，證明：若f證明： 因f
?
1?1
?g,f?g
?1，則g?f?IA,f?g?IB．
?g,則?y?B,g(y)?f
?1
(y)?x?A，有g(shù)(y)?x,f(x)?y，于是，對?y?B，有f?g(y)?f[g(y)]?f(x)?y?IB(y)，知f?g?IB；
?1
又f?g?1，則對?x?A,f(x)?g(x)?y，有f(x)?y,g(y)?x，于是，對?x?A，有g(shù)?f(x)?g[f(x)]?g(y)?x?IA(x)，知g?f?IA．
4、設(shè)函數(shù)f：A?B，g：B?A，證明：若g?f?IA,f?g?IB，則f
?
1?g,f?g
?1
．
證明：因恒等函數(shù)IA是雙射，則g?f是A上的雙射，有f是單射，g是滿射； 同樣，恒等函數(shù)IB是雙射，則g?f是B上的雙射，有f是滿射，g是單射； 所以，f和g都是雙射函數(shù)，其反函數(shù)都存在，故有f注：設(shè)函數(shù)f：A?B，g：B?A，證明： f
?1
?1
?g,f?g
?1
?1
．
?g,f?g
? g?f?IA,f?g?IB．
5、設(shè)函數(shù)f：A?B，g：B??(A)，對于b?B，g(b)?{xx?A?f(x)?b}，?(A)為A的冪集，證明：如果f是A到B的滿射，則g是B到?(A)的單射．
證明：?x1?x2?B,因f是滿射，?y1,y2?A,使f(y1)?x1?x2?f(y2),則y1?y2； 又由g的定義知，y1?g(x1),y2?g(x2)，故有g(shù)(x1)?g(x2)，則g是B到?(A)的單射．
點擊咨詢 