离散数学期末考试试题及答案
离散数学试题(B卷答案1）
一、证明题（10分）
1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R
证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)
?((?P∧?Q)∧R))∨((Q∨P)∧R)
?(?(P∨Q)∧R)∨((Q∨P)∧R)
?(?(P∨Q)∨(Q∨P))∧R
?(?(P∨Q)∨(P∨Q))∧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∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。
证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))
?（?P∧(?Q∨?R)）∨(P∧Q∧R)
?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)
?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R)
?m0∨m1∨m2∨m7
?M3∨M4∨M5∨M6
三、推理证明题（10分）
1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P
(2) ?E→(A∧?B) P
(3) (C∨D)→(A∧?B) T(1)(2)，I
(4) (A∧?B)→(R∨S) P
(5) (C∨D)→(R∨S) 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
(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∩B∩C|=2。
先求|A∩B|。
∵6=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）|-|A∩B∩C|=|（A∩B）|+5-2，∴|（A∩B）|=3。
于是|A∪B∪C|=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?（B∪C）
? x∈ A∧（x?B∧x?C）
?（x∈ A∧x?B）∧（x∈ A∧x?C）
? x∈（A-B）∧x∈（A-C）
? x∈（A-B）∩（A-C）
∴A-（B∪C）=（A-B）∩（A-C）
六、已知R、S是N上的关系，其定义如下：R={
解：R-1={
R*S={
S*R={
七、设R={
解：r(R)={
s(R)={
R2= R5={
R3={
R4={
t(R)={ c>} 八、证明整数集I上的模m同余关系R={ 证明：1）?x∈I，因为（x-x）/m=0，所以x≡x(mod m)，即xRx。 2）?x，y∈I，若xRy，则x≡y(mod m)，即（x-y）/m=k∈I，所以（y - x）/m=-k ∈I，所以y≡x(mod m)，即yRx。 3）?x，y，z∈I，若xRy，yRz，则（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v ∈I，因此xRz。 九、若f:A→B和g:B→C是双射，则（gf）-1=f-1g-1（10分）。 证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）-1：C→A。同理可推f-1g-1：C→A是双射。 因为 离散数学试题(B卷答案2） 一、证明题（10分） 1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T 证明: 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T (代入) 2) ?x?y(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)) ??x?P(x)∨?yQ(y) ???xP(x)∨?yQ(y) ?(?xP(x)→?yQ(y)) 二、求命题公式(?P→Q)→(P∨?Q) 的主析取范式和主合取范式（10分） 解：(?P→Q)→(P∨?Q)??(?P→Q)∨(P∨?Q) ??(P∨Q)∨(P∨?Q) ?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q) ?(P∨?Q) ?M1 ?m0∨m2∨m3 三、推理证明题（10分） 1)(P→(Q→S))∧(?R∨P)∧Q?R→S 证明：(1)R (2)?R∨P (3)P (4)P→(Q→S) (5)Q→S (6)Q (7)S (8)R→S 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提前进入考场，个体域：考生的集合，则命题可符号化为：?P→?x?A(x)，?xA(x)?Q Q→P。 (1)?P→?x?A(x) P (2)?P→??xA(x) T(1)，E (3)?xA(x)→P T(2)，E (4)?xA(x)?Q P (5)(?xA(x)→Q)∧(Q→?xA(x)) T(4)，E (6)Q→?xA(x) T(5)，I (7)Q→P T(6)(3)，I 五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分） 证明：∵x∈A∩（B∪C）?x∈A∧x∈（B∪C）?x∈A∧（x∈B∨x∈C）?（ x∈A ∧x∈B）∨（x∈A∧x∈C）?x∈（A∩B）∨x∈A∩C?x∈（A∩B）∪（A∩C）∴A∩（B ∪C）=（A∩B）∪（A∩C） 六、A={ x1,x2,x3 }，B={ y1,y2}，R={ 七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。 解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>, <3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R2=R5={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>} 八、设R1是A上的等价关系，R2是B上的等价关系，A≠?且B≠?。关系R满足：< 证明对任意的 对任意的 对任意的 综上可得，R是A×B上的等价关系。 九、设f：A→B，g：B→C，h：C→A，证明：如果h g f＝I A，f h g＝I B，g f h＝I C，则f、 g、h均为双射，并求出f－1、g－1和h－1（10分）。 解因I A恒等函数，由h g f＝I A可得f是单射，h是满射；因I B恒等函数，由f h g ＝I B可得g是单射，f是满射；因I C恒等函数，由g f h＝I C可得h是单射，g是满射。从而f、g、h均为双射。 由h g f＝I A，得f－1＝h g；由f h g＝I B，得g－1＝f h；由g f h＝I C，得h－1＝g f。 离散数学试题(B卷答案3） 一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程) 1)P→(P∨Q∨R) 2)?((Q→P)∨?P)∧(P∨R) 3)((?P∨Q)→R)→((P∧Q)∨R) 解：1)重言式；2)矛盾式；3)可满足式 二、（10分）求命题公式（P∨(Q∧R))→(P∨Q∨R)的主析取范式，并求成真赋值。 解：（P∨(Q∧R))→(P∨Q∨R)??(P∨(Q∧R))∨P∨Q∨R ??P∧(?Q∨?R)∨P∨Q∨R ?(?P∧?Q)∨(?P∧?R)∨(P∨Q)∨R ?(?(P∨Q)∨(P∨Q))∨(?P∧?R)∨R ?1∨((?P∧?R)∨R)?1 ?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 该式为重言式，全部赋值都是成真赋值。 三、（10分）证明 ((P∧Q∧A)→C)∧(A→(P∨Q∨C))?(A∧(P?Q))→C 证明：((P∧Q∧A)→C)∧(A→(P∨Q∨C))?(?(P∧Q∧A)∨C)∧(?A∨(P∨Q∨C)) ?((?P∨?Q∨?A)∨C)∧((?A∨P∨Q)∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((?P∨?Q∨?A)∧(?A∨P∨Q))→C ?(?(?P∨?Q∨?A)∨?(?A∨P∨Q))→C ?((P∧Q∧A)∨(A∧?P∧?Q))→C ?(A∧((P∧Q)∨(?P∧?Q)))→C ?(A∧((P∨?Q)∧(?P∨Q)))→C ?(A∧((Q→P)∧(P→Q)))→C ?(A∧(P?Q))→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）） ?（0∨0）∧（0∨1）?0∧1?0 五、（10分）对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B) 解：?x∈P(A)∩P(B)，x∈P(A)且x∈P(B)，有x?A且x?B，从而x?A∩B，x∈P(A∩ B)，由于上述过程可逆，故P(A)∩P(B)=P(A∩B) 六、（10分）已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。 解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2， 4>，<1，4>} 七、（10分）设函数f：R×R→R×R，R为实数集，f定义为：f( 1)证明f是双射。 解：1）? 2）? 八、（10分） ∈G，求证： 证明：1）?a，b∈G，a?b=a*u-1*b∈G，运算是封闭的。 2）?a，b，c∈G，（a?b）?c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a?（b?c），运算是可结合的。 3）?a∈G，设E为?的单位元，则a?E=a*u-1*E=a，得E=u，存在单位元u。 4）?a∈G，a?x=a*u-1*x=E，x=u*a-1*u，则x?a=u*a-1*u*u-1*a=u=E，每个元素都有逆元。 所以 九、（10分）已知：D= 4>，<3，5>，<5，1>}，求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+6×3+12×2+(8+10)×3+14×2＝148 离散数学试题(B卷答案4） 一、证明题（10分） 1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T 证明: 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q) ∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?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)) 二、求命题公式(?P→Q)→(P∨?Q) 的主析取范式和主合取范式（10分） 解：(?P→Q)→(P∨?Q)??(?P→Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3 三、推理证明题（10分） 1)(P→(Q→S))∧(?R∨P)∧Q?R→S 证明：（1）R 附加前提 (2)?R∨P P (3)P T(1)(2),I (4)P→(Q→S) P (5)Q→S T(3)(4),I (6)Q P (7)S T(5)(6),I (8)R→S CP 2) ?x(P(x)∨Q(x))，?x?P(x)??x Q(x) 证明：(1)?x?P(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∩(B∪C)=(A∩B)∪(A∩C) （10分） 证明：∵x∈A∩（B∪C）?x∈A∧x∈（B∪C）?x∈A∧（x∈B∨x∈C）?（ x∈A ∧x∈B）∨（x∈A∧x∈C）?x∈（A∩B）∨x∈A∩C?x∈（A∩B）∪（A∩C）∴A∩（B ∪C）=（A∩B）∪（A∩C） 六、π={A1，A2，…，A n}是集合A的一个划分，定义R={ 证明：?a∈A必有i使得a∈A i，由定义知aRa，故R自反。 ?a,b∈A，若aRb ，则a,b∈A i，即b,a∈A i，所以bRa，故R对称。 ?a,b,c∈A，若aRb 且bRc，则a,b∈A i及b,c∈A j。因为i≠j时A i∩A j=Φ，故i=j，即a,b,c∈A i，所以aRc，故R传递。 总之R是A上的等价关系。 七、若f:A→B是双射，则f-1:B→A是双射（15分）。 证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使 对任意的x∈A，若存在y1,y2∈B，使得 因此f-1是双射。 八、设 证明假设A≠G且B≠G，则存在a∈A，a?B，且存在b∈B，b?A（否则对任意的a∈A，a∈B，从而A?B，即A∪B＝B，得B＝G，矛盾。） 对于元素a*b∈G，若a*b∈A，因A是子群，a-1∈A，从而a-1 * (a*b)＝b∈A，所以矛盾，故a*b?A。同理可证a*b?B，综合有a*b?A∪B＝G。 综上所述，假设不成立，得证A＝G或B＝G。 九、若无向图G是不连通的，证明G的补图G是连通的（10分）。 证明设无向图G是不连通的，其k个连通分支为1G、2G、…、k G。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支i G（1≤i≤k）中，在不同于i G的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u 和v的任意性可知，G是连通的。 离散数学试题（B卷答案5） 一、（10分）求命题公式?(P∧Q)??(?P→R)的主合取范式。 解：?(P∧Q)??(?P→R)?（?(P∧Q)→?(?P→R)）∧（?(?P→R)→?(P∧Q)）?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)） ?(P∧Q)∨(?P∧?R) ?(P∨?R)∧（Q∨?P）∧（Q∨?R） ?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R） ?M1∧M3∧M4∧M5 二、（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∩(B∪C)=(A∩B)∪(A∩C) 证明：∵x∈ A∩（B∪C）? x∈ A∧x∈（B∪C） ? x∈ A∧（x∈B∨x∈C） ?（ x∈ A∧x∈B）∨（x∈ A∧x∈C） ? x∈（A∩B）∨x∈ A∩C ? x∈（A∩B）∪（A∩C） ∴A∩（B∪C）=（A∩B）∪（A∩C） 四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。 解：?x∈A，因为R和S是自反关系，所以 ?x、y∈A，若 因 ?x 、y 、z ∈A ，若 总之R ∩S 是等价关系。 2）因为x ∈[a]R ∩S ? 所以[a]R ∩S =[a]R ∩[a]S 。 五、(10分) 设A ＝{a ，b ，c ，d }，R 是A 上的二元关系，且R ＝{，，， s (R )＝R ∪R -1 ＝{，，， 六、(15分) 设A 、B 、C 、D 是集合，f 是A 到B 的双射，g 是C 到D 的双射，令h ：A ×C →B ×D 且? 证明：1）先证h 是满射。 ? 2）再证h 是单射。 ? 综合1）和2），h 是双射。 七、(12分)设 证明：??a,b∈H有b-1∈H，所以a*b-1∈H。 ??a∈H，则e=a*a-1∈H a-1=e*a-1∈H ∵a,b∈H及b-1∈H，∴a*b=a*（b-1）-1∈H ∵H?G且H≠Φ,∴*在H上满足结合律 ∴ 八、（10分）设G= 解：设G的每个结点的度数都大于等于6，则2|E|=∑d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。 九.G= （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)(?P ∨?Q )→(P ??Q ) (2)(P ↓Q )→(P ∧?(Q ∨?R )) 解：（1）因为(?P ∨?Q )→(P ??Q )??(?P ∨?Q )∨(P ∧?Q )∨(?P ∧Q ) ?(P ∧Q )∨(P ∧?Q )∨(?P ∧Q ) ?1m ∨2m ∨3m ?0M 所以，公式(?P ∨?Q )→(P ??Q )为可满足式。 （2）因为(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 所以，公式(P ↓Q )→(P ∧?(Q ∨?R ))为可满足式。 二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋 又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。 解：论域：所有人的集合。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)?x C(x) T(11)，EG (13)?x(C(x)∨F(x)) T(12)，I 三、（10分）设A＝{?，1，{1}}，B＝{0，{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，{0}}⊕{0，{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 是自反的，则R ∩S 是自反的。 (6)若R 和S 是传递的，则R ∪S 是传递的。 解 (1)成立。对任意的a ∈A ，因为R 和S 是自反的，则∈R ，∈S ，于是∈R *S ，故R *S 也是自反的。 (2)不成立。例如，令A ＝{1，2}，R ＝{<1，2>}，S ＝{<2，1>}，则R 和S 是反自反的，但R *S ＝{<1，1>}不是反自反的。 (3)不成立。例如，令A ＝{1，2，3}，R ＝{<1，2>，<2，1>，<3，3>}，S ＝{<2，3>，<3，2>}，则R 和S 是对称的，但R *S ＝{<1，3>，<3，2>}不是对称的。 (4)不成立。例如，令A ＝{1，2，3}，R ＝{<1，2>，<2，3>，<1，3>}，S ＝{<2，3>，<3，1>，<2，1>}，则R 和S 是传递的，但R *S ＝{<1，3>，<1，1>，<2，1>}不是传递的。 (5)成立。对任意的a ∈A ，因为R 和S 是自反的，则∈R ，∈S ，于是∈R ∩S ，所以R ∩S 是自反的。 五、（15分）令X ＝{x 1，x 2，…，x m }，Y ＝{y 1，y 2，…，y n }。问 (1)有多少个不同的由X 到Y 的函数？ (2)当n 、m 满足什么条件时，存在单射，且有多少个不同的单射？ (3)当n 、m 满足什么条件时，存在双射，且有多少个不同的双射？ 解 (1)由于对X 中每个元素可以取Y 中任一元素与其对应，每个元素有n 种取法，所以不同的函数共n m 个。 (2)显然当|m |≤|n |时，存在单射。由于在Y 中任选m 个元素的任一全排列都形成X 到 Y 的不同的单射，故不同的单射有m n C m !＝n (n －1)(n ―m ―1)个。 (3)显然当|m |＝|n |时，才存在双射。此时Y 中元素的任一不同的全排列都形成X 到Y 的不同的双射，故不同的双射有m !个。 六、（5分）集合X 上有m 个元素，集合Y 上有n 个元素，问X 到Y 的二元关系总共有多少个？ 解 X 到Y 的不同的二元关系对应X ×Y 的不同的子集，而X ×Y 的不同的子集共有个mn 2，所以X 到Y 的二元关系总共有mn 2个。 七、（10分）若 证明 设e 是群 1)*b ＝e *b ＝b 。所以，x ＝a － 1*b 是a *x ＝b 的解。 若x '∈G 也是a *x ＝b 的解，则x '＝e *x '＝(a －1*a )*x '＝a －1*(a *x ')＝a － 1*b ＝x 。所以，x ＝a － 1*b 是a *x ＝b 的惟一解。 八、（10分）给定连通简单平面图G ＝ 证明 由偶拉公式得|V |－|E |＋|F |＝2，所以|F |＝2－|V |＋|E |＝8，于是∑∈F f f d )(＝2|E |＝ 24。若存在f ∈F ，使得d (f )＞3，则3|F |＜2|E |＝24，于是|F |＜8，与|F |＝8矛盾。故对任意f ∈F ，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 ＝(A ∧C )∨(B ∧C )。 在全功能联结词组{↑}中： ?A ??(A ∧A )?A ↑A A ∧C ???( A ∧C )??( A ↑C )?(A ↑C )↑(A ↑C ) A ∨ B ??(?A ∧?B )??(( 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 ?(A ∧C )∨(B ∧C ) ?(A ∧(B ∨?B )∧C )∨((A ∨?A )∧B ∧C ) ?(A ∧B ∧C )∨(A ∧?B ∧C )∨(A ∧B ∧C )∨(?A ∧B ∧C ) ?3m ∨5m ∨7m 主析取范式 ?0M ∧1M ∧2M ∧4M ∧6M 主合取范式 二、（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))∨?x?A(x)∨?xB(x) ?(?xA(x)∨?x?A(x)∨?xB(x))∧(??xB(x)∨?x?A(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为集合，A＝P(X)－{?}－{X}且A≠?，若|X|＝n，问 (1)偏序集 (2)偏序集 (3)偏序集 解偏序集 考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X。偏序集 四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2， 5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R 3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R 4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R 2 t (R )＝∞ =1i R i ＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5， 1>，<5，4>，<5，5>}。 五、（10分）设函数g ：A →B ，f ：B →C ， (1)若f g 是满射，则f 是满射。 (2)若f g 是单射，则g 是单射。 证明 因为g ：A →B ，f ：B →C ，由定理5.5知，f g 为A 到C 的函数。 (1)对任意的z ∈C ，因f g 是满射，则存在x ∈A 使f g (x )＝z ，即f (g (x ))＝z 。由g ：A →B 可知g (x )∈B ，于是有y ＝g (x )∈B ，使得f (y )＝z 。因此，f 是满射。 (2)对任意的x 1、x 2∈A ，若x 1≠x 2，则由f g 是单射得f g (x 1)≠f g (x 2)，于是f (g (x 1))≠f (g (x 2))，必有g (x 1)≠g (x 2)。所以，g 是单射。 六、（10分）有幺元且满足消去律的有限半群一定是群。 证明 设 考虑a ，a 2，…，a k ，…。因为G 只有有限个元素，所以存在k ＞l ，使得a k ＝a l 。令m ＝k －l ，有a l *e ＝a l *a m ，其中e 是幺元。由消去率得a m ＝e 。 于是，当m ＝1时，a ＝e ，而e 是可逆的；当m ＞1时，a *a m -1＝a m -1*a ＝e 。从而a 是可逆的，其逆元是a m -1。总之，a 是可逆的。 七、（20分）有向图G 如图所示，试求： (1)求G 的邻接矩阵A 。 (2)求出A 2、A 3和A 4，v 1到v 4长度为1、2、3和4的路有多少？ (3)求出A T A 和AA T ，说明A T A 和AA T 中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P 。 (5)求出强分图。 解 (1)求G 的邻接矩阵为： ?????? ? ??=0010101011001010A (2)由于 ??????? ??=11001110102011102A ??????? ??=10202120221021203A ?????? ? ??=22103230314032304A 所以v 1到v 4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于 ??????? ??=3120110021300000A A T ?????? ? ??=1201121201211212T AA 再由定理10.19可知，所以A T A 的第(2，2)元素为3，表明那些边以2v 为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以2v 为终结点又以3v 为终结点，并且具有相同始结点的数目为0。AA T 中的第(2，2)元素为2，表明那些边以2v 为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以2v 为始结点又以3v 为始结点，并且具有相同终结点的数目为1。 (4) 因为=+++=4324A A A A B ??????? ??0010101011001010+??????? ??1100111010201110+??????? ??1020212022102120+=??????? ??2210323031403230?????? ? ??4340747074701470，所以求可达矩阵为??????? ? ?=1110111011101110P 。 (5)因为=∧T P P ??????? ??1110111011101110∧??????? ??1111111111110000＝?????? ? ??1110111011100000，所以{1v }，{2v ，3v ，4v }构成G 的强分图。 离散数学试题（B 卷答案8） 一、（10分）证明(P ∨Q )∧(P →R )∧(Q →S )S ∨R 证明 因为S ∨R ??R →S ，所以，即要证(P ∨Q )∧(P →R )∧(Q →S )?R →S 。 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 离散数学考试试题（A卷及答案） 一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。 证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。 所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)→Q(x)) P (2)P(y)→Q(y) T(1)，US (3)?xP(x) P (4)P(y) T(3)，ES (5)Q(y) T(2)(4)，I (6)?xQ(x) T(5)，EG 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。 正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。 解设R＝{ 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 《离散数学》期末考试题(B) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是 （１）（１）写出 和 的关系矩阵。（２）求 及 （1２分） 五、求 的主析取范式和主合取范式。（１０分） 六、设 是 到 的关系， 是 到 的关系，证明： （8分） 七、设 是一个等价关系，设 对某一个 ,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分） 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 试卷二十三试题与答案 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、?； C 、∈； D 、?。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=*； B 、),max(b a b a =*； C 、b a b a 5+=*； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧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∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) 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 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧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∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 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(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) 离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝_____{3}______________; ρ(A) - ρ(B)＝ ____{{3}，{1，3}，{2,3},{1,2,3}}__________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = ___2^(n^2)________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是____A1 = {(a,1), (b,1)}, A2 = {(a,2), (b,2)}, A3 = {(a,1), (b,2)}, A4 = {(a,2), (b,1)},_________ _____________, 其中双射的是______A3, A4__________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取式是____P∧?Q∧R (m5)____. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为___12______，分枝点数为_______3_________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝______{4}______; A?B＝____{1,2,3,4}_________;A－B＝______{1,2}_______ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______自反性____________, _________对称性_________, _________传递性_____________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有_____（1,0,0）__________， ______(1,0,1)________, ________(1,1,0)________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1?R2= ___{(1,3),(2,2),(3,1)}____,R2?R1 =_____{(2,4), (3,3), (4,2)}_____, R12=_______{(2,2), (3,3)}_________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = ______2^(m*n)___________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = _____{x | -1 ≤x < 0, x ∈R}_______ , B-A = ______{x | 1 < x < 2, x ∈R}_____ , A∩B = ______{x | 0 ≤x ≤1, x ∈R}__________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ ________{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}_________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束式是_____?y?x(P(y)→Q(x))________ _____.(完整版)离散数学试卷及答案
离散数学期末试题
离散数学考试试题(A卷及答案)
离散数学试题与答案
离散数学期末试题及答案完整版
【浙江工商大学】《离散数学》期末考试题(B)
离散数学期末考试试卷(A卷)
离散数学期末试卷及答案
离散数学期末考试试题及答案
离散数学期末试卷A卷及答案
离散数学试卷二十三试题与答案
的幺元为（ ）。 A 、a ； B 、b ； C 、1； D 、0。 8．给定下列序列，（ ）可以构成无向简单图的结点度数序列。 A 、（1，1，2，2，3）； B 、（1，1，2，2，2）； C 、（0，1，3，3，3）； D 、（1，3，4，4，5）。 9．设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。 A 、点与边； B 、边与点； C 、点与点； D 、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。 A 、5； B 、7； C 、9； D 、8。
离散数学试卷及答案
离散数学期末考试试题及答案
离散数学试卷及答案(1)
《离散数学》期末考试试题
离散数学期末考试试题(有几套带答案)
离散数学试题及答案