离散数学考试试题(A、B卷及答案).pdf

《离散数学考试试题(A、B卷及答案).pdf》由会员分享，可在线阅读，更多相关《离散数学考试试题(A、B卷及答案).pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学考试试题(A 卷及答案）一、证明题（10 分）1)(PQAC)(APQC)(A(PQ)C。PQ=(p-Q)合取（Q-p）证明:(PQAC)(APQC)(PQAC)(APQC)(PQA)(APQ)C反用分配律(PQA)(APQ)C(A(PQ)(PQ)C再反用分配律(A(PQ)C(A(PQ)C 2)(PQ)PQ。证明：(PQ)(PQ)(PQ)PQ。二、分别用真值表法和公式法求(P(QR)(P(QR)的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15 分）。主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由 析取范式经等值演算法算得。证明：公式

2、法：因为(P(QR)(P(QR)(PQR)(P(QR)(QR)(PQR)(PQ)(PR)(QR)分配律(PQR)(PQQ)(PQR)(PRQ)(PRR)(PQR)(PQR)(PQR)4M5M6M使（非 P 析取 Q 析取 R）为 0 所赋真值，即 100，二进制为 4 0m1m2m3m7m 所以，公式(P(QR)(P(QR)为可满足式，其相应的成真赋值为 000、001、010、011、111：成假赋值为：100、101、110。真值表法：P Q R QR P(QR)P(QR)(P(QR)(P(QR)0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

3、 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 由真值表可知，公式(P(QR)(P(QR)为可满足式，其相应的成真赋值为 000、001、010、011、111：成假赋值为：100、101、110。三、推理证明题（10 分）1）PQ，QR，RSPS。证明：(1)P 附加前提(2)PQ P(3)Q T(1)(2)，I（析取三段论）(4)QR P(5)R T(3)(4)，I（析取三段论）(6)RS P(7)S T(5)(6)，I（假言推理）(8)PS CP 2)x(P(x)Q(y)R(x)，xP(x)Q(y)x(P(

4、x)R(x)证明（1）xP(x)(2)P(a)(3)x(P(x)Q(y)R(x)(4)P(a)Q(y)R(a)(5)Q(y)R(a)(6)Q(y)(7)R(a)(8)P(a)(9)P(a)R(a)(10)x(P(x)R(x)(11)Q(y)x(P(x)R(x)五、已知 A、B、C 是三个集合，证明(AB)C(AC)(BC)（10 分）证明：因为 x(AB)Cx(AB)C x(AB)xC(xAxB)xC(xAxC)(xBxC)x(AC)x(BC)x(AC)(BC)所以，(AB)C(AC)(BC)。八、证明整数集 I 上的模 m 同余关系 R=|xy(mod m)是等价关系。其中，xy(mod m

5、)的含义是 x-y 可以被 m 整除（15 分）。X(modm)=y(modm)证明：1）xI，因为（x-x）/m=0，所以 xx(mod m)，即 xRx。2）x,yI，若 xRy，则 xy(mod m)，即（x-y）/m=kI，所以（y-x）/m=-kI，所以 yx(mod m)，即 yRx。3）x,y,zI，若 xRy，yRz，则（x-y）/m=uI，（y-z）/m=vI，于是（x-z）/m=（x-y+y-z）/m=u+v I，因此 xRz。九、若 f:AB 和 g:BC 是双射，则（gf）-1=f-1g-1（10 分）。证明：因为 f、g 是双射，所以 gf：AC 是双射，所以 gf

6、有逆函数（gf）-1：CA。同理可推 f-1g-1：CA 是双射。因为f-1g-1存在 z（g-1f-1）存在 z（fg）gf（gf）-1,所以（gf）-1=f-1g-1。离散数学考试试题(B 卷及答案）一、证明题（10 分）1)(PQ)(P(QR)(PQ)(PR)T 证明:左端(PQ)(P(QR)(PQ)(PR)(摩根律)(PQ)(PQ)(PR)(PQ)(PR)(分配律)(PQ)(PR)(PQ)(PR)(等幂律)T(代入)2)xy(P(x)Q(y)(xP(x)yQ(y)证明：xy(P(x)Q(y)xy(P(x)Q(y)x(P(x)yQ(y)xP(x)yQ(y)xP(x)yQ(y)(xP(x)

7、yQ(y)二、求命题公式(PQ)(PQ)的主析取范式和主合取范式（10 分）解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PPQ)(QPQ)(PQ)M1 析取要使之为假，即赋真值 001，即 M1 m0m2m3 使之为真 三、推理证明题（10 分）1)(P(QS)(RP)QRS 证明：(1)R (2)RP p(3)P T（1）（2）析取三段论(4)P(QS)p(5)QS T（3）（4）I 假言推理(6)Q P(7)S T（5）（6）I 假言推理(8)RS CP 2)x(A(x)yB(y)，x(B(x)yC(y)xA(x)yC(y)。证明：(1)x(A(x)yB(y)P

8、(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 提前进入考场，个体域：考生的集 合，则命题可符号化为：PxA(x)，xA(x)QQP。(1)Px

9、A(x)P(2)PxA(x)T(1)E(3)xA(x)P T(2)E (4)xA(x)Q P(5)(xA(x)Q)(QxA(x)T(4)E(6)QxA(x)T(5)I(7)QP T(6)(3)I 五、已知 A、B、C 是三个集合，证明 A(BC)=(AB)(AC)（10 分）证明：x A（BC）x Ax（BC）x A（xBxC）（x A xB）（x AxC）x（AB）x AC x（AB）（AC）A （BC）=（AB）（AC）六、A=x1,x2,x3，B=y1,y2，R=,，求其关系矩阵及关系图（10 分）。有就是 1，没就是 0 七、设 R=,，求 r(R)、s(R)和 t(R)，并作出它们及

10、 R 的关系图（15 分）。r(R)=,（自反闭包）s(R)=,（对称闭包）t(R)=,（传递闭包）九、设 f：AB，g：BC，h：CA，证明：如果 hgfIA，fhgIB，gfhIC，则 f、g、h 均为双射，并求出 f1、g1和 h1（10 分）。解 因 IA恒等函数，由 hgfIA可得 f 是单射，h 是满射；因 IB恒等函数，由 fhgIB可得 g 是单射，f 是满射；因 IC恒等函数，由 gfhIC可得 h 是单射，g 是满射。从而 f、g、h 均为双射。由 hgfIA，得 f1hg；由 fhgIB，得 g1fh；由 gfhIC，得 h1gf。五.(12 分)令 X=x1,x2,.,

11、xm,Y=y1,y2,.,yn,问:(1)有多少不同的由 X 到 Y 的关系?(2)有多少不同的由 X 到 Y 的影射?(3)有多少不同的由 X 到 Y 的单射，双射?（12 分）是个群，uG，定义 G 中的运算“”为 ab=a*u-1*b，对任意 a,bG，求证：也是个群。证明：1）a,bG，ab=a*u-1*bG，运算是封闭的。2）a,b,cG，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），运算是可结合的。3）aG，设 E 为的单位元，则 aE=a*u-1*E=a，得 E=u，存在单位元。4）aG，ax=a*u-1*x=E，x=u*a-1*u，则 xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以也是个群。六.