第一篇：二下數學期末考試試卷
離散數學 期末考試試卷答案
離散數學試題(B卷答案1)
一、證明題(10分)
1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 證明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置換)?R 2) ?x (A(x)?B(x))? ?xA(x)??xB(x) 證明 ：?x(A(x)?B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)??xB(x)
二、求命題公式(P∨(Q∧R))?(P∧Q∧R)的主析取范式和主合取范式(10分)。
證明：(P∨(Q∧R))?(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6
三、推理證明題(10分)
1) C∨D， (C∨D)? ?E， ?E?(A∧?B)， (A∧?B)?(R∨S)?R∨S 證明：(1) (C∨D)??E (2) ?E?(A∧?B)
P P
P (3) (C∨D)?(A∧?B) T(1)(2)，I (4) (A∧?B)?(R∨S) (5) (C∨D)?(R∨S) (6) C∨D
T(3)(4)， I P (7) R∨S T(5)，I 2) ?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 證明(1)?xP(x) P
(2)P(a) T(1)，ES (3)?x(P(x)?Q(y)∧R(x)) P (4)P(a)?Q(y)∧R(a) T(3)，US (5)Q(y)∧R(a) T(2)(4)，I (6)Q(y) T(5)，I (7)R(a) T(5)，I (8)P(a)∧R(a) T(2)(7)，I (9)?x(P(x)∧R(x)) T(8)，EG (10)Q(y)∧?x(P(x)∧R(x)) T(6)(9)，I
四、某班有25名學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網球，還有2人會打這三種球。而6個會打網球的人都會打另外一種球，求不會打這三種球的人數(10分)。
解：A，B，C分別表示會打排球、網球和籃球的學生集合。則|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。
先求|A∩B|。
∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2，∴|(A∩B)|=3。
于是|A∪B∪C|=12+6+14-6-5-3+2=20。不會打這三種球的人數25-20=5。
五、已知A、B、C是三個集合，證明A-(B∪C)=(A-B)∩(A-C) (10分)。
證明：∵x? A-(B∪C)? x? A∧x?(B∪C)
? x? A∧(x?B∧x?C)
?(x? A∧x?B)∧(x? A∧x?C) ? x?(A-B)∧x?(A-C) ? x?(A-B)∩(A-C)
∴A-(B∪C)=(A-B)∩(A-C)
六、已知R、S是N上的關系，其定義如下：R={| x，y?N∧y=x}，S={| x，y?N∧y=x+1}。求R、R*S、S*R、R{1，2}、S[{1，2}](10分)。
解：R={| x，y?N∧y=x} R*S={| x，y?N∧y=x+1} S*R={| x，y?N∧y=(x+1)}，R{1，2}={<1，1>，<2，4>}，S[{1，2}]={1，4}。
七、設R={，，}，求r(R)、s(R)和t(R) (15分)。
解：r(R)={，，，，，}
22-
12-1
2s(R)={，，，，，} R= R={，，} R={，，} R={，，} t(R)={，，，，，，，，，}
八、證明整數集I上的模m同余關系R={|x?y(mod m)}是等價關系。其中，x?y(mod m)的含義是x-y可以被m整除(15分)。
證明：1)?x∈I，因為(x-x)/m=0，所以x?x(mod m)，即xRx。
2)?x，y∈I，若xRy，則x?y(mod m)，即(x-y)/m=k∈I，所以(y - x)/m=-k∈I，所以y?x(mod m)，即yRx。
3)?x，y，z∈I，若xRy，yRz，則(x-y)/m=u∈I，(y-z)/m=v∈I，于是(x-z)/m=(x-y+y-z)/m=u+v ∈I，因此xRz。
九、若f:A→B和g:B→C是雙射，則(gf)=fg(10分)。
-
1-1-14325證明：因為f、g是雙射，所以gf：A→C是雙射，所以gf有逆函數(gf)：C→A。同理可推fg：C→A是雙射。
因為∈fg?存在z(∈g?∈f)?存在z(∈f?∈g)?∈gf?∈(gf)，所以(gf)=fg。
-
1-1
-1-1-1-1
-1
-1-1-1
-1離散數學試題(B卷答案2)
一、證明題(10分)
1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T 證明: 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等冪律) ?T (代入) 2) ?x?y(P(x)?Q(y))? ?(?xP(x)??yQ(y)) 證明：?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y)) ??x(?P(x)∨?yQ(y)) ??x?P(x)∨?yQ(y) ???xP(x)∨?yQ(y) ?(?xP(x)??yQ(y))
二、求命題公式(?P?Q)?(P∨?Q) 的主析取范式和主合取范式(10分)
解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q) ??(P∨Q)∨(P∨?Q) ?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q) ?(P∨?Q) ?M1 ?m0∨m2∨m3
三、推理證明題(10分)
1)(P?(Q?S))∧(?R∨P)∧Q?R?S 證明：(1)R (2)?R∨P (3)P (4)P?(Q?S) (5)Q?S (6)Q (7)S (8)R?S 2) ?x(A(x)??yB(y))，?x(B(x)??yC(y))?xA(x)??yC(y)。
證明：(1)?x(A(x)??yB(y)) P (2)A(a)??yB(y) T(1)，ES (3)?x(B(x)??yC(y)) P (4)?x(B(x)?C(c)) T(3)，ES (5)B(b)?C(c) T(4)，US (6)A(a)?B(b) T(2)，US (7)A(a)?C(c) T(5)(6)，I (8)?xA(x)?C(c) T(7)，UG (9)?xA(x)??yC(y) T(8)，EG
四、只要今天天氣不好，就一定有考生不能提前進入考場，當且僅當所有考生提前進入考場，考試才能準時進行。所以，如果考試準時進行，那么天氣就好(15分)。
解 設P：今天天氣好，Q：考試準時進行，A(e)：e提前進入考場，個體域：考生
的集合，則命題可符號化為：?P??x?A(x)，?xA(x)?QQ?P。
(1)?P??x?A(x) P (2)?P???xA(x) T(1)，E (3)?xA(x)?P T(2)，E (4)?xA(x)?Q P (5)(?xA(x)?Q)∧(Q??xA(x)) T(4)，E (6)Q??xA(x) T(5)，I (7)Q?P T(6)(3)，I
五、已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C) (10分)
證明：∵x? A∩(B∪C)? x? A∧x?(B∪C)? x? A∧(x?B∨x?C)?( x? A∧x?B)∨(x? A∧x?C)? x?(A∩B)∨x? A∩C? x?(A∩B)∪(A∩C)∴A∩(B∪C)=(A∩B)∪(A∩C)
六、A={ x1,x2,x3 }，B={ y1,y2}，R={,,}，求其關系矩陣及關系圖(10分)。
七、設R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它們及R的關系圖(15分)。
解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>, <3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R=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>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}
八、設R1是A上的等價關系，R2是B上的等價關系，A≠?且B≠?。關系R滿足：<，>∈R?∈R1且∈R2，證明R是A×B上的等價關系(10分)。
證明 對任意的∈A×B，由R1是A上的等價關系可得∈R1，由R2是B上的等價關系可得∈R2。再由R的定義，有<，>∈R，所以R是自反的。
對任意的、∈A×B，若R，則∈R1且∈R2。由R1對稱得∈R1，由R2對稱得∈R2。再由R的定義，有<，> 432
5∈R，即R，所以R是對稱的。
對任意的、、∈A×B，若R且R，則∈R1且∈R2，∈R1且∈R2。由∈R
1、∈R1及R1的傳遞性得∈R1，由∈R
2、∈R2及R2的傳遞性得∈R1。再由R的定義，有<，>∈R，即R，所以R是傳遞的。
綜上可得，R是A×B上的等價關系。
九、設f：A?B，g：B?C，h：C?A，證明：如果h?g?f=IA，f?h?g=IB，g?f?h=IC，則f、g、h均為雙射，并求出f、g和h(10分)。
解 因IA恒等函數，由h?g?f=IA可得f是單射，h是滿射;因IB恒等函數，由f?h?g=IB可得g是單射，f是滿射;因IC恒等函數，由g?f?h=IC可得h是單射，g是滿射。從而f、g、h均為雙射。
由h?g?f=IA，得f=h?g;由f?h?g=IB，得g=f?h;由g?f?h=IC，得h=g?f。 -
1-1
-1-1-1
-1離散數學試題(B卷答案3)
一、(10分)判斷下列公式的類型(永真式、永假式、可滿足式)?(寫過程) 1)P?(P∨Q∨R) 2)?((Q?P)∨?P)∧(P∨R) 3)((?P∨Q)?R)?((P∧Q)∨R) 解：1)重言式;2)矛盾式;3)可滿足式
二、(10分)求命題公式(P∨(Q∧R))?(P∨Q∨R)的主析取范式，并求成真賦值。
解：(P∨(Q∧R))?(P∨Q∨R)??(P∨(Q∧R))∨P∨Q∨R ??P∧(?Q∨?R)∨P∨Q∨R ?(?P∧?Q)∨(?P∧?R)∨(P∨Q)∨R ?(?(P∨Q)∨(P∨Q))∨(?P∧?R)∨R ?1∨((?P∧?R)∨R)?1 ?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 該式為重言式，全部賦值都是成真賦值。
三、(10分)證明 ((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(A∧(P?Q))?C 證明：((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(?(P∧Q∧A)∨C)∧(?A∨(P∨Q∨C)) ?((?P∨?Q∨?A)∨C)∧((?A∨P∨Q)∨C)
?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((?P∨?Q∨?A)∧(?A∨P∨Q))?C ?(?(?P∨?Q∨?A)∨?(?A∨P∨Q))?C ?((P∧Q∧A)∨(A∧?P∧?Q))?C ?(A∧((P∧Q)∨(?P∧?Q)))?C ?(A∧((P∨?Q)∧(?P∨Q)))?C ?(A∧((Q?P)∧(P?Q)))?C ?(A∧(P?Q))?C
四、(10分)個體域為{1，2}，求?x?y(x+y=4)的真值。
解：?x?y(x+y=4)??x((x+1=4)∨(x+2=4))
?((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+2=4)) ?(0∨0)∧(0∨1)?0∧1?0
五、(10分)對于任意集合A，B，試證明：P(A)∩P(B)=P(A∩B) 解：?x?P(A)∩P(B)，x?P(A)且x?P(B)，有x?A且x?B，從而x?A∩B，x?P(A∩B)，由于上述過程可逆，故P(A)∩P(B)=P(A∩B)
六、(10分)已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。
解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>}
七、(10分)設函數f：R×R?R×R，R為實數集，f定義為：f()=。1)證明f是雙射。
解：1)?，∈R×R，若f()=f()，即=，則x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2從而f是單射。
2)?∈R×R，由f()=，通過計算可得x=(p+q)/2;y=(p-q)/2;從而的原象存在，f是滿射。
八、(10分)是個群，u∈G，定義G中的運算“?”為a?b=a*u*b，對任意a，b∈G，求證：也是個群。
證明：1)?a，b∈G，a?b=a*u*b∈G，運算是封閉的。
2)?a，b，c∈G，(a?b)?c=(a*u*b)*u*c=a*u*(b*u*c)=a?(b?c)，運算是可結合的。
3)?a∈G，設E為?的單位元，則a?E=a*u*E=a，得E=u，存在單位元u。 4)?a∈G，a?x=a*u*x=E，x=u*a*u，則x?a=u*a*u*u*a=u=E，每個元素都有逆元。
所以也是個群。
九、(10分)已知：D=，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的鄰接距陣A和可達距陣P。
解：1)D的鄰接距陣A和可達距陣P如下：
A= 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1
1 1 1 0 1 -
1-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
P= 1 1 1 1
十、(10分)求葉的權分別為
2、
4、
6、
8、
10、
12、14的最優二叉樹及其權。
解：最優二叉樹為
權=(2+4)×4+6×3+12×2+(8+10)×3+14×2=148
離散數學試題(B卷答案4)
一、證明題(10分)
1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T
證明: 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等冪律) ?T (代入) 2)?x(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x)) 證明：?x(P(x)?Q(x))∧?xP(x)??x((P(x)?Q(x)∧P(x))??x((?P(x)∨Q(x)∧P(x))??x(P(x)∧Q(x))??xP(x)∧?xQ(x)??x(P(x)∧Q(x))
二、求命題公式(?P?Q)?(P∨?Q) 的主析取范式和主合取范式(10分)
解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3
三、推理證明題(10分)
1)(P?(Q?S))∧(?R∨P)∧Q?R?S 證明：(1)R 附加前提 (2)?R∨P P (3)P T(1)(2),I (4)P?(Q?S) P (5)Q?S T(3)(4),I (6)Q P (7)S T(5)(6),I (8)R?S CP 2) ?x(P(x)∨Q(x))，?x?P(x)??x Q(x) 證明：(1)?x?P(x) P (2)?P(c) T(1),US (3)?x(P(x)∨Q(x)) P (4)P(c)∨Q(c) T(3),US (5)Q(c) T(2)(4),I (6)?x Q(x) T(5),EG
四、例5在邊長為1的正方形內任意放置九個點，證明其中必存在三個點，使得由它們組成的三角形(可能是退化的)面積不超過1/8(10分)。
證明：把邊長為1的正方形分成四個全等的小正方形，則至少有一個小正方形內有三個點，它們組成的三角形(可能是退化的)面積不超過小正方形的一半，即1/8。
五、已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C) (10分)
證明：∵x? A∩(B∪C)? x? A∧x?(B∪C)? x? A∧(x?B∨x?C)?( x? A∧x?B)∨(x? A∧x?C)? x?(A∩B)∨x? A∩C? x?(A∩B)∪(A∩C)∴A∩(B∪C)=(A∩B)∪(A∩C)
六、?={A1，A2，„，An}是集合A的一個劃分，定義R={|a、b∈Ai，I=1，2，„，n}，則R是A上的等價關系(15分)。
證明：?a∈A必有i使得a∈Ai，由定義知aRa，故R自反。 ?a,b∈A，若aRb ，則a,b∈Ai，即b,a∈Ai，所以bRa，故R對稱。
?a,b,c∈A，若aRb 且bRc，則a,b∈Ai及b,c∈Aj。因為i≠j時Ai∩Aj=?，故i=j，即a,b,c∈Ai，所以aRc，故R傳遞。
總之R是A上的等價關系。
七、若f:A→B是雙射，則f:B→A是雙射(15分)。
證明:對任意的x∈A，因為f是從A到B的函數，故存在y∈B，使∈f，∈f。所以,f是滿射。
對任意的x∈A，若存在y1,y2∈B，使得∈f且∈f,則有∈f且∈f。因為f是函數，則y1=y2。所以，f是單射。
因此f是雙射。
八、設是群，和是的子群，證明：若A∪B=G，則A=G或B=G(10分)。
證明 假設A≠G且B≠G，則存在a?A，a?B，且存在b?B，b?A(否則對任意的a?A，a?B，從而A?B，即A∪B=B，得B=G，矛盾。)
對于元素a*b?G，若a*b?A，因A是子群，a?A，從而a * (a*b)=b ?A，所以矛盾，故a*b?A。同理可證a*b?B，綜合有a*b?A∪B=G。 綜上所述，假設不成立，得證A=G或B=G。
九、若無向圖G是不連通的，證明G的補圖G是連通的(10分)。
證明 設無向圖G是不連通的，其k個連通分支為G
1、G
2、„、Gk。任取結點u、v∈G，若u和v不在圖G的同一個連通分支中，則[u，v]不是圖G的邊，因而[u，v]
-
1-1-1
-1
-1
-1-1-1-1是圖G的邊;若u和v在圖G的同一個連通分支中，不妨設其在連通分支Gi(1≤i≤k)中，在不同于Gi的另一連通分支上取一結點w，則[u，w]和[w，v]都不是圖G的邊，，
因而[u，w]和[w，v]都是G的邊。綜上可知，不管那種情況，u和v都是可達的。由u和v的任意性可知，G是連通的。
離散數學試題(B卷答案5)
一、(10分)求命題公式?(P∧Q)??(?P?R)的主合取范式。
解：?(P∧Q)??(?P?R)?(?(P∧Q)??(?P?R))∧(?(?P?R)??(P∧Q)) ?((P∧Q)∨(?P∧?R))∧((P∨R)∨(?P∨?Q)) ?(P∧Q)∨(?P∧?R) ?(P∨?R)∧(Q∨?P)∧(Q∨?R)
?(P∨Q∨?R)∧(P∨?Q∨?R)∧(?P∨Q∨R)∧(?P∨Q∨?R) ?M1∧M3∧M4∧M5
二、(8分)敘述并證明蘇格拉底三段論
解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。 符號化：F(x)：x是一個人。G(x)：x要死的。A：蘇格拉底。 命題符號化為?x(F(x)?G(x))，F(a)?G(a) 證明：
(1)?x(F(x)?G(x)) P (2)F(a)?G(a) T(1),US (3)F(a) P (4)G(a) T(2)(3),I
三、(8分)已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C) 證明：∵x? A∩(B∪C)? x? A∧x?(B∪C)
? x? A∧(x?B∨x?C)
?( x? A∧x?B)∨(x? A∧x?C) ? x?(A∩B)∨x? A∩C ? x?(A∩B)∪(A∩C)
∴A∩(B∪C)=(A∩B)∪(A∩C)
四、(10分)已知R和S是非空集合A上的等價關系，試證：1)R∩S是A上的等價關系;2)對a∈A，[a]R∩S=[a]R∩[a]S。
解：?x∈A，因為R和S是自反關系，所以∈R、∈S，因而∈R∩S，
故R∩S是自反的。
?x、y∈A，若∈R∩S，則∈R、∈S，因為R和S是對稱關系，所以因∈R、∈S，因而∈R∩S，故R∩S是對稱的。
?x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因為R和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的。
總之R∩S是等價關系。
2)因為x∈[a]R∩S?∈R∩S?
∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。
五、(10分) 設A={a，b，c，d}，R是A上的二元關系，且R={，，，}，求r(R)、s(R)和t(R)。
解 r(R)=R∪IA={，，，，，，，} s(R)=R∪R={，，，，，} R={，，，} R={，，，} R={，，，}=R
t(R)=?R={，，，，，，，
4232-1d>，}
六、(15分) 設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且?∈A×C，h()=。證明h是雙射。
證明：1)先證h是滿射。
?∈B×D，則b∈B，d∈D，因為f是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()==，所以h是滿射。
2)再證h是單射。
?、∈A×C，若h()=h()，則= ，所以f(a1)=f(a2)，g(c1)=g(c2)，因為f是A到B的雙射，g是C
到D的雙射，所以a1=a2，c1=c2，所以=，所以h是單射。
綜合1)和2)，h是雙射。
七、(12分)設是群，H是G的非空子集，證明是的子群的充要條件是若a，b?H，則有a*b?H。
證明：? ?a,b∈H有b∈H，所以a*b∈H。 ??a∈H，則e=a*a∈H a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*(b)∈H ∵H?G且H≠?,∴*在H上滿足結合律 ∴是的子群。
八、(10分)設G=是簡單的無向平面圖，證明G至少有一個結點的度數小于等于5。
解：設G的每個結點的度數都大于等于6，則2|E|=?d(v)≥6|V|，即|E|≥3|V|，與簡單無向平面圖的|E|≤3|V|-6矛盾，所以G至少有一個結點的度數小于等于5。 九.G=,A={a,b,c},*的運算表為：(寫過程，7分) -
1-1
-1-1-1-1-1
-1-1 (1)G是否為阿貝爾群?
(2)找出G的單位元;(3)找出G的冪等元(4)求b的逆元和c的逆元 解：(1)(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c) (a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿貝爾群
(2)因為a*a=a a*b=b*a=b a*c=c*a=c 所以G的單位元是a (3)因為a*a=a 所以G的冪等元是a (4)因為b*c=c*b=a，所以b的逆元是c且c的逆元是b
十、(10分)求葉的權分別為
2、
4、
6、
8、
10、
12、14的最優二叉樹及其權。
解：最優二叉樹為
權=148 離散數學試題(B卷答案6)
一、(20分)用公式法判斷下列公式的類型： (1)(?P∨?Q)?(P??Q) (2)(P?Q)?(P∧?(Q∨?R)) 解：(1)因為(?P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q)
?(P∧Q)∨(P∧?Q)∨(?P∧Q) ?m1∨m2∨m3 ?M0
所以，公式(?P∨?Q)?(P??Q)為可滿足式。
(2)因為(P?Q)?(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R))
?(P∨Q)∨(P∧?Q∧R))
?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R)
?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ?M0∧M1
?m2∨m3∨m4∨m5∨m6∨m7
所以，公式(P?Q)?(P∧?(Q∨?R))為可滿足式。
二、(15分)在謂詞邏輯中構造下面推理的證明：每個科學家都是勤奮的，每個勤奮
又身體健康的人在事業中都會獲得成功。存在著身體健康的科學家。所以，存在著事業獲得成功的人或事業半途而廢的人。
解：論域：所有人的集合。Q(x)：x是勤奮的;H(x)：x是身體健康的;S(x)：x是科學家;C(x)：x是事業獲得成功的人;F(x)：x是事業半途而廢的人;則推理化形式為：
?x(S(x)?H(x))Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(x)∧?x(C(x)∨F(x)) 下面給出證明：
(1)?x(S(x)∧H(x))
P (2)S(a)∧H(a)
T(1)，ES (3)?x(S(x)?Q(x))
P (4)S(a)?Q(a)
T(1)，US (5)S(a)
T(2)，I (6)Q(a)
T(4)(5)，I (7)H(a)
T(2)，I (8)Q(a)∧H(a)
T(6)(7)，I (9)?x(Q(x)∧H(x)?C(x))
P (10)Q(a)∧H(a)?C(a)
T(9)，Us (11)C(a)
T(8)(10)，I (12)?xC(x)
T(11)，EG (13)?x(C(x)∨F(x))
T(12)，I
三、(10分)設A={?，1，{1}}，B={0，{0}}，求P(A)、P(B)-{0}、P(B)?B。 解
P(A)={?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)-{0}={?，{0}，{{0}}，{0，{0}}-{0}={?，{0}，{{0}}，{0，{0}} P(B)?B={?，{0}，{{0}}，{0，{0}}?{0，{0}}={?，0，{{0}}，{0，{0}}
四、(15分)設R和S是集合A上的任意關系，判斷下列命題是否成立? (1)若R和S是自反的，則R*S也是自反的。 (2)若R和S是反自反的，則R*S也是反自反的。 (3)若R和S是對稱的，則R*S也是對稱的。
(4)若R和S是傳遞的，則R*S也是傳遞的。 (5)若R和S是自反的，則R∩S是自反的。 (6)若R和S是傳遞的，則R∪S是傳遞的。
解
(1)成立。對任意的a∈A，因為R和S是自反的，則∈R，∈S，于是∈R*S，故R*S也是自反的。
(2)不成立。例如，令A={1，2}，R={<1，2>}，S={<2，1>}，則R和S是反自反的，但R*S={<1，1>}不是反自反的。
(3)不成立。例如，令A={1，2，3}，R={<1，2>，<2，1>，<3，3>}，S={<2，3>，<3，2>}，則R和S是對稱的，但R*S={<1，3>，<3，2>}不是對稱的。
(4)不成立。例如，令A={1，2，3}，R={<1，2>，<2，3>，<1，3>}，S={<2，3>，<3，1>，<2，1>}，則R和S是傳遞的，但R*S={<1，3>，<1，1>，<2，1>}不是傳遞的。
(5)成立。對任意的a∈A，因為R和S是自反的，則∈R，∈S，于是∈R∩S，所以R∩S是自反的。
五、(15分)令X={x1，x2，„，xm}，Y={y1，y2，„，yn}。問 (1)有多少個不同的由X到Y的函數?
(2)當n、m滿足什么條件時，存在單射，且有多少個不同的單射? (3)當n、m滿足什么條件時，存在雙射，且有多少個不同的雙射?
解
(1)由于對X中每個元素可以取Y中任一元素與其對應，每個元素有n種取法，所以不同的函數共nm個。
(2)顯然當|m|≤|n|時，存在單射。由于在Y中任選m個元素的任一全排列都形成X到
mY的不同的單射，故不同的單射有Cnm!=n(n-1)(n―m―1)個。
(3)顯然當|m|=|n|時，才存在雙射。此時Y中元素的任一不同的全排列都形成X到Y的不同的雙射，故不同的雙射有m!個。
六、(5分)集合X上有m個元素，集合Y上有n個元素，問X到Y的二元關系總共有多少個?
解
X到Y的不同的二元關系對應X×Y的不同的子集，而X×Y的不同的子集共有個2mn，所以X到Y的二元關系總共有2mn個。
七、(10分)若是群，則對于任意的a、b∈G，必有惟一的x∈G使得a*x=
b。
證明 設e是群的幺元。令x=a1*b，則a*x=a*(a1*b)=(a*a1)*b=e*b=b。
-
-
-所以，x=a1*b是a*x=b的解。 -若x?∈G也是a*x=b的解，則x?=e*x?=(a1*a)*x?=a1*(a*x?)=a1*b=x。所以，x
-
-
-=a1*b是a*x=b的惟一解。 -
八、(10分)給定連通簡單平面圖G=，且|V|=6，|E|=12。證明：對任意f∈F，d(f)=3。
證明
由偶拉公式得|V|-|E|+|F|=2，所以|F|=2-|V|+|E|=8，于是?d(f)=2|E|=
f?F24。若存在f∈F，使得d(f)>3，則3|F|<2|E|=24，于是|F|<8，與|F|=8矛盾。故對任意f∈F，d(f)=3。
離散數學試題(B卷答案7)
一、(15分)設計一盞電燈的開關電路，要求受3個開關A、B、C的控制：當且僅當A和C同時關閉或B和C同時關閉時燈亮。設F表示燈亮。
(1)寫出F在全功能聯結詞組{?}中的命題公式。 (2)寫出F的主析取范式與主合取范式。
解
(1)設A：開關A關閉;B：開關B關閉;C：開關C關閉;F=(A∧C)∨(B∧C)。 在全功能聯結詞組{?}中：
?A??(A∧A)?A?A A∧C???( A∧C)??( A?C)?(A?C)?(A?C)
A∨B??(?A∧?B)??(( A?A)∧(B?B))?( A?A)?(B?B) 所以
F?((A?C)?(A?C))∨((B?C)?(B?C)) ?(((A?C)?(A?C))?((A?C)?(A?C)))?(((B?C)?(B?C))?((B?C)?(B?C))) (2)F?(A∧C)∨(B∧C)
?(A∧(B∨?B)∧C)∨((A∨?A)∧B∧C) ?(A∧B∧C)∨(A∧?B∧C)∨(A∧B∧C)∨(?A∧B∧C) ?m3∨m5∨m7
主析取范式 ?M0∧M1∧M2∧M4∧M6
主合取范式
二、(10分)判斷下列公式是否是永真式? (1)(?xA(x)??xB(x))??x(A(x)?B(x))。 (2)(?xA(x)??xB(x))??x(A(x)?B(x)))。 解
(1)(?xA(x)??xB(x))??x(A(x)?B(x)) ?(??xA(x)∨?xB(x))??x(A(x)?B(x)) ??(??xA(x)∨?xB(x))∨?x(?A(x)∨B(x)) ?(?xA(x)∧??xB(x))∨?x?A(x)∨?xB(x) ?(?xA(x)∨?x?A(x)∨?xB(x))∧(??xB(x)∨?x?A(x)∨?xB(x)) ??x(A(x)∨?A(x))∨?xB(x) ?T
所以，(?xA(x)??xB(x))??x(A(x)?B(x))為永真式。
(2)設論域為{1，2}，令A(1)=T;A(2)=F;B(1)=F;B(2)=T。
則?xA(x)為假，?xB(x)也為假，從而?xA(x)??xB(x)為真;而由于A(1)?B(1)為假，所以?x(A(x)?B(x))也為假，因此公式(?xA(x)??xB(x))??x(A(x)?B(x))為假。該公式不是永真式。
三、(15分)設X為集合，A=P(X)-{?}-{X}且A≠?，若|X|=n，問 (1)偏序集是否有最大元? (2)偏序集是否有最小元?
(3)偏序集中極大元和極小元的一般形式是什么?并說明理由。 解
偏序集不存在最大元和最小元，因為n>2。
考察P(X)的哈斯圖，最底層的頂點是空集，記作第0層，由底向上，第一層是單元集，第二層是二元集，…，由|X|=n，則第n-1層是X的n-1元子集，第n層是X。偏序集與偏序集相比，恰好缺少第0層和第n層。因此的極小元就是X的所有單元集，即{x}，x∈X;而極大元恰好是比X少一個元素，即X-{x}，x∈X。
四、(10分)設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∪R1={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，-
<4，2>，<4，3>} R2={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}=R2 t(R)=?Ri={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i?1?1>，<5，4>，<5，5>}。
五、(10分)設函數g：A→B，f：B→C，
(1)若f?g是滿射，則f是滿射。 (2)若f?g是單射，則g是單射。
證明
因為g：A→B，f：B→C，由定理5.5知，f?g為A到C的函數。
(1)對任意的z∈C，因f?g是滿射，則存在x∈A使f?g(x)=z，即f(g(x))=z。由g：A→B可知g(x)∈B，于是有y=g(x)∈B，使得f(y)=z。因此，f是滿射。
(2)對任意的x
1、x2∈A，若x1≠x2，則由f?g是單射得f?g(x1)≠f?g(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是單射。
六、(10分)有幺元且滿足消去律的有限半群一定是群。
證明
設是一個有幺元且滿足消去律的有限半群，要證是群，只需證明G的任一元素a可逆。
考慮a，a2，„，ak，„。因為G只有有限個元素，所以存在k>l，使得ak=al。令m=k-l，有al*e=al*am，其中e是幺元。由消去率得am=e。
于是，當m=1時，a=e，而e是可逆的;當m>1時，a*am-1=am-1*a=e。從而a是可逆的，其逆元是am-1?？傊?，a是可逆的。
七、(20分)有向圖G如圖所示，試求： (1)求G的鄰接矩陣A。
(2)求出A
2、A3和A4，v1到v4長度為
1、
2、3和4的路有多少?
(3)求出ATA和AAT，說明ATA和AAT中的第(2，2)元素和第(2，3)元素的意義。 (4)求出可達矩陣P。 (5)求出強分圖。
解
(1)求G的鄰接矩陣為：
?0??0A??0??0?101??011?
101??100??(2)由于
?0??02A??0??0?111??02??201?3?0
1 A??02111????02011???12??03??22??044A?
?0312????0101???23??13? 23??22??所以v1到v4長度為
1、
2、3和4的路的個數分別為
1、
1、
2、3。 (3)由于
?0??0ATA??0??0?000??21??312??12TAA?
?21011????10213???21??10? 21??21??再由定理10.19可知，所以ATA的第(2，2)元素為3，表明那些邊以v2為終結點且具有不同始結點的數目為3，其第(2，3)元素為0，表明那些邊既以v2為終結點又以v3為終結點，并且具有相同始結點的數目為0。AAT中的第(2，2)元素為2，表明那些邊以v2為始結點且具有不同終結點的數目為2，其第(2，3)元素為1，表明那些邊既以v2為始結點又以v3為始結點，并且具有相同終結點的數目為1。
(4)?0??0B4?A?A2?A3?A4??0??0??0??0所以求可達矩陣為P??0??0??0??0(5)因為P?PT??0??0?101??0??011??0+101??0???100???0111??111?。
111??111??111??0??111??1∧?1111????1111???000??0??111??0=?0111????0111???000??111?，所以{v1}，{v2，v3，v4}
111??111??因
111??0
??
201??0
+
111??0
???011???0
212??03??122??04+
212??03???201???0123??13??23??22???0
??0?0??0?
為
741?
?
747?
，
747?
?
434??構成G的強分圖。
離散數學試題(B卷答案8)
一、(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?R
P (3)?P
T(1)(2)，I (4)P∨Q
P (5)Q
T(3)(4)，I (6)Q?S
P (7)S
T(5)(6)，I (8)?R?S
CP (9)S∨R
T(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，|A?B?C|=25-20=5。故，不會打這三種球的共5人。
四、(10分)設A
1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱
i?13為由A
1、A2和A3產生的小項。試證由A
1、A2和A3所產生的所有非空小項的集合構成全集U的一個劃分。
證明
小項共8個，設有r個非空小項s
1、s
2、…、sr(r≤8)。
對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，即有a∈?si，于是U??si。又顯然有?si?U，所以U=?si。
i?1i?1i?1i?1i?13rrrr任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和Ai分別出現在sp和sq中，于是sp∩sq=?。
綜上可知，{s1，s2，…，sr}是U的一個劃分。
五、(15分)設R是A上的二元關系，則：R是傳遞的?R*R?R。
證明
(5)若R是傳遞的，則∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。
反之，若R*R?R，則對任意的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)f?g是A到C的函數;
(2)對任意的x∈A，有f?g(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，即∈f?g。所以Df?g=A。
對任意的x∈A，若存在y
1、y2∈C，使得、∈f?g=g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因為g：A→B是函數，則t1=t2。又因f：B→C是函數，則y1=y2。所以A中的每個元素對應C中惟一的元素。
綜上可知，f?g是A到C的函數。
(2)對任意的x∈A，由g：A→B是函數，有∈g且g(x)∈B，又由f：B→C是函數，得∈f，于是∈g*f=f?g。又因f?g是A到C的函數，則可寫為f?g(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。所以
-
-
-a>∈R。
若∈R，∈R，則a1*b∈H，b1*c∈H。因為H是G的子群，所以(a
-
-
-1*b)*(b1*c)=a1*c∈H，故∈R。 --綜上可得，R是G中的一個等價關系。
對于任意的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，
-b>∈R，故aH?[a]R。所以，[a]R=aH。
離散數學試題(B卷答案9)
一、(10分)證明(P∧Q∧A?C)∧(A?P∨Q∨C)?(A∧(P?Q))?C。 證明：(P∧Q∧A?C)∧(A?P∨Q∨C)?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)
?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((P∧Q∧A)∨(A∧?P∧?Q))∨C ??( A∧((P∧Q)∨(?P∧?Q)))∨C ??( A∧(P?Q))∨C ?(A∧(P?Q))?C。
二、(10分)舉例說明下面推理不正確：?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))。
解：設論域為{1，2}，令P(1)=P(2)=T;Q(1)=Q(2)=T;R(1)=R(2)=F。則： ?x?y(P(x)?Q(y))??x((P(x)?Q(1))∨(P(x)?Q(2)))
?((P(1)?Q(1))∨(P(1)?Q(2)))∧((P(2)?Q(1))∨(P(2)?Q(2))) ?((T?T)∨(T?T))∧((T?T)∨(T?T)) ?T ?y?z(R(y)?Q(z))??y((R(y)?Q(1))∨(R(y)?Q(2)))
?((R(1)?Q(1))∨(R(1)?Q(2)))∧((R(2)?Q(1))∨(R(2)?Q(2)))
?((F?T)∨(F?T))∧((F?T)∨(F?T))
?T
但
?x?z(P(x)?R(z))??x((P(x)?R(1))∧(P(x)?R(2))) ?((P(1)?R(1))∧(P(1)?R(2)))∨((P(2)?R(1))∧(P(2)?R(2))) ?((T?F)∧(T?F))∨((T?F)∧(T?F)) ?F 所以，?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))不正確。
三、(15分)在謂詞邏輯中構造下面推理的證明：所有牛都有角，有些動物是牛，所以，有些動物有角。
解：令P(x)：x是牛;Q(x)：x有角;R(x)：x是動物;則推理化形式為：
?x(P(x)?Q(x))，?x(P(x)∧R(x))?x(Q(x)∧R(x)) 下面給出證明：
(1)?x(P(x)∧R(x))
P (2)P(a)∧R(a)
T(1)，ES (3)?x(P(x)?Q(x))
P (4)P(a)?Q(a)
T(3)，US (5)P(a)
T(2)，I (6)Q(a)
T(4)(5)，I (7)R(a)
T(2)，I (8)Q(a)∧R(a)
T(6)(7)，I (9)?x(Q(x)∧R(x))
T(8)，EG
四、(10分)證明(A∩B)×(C∩D)=(A×C)∩(B×D)。
證明：因為∈(A∩B)×(C∩D)?x∈(A∩B)∧y∈(C∩D)?x∈A∧x∈B∧y∈C∧y∈D?(x∈A∧y∈C)∧(x∈B∧y∈D)?∈A×C∧∈B×D?∈(A×C)∩(B×D)，所以(A∩B)×(C∩D)=(A×C)∩(B×D)。
五、(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∪R1={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，-
<4，2>，<4，3>} R2={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}=R2 t(R)=?Ri={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i?1?1>，<5，4>，<5，5>}。
六、(10分)若函數f：A→B是雙射，則對任意x∈A，有f1(f(x))=x。
-證明
對任意的x∈A，因為f：A→B是函數，則∈f，于是
-由f-1是B到A的函數，于是可寫為f1(f(x))=x。
-
七、(10分)若G為有限群，則|G|=|H|·[G:H]。
證明
設[G:H]=k，a
1、a
2、…、ak分別為H的k個左陪集的代表元，由定理8.38得
G??[ai]R??aiH
i?1i?1kk又因為對H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|=…=|akH|=|H|。因此
|G|?|?aiH|?i?1k?|aH|?k|H|=|H|·[G:H]。
ii?1k
八、(20分)(1)畫出3階2條邊的所有非同構有向簡單圖。
解：由握手定理可知，所畫的有向簡單圖各結點度數之和為4，且最大出度和最大入度均小于或等于2。度數列與入度列、出度列為：
1、
2、1：入度列為0、
1、1或0、
2、0或
1、0、1;出度列為
1、
1、0或
1、0、1或0、
2、0
2、
2、0：入度列為
1、
1、0;出度列為
1、
1、0 四個所求有向簡單圖如圖所示。
(2)設G是n(n≥4)階極大平面圖，則G的最小度?≥3。
證明
設v是極大平面圖G的任一結點，則v在平面圖G-{v}的某個面f內。由于G-{v}是一個平面簡單圖且其結點數大于等于3，所以d(f)≥3。由G的極大平面性，v與f上的結點之間都有邊，因此d(v)≥3。由v的任意性可得，G的最小度?≥3。
離散數學試題(B卷答案10)
一、(10分)使用將命題公式化為主范式的方法，證明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。
證明：因為(P?Q)?(P∧Q)??(?P∨Q)∨(P∧Q)
?(P∧?Q)∨(P∧Q) (Q?P)∧(P∨Q)?(?Q∨P)∧(P∨Q) ?(P∧?Q)∨(?Q∧Q)∨(P∧P) ∨(P∧Q) ?(P∧?Q)∨P
?(P∧?Q)∨(P∧(Q∨?Q)) ?(P∧?Q)∨(P∧Q)∨(P∧?Q) ?(P∧?Q)∨(P∧Q) 所以，(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。
二、(10分)證明下述推理： 如果A努力工作，那么B或C感到愉快;如果B愉快，那么A不努力工作;如果D愉快那么C不愉快。所以，如果A努力工作，則D不愉快。
解 設A：A努力工作;B、C、D分別表示B、C、D愉快;則推理化形式為： A?B∨C，B??A，D??CA??D
(1)A 附加前提 (2)A?B∨C P (3)B∨C T(1)(2)，I (4)B??A P (5)A??B
T(4)，E (6)?B T(1)(5)，I (7)C T(3)(6)，I
(8)D??C P (9)?D T(7)(8)，I (10)A??D CP
三、(10分)證明?x?y(P(x)?Q(y))?(?xP(x)??yQ(y))。 ?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y)) ??x(?P(x)∨?yQ(y)) ??x?P(x)∨?yQ(y) ???xP(x)∨?yQ(y) ?(?xP(x)??yQ(y))
四、(10分)設A={?，1，{1}}，B={0，{0}}，求P(A)、P(B)-{0}、P(B)?B。 解 P(A)={?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)-{0}={?，{0}，{{0}}，{0，{0}}-{0}={?，{0}，{{0}}，{0，{0}} P(B)?B={?，{0}，{{0}}，{0，{0}}?{0，{0}}={?，0，{{0}}，{0，{0}}
五、(15分)設X={1，2，3，4}，R是X上的二元關系，R={<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)畫出R的關系圖。 (2)寫出R的關系矩陣。
(3)說明R是否是自反、反自反、對稱、傳遞的。 解 (1)R的關系圖如圖所示： (2) R的關系矩陣為：
?1??0M(R)??1??1?101110110??0? 0??0??(3)對于R的關系矩陣，由于對角線上不全為1，R不是自反的;由于對角線上存在非0元，R不是反自反的;由于矩陣不對稱，R不是對稱的;
經過計算可得
?1??0M(R2)??1??1?101110110??0??M(R)，所以R是傳遞的。 ?0?0??
六、(15分)設函數f：R×R?R×R，f定義為：f()=。 (1)證明f是單射。 (2)證明f是滿射。 (3)求逆函數f。
(4)求復合函數f?f和f?f。
證明 (1)對任意的x，y，x1，y1∈R，若f()=f()，則=，x+y=x1+y1，x-y=x1-y1，從而x=x1，y=y1，故f是單射。
(2)對任意的∈R×R，令x=-1-
1u?wu?wu?wu?w
，y=，則f()=<+，2222u?wu?w->=，所以f是滿射。 22(3)f()=<-1-1u?wu?w，>。 22-1(4)f?f()=f(f())=f
-1
()=<
x?y?x?y，
2x?y?(x?y)>= 2f?f()=f(f())=f()==<2x，2y>。
七、(15分)給定群，若對G中任意元a和b，有a*b=(a*b)，a*b=(a*b)，a*b=(a*b)，試證是Abel群。
證明 對G中任意元a和b。
因為a*b=(a*b)，所以a*a*b*b=a*(a*b)*b，即得a*b=(b*a)。同33
333
3
2
2255
53
3
3
4
44
?13
?1?1?1理，由a*b=(a*b)可得，a*b=(b*a)。由a*b=(a*b)可得，a*b=(b*a)。
于是(a*b)*(b*a)=(b*a)=a*b，即b*a=a*b。同理可得，(a*b)*(b*a)=(b*a)=a*b，即b*a=a*b。
3333334
4
4
4
4
2
2
344433555444
由于(a*b)*b=a*b=b*a=b*(b*a)=b*(a*b)=(b*a)*b，故a*b=b*a。
八、(15分)(1)證明在n個結點的連通圖G中，至少有n-1條邊。
證明 不妨設G是無向連通圖(若G為有向圖，可略去邊的方向討論對應的無向圖)。 設G中結點為v
1、v
2、„、vn。由連通性，必存在與v1相鄰的結點，不妨設它為v2(否則可重新編號)，連接v1和v2，得邊e1，還是由連通性，在v
3、v
4、„、vn中必存在與v1或v2相鄰的結點，不妨設為v3，將其連接得邊e2，續行此法，vn必與v
1、v
2、„、vn?1中的某個結點相鄰，得新邊en?1，由此可見G中至少有n-1條邊。
(2)試給出|V|=n，|E|=(n-1)(n-2)的簡單無向圖G=是不連通的例子。
解 下圖滿足條件但不連通。
12344333
第二篇：初三數學期末考試試卷分析
2013-2014學年度第一學期期末考試
初三數學試卷分析
這次期末考試全面提高數學教育質量，有利于初中數學課程改革和教學改革，培養學生的創新精神和實踐能力;有利于減輕學生過重的負擔，促進學生主動、活潑、生動地學習.
一、試卷的整體分析
試卷的總體難度適宜，能堅持“以綱為綱，以本為本的原則”，在加強基礎知識的考查的同時，還加強了對學生的能力的考查的比例設置考題，命題能向課程改革靠攏.注重基礎，加大知識點的覆蓋面，控制題目的煩瑣程度，題目力求簡潔明快，不在運算的復雜上做文章;整體布局力求合理有序，提高應用題的考查力度，適當設置創新考題，注重知識的拓展與應用，適應課程改革的形勢.
二、存在的主要問題：
1、缺少高分，優秀率低。
2、學生對基礎知識掌握的不牢。知識不系統，綜合能力應變能力較差，不能舉一反三。
3、做題步驟不嚴密、解題不靈活,不注重方法和技巧。
三、典型錯誤：
1.解選擇題第1 題時由于不仔細部分學生忽略了分母不能為0。 2.解填空題第5題時考慮不全面，好多學生將C坐標找錯。 3.填空題第8題扇形面積問題，忘記公式，不能正確理解出錯率高。
4、填空題第10題，不會靈活應用樹形圖求概率，導致丟分。
5、第五題解方程，很多學生不能結合周長寫出正確的解析式。
6.第六，七等題都是對圓的理解，部分學生出錯率也較高。 7.解第八題時，錯誤也較多。
8.第九題求值，第三小題不會靈活運用韋達定理解題，出錯率高。
四、今后工作思路
我們提出要加強基礎知識教學要加強對學生“三基”的教學和訓練，使學生掌握必要的基礎知識、基本技能和基本方法.在概念、基本定理、基本法則、性質等教學過程中，要加強知識發生過程的教學，使學生加深對基礎知識的理解;要加強對學生數學語言的訓練，使學生的數學語言表達規范、準確、到位;要加強運算能力的教學，使學生明白算理，并選擇簡捷、合理的算法，提高運算的速度和準確率;要依綱據本進行教學，踏踏實實地教好第一遍，切不可不切實際地脫離課本，搞難題訓練，更不能隨意補充綱本外的知識.教學中要立足于把已學的知識弄懂弄通，真正讓學生形成良好的認知結構和知識網絡，打好初中數學基礎，全面提高學生的數學素質.
這次考試數學的統計數據進一步說明，在數學學習上的困難生還比較多，怎樣使這些學生盡快“脫貧”、擺脫中考成績個位數的困境，以適應在高一級學校的繼續學習和當今的信息時代，這是我們每一個初中數學教育工作者的一個重要研究課題.重視培優，更應關注補差.課堂教學中，要根據本班的學情，選擇好教學內容，合理地確定教學的起點和進程.課外要多給學習有困難的學生開“小灶”，滿腔熱情地關心每一位后進生，讓他們盡快地跟上其他同學，促進全體學生的進步和發展.
踏虎學校：張艷芳
第三篇：七年級數學期末考試數學試卷分析
杜丹丹
一、基本情況及考試成績分析
本次期末測試共有三個大題，分為選擇、填空、解答，共計有27個小題。滿分120分，其中選擇題10個，每小題2分，滿分20分;填空題10個，每小題3分，滿分30分;解答題7個，共70分?？疾閮热荩杭浇贪嫫吣昙墧祵W上冊全書內容。，重點考察有理數混合運算、角、整式、一元一次方程、列方程解應用題、找規律、合并同類項等。試卷內容比較靈活多樣，對基礎知識、生活實踐、等都有考察。
1、基本情況：七年級一班，其中數學100分以上的7人，80分以上的8人，最高分112分，最低分8分，班級平均分為68分。七年級二班，數學100分以上的6人，80分以上的13人，最高分120分，最低分2分，班級平均分為69分。
2、逐題試卷分析：一題“選擇”：滿分20分，大部分得分在14—20分間，錯誤較多的試題依次為第4題、第5題、第9題、和第10題。二題“填空”：滿分30分，大多得分12—24分，錯的較多的是
12、
15、
16、
17、19題。三題“解答題”總分70分，其中
21、
22、23是計算題，其中21題考察的是有理數的混合運算，22題考察的是整式的計算，23題考察的是解一元一次方程，都是平時常見常做的題型，但是很少有學生能拿到滿分，從這可以看出同學們的計算能力比較薄弱。24題為有理數的應用題，同學們大部分能把算式寫對，但是得數算錯，造成失分。25題為一元一次方程的應用題，一部分同學得0分，因為沒有理解對題意，一部分同學只得了4分，只是答對了第一問，第二問的題意理解不清。26題考察的是角的和與差知識，這道題大部分同學得0分，因為沒有理解清楚角的倍數關系，導致題目分析不出來，平時常做的是角平分線有關的題目，這方面的題目練習較少，大部分同學不能自己分析題目，導致失分，從這可以看出學生的分析能力薄弱。27題為找規律的計算題，大部分的得分在4到7分之間，錯的最多的是1+2+3····+n的和不能求出，這個公式平時講課的時候講過，但是有的同學已經忘記了，所以還要加強平時基礎的鞏固與強化。
二、教情分析。本學期是本人第一次執教七年級數學，本次期末考試后，本人經過反思，認為七年級數學期末成績一般，主要失誤是：
1、對學生基礎情況還不夠了解，作業要求不太嚴格。如：少數學生不按要求完成預習作業、課后作業，甚至有少部分學生長期不按時交作業，導致一部分差生沒有學懂;
2、使用多媒體教學，雖然課堂容量大，但是課堂練習落實不到位，一部分學生課堂上沒有認真完成練習任務;
3、課后沒有足夠的時間認真組織學生復習，導致大部分中等生和學困生基本功不扎實;
4、要求學生記憶的公式、定理、性質，沒有按時督促完成，使學生對基本概念的理解和掌握不深刻。不會運用學過的公式、定理、性質解決問題;
5、教學中對學生的運算訓練不扎實，導致學生基本運算能力差。
三、今后教學的方向
1、狠抓課堂教學，注重基礎，使學生的基礎知識真正的落實;
2、加強運算能力的訓練與基本概念的掌握，重視解題能力的培養;
3、重視學生預習習慣的養成、培養學生的自學能力;
4、做好學生的思想工作，充分調動學生的學習積極性，端正學習態度;
5、認真做好培優補差工作，大面積提高教學質量。
總之，今后本人一定吸取教訓，改進方法，總結以前教學中的得失，為今后教學做借鑒;引導學生掌握、理解新課程的基本理念，學好數學知識。
第四篇：九年級數學期末考試試卷分析
2013----2014學年度解集中學九年級數學期末考試試卷分析
一、 試題分析
這次期末考試全面提高數學教育質量，有利于初中數學課程改革和教學改革，培養學生的創新精神和實踐能力;有利于減輕學生過重的負擔，促進學生主動、活潑、生動地學習.這次考試主要考察了九年級數學上冊的內容。主要內容有，二次函數，反比例函數，相似形等。
試卷的總體難度適宜，能堅持“以綱為綱，以本為本的原則”，在加強基礎知識的考查的同時，還加強了對學生的能力的考查的比例設置考題，命題能向課程改革靠攏.注重基礎，加大知識點的覆蓋面，控制題目的煩瑣程度，題目力求簡潔明快，不在運算的復雜上做文章;整體布局力求合理有序，提高應用題的考查力度，適當設置創新考題，注重知識的拓展與應用，適應課程改革的形勢.
二.試卷分析
本套試卷共24道題，其中選擇題共30分，填空題占24分，解答題共24分，解答或證明題22分。整體難易程度在7:2:1，難易程度適中，其中，選擇題第
4、9題具有探索性，有利于考察不同層次的學生分析、探求、解決問題的能力，第
16、19題能考察學生靈活運用知識與方法的能力,第
12、21題具有開放性，考察學生從現實生活中抽象數學模型的能力，2,1題第2問較難，好多同學失分的原因是考慮不全面有漏算的情況。得分率較高的題目都是基本知識的應用，說明多數學生對基礎知識掌握較好。得分率較低的題目大多是開放性的、新穎的，實際應用的題目。
三.存在的問題
1、學生的基礎知識不扎實以及計算能力不高是失分的主要原因。本次試題基礎題所占比例大，從答題情況看，主要原因是基礎不扎實，對課本知識生疏，或不能熟練運用，相當一部分后進生表現尤為突出。
2、審題不仔細是造成失分的另一主要原因。
3、平時學習過程中，不理解概念的實質，不理解知識形成發展過程，死記硬背，因而不能在一定的數學情境中正確運用概念，不能正確辨明數學關系，靈活解決和處理問題的能力不足。尤其表現在對課本上的一些變式問題缺乏分析和解決問題的能力。
4、平時檢測密度不夠，只注重了新課程的教學而忽略了對舊知識的復習和鞏固，尤其對課本知識掌握不熟練，對規律探究性問題缺乏歸納和分析的能力，不能正確運用整體的數學思想解決問題。
5、轉差工作不夠細致，效率不高，往往事倍而功半，只注重了對學生的輔導而忽略了對學習效果的檢測，方法過于死板，學生負擔重。
四、今后工作思路
1、重視“雙基”訓練 ①把好計算的準確關：平時計算時要強調穩，分步計算，注意檢查。②把好理解審題關：平時教學中要加強訓練，題意不清，不急于動筆答題。③把好表達規范關：一是注意表達要有邏輯性，推理要力求嚴謹;二是要書寫整潔規范。
2、重視回歸課本、回歸課堂， 中考試題多來源于課本或從課本的基本要求出發加以拓寬，而不是加深，這樣將更好地指導我們的課堂教學。我們要逐步改變“老師講，學生聽;教師問，學生答;及大量演練習題”的數學教學模式，應引導學生從生活經驗出發，親歷數學化的過程。我們必須關注當前課改的新理念，給學生以充分從事數學活動的 時間、空間，使學生在自己探索、親身實踐、合作交流中解決問題。
3、重視問題變式訓練(一題多變、一題多解) 在問題變式教學中，教師或通過對命題結論的改變，引出新命題;或通過對 命題條件的改變，引出新命題;或通過特殊到一般聯想，引出新命題;有時還可 以引導學生思考以下幾個方面的問題：這一問題有哪些特例，還能否推廣，它的反面情形如何，逆向思考結果怎樣，與其相關問題結合起來情形如何。這樣的變式訓練不但有利于學生更好地把握數學知識的本質內涵，而且也是培養學生思維 能力的有效途徑，從而可以有效地提高解決開放探究性問題的能力。
4、關注每一位學生，加強學法指導 ，從近幾年中考試題來看，面向每位學生、加強學法指導是擺在廣大教師面前 不可忽視的問題，應予以足夠重視。要努力提高學生學習數學的興趣和愿望，努力營造學生主動學習、合作學習、探究學習的氛圍，挖掘學生的潛能，及時發現學生學習方法上的問題并采取具體措施。
5、強化全面意識，加強補差工作
這次考試數學的統計數據進一步說明，在數學學習上的困難生還比較多，怎樣使這些學生盡快“脫貧”、擺脫中考成績個位數的困境，以適應在高一級學校的繼續學習和當今的信息時代，這是我們每一個初中數學教育工作者的一個重要研究課題.重視培優，更應關注補差.課堂教學中，要根據本班的學情，選擇好教學內容，合理地確定教學的起點和進程.課外要多給學習有困難的學生開“小灶”，滿腔熱情地關心每一位后進生，讓他們盡快地跟上其他同學，促進全體學生的進步和發展.
6、強化過程意識，暴露思維過程
數學教學活動必須建立在學生的認知發展水平和已有的知識經驗基礎之上.數學教學中，應當有意識地精選一些典型例題和習題進行思維訓練.激發學生的學習積極性，向學生提供充分從事數學活動的機會.暴露學生把抽象的數學問題具體化和形象化的過程;要讓學生多說解題思路和解決問題的策略，暴露學生解決數學問題的思維過程;經常性地進行數學語言的訓練，暴露學生對復雜的數學語言進行分解與簡化的過程;要通過一題多解和一題多變的訓練，暴露學生對數學問題多種解法的比較與反思過程.讓學生在自主探索和合作交流的過程中真正理解和掌握基本的數學知識與技能、數學思想和方法，獲得廣泛的數學活動經驗.
7、教學中重在凸現學生的學習過程，培養學生的分析能力。 在平時的教學中，作為教師應盡可能地為學生提供學習材料，創造自主學習的機會。尤其是在應用題的教學中，要讓學生的思維得到充分的展示，讓他們自己來分析題目，設計解題的策略，多做分析和編題等訓練，讓有的學生從“怕”應用題到喜歡應用題。
8、多做多練，切實培養和提高學生的計算能力。
要學生說題目的算理，也許不一定會錯，但有時他們是憑自己的直覺做題，不講道理，不想原因。這點可以從試卷上很清晰地反映出來。學生排除計算干擾的本領。
九年級數學期末考試試卷分析
解集中心學校數學組
謝立民
2014年1月
第五篇：三年級數學期末考試試卷分析
聶華卿
一、試題分析：
本次質量檢測試卷的整個難易程度適中，題量合適，注重基礎知識，考察的知識面廣，題目的形式多樣，實際運用較好，符合新課標的要求，是一份比較好的檢測學生雙基知識的試題，為今后的教學起到了一定的導向作用。試題的編制即側重于對數學基礎知識的考查，同時部分試題蘊涵了對學生運用數學知識解決生活實際問題能力等數學知識綜合運用水平的考查，缺少動手操作題是唯一的遺憾。試卷有以下幾個特點：
1、題型多樣。包括填空題、選擇題、計算題(口算、筆算)、應用題等;
2、綜合運用性強。一道題目不僅考查一個知識點，而是考查有聯系并且易混淆的多個知識點。目的是要求學生能融合貫通，全面分析并掌握所學知識。
3、注重計算能力的考查，測試學生是否有扎實的基本知識和熟練的運算能力。整套試卷，不但計算量大，而且范圍廣，分布于填空、選擇、口算、豎式計算、解決問題中。
4、注重運用，有一定靈活性。
5、貼近生活，注重考查學生的生活經驗在數學中的應用。
二、學生答題情況及分析
優點：全班卷面達到了干凈整潔，書寫漂亮?；A知識掌握扎實，成績良好。計算題較好。
不足：通過看卷子，我們找到了下面問題：
1、學生缺乏良好的考試習慣，自己檢查錯誤的能力有待加強。如：填空題中一些基本的題目出錯;計算題豎式正確，答案填錯;應用題抄錯數。
2、學生馬虎現象嚴重：單位名稱落寫，橫式不寫得數，有5人小數計算沒有驗算等。
3、課上聽講不好，對兩步計算的應用題目的理解能力需要繼續提高。
三、改進措施：
1、教師及時反思進行詳細卷面分析針對每個學生進行分析。指點不足，鼓勵差生。
2、利用假期狠抓學生舉一反三能力的培養。
3、繼續培養學生良好的學習習慣，包括分析能力、計算能力、認真檢查能力。從最后一名學生抓起.及時反饋，及時補差。
4、 加強與家長的聯系，及時溝通，共同努力，提高學生綜合素質.
5、 利用假期留分層次作業，讓每個學生在假期知識有銜接,能力有提高。