《(5.6)--离散数学试卷及答案.doc》由会员分享，可在线阅读，更多相关《(5.6)--离散数学试卷及答案.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学试题(A卷答案)一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)1)P(PQR) 2)(PQ)Q 3)(PQ)R 解：1)重言式；2)矛盾式；3)可满足式二、（10分）求命题公式(PQ)(QP)的主析取范式，并求成真赋值。解：(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ)QPQP(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) m0m2m3成真赋值为：00、10、11。三、（10分）证明下列命题的等值关系：(PQ)(PQ)(PQ）证明：(PQ)(PQ)(PQ)(PQ)(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ）四、（10分）叙述
2、并证明苏格拉底三段论解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：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（xBxC）（ x AxB）（x AxC） x（AB）x AC x（AB）（AC）A（BC）=（AB）（AC）六、（10分）R为集合X上的二元关系，X=1，2，3，
3、4，5，6，7，R=，求:R的等价闭包R*(即包含R的最小的等价关系)。解：R*=，七、（10分）设函数f：RRRR，R为实数集，f定义为：f()=。1)证明f是双射。解：1），RR，若f()=f()，即=，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。2）RR，由f()=，通过计算可得x=(p+q)/2；y=(p-q)/2；从而的原象存在，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，有
4、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分）判断下列
5、公式的类型（永真式、永假式、可满足式）？(写过程)1)P(PQR) 2)(QP)P)(PR) 3)(PQ)R)(PQ)R)解：1)重言式；2)矛盾式；3)可满足式二、（10分）求命题公式（P(QR)(PQR)的主析取范式，并求成真赋值。解：（P(QR)(PQR)(P(QR)PQRP(QR)PQR(PQ)(PR)(PQ)R(PQ)(PQ)(PR)R1(PR)R)1m0m1m2m3m4m5m6m7该式为重言式，全部赋值都是成真赋值。三、（10分）证明 (PQA)C)(A(PQC)(A(PQ)C证明：(PQA)C)(A(PQC)(PQA)C)(A(PQC)(PQA)C)(APQ)C)(PQA)(AP
6、Q)C(PQA)(APQ)C(PQA)(APQ)C(PQA)(APQ)C(A(PQ)(PQ)C(A(PQ)(PQ)C(A(QP)(PQ)C(A(PQ)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）010五、（10分）对于任意集合A，B，试证明：P(A)P(B)=P(AB)解：xP(A)P(B)，xP(A)且xP(B)，有xA且xB，从而xAB，xP(AB)，由于上述过程可逆，故P(A)P(B)=P(AB)六、（10分）已知A=1，2，3，4，5和R=，求
7、r(R)、s(R)和t(R)。解：r(R)=，s(R)=，t(R)=，七、（10分）设函数f：RRRR，R为实数集，f定义为：f()=。1)证明f是双射。解：1），RR，若f()=f()，即=，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。2）RR，由f()=，通过计算可得x=(p+q)/2；y=(p-q)/2；从而的原象存在，f是满射。八、（10分）是个群，uG，定义G中的运算“D”为aDb=a*u-1*b，对任意a，bG，求证：也是个群。证明：1）a，bG，aDb=a*u-1*bG，运算是封闭的。2）a，b，cG，（aDb）Dc=（a*u-1*b）*
8、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，每个元素都有逆元。所以也是个群。九、（10分）已知：D=，V=1，2，3，4，5，E=，求D的邻接距阵A和可达距阵P。解：1）D的邻接距阵A和可达距阵P如下：01010111110010011111A=00011P=1111100000000001000011111十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。解：最优二叉树为权(2+4)4+63+122+(8+10)3+142148