《离散数学》试题及答案
一、填空题
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 是( ).
(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)
3 2 3 2 0 0 1 1
试求(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 < x < 2, x∈R}; {x | 0≤x≤1, x∈R}.
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, (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∧R) = (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)
= m3∨m4∨m5∨m6∨m7 = ∑(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∪R2∪R3∪R4＝{(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)
＝m6∨m7∨m3
＝∑ (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)
＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)
＝m6∨m3∨m7
＝∑ (3, 6, 7)
G ,H 的主析取范式相同，所以G = H.
13. (1)????
?????
???=00
00
10000100
0101R M ?????
???????=10
00
00001100001
S 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)
= 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－B
所以：A－(A∩B) = (A∪B)－B.
离散数学试题与答案
试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。
离散数学试题与参考答案
《离散数学》试题及答案 一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。 1. 命题公式Q Q P →∨)(为 ( ) (A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式 2．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。 (A)． P Q →； (B)．P Q ∧； (C)．P Q ?→?； (D)．P Q ?∨． 3.设集合A ={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( ) (A) 1A (B) {1,2, 3}A (C) {{4,5}}A (D) A 4. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B C )= ( ) (A) {<1,c >,<2,c >} (B) {
离散数学模拟题一套及答案
离散数学考试（试题及答案） 一、（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去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (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 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分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（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>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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卷答案） 一、（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 ＝{，，，，，，，，
离散数学模拟试题讲解
1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f
2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44 离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。 （A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈? （D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） ）。 （A）2 （B）4 （C）3 （D）5 10．连通图G是一棵树，当且仅当G中（）。 （A）有些边不是割边（B）每条边都是割边 （C）无割边集（D）每条边都不是割边 二、填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下 五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质： 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 试卷二十三试题与答案 一、单项选择题：（每小题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 ,则 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 离散数学课后答案 习题一 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 精品文档 离散数学 10.设仃限集丸 B. |A|■申 p|p |p(AxB)| = 带伞”可符号化为( ) (C ) P A Q (D ) P A Q 2 ?下列命题公式为永真蕴含式的是( ) (A ) C H( P A Q ) ( B ) P -( P A Q ) (C ) (P A Q — P ( D (P V Q)— Q 3、 命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死 的”的否定是( )。 (A) 所有人都不是大学生，有些人不会死 (B) 所有人不都是大学生，所有人都不会死 (C) 存在一些人不是大学生，有些人不会死 (D) 所有人都不是大学生，所有人都不会死 4、 永真式的否定是()。 (A )永真式 (B )永假式 (C )可满足式 (D )以上均有可能 5、以下选项中正确的是()。 (A ) 0= ? (B ) 0 ? (C 0€ ? (D ) 0?? 6、以下哪个不是集合A 上的等价关系的性质？( ) (A )自反性 (B )有限性 (C )对称性 (D ) 传递性 7、集合 A={1,2,…;10}上的关系 R={ 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (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 ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 一、判断正误20% （每小题2分） 1、设A.B. C是任意三个集合。 （1）若A∈B且B?C，则A?C。（） （2）若A?B且B∈C，则A?C。（） （3）若A?B且B∈C，则A?C。（） （4）A) ( ) ( ) (C A B A C B ⊕ = ⊕。（） （5）(A–B)?C=(A?C)-(B?C)。（） 2、可能有某种关系，既不是自反的，也不是反自反的。（） ３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（） ４、一个图是平面图，当且仅当它包含与Ｋ 3， 3 或Ｋ 5 在２度结点内同构的子图。（） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（） ６、群是每个元素都有逆元的半群。（） 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．F A F E D D C B A →?→∨∧→∨,。 ２．?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论：?→?)()((x F x S ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%（每小题2分） 《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={ 5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集 离散数学试题(A卷答案） 一、证明题（10分） 1) (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 ??( A∧((P∧Q)∨(?P∧?Q)))∨C ??( A∧(P?Q))∨C ?(A∧(P?Q))→C 2) ?(P↑Q)??P↓?Q。 证明：?(P↑Q)??(?(P∧Q))??(?P∨?Q))??P↓?Q。 二、分别用真值表法和公式法求(P→(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 证明： 公式法：因为(P→(Q∨R))∧(?P∨(Q?R)) ?(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R)) ?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R)) ?(?P∨Q∨R)∧(?P∨Q∨?Q)∧(?P∨Q∨?R)∧(?P∨R∨?Q)∧(?P∨R∨?R) ?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R) ? M∧5M∧6M 4 ? m∨1m∨2m∨3m∨7m 所以，公式(P→(Q∨R))∧(?P∨(Q?R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 真值表法： 式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 三、推理证明题（10分） 1）?P∨Q，?Q∨R，R→S P→S。 证明：(1)P附加前提《离散数学》及答案
离散数学试题及解答
离散数学试卷及答案一
离散数学模拟试卷和答案
离散数学作业答案
离散数学试卷二十三试题与答案
的幺元为（ ）。 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。
离散数学模拟试题及答案
离散数学课后答案
离散数学试题及解答
离散数学考试试题(A、B卷及答案)
离散数学试卷及答案(17)
离散数学期末试卷A卷及答案
离散数学答案
最新离散数学试卷及答案 (1)