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

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 分） 。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 证明： 公式法：因为(P(QR)(P(QR) (PQR)(P(QR)(QR) (PQR)(PQ) (PR)(QR)分配律 (PQR)(PQQ)(PQR)(PRQ)(P RR) (PQR)(PQR)(PQR) 4 M 5 M 6 M使（非 P 析取 Q 析取 R）为 0 所赋真值，即100，二进 制为 4 . 精品 0 m 1 m 2 m 3 m

2、 7 m 所以， 公式 (P(QR) (P(QR)为可满足式， 其相应的成真赋值为000、001、 010、011、111：成假赋值为：100、 101、110。 真值表法： PQRQRP(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 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)PQP (3)QT(1)(2)， I（析取三段论） (4)QRP (5)RT(3)(4)，I（析取三段论） (6)RSP (7)ST(5)(6)，I（假言推理） (8)PSCP 2) x(P(x)Q(y)R(x)，xP(x)Q(y)x(P(x)R(x) 证明（ 1）xP(x) (2)P(a) (3)x(

3、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)x C (xAxB)xC (xAxC)(xBxC) x(AC)x(BC) x(AC)(BC) 所以， (AB)C(AC)(BC)。 八、 证明整数集I 上的模 m 同余关系R=|xy(mod m) 是等价关系。 其中， xy(mod m)的含义是x-y 可以被 m 整除（ 15分） 。X(modm)=y(modm) 证明： 1）x I，因为（ x-x）/m=0 ，所以 xx(mod m)，即 xRx。 2）x,yI，若 xRy，则 xy(mod m)，即（ x-y）/m=k I，所以（ y - x）/m=-k I， 所以 yx(mod m)，即 yRx。 3）x,y,zI，若 xRy，yRz，则（ x-y）/m=u I， （y-z）

4、/m=v I，于是（ 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 有逆函数（ gf）-1：CA。同理可 推 f-1g-1：CA 是双射。 因为 f -1g-1 存在 z（ g-1 f-1）存在 z（ f g） gf （ gf） -1,所以（ gf）-1=f-1g-1。 离散数学考试试题 (B 卷及答案） 一、证明题（10 分） 1)(PQ)(P(QR)(PQ)(PR)T 证明 : 左端(PQ)(P(QR)(PQ)(PR)(摩根律 ) (P Q)(PQ)(P R)(PQ)(PR)(分配律 ) (P Q)(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)yQ(y) 二、求命题公式(PQ)(PQ) 的主析取范式和主合取范

5、式（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 (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 四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入

6、考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15 分） 。 解 ： 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集 合，则命题可符号化为：PxA(x)，xA(x)QQP。 . 精品 (1)PxA(x) P (2)PxA(x) T(1)E (3)xA(x)PT(2)E (4)xA(x)QP (5)(xA(x)Q)(QxA(x) T(4)E (6)QxA(x) T(5)I (7)QPT(6)(3)I 五、已知 A、B、C 是三个集合，证明A(BC)=(A B)(AC) （10 分） 证明： x A（ BC） x Ax（BC） x A（ xB xC）（ x A xB）（ x A xC） x（AB） x A C 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)，并作出它们及R 的关系图（ 15 分） 。 r(R)=,（自反闭包） s(R)=,（对称闭包） t(R)

7、=,（传递闭包） 九、设f：AB，g：BC，h：CA，证明：如果hogofIA，fohogIB，gofohIC，则 f、g、h均为双射，并求出f 1、g 1 和h 1（10 分） 。 解因IA恒等函数， 由hogofIA可得f是单射，h是满射； 因IB恒等函数， 由fohog IB可得g是单射，f是满射；因IC恒等函数，由gofohIC可得h是单射，g是满射。从 而f、g、h均为双射。 由hogofIA，得f1hog；由fohogIB，得g 1foh；由 gofohIC，得h 1gof。 . 精品 五. (12 分)令 X=x1,x2,.,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*b G，运算是封闭的。 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 ，每个元素都 有逆元。 所以 也是个群。 六. 如有侵权请联系告知删除，感谢你们的配合！

《离散数学考试试题(A、B卷及答案)》由会员雨水分享，可在线阅读，更多相关《离散数学考试试题(A、B卷及答案)》请在金锄头文库上搜索。