1、（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）|
2、+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=x2 R*S=| x，yNy=
3、x2+1S*R=| x，yNy=（x+1）2，R 1，2=，S1，2=1，4。七、设 R=b，cc，a，求 r（R）、s（R）和 t（R） （15 分）。r（R）=b，bc，c s（R）=c，ba，cR2= 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）
4、，即 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）1）（PQ）（P（QR）（PQ）（PR）T 左端（PQ）（P（QR）（PQ）（PR）（摩
5、根律） （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）M1m0m2m31）（P（QS）（RP）QRS（1）R （2）RP （3）P （4）P（QS） （5）QS（6）Q（7）S（8）RS2） x（A
6、（x）yB（y），x（B（x）yC（y） xA（x）yC（y） 。（1）x（A（x）yB（y） P（2）A（a）yB（y）（3）x（B（x）yC（y）（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）四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15 分）。解 设 P：今天天气好，Q：考试准时进行，A（e）：e 提前
7、进入考场，个体域：考生的集合，则命题可符号化为：PxA（x），xA（x）Q QP。（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）（ xAxB）（x AxC） x（AB）x AC x（AB）（AC）A（BC）=（AB）（AC）六、A= x1,x2,x3 ，B= y1,y2，R=,x3, y2，
8、求其关系矩阵及关系图（10 分）。2,12,52,43,44,45,2，求 r（R）、s（R）和 t（R），并作出它们及 R 的关系图（15 分）。1,12,2,5,51,24,24,3R2=R5=5,4R3=R4= t（R）=x2，y2RR1 且R2，证明 R 是 AB 上的等价关系（10 分）。证明 对任意的AB，由 R1 是 A 上的等价关系可得R1，由 R2 是B上的等价关系可得R2。再由 R 的定义，有R，所以 R 是自反的。对任意的、B，若R，则R1 且y，v由 R1 对称得R1，由 R2 对称得再由 R 的定义，有R，即且，则R2，v，t由R1、R1 及R1 的传递性得R1，由R
9、2、R2 及 R2 的传递性得R1。再由R 的定义，有，所以 R 是传递的。综上可得，R 是 AB 上的等价关系。九、设 f：AB，g：BC，h：CA，证明：如果 h g fIA，f h gIB，g f hIC，则f、g、h 均为双射，并求出 f1、g1 和 h1（10 分）。解 因 IA 恒等函数，由 h g fIA 可得 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，得 g1f h；由 g f
10、 hIC，得 h1g f。离散数学试题（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
11、）（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），由于上述过程可逆，故
12、 P（A）P（B）=P（AB）六、（10 分）已知 A=1，2，3，4，5和 R=2，12，33，45，4， 求 r（R）、s（R）和 t（R）。r（R）2，23，34，45，5s（R）=4，34，5t（R）1，31，4七、（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）R，由 f（，通过计算可得 x=（p+q）/2；y=（p-q）/2；从而的原象存在，f 是满射。八、（10 分）是个群，uG，定义 G 中的运算“
13、”为 ab=a*u-1*b，对任意a，bG，求证：G， 也是个群。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=3，55，1，求 D 的邻接距阵 A 和可达距阵 P。1）D 的邻接距阵 A
14、 和可达距阵 P 如下：A=P=十、（10 分）求叶的权分别为 2、4、6、8、10、12、14 的最优二叉树及其权。最优二叉树为权（2+4）4+63+122+（8+10）3+142148离散数学试题（B 卷答案 4） 左端（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）（
15、PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ） （PPQ）（QPQ）（PQ）M1m0m2m3 三、推理证明题（10 分）（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 的正方形内任意放置九个点，证明其中必
16、存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过 1/8（10 分）。把边长为 1 的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即 1/8。六、=A1，A2，An是集合 A 的一个划分，定义|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
17、=j，即 a,b,cAi，所以 aRc，故 R 传递。总之 R 是 A 上的等价关系。七、若 f:AB 是双射，则 f-1:BA 是双射（15 分）。对任意的 xA，因为 f 是从 A 到 B 的函数，故存在 yB，使x,yf，f-1。所以,f-1 是满射。对任意的 xA，若存在 y1,y2B，使得f-1 且f-1,则有x,y1f 且f。因为 f 是函数，则 y1=y2。所以，f-1 是单射。因此 f-1 是双射。八、设是群，和是的子群，证明：若 ABG，则 AG或 BG（10 分）。证明 假设 AG 且 BG，则存在 aA，aB，且存在 bB，bA（否则对任意的aA，aB，从而 AB，即 A
18、BB，得 BG，矛盾。）对于元素 a*bG，若 a*bA，因 A 是子群，a-1A，从而 a-1 * （a*b）b A，所以矛盾，故 a*bA。同理可证 a*bB，综合有 a*bABG。综上所述，假设不成立，得证 AG 或 BG。九、若无向图 G 是不连通的，证明 G 的补图G 是连通的（10 分）。证明 设无向图 G 是不连通的，其 k 个连通分支为G1 、G2 、Gk 。任取结点u 、v G，若u 和v 不在图 G 的同一个连通分支中，则 u ， v 不是图 G 的边，因而 u ， v 是图G 的边；若u 和v 在图 G 的同一个连通分支中，不妨设其在连通分支Gi （1 i k ）中，在不同于Gi 的另一连通分支上取一结点 w ，则 u ， w 和 w ， v 都不是图 G 的边，因而 u ， w 和 w ， v 都是G 的边。综上可知，不管那种情况， u 和v 都是可达的。由u 和v 的任意性可知， G 是连通的。离散数学试题（B 卷答案 5）一、（10 分）求命题公式（PQ）（PR）的主合取范式。（PQ）（PR）（PQ）（PR）（PR）（PQ）（PQ）（PR）（PR）（PQ）（PQ）（PR）（PR）（QP）（QR）（PQR）（PQR）（PQR）（PQR）
