2022年2022年离散数学期末考试试题及答案 .pdf

离散数学试题 (B 卷答案 1）一、证明题（10 分）1)(P(QR) (QR)(P R)R 证明: 左端(P Q R)(QP)R) (P Q)R)(QP)R) (PQ) R)(QP)R) (PQ) (Q P)R (PQ) (PQ)R T R(置换)R 2) x (A(x)B(x)xA(x)xB(x) 证明 ： x(A(x)B(x)x( A(x)B(x) x A(x) xB(x) xA(x) xB(x) xA(x)xB(x) 二、求命题公式(P(QR)(PQ R)的主析取范式和主合取范式（10 分） 。证明： (P(QR)(PQR)(P(Q R) (PQ R) （P (QR)）(PQR) (PQ)(PR) (PQR) (PQ R)(PQ R)(PQ R) (PQR) (PQR) m0m1m2m7M3M4M5M6三、推理证明题（10 分）1） CD， (C D)E，E(AB)， (A B)(RS)RS 证明： (1) (CD)E P (2) E(AB) P (3) (C D)(AB) T(1)(2)，I (4) (AB)(RS) P (5) (C D)(RS) T(3)(4)， I (6) C D P (7) R S T(5)，I 2) x(P(x)Q(y) R(x) ， xP(x)Q(y) x(P(x) R(x) 证明 (1)xP(x) P 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - (2)P(a) T(1)，ES (3)x(P(x)Q(y) R(x) P (4)P(a)Q(y) R(a) T(3)，US (5)Q(y) R(a) T(2)(4)，I (6)Q(y) T(5)，I (7)R(a) T(5)，I (8)P(a)R(a) T(2)(7)，I (9)x(P(x)R(x) T(8)，EG (10)Q(y) x(P(x)R(x) T(6)(9)，I 四、某班有25 名学生，其中14 人会打篮球， 12 人会打排球，6 人会打篮球和排球，5人会打篮球和网球，还有2 人会打这三种球。而6 个会打网球的人都会打另外一种球，求不会打这三种球的人数（10 分） 。解：A，B，C分别表示会打排球、网球和篮球的学生集合。则 |A|=12 ，|B|=6 ，|C|=14 ，|A C|=6，|B C|=5，|A BC|=2。先求 |AB| 。6=| （AC） B|=| （AB）（ BC）|=| （AB）|+| （BC）|-|A BC|=|（AB）|+5-2 ， | （AB）|=3 。于是 |ABC|=12+6+14-6-5-3+2=20 。不会打这三种球的人数25-20=5 。五、已知A 、B、C是三个集合，证明A-(B C)=(A-B) (A-C) （10 分） 。证明： x A- （B C） x A x（BC） x A（ xBxC）（x AxB）（ x AxC） x（A-B） x（A-C） x（A-B）（ A-C）A-（BC）=（A-B）（ A-C）六、已知 R、S是 N上的关系，其定义如下：R=| x，yNy=x2，S=| x，yNy=x+1 。求 R-1、R*S、S*R、R 1，2 、S1 ，2 （10 分） 。解： R-1=| x ，yNy=x2 R*S=| x ，yNy=x2+1 S*R=| x，yNy=（x+1）2 ，R 1，2= ，S1 ，2=1 ，4 。七、设 R=，求 r(R) 、s(R) 和 t(R) （15 分） 。解： r(R)=， s(R)=， 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - - - - - - R2= R5=， ， R3=， ， R4=， ， t(R)=， ， 八、证明整数集I 上的模 m同余关系 R=|xy(mod m) 是等价关系。 其中， x y(mod m)的含义是x-y 可以被 m整除（ 15 分） 。证明： 1）x I ，因为（ x-x ）/m=0，所以 x x(mod m) ，即 xRx。2）x，yI ，若xRy，则 x y(mod m) ，即（ x-y ）/m=k I ，所以（ y - x）/m=-kI ，所以 y x(mod m) ，即 yRx。3）x，y，z I ，若 xRy，yRz，则（ x-y ）/m=uI ， （y-z ）/m=vI ，于是（ x-z ）/m=（ x-y+y-z ）/m=u+v I ，因此 xRz。九、若 f:A B和 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-1f-1）存在 z（fg）gf（ gf ）-1，所以（ gf ）-1=f-1g-1。离散数学试题 (B卷答案 2）一、证明题（10 分）1)(P Q)(P(QR) (P Q)(PR)T 证明 : 左端(P Q)(P(QR) (P Q)(PR)( 摩根律 ) (P Q) (PQ)(P R) (P Q)(P R)( 分配律 ) (P Q) (PR) (P Q)(PR) (等幂律 ) T ( 代入 ) 2) xy( P( x)Q( y)(xP( x)yQ( y) 证明：x y( P( x)Q( y)x y(P( x) Q( y) x(P( x) yQ( y) xP( x) yQ( y) xP( x) yQ( y) (xP( x)yQ( y) 二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式（10 分）解： (PQ)(PQ)(PQ)(PQ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 29 页 - - - - - - - - - (PQ)(PQ) (PQ)(PQ) (PPQ)(Q PQ) (PQ) M1 m0 m2 m3 三、推理证明题（10 分）1)(P(QS) (RP)QRS 证明： (1)R (2)RP (3)P (4)P(QS) (5)QS (6)Q (7)S (8)RS 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 四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15 分） 。解设 P：今天天气好，Q：考试准时进行，A( e) ：e 提前进入考场，个体域：考生的集合，则命题可符号化为：Px A(x) ，xA(x)QQP。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - (1)Px A( 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)=(AB)(AC) （10 分）证明： xA（ BC）xAx（BC）xA（ xBxC）（ xAxB）（ xAxC）x（AB） xACx（A B）（ AC） A（ BC） =（AB）（ AC）六、 A= x1,x2,x3 ，B= y1,y2， R=, ，求其关系矩阵及关系图（ 10 分） 。七、设 R=,，求 r(R) 、s(R) 和 t(R) ，并作出它们及 R的关系图（ 15 分） 。解： r(R)=, , s(R)=, R2=R5=, R3=, R4=, t(R)=, 八、设 R1是 A 上的等价关系， R2是 B 上的等价关系， A且 B。关系 R 满足： ，RR1且R2，证明 R 是 AB 上的等价关系（10 分） 。证明对任意的 AB，由 R1是 A 上的等价关系可得R1，由 R2是 B上的等价关系可得R2。再由 R 的定义，有 ，R，所以 R 是自反的。对任意的 、 AB，若 R，则 R1且R2。由 R1对称得 R1，由 R2对称得 R2。再由 R 的定义，有 ，R，即 R，所以 R 是对称的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29 页 - - - - - - - - - 对任意的 、AB，若R且R，则 R1且R2，R1且 R2。由R1、R1及 R1的传递性得 R1，由 R2、R2及 R2的传递性得 R1。再由 R 的定义，有， R，即 R，所以 R 是传递的。综上可得， R 是 AB 上的等价关系。九、设 f：AB，g：BC，h：CA，证明：如果h g fIA，f h gIB，g f hIC，则f、g、h 均为双射，并求出f 1、 g1和 h1（10 分） 。解因 IA恒等函数， 由 h g f IA可得 f 是单射， h 是满射； 因 IB恒等函数， 由 f h gIB可得 g 是单射， f 是满射；因 IC恒等函数，由g f hIC可得 h 是单射， g 是满射。从而 f、g、h 均为双射。由 h g fIA，得 f1h g；由 f h gIB，得 g 1f h；由 g f hIC，得 h1g f。离散数学试题 (B 卷答案 3）一、 （10 分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程 ) 1)P(PQ R) 2)(QP)P)(PR) 3)(PQ)R)(P Q)R) 解： 1)重言式； 2) 矛盾式； 3) 可满足式二、 （10 分）求命题公式（P(QR)(PQR)的主析取范式，并求成真赋值。解： （P (QR)(PQR)(P(QR) PQR P(QR)PQR (PQ)(PR)(PQ)R (PQ)(P Q) (PR)R 1(PR)R)1 m0m1m2m3 m4 m5m6 m7 该式为重言式，全部赋值都是成真赋值。三、 （10 分）证明 (P QA)C)(A(PQ C)(A (PQ)C 证明： (P QA)C) (A(PQC)(PQA)C)(A(PQC) (PQ A) C)(APQ)C) (PQ A) (APQ) C 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - (PQ A)(APQ)C (PQ A)(APQ)C (P QA)(APQ)C (A(P Q) (PQ)C (A(P Q)(P Q)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(A B) 解：xP(A) P(B) ，xP(A) 且 xP(B)，有 xA 且 xB，从而 xAB ，xP(AB)，由于上述过程可逆，故P(A) P(B)=P(A B) 六、 （10 分）已知 A=1，2，3，4，5 和 R=， ，求 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中的运算“”为 a b=a*u-1*b，对任意a，b名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - G ，求证： 也是个群。证明： 1）a，bG，a b=a*u-1*bG，运算是封闭的。2）a，b，cG ， （a b）c=（a*u-1*b）*u-1*c=a*u-1* （b*u-1*c ）=a （b c） ，运算是可结合的。3）aG ，设 E为的单位元，则a E=a*u-1*E=a，得 E=u，存在单位元u。4）aG ，a x=a*u-1*x=E，x=u*a-1*u，则 xa=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如下：0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 A= 0 0 0 1 1 P= 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 十、 （10 分）求叶的权分别为2、4、6、8、10、12、14 的最优二叉树及其权。解：最优二叉树为权 (2+4) 4+63+122+(8+10) 3+142148离散数学试题 (B 卷答案 4）一、证明题（10 分）1)(P Q)(P(QR) (P Q)(PR)T 证明 : 左端(P Q)(P(QR) (P Q)(PR)( 摩根律 ) (P Q)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - - - - - (PQ)(PR) (P Q)(PR)( 分配律 ) (P Q) (PR) (P Q)(PR) (等幂律 ) T ( 代入 ) 2)x(P(x)Q(x) xP(x)x(P(x) Q(x) 证明：x(P(x)Q(x) xP(x)x(P(x)Q(x) P(x)x(P(x) Q(x) P(x)x(P(x) Q(x)xP(x) xQ(x)x(P(x) Q(x) 二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式（10 分）解：(PQ)(P Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2 m3 三、推理证明题（10 分）1)(P(QS) (RP) QRS 证明： （1）R 附加前提(2)RP P (3)P T(1)(2),I (4)P(QS) P (5)QS T(3)(4),I (6)Q P (7)S T(5)(6),I (8)RS CP 2) x(P(x)Q(x) ，xP(x)x Q(x) 证明： (1)xP(x) P (2)P(c) T(1),US (3)x(P(x) Q(x) P (4)P(c)Q(c) T(3),US (5)Q(c) T(2)(4),I (6)x Q(x) T(5),EG 四、例 5 在边长为1 的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8 （10 分） 。证明：把边长为1 的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8 。五、已知A 、B、C是三个集合，证明A(BC)=(AB)(AC) （10 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - 证明： xA（BC）xAx（BC）xA（ xBxC）（ xAxB）（ xAxC）x（AB） xACx（A B）（ AC） A（ BC）=（AB）（ AC）六、=A1，A2， An是集合 A的一个划分，定义R=|a 、bAi，I=1 ，2，n ，则 R是 A上的等价关系（15 分） 。证明：aA必有 i 使得 aAi，由定义知aRa，故 R自反。a,b A ，若 aRb ，则 a,b Ai，即 b,a Ai，所以 bRa，故 R对称。a,b,c A，若 aRb 且 bRc，则 a,b Ai及 b,c Aj。因为 i j 时 AiAj=，故 i=j ，即 a,b,c Ai，所以 aRc，故 R传递。总之 R是 A上的等价关系。七、若 f:A B是双射，则f-1:BA是双射（ 15 分） 。证明 : 对任意的xA，因为 f 是从 A到 B的函数，故存在yB，使 f ，f-1。所以 ,f-1是满射。对任意的xA ，若存在y1,y2B，使得 f-1且 f-1, 则有 f 且f 。因为 f 是函数，则y1=y2。所以， f-1是单射。因此 f-1是双射。八、设 是群， 和是的子群，证明：若ABG，则 AG 或BG（10 分）。证明假设 AG 且 BG，则存在 a A，aB，且存在 bB，bA（否则对任意的aA，a B，从而 AB，即 ABB，得 BG，矛盾。）对于元素a* b G，若 a* b A，因 A 是子群， a-1A，从而 a-1 * (a*b) bA，所以矛盾，故a* b A。同理可证a* b B，综合有 a* b ABG。综上所述，假设不成立，得证AG 或 BG。九、若无向图G 是不连通的，证明G 的补图G是连通的（ 10 分） 。证明设无向图G 是不连通的，其k 个连通分支为1G、2G、kG。任取结点u、vG，若u和v不在图 G 的同一个连通分支中，则u，v 不是图 G 的边，因而 u，v是图G的边；若u和v在图 G 的同一个连通分支中，不妨设其在连通分支iG（1ik）中，在不同于iG的另一连通分支上取一结点w，则u，w 和w，v 都不是图G 的边，因而 u，w 和w，v 都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 29 页 - - - - - - - - - 离散数学试题（ B卷答案 5）一、 （10 分）求命题公式(PQ)(PR)的主合取范式。解：(PQ)(PR)（(PQ)(PR)）（(PR)(PQ)）（(P Q)(PR)）（ (P R)(PQ)）(PQ)(PR) (PR)（ Q P）（ QR ）(PQR)(PQR)（PQ R）（PQR ）M1M3M4M5二、 （8 分）叙述并证明苏格拉底三段论解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化： 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 三、 （8 分）已知A、B、C是三个集合，证明A(BC)=(AB)(A C) 证明： x A（ BC） x Ax（B C） x A（xBxC）（ x AxB）（ x AxC） x（AB） x AC x（AB）（ AC）A（ BC）=（AB）（ A C）四、 （10 分）已知 R和 S是非空集合A上的等价关系， 试证： 1）RS是 A上的等价关系；2）对 a A ，aR S=aRaS。解：xA，因为 R和 S是自反关系，所以 R、 S，因而 RS，故 RS是自反的。x、yA，若 RS，则 R、 S，因为 R和 S是对称关系，所以名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 因 R 、 S，因而 RS，故 RS是对称的。x、y、zA，若 RS且 RS，则 R、 S且 R、 S，因为 R和 S是传递的，所以因 R、 S，因而 RS，故 RS是传递的。总之 R S是等价关系。2）因为 xaR S RS R S x aRx aS x aRaS 所以 aR S=aRaS。五、 (10 分) 设 A a，b， c，d，R 是 A 上的二元关系，且R，求 r( R) 、s( R) 和 t( R) 。解r( R) RIA ， s( R) RR-1， ， R2， R3， R4， R2t( R) iiR1， ， 六、 (15 分) 设 A 、B、C、D是集合， f 是 A到 B的双射， g 是 C到 D的双射，令h：ACBD且 A C，h()。证明 h 是双射。证明： 1）先证 h 是满射。 BD，则 bB，dD ，因为 f 是 A到 B的双射， g 是 C到 D的双射，所以存在a A， c C，使得f(a)=b ， f(c)=d，亦即存在 AC，使得h() ，所以 h 是满射。2）再证 h 是单射。 、 A C，若h() h()，则 ，所以 f(a1) f(a2)，g(c1) g(c2) ，因为 f 是 A到 B 的双射， g 是 C到 D的双射，所以a1a2，c1c2，所以 ，所以 h 是单射。综合 1）和 2） ，h 是双射。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - 七、 (12 分) 设是群， H 是 G的非空子集，证明是的子群的充要条件是若 a，b H，则有 a*b-1H。证明：a,b H有 b-1H，所以 a*b-1H。aH ，则 e=a*a-1H a-1=e*a-1H a,b H及 b-1H，a*b=a* （b-1）-1H H G且 H, * 在 H上满足结合律 是的子群。八、 （10 分）设 G=是简单的无向平面图，证明 G至少有一个结点的度数小于等于5。解：设 G的每个结点的度数都大于等于6，则 2|E|=d(v) 6|V| ，即|E| 3|V| ，与简单无向平面图的|E| 3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=,A=a,b,c,*的运算表为： ( 写过程， 7 分) （1）G是否为阿贝尔群？（2）找出 G的单位元；（3）找出 G的幂等元（ 4）求 b 的逆元和 c 的逆元解： （1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c) (a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以 G是阿贝尔群（2）因为 a*a=a a*b=b*a=b a*c=c*a=c 所以 G的单位元是a （3）因为 a*a=a 所以 G的幂等元是a （4）因为 b*c=c*b=a ，所以 b 的逆元是 c 且 c 的逆元是 b 十、 (10 分) 求叶的权分别为2、4、6、8、10、12、14 的最优二叉树及其权。解：最优二叉树为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 29 页 - - - - - - - - - 权 148 离散数学试题（ B 卷答案 6）一、 （20 分）用公式法判断下列公式的类型：(1)(PQ)(PQ) (2)(P Q)(P(QR) 解： （1）因为 (PQ)(PQ)(PQ) (PQ)( PQ) (PQ)(PQ)(PQ) 1m2m3m0M所以，公式 (PQ)(PQ)为可满足式。（2）因为 (P Q)(P(QR)( PQ)(PQR) (PQ)(PQR) (PQP)(PQQ)(PQR) (PQ)(PQR) (PQ(RR)(PQR) (PQR)(PQR)(PQR) 0M1M2m3m4m5m6m7m所以，公式 (P Q)(P(QR)为可满足式。二、 （15 分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 29 页 - - - - - - - - - 又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。解：论域：所有人的集合。Q(x)：x是勤奋的；H(x)：x是身体健康的；S(x)：x是科学家；C (x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为：x(S(x)Q(x) ，x(Q(x) H(x)C (x) ，x(S(x) H(x)x( C (x)F(x) 下面给出证明：(1)x(S(x)H(x) P (2)S(a)H(a) T(1)，ES (3)x(S(x)Q(x) P (4)S(a)Q(a) T(1) ，US (5)S(a) T(2)，I (6)Q(a) T(4)(5) ，I (7)H(a) T(2) ，I (8)Q(a)H(a) T(6)(7) ，I (9)x(Q(x)H(x)C (x) P (10)Q(a)H(a)C (a) T(9) ，Us (11) C (a) T(8)(10) ，I (12)xC (x) T(11) ，EG (13)x( C (x)F(x) T(12) ，I 三、 （10 分）设 A，1，1 ，B0 ，0 ，求 P(A)、P(B)0 、P(B)B。解P(A) ，1 ，1，1，1 ，1，1 ，1，1 P(B)0 ，0 ，0 ，0 ，0 0 ，0 ，0，0，0 P(B)B，0 ，0，0 ，00 ，0 ，0，0 ，0 ，0 四、 （15 分）设 R 和 S是集合 A 上的任意关系，判断下列命题是否成立？(1)若 R 和 S是自反的，则R*S也是自反的。(2)若 R 和 S是反自反的，则R* S也是反自反的。(3)若 R 和 S是对称的，则R*S也是对称的。(4)若 R 和 S是传递的，则R*S也是传递的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 29 页 - - - - - - - - - (5)若 R 和 S是自反的，则RS是自反的。(6)若 R 和 S是传递的，则RS是传递的。解(1)成立。对任意的aA，因为 R 和 S 是自反的，则 R，S，于是 R* S，故 R*S也是自反的。(2)不成立。例如，令A1，2 ，R ，S ，则 R 和 S是反自反的，但 R*S 不是反自反的。(3)不成立。例如，令A1，2，3，R ， ，S， ，则 R 和 S是对称的，但R*S， 不是对称的。(4)不成立。例如，令A1，2，3，R ， ，S，则 R 和 S 是传递的，但R*S， 不是传递的。(5)成立。对任意的aA，因为 R 和 S是自反的，则 R，S，于是 R S ，所以 RS是自反的。五、 （15 分）令 Xx1，x2， xm ，Yy1，y2， yn。问(1)有多少个不同的由X 到 Y 的函数？(2)当 n、m 满足什么条件时，存在单射，且有多少个不同的单射？(3)当 n、m 满足什么条件时，存在双射，且有多少个不同的双射？解(1)由于对 X 中每个元素可以取Y中任一元素与其对应，每个元素有n 种取法，所以不同的函数共nm个。(2)显然当 |m|n|时，存在单射。由于在Y 中任选 m 个元素的任一全排列都形成X 到Y 的不同的单射，故不同的单射有mnCm!n(n 1)(nm 1)个。(3)显然当 |m|n|时，才存在双射。此时Y 中元素的任一不同的全排列都形成X 到 Y的不同的双射，故不同的双射有m!个。六、 （5 分）集合 X 上有 m 个元素， 集合 Y 上有 n个元素，问X 到 Y 的二元关系总共有多少个？解X 到 Y 的不同的二元关系对应XY 的不同的子集，而XY的不同的子集共有个mn2，所以 X 到 Y 的二元关系总共有mn2个。七、 （10 分）若 是群，则对于任意的a、bG，必有惟一的xG 使得 a* xb。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 - - - - - - - - - 证明设 e 是群 的幺元。 令 xa1*b，则 a*xa*( a1* b)(a*a1)* b e* bb。所以， xa1*b 是 a*xb 的解。若 x G 也是 a*xb 的解，则 x e*x (a1*a)* x a1*( a*x )a1*bx。所以， xa1*b 是 a*xb 的惟一解。八、 （10 分）给定连通简单平面图G，且 |V| 6，|E| 12。证明：对任意 fF，d(f)3。证明由偶拉公式得|V| |E|F|2，所以 |F|2|V|E|8，于是Fffd)(2|E|24。若存在fF，使得d(f) 3，则 3|F|2|E|24，于是 |F| 8，与 |F|8 矛盾。故对任意 fF，d(f)3。离散数学试题（B 卷答案 7）一、 （15 分）设计一盏电灯的开关电路，要求受3 个开关 A、B、C 的控制：当且仅当 A 和 C 同时关闭或B 和 C 同时关闭时灯亮。设F 表示灯亮。(1)写出 F 在全功能联结词组中的命题公式。(2)写出 F 的主析取范式与主合取范式。解(1)设 A：开关 A 关闭； B：开关 B 关闭； C：开关 C 关闭； F(AC) (BC)。在全功能联结词组 中：A(AA)A A AC( AC)( A C)(A C) (A C)AB(AB)( A A)(B B)( A A) (B B) 所以F(A C) (A C)(B C) (B C) (A C) (A C)(A C) (A C)(B C) (B C) (B C) (B C) (2)F(AC)(BC) (A(BB)C)(AA)BC) (ABC)(ABC)(A BC)(ABC) 3m5m7m主析取范式0M1M2M4M6M主合取范式二、 （10 分）判断下列公式是否是永真式？(1)( xA(x)xB(x)x(A(x)B(x)。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 29 页 - - - - - - - - - (2)(xA(x)xB(x)x(A(x)B(x)。解(1)( xA(x)xB(x)x(A(x)B(x) (xA(x) xB(x)x(A(x)B(x) (xA(x) xB(x) x(A(x)B(x) ( xA(x)xB(x) xA(x) xB(x) ( xA(x)x A(x)xB(x)(xB(x) xA(x) xB(x) x(A(x)A(x) xB(x) T 所以， ( xA(x)xB(x)x(A(x)B(x)为永真式。(2)设论域为 1，2，令 A(1)T；A(2)F；B(1)F；B(2)T。则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真；而由于A(1)B(1)为假，所以x(A(x)B(x)也为假，因此公式(xA(x)xB(x)x(A(x)B(x)为假。该公式不是永真式。三、 （15 分）设 X 为集合， AP(X) X且 A，若|X| n，问(1)偏序集 是否有最大元？(2)偏序集 是否有最小元？(3)偏序集 中极大元和极小元的一般形式是什么？并说明理由。解偏序集 不存在最大元和最小元，因为n2。考察 P(X)的哈斯图，最底层的顶点是空集，记作第0 层，由底向上，第一层是单元集，第二层是二元集，由 |X|n，则第 n1 层是 X 的 n1 元子集，第n 层是 X。偏序集 与偏序集 相比，恰好缺少第0 层和第 n 层。因此 的极小元就是 X 的所有单元集，即x，xX；而极大元恰好是比X 少一个元素，即X x ，xX。四、 （10 分）设 A1，2，3，4，5， R 是 A 上的二元关系，且R， ，求 r(R)、s(R)和 t(R)。解r(R)RIA， s(R)RR1， ， R2， 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - R3， R4，R2t(R)1iRi， 。五、 （10 分）设函数g：AB，f：BC，(1)若 f g 是满射，则f 是满射。(2)若 f g 是单射，则g 是单射。证明因为 g：AB，f：BC，由定理 5.5 知，f g 为 A到 C 的函数。(1)对任意的zC， 因 f g 是满射，则存在 xA 使 f g(x)z，即 f(g(x)z。 由 g： AB可知 g(x)B，于是有 yg(x)B，使得 f(y) z。因此， f 是满射。(2)对任意的x1、x2A，若 x1x2，则由 f g 是单射得f g(x1)f g(x2)，于是 f(g(x1)f(g(x2)，必有 g(x1)g(x2)。所以， g 是单射。六、 （10 分）有幺元且满足消去律的有限半群一定是群。证明设 是一个有幺元且满足消去律的有限半群，要证是群，只需证明 G 的任一元素a 可逆。考虑 a，a2， ak，。因为G 只有有限个元素，所以存在kl，使得 akal。令mkl，有 al* eal*am，其中 e 是幺元。由消去率得ame。于是，当m1 时， ae，而 e 是可逆的；当m1 时， a* am-1am-1* ae。从而a是可逆的，其逆元是am-1。总之， a是可逆的。七、 （20 分）有向图G 如图所示，试求：(1)求 G 的邻接矩阵 A。(2)求出 A2、A3和 A4，v1到 v4长度为 1、2、3 和 4 的路有多少？(3)求出 ATA 和 AAT，说明 ATA 和 AAT中的第 (2，2)元素和第 (2，3)元素的意义。(4)求出可达矩阵P。(5)求出强分图。解(1)求 G 的邻接矩阵为：0010101011001010A名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 - - - - - - - - - (2)由于11001110102011102A10202120221021203A2210323031403