(5.6)--离散数学试卷及答案.doc

离散数学试题(A卷答案)一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)1)P®(PQR) 2)Ø(P®Q)Q 3)(P®Q)ØR 解：1)重言式；2)矛盾式；3)可满足式二、（10分）求命题公式(ØP®Q)®(ØQP)的主析取范式，并求成真赋值。解：(ØP®Q)®(ØQP)Û(PQ)®(ØQP)ÛØ(PQ)(ØQP)Û(ØPØQ)ØQPÛØQPÛ(PØP)ØQ)(PØQ)(PQ)Û(ØPØQ)(PØQ)(PØQ)(PQ)Û m0m2m3成真赋值为：00、10、11。三、（10分）证明下列命题的等值关系：(PQ)Ø(PQ)ÛØ(P«Q）证明：(PQ)Ø(PQ)Û(PQ)(ØPØQ)Û(PØQ)(QØP)ÛØ(ØPQ)(ØQP)ÛØ(P®Q)(Q®P)ÛØ(P«Q）四、（10分）叙述并证明苏格拉底三段论解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：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五、（10分）已知A、B、C是三个集合，证明A(BC)=(AB)(AC)证明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC）Û xÎ（AB）xÎ ACÛ xÎ（AB）（AC）A（BC）=（AB）（AC）六、（10分）R为集合X上的二元关系，X=1，2，3，4，5，6，7，R=<1，1>，<1，2>，<2，4>，<6，3>，<6，6>，<7，1>，求:R的等价闭包R*(即包含R的最小的等价关系)。解：R*=<1，1>，<2，2>，<3，3>，<4，4>，<5，5>，<6，6>，<7，7>，<1，2>，<2，1>，<2，4>，<4，2>，<6，3>，<3，6>，<7，1>，<1，7>，<1，4>，<4，1>，<2，7>，<7，2>，<7，4>，<4，7>七、（10分）设函数f：R×R®R×R，R为实数集，f定义为：f(<x，y>)=<x+y，x-y>。1)证明f是双射。解：1）"<x1，y1>，<x2，y2>R×R，若f(<x1，y1>)=f(<x2，y2>)，即<x1+y1，x1-y1>=<x2+y2，x2-y2>，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。2）"<p，q>R×R，由f(<x，y>)=<p，q>，通过计算可得x=(p+q)/2；y=(p-q)/2；从而<p，q>的原象存在，f是满射。八、（10分）设G是一群，H是G的子群，xG，证明xHx-1=xhx-1| hH 是G的子群。解：由H非空，知xHX-1非空。"a，bxHx-1，即存在h1，h2H，使得a=xh1x-1，b=xh2x-1，有ab-1=(xh1x-1)(xh2x-1)-1=xh1x-1（X-1）-1h2-1x-1=x(h1h2-1) x-1因H为G的子群，有h1h2-1=h3H从而ab-1= xh3x-1xHx-1。所以xHx-1为子群。九、（10分）若G是连通平面图，且G的每个面的次数至少为l(l3)，则G的边数m与结点数n有如下关系： 证明：设G有r个面，则2m=，2mlr。由欧拉公式得，n-m+r=2，r=2-n+m。于是十、（10分）求叶的权分别为7、8、9、12、16的最优二叉树及其权。解：最优二叉树如图所示：树的权为(9+12+16)×2+(7+8)×3=119离散数学试题(B卷答案）一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)1)P®(PQR) 2)Ø(Q®P)ØP)(PR) 3)(ØPQ)®R)®(PQ)R)解：1)重言式；2)矛盾式；3)可满足式二、（10分）求命题公式（P(QR)®(PQR)的主析取范式，并求成真赋值。解：（P(QR)®(PQR)ÛØ(P(QR)PQRÛØP(ØQØR)PQRÛ(ØPØQ)(ØPØR)(PQ)RÛ(Ø(PQ)(PQ)(ØPØR)RÛ1(ØPØR)R)Û1Ûm0m1m2m3m4m5m6m7该式为重言式，全部赋值都是成真赋值。三、（10分）证明 (PQA)®C)(A®(PQC)Û(A(P«Q)®C证明：(PQA)®C)(A®(PQC)Û(Ø(PQA)C)(ØA(PQC)Û(ØPØQØA)C)(ØAPQ)C)Û(ØPØQØA)(ØAPQ)CÛØ(ØPØQØA)(ØAPQ)®CÛ(Ø(ØPØQØA)Ø(ØAPQ)®CÛ(PQA)(AØPØQ)®CÛ(A(PQ)(ØPØQ)®CÛ(A(PØQ)(ØPQ)®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）Û（00）（01）Û01Û0五、（10分）对于任意集合A，B，试证明：P(A)P(B)=P(AB)解："xÎP(A)P(B)，xÎP(A)且xÎP(B)，有xÍA且xÍB，从而xÍAB，xÎP(AB)，由于上述过程可逆，故P(A)P(B)=P(AB)六、（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(<x，y>)=<x+y，x-y>。1)证明f是双射。解：1）"<x1，y1>，<x2，y2>R×R，若f(<x1，y1>)=f(<x2，y2>)，即<x1+y1，x1-y1>=<x2+y2，x2-y2>，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。2）"<p，q>R×R，由f(<x，y>)=<p，q>，通过计算可得x=(p+q)/2；y=(p-q)/2；从而<p，q>的原象存在，f是满射。八、（10分）<G，*>是个群，uG，定义G中的运算“D”为aDb=a*u-1*b，对任意a，bG，求证：<G， D>也是个群。证明：1）"a，bG，aDb=a*u-1*bG，运算是封闭的。2）"a，b，cG，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），运算是可结合的。3）"aG，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元u。4）"aG，aDx=a*u-1*x=E，x=u*a-1*u，则xDa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以<G， D>也是个群。九、（10分）已知：D=<V，E>，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如下：01010111110010011111A=00011P=1111100000000001000011111十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。解：最优二叉树为权(2+4)×4+6×3+12×2+(8+10)×3+14×2148