离散数学试题及答案解析
离散数学试题及答案
一、填空题
1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________;ρ(A)-ρ(B)＝__________________________.
2.设有限集合A,|A|=n,则|ρ(A×A)|=__________________________.
3.设集合A={a,b},B={1,2},则从A到B的所有映射是__________________________
_____________,其中双射的是__________________________.
4.已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________
__________________________________________________________.
5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.
6设A、B为两个集合,A={1,2,4},B={3,4},则从A?B＝_________________________;A?B ＝_________________________;A－B＝_____________________.
7.设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________,
________________________,_______________________________.
8.设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，
_____________________________,__________________________.
9.设集合A＝{1,2,3,4},A上的关系R1={(1,4),(2,3),(3,2)},R1={(2,1),(3,2),(4,3)},则R1?R2=
________________________,R2?R1=____________________________,R12
=________________________.
10.设有限集A,B，|A|=m,|B|=n,则||ρ(A?B)|=_____________________________.
11设A,B,R是三个集合，其中R是实数集，A={x|-1≤x≤1,x∈R},B={x|0≤x<2,x∈R},则A-B=__________________________,B-A=__________________________,
A∩B=__________________________,.
13.设集合A＝{2,3,4,5,6}，R是A上的整除，则R以集合形式(列举法)记为___________
_______________________________________________________.
14.设一阶逻辑公式G=?xP(x)→?xQ(x)，则G的前束范式是__________________________
_____.
15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.
17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________,R 2＝______________________________________________________.
二、选择题1
设集合A={2,{a},3,4}，B ={{a},3,4,1}，E 为全集，则下列命题正确的是()。
(A){2}∈A (B){a}?A
(C)??{{a}}?B ?E
(D){{a},1,3,4}?B.
2
设集合A={1,2,3},A 上的关系R ＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R 不具备().(A)自反性
(B)传递性
(C)对称性
(D)反对称性
3设半序集(A,≤)关系≤的哈斯图如下所示，若A 的子集B ={2,3,4,5},则元素6为B 的(
)。
(A)下界(B)上界(C)最小上界(D)以上答案都不对
4
下列语句中，()是命题。
(A)请把门关上(B)地球外的星球上也有人(C)x +5>6
(D)下午有会吗？
5设I 是如下一个解释：D ＝{a,b},
1 0 1b) P(b,a) P(b,b) P(a,),(a a P 则在解释I 下取真值为1的公式是().(A)?x ?yP(x,y)
(B)?x ?yP(x,y)
(C)?xP(x,x)
(D)?x ?yP(x,y).
6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是(
).
(A)(1,2,2,3,4,5)
(B)(1,2,3,4,5,5)
(C)(1,1,1,2,3)
(D)(2,3,3,4,5,6).
7.设G 、H 是一阶逻辑公式，P 是一个谓词，G ＝?xP(x),H ＝?xP(x),则一阶逻辑公式G →H
123
4
56
是().(A)恒真的
(B)恒假的
(C)可满足的
(D)前束范式.
8设命题公式G ＝?(P →Q)，H ＝P →(Q →?P)，则G 与H 的关系是()。
(A)G ?H
(B)H ?G
(C)G ＝H (D)以上都不是.
9设A,B 为集合，当()时A －B ＝B.
(A)A ＝B
(B)A ?B
(C)B ?A
(D)A ＝B ＝?.
10设集合A ={1,2,3,4},A 上的关系R ＝{(1,1),(2,3),(2,4),(3,4)},则R 具有()。
(A)自反性
(B)传递性
(C)对称性
(D)以上答案都不对
11下列关于集合的表示中正确的为(
)。(A){a}∈{a,b,c}(B){a}?{a,b,c}
(C)?∈{a,b,c}
(D){a,b}∈{a,b,c}12命题?xG(x)取真值1的充分必要条件是(
).
(A)对任意x ，G(x)都取真值1.(B)有一个x 0，使G(x 0)取真值1.(C)有某些x ，使G(x 0)取真值1.
(D)以上答案都不对.
13.设G 是连通平面图，有5个顶点，6个面，则G 的边数是(
).
(A)9条
(B)5条
(C)6条
(D)11条.
14.设G 是5个顶点的完全图，则从G 中删去(
)条边可以得到树.
(A)6(B)5
(C)10
(D)4.
15.设图G
的相邻矩阵为???
?
??
?
??????
???01101
101011101100101
11110，则
G 的顶点数与边数分别为().
(A)4,5(B)5,6(C)4,10(D)5,8.
三、计算证明题
1.设集合A ＝{1,2,3,4,6,8,9,12}，R 为整除关系。
(1)画出半序集(A,R)的哈斯图；
(2)写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；
(3)写出A的最大元，最小元，极大元，极小元。
2.设集合A＝{1,2,3,4}，A上的关系R＝{(x,y)|x,y∈A且x≥y},求
(1)画出R的关系图；
(2)写出R的关系矩阵.
3.设R是实数集合，σ,τ,?是R上的三个映射，σ(x)=x+3,τ(x)=2x,?(x)＝x/4,试求复
合映射σ?τ，σ?σ,σ??,??τ，σ???τ.
4.设I是如下一个解释：D={2,3},
a b f(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)
32320011试求(1)P(a,f(a))∧P(b,f(b));
(2)?x?y P(y,x).
5.设集合A＝{1,2,4,6,8,12}，R为A上整除关系。
(1)画出半序集(A,R)的哈斯图；
(2)写出A的最大元，最小元，极大元，极小元；
(3)写出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.
6.设命题公式G=?(P→Q)∨(Q∧(?P→R)),求G的主析取范式。
7.(9分)设一阶逻辑公式：G=(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式.
9.设R是集合A={a,b,c,d}.R是A上的二元关系,R={(a,b),(b,a),(b,c),(c,d)},
(1)求出r(R),s(R),t(R)；
(2)画出r(R),s(R),t(R)的关系图.
11.通过求主析取范式判断下列命题公式是否等价：
(1)G=(P∧Q)∨(?P∧Q∧R)
(2)H=(P∨(Q∧R))∧(Q∨(?P∧R))
13.设R和S是集合A＝{a,b,c,d}上的关系，其中R＝{(a,a),(a,c),(b,c),(c,d)},
S＝{(a,b),(b,c),(b,d),(d,d)}.
(1)试写出R和S的关系矩阵；
(2)计算R?S,R∪S,R－1,S－1?R－1.
四、证明题
1.利用形式演绎法证明：{P→Q,R→S,P∨R}蕴涵Q∨S。
2.设A,B为任意集合，证明：(A-B)-C=A-(B∪C).
3.(本题10分)利用形式演绎法证明：{?A∨B,?C→?B,C→D}蕴涵A→D。
4.(本题10分)A,B为两个任意集合，求证：
A－(A∩B)=(A∪B)－B.
参考答案
一、填空题
1.{3};{{3},{1,3},{2,3},{1,2,3}}.
2n.
2.2
3.α1={(a,1),(b,1)},α2={(a,2),(b,2)},α3={(a,1),(b,2)},α4={(a,2),(b,1)};α3,α
4.
4.(P∧?Q∧R).
5.12,3.
6.{4},{1,2,3,4},{1,2}.
7.自反性；对称性；传递性.
8.(1,0,0),(1,0,1),(1,1,0).
9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.
10.2m?n.
11.{x|-1≤x<0,x∈R};{x|1 12.12;6. 13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14.?x(?P(x)∨Q(x)).15.21. 16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(1,3),(2,2)};{(1,1),(1,2),(1,3)}. 二、选择题1. C. 2. D. 3. B. 4. B. 5. D. 6. C. 7. C. 8.A. 9. D.10. B. 11. B. 13. A. 14. A. 15.D 三、计算证明题1.(1) (2)B 无上界，也无最小上界。下界1,3;最大下界是3.(3)A 无最大元，最小元是1，极大元8,12,90+;极小元是1.2.R ={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}. (1) (2)10001 10011101 11 1R M ????? ?=?????? 3.(1)σ?τ＝σ(τ(x))＝τ(x)+3＝2x+3＝2x+3. (2)σ?σ＝σ(σ(x))＝σ(x)+3＝(x+3)+3＝x+6, 1 2 4 8 3 6 12 9 1 2 3 4 (3)σ??＝σ(?(x))＝?(x)+3＝x/4+3,(4)??τ＝?(τ(x))＝τ(x)/4＝2x/4=x/2,(5)σ???τ＝σ?(??τ)＝??τ+3＝2x/4+3＝x/2+3.4. (1)P (a ,f (a ))∧P (b ,f (b ))=P (3,f (3))∧P (2,f (2)) =P (3,2)∧P (2,3)=1∧0=0. (2)?x ?y P (y ,x )=?x (P (2,x )∨P (3,x )) =(P (2,2)∨P (3,2))∧(P (2,3)∨P (3,3))=(0∨1)∧(0∨1)=1∧1=1. 5.(1) (2)无最大元，最小元1，极大元8,12;极小元是1.(3)B 无上界，无最小上界。下界1,2;最大下界2. 6. G =?(P →Q)∨(Q ∧(?P →R))=?(?P ∨Q)∨(Q ∧(P ∨R))=(P ∧?Q)∨(Q ∧(P ∨R))=(P ∧?Q)∨(Q ∧P)∨(Q ∧R) =(P ∧?Q ∧R)∨(P ∧?Q ∧?R)∨(P ∧Q ∧R)∨(P ∧Q ∧?R)∨(P ∧Q ∧R)∨(?P ∧Q ∧ 2 4 1 6 812 R) =(P ∧?Q ∧R)∨(P ∧?Q ∧?R)∨(P ∧Q ∧R)∨(P ∧Q ∧?R)∨(?P ∧Q ∧R)=m 3∨m 4∨m 5∨m 6∨m 7=∑(3,4,5,6,7).7. G =(?xP (x )∨?yQ (y ))→?xR (x )=?(?xP (x )∨?yQ (y ))∨?xR (x )=(??xP (x )∧??yQ (y ))∨?xR (x )=(?x ?P (x )∧?y ?Q (y ))∨?zR (z )=?x ?y ?z ((?P (x )∧?Q (y ))∨R (z )) 9.(1)r(R)＝R ∪I A ＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R ∪R －1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, t(R)＝R ∪R 2∪R 3∪R 4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)关系图: 11.G ＝(P ∧Q)∨(?P ∧Q ∧R) ＝(P ∧Q ∧?R)∨(P ∧Q ∧R)∨(?P ∧Q ∧R)＝m 6∨m 7∨m 3＝∑(3,6,7) H =(P ∨(Q ∧R))∧(Q ∨(?P ∧R))＝(P ∧Q)∨(Q ∧R))∨(?P ∧Q ∧R) ＝(P ∧Q ∧?R)∨(P ∧Q ∧R)∨(?P ∧Q ∧R)∨(P ∧Q ∧R)∨(?P ∧Q ∧R) b a c d r(R) b a c d s(R) b a c d t(R) ＝(P ∧Q ∧?R)∨(?P ∧Q ∧R)∨(P ∧Q ∧R)＝m 6∨m 3∨m 7＝∑(3,6,7) G,H 的主析取范式相同，所以G =H. 13. (1)????? ???? ???=0000 10000100 0101R M ????? ???? ???=1000 000011000010S M (2)R?S ＝{(a ,b ),(c ,d )}, R ∪S ＝{(a ,a ),(a ,b ),(a ,c ),(b ,c ),(b ,d ),(c ,d ),(d ,d )},R －1＝{(a ,a ),(c ,a ),(c ,b ),(d ,c )},S －1?R －1＝{(b ,a ),(d ,c )}.四证明题 1.证明：{P →Q ,R →S ,P ∨R }蕴涵Q ∨S (1)P ∨R P (2)?R →P Q(1) (3)P →Q P (4)?R →Q Q(2)(3)(5)?Q →R Q(4) (6)R →S P (7)?Q →S Q(5)(6) (8)Q ∨S Q(7) 2.证明：(A-B)-C =(A ∩~B)∩~C =A ∩(~B ∩~C) =A-(B∪C) 3.证明：{?A∨B,?C→?B,C→D}蕴涵A→D (1)A D(附加) (2)?A∨B P (3)B Q(1)(2) (4)?C→?B P (5)B→C Q(4) (6)C Q(3)(5) (7)C→D P (8)D Q(6)(7) (9)A→D D(1)(8) 所以{?A∨B,?C→?B,C→D}蕴涵A→D. 4.证明：A－(A∩B) =A∩~(A∩B) ＝A∩(~A∪~B) ＝(A∩~A)∪(A∩~B) ＝?∪(A∩~B) ＝(A∩~B) ＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B) =A－B 所以：A－(A∩B)=(A∪B)－B. 离散数学试题（A卷及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：A→C⊕D，?(B∧C)，C→?D必须同时成立。因此 (A→C⊕D)∧?(B∧C)∧(C→?D) ?(?A∨(C∧?D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D) ?(?A∨(C∧?D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D)) ?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D) ∨(C∧?D∧?B∧?C)∨(C∧?D∧?B∧?D)∨(C∧?D∧?C)∨(C∧?D∧?C∧?D) ∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D ∧?C∧?D) ?F∨F∨(?A∧?C)∨F∨F∨(C∧?D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧?D)∨(?C∧D∧?B)∨(?C∧D) ?(?A∧?C)∨(?B∧C∧?D)∨(?C∧D) ?T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为： ?x( S(x)∧W(x))，?x Y(x)?x(S(x)∧Y(x)) 下面给出证明： (1)?x Y(x)P (2)Y(c)T(1)，ES (3)?x(S(x)∧W(x))P (4)S(c)∧W(c)T(3)，US (5)S(c)T(4)，I (6)S(c)∧Y(c)T(2)(5)，I (7)?x(S(x)∧Y(x))T(6)，EG 三、（10分）设A、B和C是三个集合，则A?B??(B?A)。 证明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B) ??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A)) ??(B?A)。 四、（15分）设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>} R3＝{<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分）R 是非空集合A 上的二元关系，若R 是对称的，则r (R )和t (R )是对称的。 证明 对任意的x 、y ∈A ，若xr (R )y ，则由r (R )＝R ∪I A 得，xRy 或xI A y 。因R 与I A 对称，所以有yRx 或yI A x ，于是yr (R )x 。所以r (R )是对称的。 下证对任意正整数n ，R n 对称。 因R 对称，则有xR 2y ??z (xRz ∧zRy )??z (zRx ∧yRz )?yR 2x ，所以R 2对称。若n R 对称，则x 1+n R y ??z (x n R z ∧zRy )??z (z n R x ∧yRz )?y 1+n R x ，所以1+n R 对称。因此，对任意正整数n ，n R 对称。 对任意的x 、y ∈A ，若xt (R )y ，则存在m 使得xR m y ，于是有yR m x ，即有yt (R )x 。因此，t (R )是对称的。 六、（10分）若f ：A →B 是双射，则f －1：B →A 是双射。 证明因为f ：A →B 是双射，则f －1是B 到A 的函数。下证f －1是双射。 对任意x ∈A ，必存在y ∈B 使f (x)＝y ，从而f －1(y )＝x ，所以f －1 是满射。 对任意的y 1、y 2∈B ，若f －1(y 1)＝f －1 (y 2)＝x ，则f (x)＝y 1，f (x)＝y 2。因为f ：A→B 是 函数，则y 1＝y 2。所以f －1是单射。 综上可得，f －1 ：B →A 是双射。 七、（10分）设 因为 ＝b 2*b ∈S ，…，b n ∈S ，…。 因为S 是有限集，所以必存在j ＞i ，使得i b ＝j b 。令p ＝j －i ，则j b ＝p b *j b 。所以对q ≥i ，有q b ＝p b *q b 。 因为p ≥1，所以总可找到k ≥1，使得kp ≥i 。对于kp b ∈S ，有kp b ＝p b *kp b ＝p b *(p b *kp b )＝…＝kp b *kp b 。 令a ＝kp b ，则a ∈S 且a *a ＝a 。 八、（20分）（1）若G 是连通的平面图，且G 的每个面的次数至少为l (l ≥3)，则G 的边数m 与结点数n 有如下关系： m ≤ 2 -l l (n －2)。 证明设G 有r 个面，则2m ＝∑=r i i f d 1 )(≥lr 。由欧拉公式得，n －m ＋r ＝2。于是，m ≤ 2 -l l (n －2)。 （2）设平面图G ＝ 设G * ＝ ?G ，于是|F | ＝|V *|＝|V |，将其代入欧拉公式|V |－|E |＋|F |＝2得，|E |＝2(|V |－1)。 离散数学试题（B卷及答案） 一、（10分）证明(P∨Q)∧(P→R)∧(Q→S)S∨R 证明因为S∨R??R→S，所以，即要证(P∨Q)∧(P→R)∧(Q→S)?R→S。 (1)?R附加前提 (2)P→R P (3)?P T(1)(2)，I (4)P∨Q P (5)Q T(3)(4)，I (6)Q→S P (7)S T(5)(6)，I (8)?R→S CP (9)S∨R 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，|A ∩C |＝6，|B ∩C |＝5，|A ∩B ∩C |＝2，|(A ∪C )∩B |＝6。因为|(A ∪C )∩B |＝(A ∩B )∪(B ∩C )|＝|(A ∩B )|＋|(B ∩C )|－|A ∩B ∩C |＝|(A ∩B )|＋5－2＝6，所以|(A ∩B )|＝3。于是|A ∪B ∪C |＝12＋6＋14－6－5－3＋2＝20，||C B A ＝25－20＝5。故，不会打这三种球的共5人。 四、（10分）设A 1、A 2和A 3是全集U 的子集，则形如3 1=i A i '(A i '为A i 或i A )的集合称为由A 1、 A 2和A 3产生的小项。试证由A 1、A 2和A 3所产生的所有非空小项的集合构成全集U 的一个划分。 证明 小项共8个，设有r 个非空小项s 1、s 2、…、s r (r ≤8)。 对任意的a ∈U ，则a ∈A i 或a ∈i A ，两者必有一个成立，取A i '为包含元素a 的A i 或i A ，则a ∈3 1 =i A i '，即有a ∈r i 1 = s i ，于是U ?r i 1 = s i 。又显然有r i 1 = s i ?U ，所以U ＝r i 1 = s i 。 任取两个非空小项s p 和s q ，若s p ≠s q ，则必存在某个A i 和i A 分别出现在s p 和s q 中，于是s p ∩s q ＝?。 综上可知，{s 1，s 2，…，s r }是U 的一个划分。 五、（15分）设R 是A 上的二元关系，则：R 是传递的?R *R ?R 。证明 (5)若R 是传递的，则 即有 反之，若R *R ?R ，则对任意的x 、y 、z ∈A ，如果xRz 且zRy ，则 六、（15分）若G 为连通平面图，则n －m ＋r ＝2，其中，n 、m 、r 分别为G 的结点数、边数和面数。 证明 对G 的边数m 作归纳法。 当m ＝0时，由于G 是连通图，所以G 为平凡图，此时n ＝1，r ＝1，结论自然成立。 假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。 设e是G的一条边，从G中删去e后得到的图记为G'，并设其结点数、边数和面数分别为n'、m'和r'。对e分为下列情况来讨论： 若e为割边，则G'有两个连通分支G1和G2。G i的结点数、边数和面数分别为n i、m i和r i。显然n1＋n2＝n'＝n，m1＋m2＝m'＝m－1，r1＋r2＝r'＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。 若e不为割边，则n'＝n，m'＝m－1，r'＝r－1，由归纳假设有n'－m'＋r'＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。 由数学归纳法知，结论成立。 七、（10分）设函数g：A→B，f：B→C，则： (1)f g是A到C的函数； (2)对任意的x∈A，有f g(x)＝f(g(x))。 证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使 ＝A。 g 对任意的x∈A，若存在y1、y2∈C，使得 综上可知，f g是A到C的函数。 (2)对任意的x∈A，由g：A→B是函数，有 八、（15分）设 证明对于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以 若 若 综上可得，R是G中的一个等价关系。 对于任意的b∈[a]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) ? 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. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素； 7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}} 试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。 习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1. （2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表： 离散数学期末试题及答 案 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的补元( ). 离散数学期末考试试卷(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?{ 《离散数学》试卷（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) 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 一、填空 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) = 离散数学试题(Ｂ卷答案１） 一、证明题(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卷及答案） 一、证明题（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)是一个半群，如果S 是有限集，则必存在a ∈S ，使得a *a ＝a 。证明是一个半群，对任意的b ∈S ，由*的封闭性可知，b 2＝b *b ∈S ，b 3(完整版)离散数学试卷及答案
离散数学期末试题
离散数学考试试题(A卷及答案)
离散数学第三版课后习题答案
离散数学试题与答案
离散数学习题解答
离散数学期末试题及答案完整版
离散数学期末考试试卷(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)
离散数学期末考试试题及答案
离散数学期末考试试题(有几套带答案)