离散数学考试试题(A卷及答案)

离散数学考试试题〔A卷及答案〕一〔10分〕推断以下公式的类型〔永真式、永假式、可满足式〕？1)((PQ)∧Q)((Q∨R)∧Q) 2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解：1)永真式；2〕永假式；3)可满足式。〔8分〕个体域为{1，2}，求xy〔x+y=4〕的真值。x〔x+y=x+1=〕∨x+2=〕〔1+1=〕∨1+2=〕∧〔2+1=〕∨2+1=〕〔0∨0〕∧〔0∨1〕1∧10〔8〕集合A和B|A|=n，|B|=m，求ABA到B解：由于|P(A×B)|=2|A×B|=2|A||B|=2mn，所以AB2mn|BA|=|B||A|=mn，AB的函数mn〔10〕A={1,2,3,4,5R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>r(R)、s(Rt(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>}五、(10752055人至少乘坐过其中的两种。假设每样乘坐一次的费用是0.5场总共收入70元，求有多少儿童没有乘坐过其中任何一种。A、B、C|ABC|＝20，|AB|＋|AC|＋|BC|－2|ABC|＝55，|A|＋|B|＋|C|＝70/0.5＝140。由容斥原理，得|ABC|＝|A|＋|B|＋|C|―|AB|―|AC|―|BC|＋|ABC|所以|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|ABC|)＋|ABC|＝75－140＋55＋20＝1010〔12〕RSA1〕R∩SA2〕a∈A，[a]R=[a]∩[a]∩S R S解：x∈A，RS<x,x>∈R、<x,x>∈S，因而<x,x>∈R∩SR∩S的。xy∈A，假设<x,y>∈R∩S，则<x,y>∈R<x,y>∈SRS<y,x>∈R<y,x>∈S，因而<y,x>∈R∩S，故R∩S1x、y、z∈A，假设<x,y>∈R∩S<y,z>∈R∩S，则<x,y>∈R、<x,y>∈S<y,z>∈R、<y,z>∈S，由于RS<x,z>∈R、<x,z>∈S，因而<x,z>∈R∩S，故R∩SR∩S2〕由于x∈[a]<x,a>∈R∩S<x,a>∈R∧<x,a>∈Sx∈[a]x∈[a]x∈[a][a]R∩S R S R S所以[a]=[a]∩[a]R∩S R S七〔10〕A、B、C、DfABgCDh：A×CB×D<a,c>∈A×C，h(<a,c>)＝<f(a),g(c)>。证明h是双射。证明：1〕先证h<b,d>∈B×D，则b∈B，d∈D，由于f是A到Bg是C到D的双射，所以存在a∈A，c∈C，f(a)=b，f(c)=d，亦即存在<a,c>∈A×C，使得h(<a,c>)＝<f(a),g(c)>＝<b,d>，所以h再证h<a1,c1>、<a2,c2>∈A×C，假设h(<a1,c1>)＝h(<a2,c2>)，则<f(a1),g(c1)>＝<f(a2),g(c2)>，所以f(a1)＝f(a2)，g(c1)＝g(c2)，由于fABg是C到D的双射，所以a1＝a2，c1＝c2，所以<a1,c1>＝<a2,c2>，所以h综合〕和2h是双射。〔12〕<G,*>是个群，u∈G，定义G”为ab=a*u-1*b，对任意a,b∈G，求证：<G,>也是个群。证明：1〕a,b∈G，ab=a*u-1*b∈G，运算是封闭的。2〕a,b,∈〔〕c〔a*u-1*〕*u-1*c=a*u-1〔b*u-1*=〔bc，运算是可结合的。a∈G，设E的单位元，则aE=a*u-1*E=aE=u，存在单位元。a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以<G,>也是个群。〔10〕：D=<V,E>，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>DA和可达距阵P。解：D的邻接距阵A和可达距阵P0 10 0A= 0 00 01 0

0 1 01 0 00 1 10 0 00 0 0

1 1 1 1 11 1 1 1 1P= 1 1 1 1 10 0 0 0 01 1 1 1 1〔10〕2、4、6、8、10、12、14解：最优二叉树为2权＝148离散数学考试试题〔B卷及答案〕〔10〕求命题公式(P∧Q)(PR)的主合取范式。解：(P∧Q)(PR)〔(P∧Q)(PR)〕∧〔(PR)(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〕M∧M∧M∧M1 3 4 5〔8〕表达并证明苏格拉底三段论解：全部人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化〔x：xxx：苏格拉底。命题符号化为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)证明：∵xA∩〔B∪C〕xA∧x〔B∪C〕xA∧〔xB∨xC〕〔xA∧xB〕∨〔xA∧xC〕x〔A∩B〕∨xA∩Cx〔A∩B〕∪〔A∩C〕3∴A∩〔B∪C〕=〔A∩B〕∪〔A∩C〕〔10〕RSA1〕R∩SA2〕a∈A，[a]R=[a]∩[a]∩S R S解：x∈A，RS<x,x>∈R、<x,x>∈S，因而<x,x>∈R∩SR∩S的。xy∈A，假设<x,y>∈R∩S，则<x,y>∈R<x,y>∈SRS<y,x>∈R<y,x>∈S，因而<y,x>∈R∩S，故R∩Sx、y、z∈A，假设<x,y>∈R∩S<y,z>∈R∩S，则<x,y>∈R、<x,y>∈S<y,z>∈R、<y,z>∈S，由于RS<x,z>∈R、<x,z>∈S，因而<x,z>∈R∩S，故R∩SR∩S2〕由于x∈[a]<x,a>∈R∩SR∩S<x,a>∈R∧<x,a>∈Sx∈[a]∧x∈[a]x∈[a]∩[a]R S R S所以[a]=[a]∩[a]R∩S R S五、(10A＝{a，b，c，d}，RAR＝{<a，b>，<b，a>，<b，c>，<c，d>}，求r(R)、s(Rt(R)。解r(R)＝R∪IA＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>}s(R)＝R∪R-1＝{<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>}R2＝{<a，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)＝

i1

Ri＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>}六、(15A、B、C、DfABgCDh：A×CB×D<a,c>∈A×C，h(<a,c>)＝<f(a),g(c)>。证明h是双射。证明：1〕先证h<b,d>∈B×D，则b∈B，d∈D，由于f是A到Bg是C到D的双射，所以存在a∈A，c∈C，f(a)=b，f(c)=d，亦即存在<a,c>∈A×C，使得h(<a,c>)＝<f(a),g(c)>＝<b,d>，所以h2〕再证h<a1,c1>、<a2,c2>∈A×C，假设h(<a1,c1>)＝h(<a2,c2>)，则<f(a1),g(c1)>＝<f(a2),g(c2)>，所f(a1)＝f(a2)，g(c1)＝g(c2)，由于fABgCDa1＝a2，c1＝c2，所以<a1,c1>＝<a2,c2>，所以h综合〕和2h是双射。七、(12<G，*>是群，H是G的非空子集，证明<H，*>是<G，*>a，bH，则a*b-1H。证明：a,b∈Hb-1∈H，所以a*b-1∈H。a∈He=a*a-1∈H4a-1=e*a-1∈H∵a,b∈Hb-1∈H，∴a*b=a*〔b-1〕-1∈H∵HG且H≠,∴*H∴<H，*>是<G，*>的子群。〔10〕设G=<V，E>是简洁的无向平面图，证明G5。解：设G6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简洁无向平面图的|E|≤3|V|-6G5。九.G=<A,*>,A={a,b,c},*的运算表为：(写过程，7分)〔1〕G〔2〕找出G〕找出G的幂等元4〕求b的逆元和c〔〕(a*c)*(a*c)