離散數(shù)學考試試

1、離散數(shù)學考試試題（B卷及答案）一、（10分）求命題公式Ø(PQ)«Ø(ØP®R)的主合取范式。解：Ø(PQ)«Ø(ØP®R)Û（Ø(PQ)®Ø(ØP®R)）（Ø(ØP®R)®Ø(PQ)）Û（(PQ)(ØPØR)）（(PR)(ØPØQ)）Û(PQ)(ØPØR)Û(PØR)（QØP）

2、（QØR）Û(PQØR)(PØQØR)（ØPQR）（ØPQØR）ÛM1M3M4M5二、（8分）敘述并證明蘇格拉底三段論解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號化：F（x）：x是一個人。G（x）：x要死的。A：蘇格拉底。命題符號化為"x（F（x）®G（x），F(xiàn)（a）ÞG（a）證明：（1）"x(F(x)®G(x)    P（2）F(a)®G(a)    

3、60;    T(1),US（3）F(a)               P（4）G(a)               T(2)(3),I三、（8分）已知A、B、C是三個集合，證明A(BC)=(AB)(AC)證明：xÎ A（BC）Û xÎ AxÎ（BC

4、）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC）        Û xÎ（AB）xÎ AC                  Û xÎ（AB）（AC）  &#

5、160;              A（BC）=（AB）（AC）四、（10分）已知R和S是非空集合A上的等價關(guān)系，試證：1）RS是A上的等價關(guān)系；2）對aA，aRS=aRaS。解："xA，因為R和S是自反關(guān)系，所以<x,x>R、<x,x>S，因而<x,x>RS，故RS是自反的。"x、yA，若<x,y>RS，則<x,y>R、<x,y>S，因為R和S是對稱關(guān)系，所以因&

6、lt;y,x>R、<y,x>S，因而<y,x>RS，故RS是對稱的。"x、y、zA，若<x,y>RS且<y,z>RS，則<x,y>R、<x,y>S且<y,z>R、<y,z>S，因為R和S是傳遞的，所以因<x,z>R、<x,z>S，因而<x,z>RS，故RS是傳遞的?？傊甊S是等價關(guān)系。2）因為xaRSÛ<x,a>RSÛ<x,a>R<x,a>SÛ xaRxaSÛ xaRaS所

7、以aRS=aRaS。五、(10分) 設Aa，b，c，d，R是A上的二元關(guān)系，且R<a，b>，<b，a>，<b，c>，<c，d>，求r(R)、s(R)和t(R)。解  r(R)RIA<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>s(R)RR-1<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>R2<a

8、，a>，<a，c>，<b，b>，<b，d>R3<a，b>，<a，d>，<b，a>，<b，c>R4<a，a>，<a，c>，<b，b>，<b，d>R2t(R)<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>六、(15分) 設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×

9、;C®B×D且"<a,c>A×C，h(<a,c>)<f(a),g(c)>。證明h是雙射。證明：1）先證h是滿射。"<b,d>B×D，則bB，dD，因為f是A到B的雙射，g是C到D的雙射，所以存在aA，cC，使得f(a)=b，f(c)=d，亦即存在<a,c>A×C，使得h(<a,c>)<f(a),g(c)><b,d>，所以h是滿射。2）再證h是單射。"<a1,c1>、<a2,c2>A×C，

10、若h(<a1,c1>)h(<a2,c2>)，則<f(a1),g(c1)><f(a2),g(c2)> ，所以f(a1)f(a2)，g(c1)g(c2)，因為f是A到B的雙射，g是C到D的雙射，所以a1a2，c1c2，所以<a1,c1><a2,c2>，所以h是單射。綜合1）和2），h是雙射。七、(12分)設<G，*>是群，H是G的非空子集，證明<H，*>是<G，*>的子群的充要條件是若a，bÎH，則有a*b-1ÎH。證明：Þ "a,bH有b-1H，所以

11、a*b-1H。Ü"aH，則e=a*a-1H            a-1=e*a-1H                       a,bH及b-1H，a*b=a*（b-1）-1HHÍG且HF,*在H上滿足結(jié)合律

12、0; <H，*>是<G，*>的子群。八、（10分）設G=<V，E>是簡單的無向平面圖，證明G至少有一個結(jié)點的度數(shù)小于等于5。解：設G的每個結(jié)點的度數(shù)都大于等于6，則2|E|=Sd(v)6|V|，即|E|3|V|，與簡單無向平面圖的|E|3|V|-6矛盾，所以G至少有一個結(jié)點的度數(shù)小于等于5。九.G=<A,*>,A=a,b,c,*的運算表為：(寫過程，7分)                  （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)   &#