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

离散数学试题离散数学试题(B(B 卷答案卷答案 1 1）一、证明题（10 分）1)(P(QR)(QR)(PR)R证明:左端(PQR)(QP)R)(PQ)R)(QP)R)(PQ)R)(QP)R)(PQ)(QP)R(PQ)(PQ)RTR(置换)R2)x(A(x)B(x)xA(x)xB(x)证明 ：x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)二、求命题公式(P(QR)(PQR)的主析取范式和主合取范式（10 分）。证明：(P(QR)(PQR)(P(QR)(PQR)（P(QR)）(PQR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m0m1m2m7M3M4M5M6三、推理证明题（10 分）1）CD，(CD)E，E(AB)，(AB)(RS)RS证明：(1)(CD)E P(2)E(AB)P(3)(CD)(AB)T(1)(2)，I(4)(AB)(RS)P(5)(CD)(RS)T(3)(4)，I(6)CD P(7)RS T(5)，I 2)x(P(x)Q(y)R(x)，xP(x)Q(y)x(P(x)R(x)证明(1)xP(x)P(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，|AC|=6，|BC|=5，|ABC|=2。先求|AB|。6=|（AC）B|=|（AB）（BC）|=|（AB）|+|（BC）|-|ABC|=|（AB）|+5-2，|（AB）|=3。于是|ABC|=12+6+14-6-5-3+2=20。不会打这三种球的人数 25-20=5。五、已知 A、B、C 是三个集合，证明 A-(BC)=(A-B)(A-C)（10 分）。证明：x A-（BC）x Ax（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=x2R*S=|x，yNy=x2+1S*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)=，R2=R5=，R3=，R4=，t(R)=，八、证明整数集 I 上的模 m 同余关系 R=|xy(mod m)是等价关系。其中，xy(mod m)的含义是 x-y 可以被 m 整除（15 分）。证明：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 有逆函数（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)(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)yQ(y)二、求命题公式(PQ)(PQ)的主析取范式和主合取范式（10 分）解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PPQ)(QPQ)(PQ)M1m0m2m3三、推理证明题（10 分）1)(P(QS)(RP)QRS证明：(1)R(2)RP(3)P(4)P(QS)(5)QS(6)Q(7)S(8)RS2)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()T(3)，ESc(5)B()C()T(4)，USbc(6)A(a)B()T(2)，USb(7)A(a)C()T(5)(6)，Ic(8)xA(x)C()T(7)，UGc(9)xA(x)yC(y)T(8)，EG四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15 分）。解 设 P：今天天气好，Q：考试准时进行，A(e)：e 提前进入考场，个体域：考生的集合，则命题可符号化为：PxA(x)，xA(x)QQP。(1)PxA(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 AxB）（x AxC）x（AB）x AC x（AB）（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 是对称的。对任意的、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，证明：如果 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。离散数学试题(B 卷答案 3）一、（10 分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)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)(APQ)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，求xy（x+y=4）的真值。解：xy（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=，求 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 中的运算“”为 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，存在单位元 u。4）aG，ax=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 如下：01010111110010011111A=00011P=1111100000000001000011111十、（10 分）求叶的权分别为 2、4、6、8、10、12、14 的最优二叉树及其权。解：最优二叉树为权(2+4)4+63+122+(8+10)3+142148离散数学试题(B 卷答案 4）一、证明题（10 分）1)(PQ)(P(QR)(PQ)(PR)T证明:左端(PQ)(P(QR)(PQ)(PR)(摩根律)(PQ)(PQ)(PR)(PQ)(PR)(分配律)(PQ)(PR)(PQ)(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)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PPQ)(QPQ)(PQ)M1m0m2m3三、推理证明题（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 CP2)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 分）证明：x A（BC）x Ax（BC）x A（xBxC）（x AxB）（x AxC）x（AB）x AC x（AB）（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,bA，若 aRb，则 a,bAi，即 b,aAi，所以 bRa，故 R 对称。a,b,cA，若 aRb 且 bRc，则 a,bAi及 b,cAj。因为 ij 时 AiAj=，故i=j，即 a,b,cAi，所以 aRc，故 R 传递。总之 R 是 A 上的等价关系。七、若 f:AB 是双射，则 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，则存在 aA，aB，且存在 bB，bA（否则对任意的aA，aB，从而 AB，即 ABB，得 BG，矛盾。）对于元素 a*bG，若 a*bA，因 A 是子群，a-1A，从而 a-1*(a*b)b A，所以矛盾，故 a*bA。同理可证 a*bB，综合有 a*bABG。综上所述，假设不成立，得证 AG 或 BG。九、若无向图 G 是不连通的，证明 G 的补图是连通的（10 分）。G证明 设无向图 G 是不连通的，其 k 个连通分支为、。任取结点、1G2GkGuG，若和 不在图 G 的同一个连通分支中，则，不是图 G 的边，因而，是vuvuvuv图的边；若和 在图 G 的同一个连通分支中，不妨设其在连通分支（1）GuviGik中，在不同于的另一连通分支上取一结点，则，和，都不是图 G 的边，iGwuwwv，因而，和，都是的边。综上可知，不管那种情况，和 都是可达的。uwwvGuv由和 的任意性可知，是连通的。uvG离散数学试题（离散数学试题（B B 卷答案卷答案 5 5）一、（10 分）求命题公式(PQ)(PR)的主合取范式。解：(PQ)(PR)（(PQ)(PR)）（(PR)(PQ)）（(PQ)(PR)）（(PR)(PQ)）(PQ)(PR)(PR)（QP）（QR）(PQR)(PQR)（PQR）（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)(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 和 S 是非空集合 A 上的等价关系，试证：1）RS 是 A 上的等价关系；2）对 aA，aRS=aRaS。解：xA，因为 R 和 S 是自反关系，所以R、S，因而RS，故 RS 是自反的。x、yA，若RS，则R、S，因为 R 和 S 是对称关系，所以因R、S，因而RS，故 RS 是对称的。x、y、zA，若RS 且RS，则R、S 且R、S，因为 R 和 S 是传递的，所以因R、S，因而RS，故 RS 是传递的。总之 RS 是等价关系。2）因为 xaRSRSRS xaRxaS xaRaS所以aRS=aRaS。五、(10 分)设 Aa，b，c，d，R 是 A 上的二元关系，且R，求 r(R)、s(R)和 t(R)。解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，六、(15 分)设 A、B、C、D 是集合，f 是 A 到 B 的双射，g 是 C 到 D 的双射，令h：ACBD 且AC，h()。证明 h 是双射。证明：1）先证 h 是满射。BD，则 bB，dD，因为 f 是 A 到 B 的双射，g 是 C 到 D 的双射，所以存在 aA，cC，使得 f(a)=b，f(c)=d，亦即存在AC，使得 h()，所以 h 是满射。2）再证 h 是单射。、AC，若 h()h()，则，所以 f(a1)f(a2)，g(c1)g(c2)，因为 f 是 A 到 B 的双射，g 是C 到 D 的双射，所以 a1a2，c1c2，所以，所以 h 是单射。综合 1）和 2），h 是双射。七、(12 分)设是群，H 是 G 的非空子集，证明是的子群的充要条件是若 a，bH，则有 a*b-1H。证明：a,bH 有 b-1H，所以 a*b-1H。aH，则 e=a*a-1H a-1=e*a-1H a,bH 及 b-1H，a*b=a*（b-1）-1HHG 且 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 的最优二叉树及其权。解：最优二叉树为权148 离散数学试题（B 卷答案 6）一、（20 分）用公式法判断下列公式的类型：(1)(PQ)(PQ)(2)(PQ)(P(QR)解：（1）因为(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)1m2m3m0M所以，公式(PQ)(PQ)为可满足式。（2）因为(PQ)(P(QR)(PQ)(PQR)(PQ)(PQR)(PQP)(PQQ)(PQR)(PQ)(PQR)(PQ(RR)(PQR)(PQR)(PQR)(PQR)0M1M2m3m4m5m6m7m所以，公式(PQ)(P(QR)为可满足式。二、（15 分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。解：论域：所有人的集合。()：是勤奋的；()：是身体健康的；()：QxxHxxSx是科学家；()：是事业获得成功的人；()：是事业半途而废的人；则推理xCxxFxx化形式为：()()，()()()，()()(xSxQxxQxHxCxxSxHxx()()CxFx下面给出证明：(1)()()PxSxHx(2)()()T(1)，ESSaHa(3)()()PxSxQx(4)()()T(1)，USSaQa(5)()T(2)，ISa(6)()T(4)(5)，IQa(7)()T(2)，IHa(8)()()T(6)(7)，IQaHa(9)()()()PxQxHxCx(10)()()()T(9)，UsQaHaCa(11)()T(8)(10)，ICa(12)()T(11)，EGxCx(13)()()T(12)，IxCxFx三、（10 分）设 A，1，1，B0，0，求 P(A)、P(B)0、P(B)B。解 P(A)，1，1，1，1，1，1，1，1P(B)0，0，0，0，00，0，0，0，0P(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 也是传递的。(5)若 R 和 S 是自反的，则 RS 是自反的。(6)若 R 和 S 是传递的，则 RS 是传递的。解 (1)成立。对任意的，因为 R 和 S 是自反的，则aAR，S，于是R*S，故 R*S 也是自反的。aaaaaa(2)不成立。例如，令1，2，R，S，则 R 和 S 是反自A反的，但 R*S不是反自反的。(3)不成立。例如，令1，2，3，R，AS，则 R 和 S 是对称的，但 R*S，不是对称的。(4)不成立。例如，令1，2，3，R，AS，则 R 和 S 是传递的，但R*S，不是传递的。(5)成立。对任意的，因为 R 和 S 是自反的，则aAR，S，于是RS，所以 RS 是自反的。aaaaaa五、（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 的不同的单射，故不同的单射有m!n(n1)(nm1)个。mnC(3)显然当|m|n|时，才存在双射。此时 Y 中元素的任一不同的全排列都形成 X 到Y 的不同的双射，故不同的双射有 m!个。六、（5 分）集合 X 上有 m 个元素，集合 Y 上有 n 个元素，问 X 到 Y 的二元关系总共有多少个？解 X 到 Y 的不同的二元关系对应 XY 的不同的子集，而 XY 的不同的子集共有个，所以 X 到 Y 的二元关系总共有个。mn2mn2七、（10 分）若是群，则对于任意的 a、bG，必有惟一的 xG 使得a*xb。证明 设 e 是群的幺元。令 xa1*b，则 a*xa*(a1*b)(a*a1)*be*bb。所以，xa1*b 是 a*xb 的解。若 xG 也是 a*xb 的解，则 xe*x(a1*a)*xa1*(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，于是2|E|24。若存在 fF，使得 d(f)3，则 3|F|2|E|24，于是|F|8，与Fffd)(|F|8 矛盾。故对任意 fF，d(f)3。离散数学试题（离散数学试题（B B 卷答案卷答案 7 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)AAAC(AC)(AC)(AC)(AC)AB(AB)(AA)(BB)(AA)(BB)所以F(AC)(AC)(BC)(BC)(AC)(AC)(AC)(AC)(BC)(BC)(BC)(BC)(2)F(AC)(BC)(A(BB)C)(AA)BC)(ABC)(ABC)(ABC)(ABC)主析取范式3m5m7m 主合取范式0M1M2M4M6M二、（10 分）判断下列公式是否是永真式？(1)(xA(x)xB(x)x(A(x)B(x)。(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)xA(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 少一个元素，即 Xx，xX。四、（10 分）设 A1，2，3，4，5，R 是 A 上的二元关系，且R，求 r(R)、s(R)和 t(R)。解 r(R)RIA，s(R)RR1，R2，R3，R4，R2t(R)Ri，。五、（10 分）设函数 g：AB，f：BC，(1)若 fg 是满射，则 f 是满射。(2)若 fg 是单射，则 g 是单射。证明 因为 g：AB，f：BC，由定理 5.5 知，fg 为 A 到 C 的函数。(1)对任意的 zC，因 fg 是满射，则存在 xA 使 fg(x)z，即 f(g(x)z。由g：AB 可知 g(x)B，于是有 yg(x)B，使得 f(y)z。因此，f 是满射。(2)对任意的 x1、x2A，若 x1x2，则由 fg 是单射得 fg(x1)fg(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(2)由于 11001110102011102A10202120221021203A22103230314032304A所以 v1到 v4长度为 1、2、3 和 4 的路的个数分别为 1、1、2、3。(3)由于 3120110021300000AAT1201121201211212TAA再由定理 10.19 可知，所以 ATA 的第(2，2)元素为 3，表明那些边以为终结点且具2v有不同始结点的数目为 3，其第(2，3)元素为 0，表明那些边既以为终结点又以为终2v3v结点，并且具有相同始结点的数目为 0。AAT中的第(2，2)元素为 2，表明那些边以为2v始结点且具有不同终结点的数目为 2，其第(2，3)元素为 1，表明那些边既以为始结点2v又以为始结点，并且具有相同终结点的数目为 1。3v(4)因为+4324AAAAB0010101011001010110011101020111010202120221021202210323031403230，所以求可达矩阵为。43407470747014701110111011101110P(5)因为，所以，TPP1110111011101110111111111111000011101110111000001v2v3v4v构成 G 的强分图。离散数学试题（B 卷答案 8）一、（10 分）证明(PQ)(PR)(QS)SR证明 因为 SRRS，所以，即要证(PQ)(PR)(QS)RS。(1)R 附加前提(2)PR P(3)P T(1)(2)，I(4)PQ P(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)SR T(8)，E二、（15 分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设 P(e)：e 是考生，Q(e)：e 将有所作为，A(e)：e 是勤奋的，B(e)：e 是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)B(x)，x(A(x)Q(x)，x(P(x)Q(x)x(P(x)B(x)。(1)x(P(x)Q(x)P(2)x(P(x)Q(x)T(1)，E(3)x(P(x)Q(x)T(2)，E(4)P(a)Q(a)T(3)，ES(5)P(a)T(4)，I(6)Q(a)T(4)，I(7)x(P(x)(A(x)B(x)P(8)P(a)(A(a)B(a)T(7)，US(9)A(a)B(a)T(8)(5)，I(10)x(A(x)Q(x)P(11)A(a)Q(a)T(10)，US(12)A(a)T(11)(6)，I(13)B(a)T(12)(9)，I(14)P(a)B(a)T(5)(13)，I(15)x(P(x)B(x)T(14)，EG三、（10 分）某班有 25 名学生，其中 14 人会打篮球，12 人会打排球，6 人会打篮球和排球，5 人会打篮球和网球，还有 2 人会打这三种球。而 6 个会打网球的人都会打另外一种球，求不会打这三种球的人数。解 设 A、B、C 分别表示会打排球、网球和篮球的学生集合。则：|A|12，|B|6，|C|14，|AC|6，|BC|5，|ABC|2，|(AC)B|6。因为|(AC)B|(AB)(BC)|(AB)|(BC)|ABC|(AB)|526，所以|(AB)|3。于是|ABC|12614653220，25205。故，不会打这三种球的共 5 人。|CBA四、（10 分）设 A1、A2和 A3是全集 U 的子集，则形如Ai(Ai为 Ai或)的集合称31iiA为由 A1、A2和 A3产生的小项。试证由 A1、A2和 A3所产生的所有非空小项的集合构成全集 U 的一个划分。证明 小项共 8 个，设有 r 个非空小项 s1、s2、sr(r8)。对任意的 aU，则 aAi或 a，两者必有一个成立，取 Ai为包含元素 a 的 AiiA或，则 aAi，即有 asi，于是 Usi。又显然有siU，所以 Usi。iA31iri 1ri 1ri 1ri 1任取两个非空小项 sp和 sq，若 spsq，则必存在某个 Ai和分别出现在 sp和 sq中，iA于是 spsq。综上可知，s1，s2，sr是 U 的一个划分。五、（15 分）设 R 是 A 上的二元关系，则：R 是传递的R*RR。证明 (5)若 R 是传递的，则R*Rz(xRzzSy)xRccSy，由 R 是传递的得 xRy，即有R，所以 R*RR。反之，若 R*RR，则对任意的 x、y、zA，如果 xRz 且 zRy，则R*R，于是有R，即有 xRy，所以 R 是传递的。六、（15 分）若 G 为连通平面图，则 nmr2，其中，n、m、r 分别为 G 的结点数、边数和面数。证明 对 G 的边数 m 作归纳法。当 m0 时，由于 G 是连通图，所以 G 为平凡图，此时 n1，r1，结论自然成立。假设对边数小于 m 的连通平面图结论成立。下面考虑连通平面图 G 的边数为 m 的情况。设 e 是 G 的一条边，从 G 中删去 e 后得到的图记为 G，并设其结点数、边数和面数分别为 n、m和 r。对 e 分为下列情况来讨论：若 e 为割边，则 G有两个连通分支 G1和 G2。Gi的结点数、边数和面数分别为ni、mi和 ri。显然 n1n2nn，m1m2mm1，r1r2r1r1。由归纳假设有 n1m1r12，n2m2r22，从而(n1n2)(m1m2)(r1r2)4，n(m1)(r1)4，即 nmr2。若 e 不为割边，则 nn，mm1，rr1，由归纳假设有 nmr2，从而n(m1)r12，即 nmr2。由数学归纳法知，结论成立。七、（10 分）设函数 g：AB，f：BC，则：(1)fg 是 A 到 C 的函数；(2)对任意的 xA，有 fg(x)f(g(x)。证明 (1)对任意的 xA，因为 g：AB 是函数，则存在 yB 使g。对于yB，因 f：BC 是函数，则存在 zC 使f。根据复合关系的定义，由g 和f 得g*f，即fg。所以 DfgA。对任意的 xA，若存在 y1、y2C，使得、fgg*f，则存在 t1使得g 且f，存在 t2使得g 且f。因为 g：AB 是函数，则 t1t2。又因 f：BC 是函数，则 y1y2。所以 A 中的每个元素对应 C 中惟一的元素。综上可知，fg 是 A 到 C 的函数。(2)对任意的 xA，由 g：AB 是函数，有g 且 g(x)B，又由 f：BC是函数，得f，于是g*ffg。又因 fg 是 A 到 C 的函数，则可写为 fg(x)f(g(x)。八、（15 分）设是的子群，定义 R|a、bG 且 a1*bH，则 R 是 G 中的一个等价关系，且aRaH。证明 对于任意 aG，必有 a1G 使得 a1*aeH，所以R。若R，则 a1*bH。因为 H 是 G 的子群，故(a1*b)1b1*aH。所以R。若R，R，则 a1*bH，b1*cH。因为 H 是 G 的子群，所以(a1*b)*(b1*c)a1*cH，故R。综上可得，R 是 G 中的一个等价关系。对于任意的 baR，有R，a1*bH，则存在 hH 使得a1*bh，ba*h，于是 baH，aRaH。对任意的 baH，存在 hH 使得ba*h，a1*bhH，R，故 aHaR。所以，aRaH。离散数学试题（离散数学试题（B B 卷答案卷答案 9 9）一、（10 分）证明(PQAC)(APQC)(A(PQ)C。证明：(PQAC)(A