离散数学考试模拟试题及详细参考答案共四套教学内容
更新时间:2023-04-14 05:18:01 阅读量: 实用文档 文档下载
- 离散数学考试题推荐度:
- 相关推荐
离散模拟答案1
1命题符号化(共6小题,每小题3分,共计18分)
1.用命题逻辑把下列命题符号化
a)假如上午不下雨,我去看电影,否则就在家里读书或看报。
b)我今天进城,除非下雨。
c)仅当你走,我将留下。
2.用谓词逻辑把下列命题符号化
a)有些实数不是有理数
b)对于所有非零实数x,总存在y使得xy=1。
c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b.
一、简答题(共6道题,共32分)
1.求命题公式(P→(Q→R))?(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋
值。(5分)
2.设个体域为{1,2,3},求下列命题的真值(4分)
a)?x?y(x+y=4)
b)?y?x (x+y=4)
3.求?x(F(x)→G(x))→(?xF(x)→?xG(x))的前束范式。(4分)
4.判断下面命题的真假,并说明原因。(每小题2分,共4分)
a)(A?B)-C=(A-B) ?(A-C)
b)若f是从集合A到集合B的入射函数,则|A|≤|B|
5.设A是有穷集,|A|=5,问(每小题2分,共4分)
a)A上有多少种不同的等价关系?
b)从A到A的不同双射函数有多少个?
6.设有偏序集,其哈斯图如图1,求子集B={b,d,e}的最小元,最大元、极大元、
极小元、上界集合、下界集合、上确界、下确界,(5分)
f g
图1
7.已知有限集S={a1,a2,…,a n},N为自然数集合,R为实数集合,求下列集合的基数
S;P(S);N,N n;P(N);R,R×R,{o,1}N(写出即可)(6分)
二、证明题(共3小题,共计40分)
1.使用构造性证明,证明下面推理的有效性。(每小题5分,共10分)
a)A→(B∧C),(E→?F)→?C, B→(A∧?S)?B→E
b)?x(P(x)→?Q(x)), ?x(Q(x)∨R(x)),?x?R(x) ??x?P(x)
2.设R1是A上的等价关系,R2是B上的等价关系,A≠?且B≠?,关系R满足:
<
3.用伯恩斯坦定理证明(0,1]和(a,b)等势。(10分)
4.设R是集合A上的等价关系,A的元素个数为n,R作为集合有s个元素,若A关于R
的商集A/R有r个元素,证明:rs≥n2。(10分)
三、应用题(10分)
在一个道路上连接有8个城市,分别标记为a,b,c,d,e,f,g,h。城市之间的直接连接的道路是单向的,有a→b, a→c, b→g, g→b, c→f, f→e, b→d, d→f.对每一个城市求出从它出发所能够到达的所有其他城市。
离散数学考试题答案
一、命题符号化(共6小题,每小题3分,共计18分)
1.用命题逻辑把下列命题符号化
a)设P表示命题“上午下雨”,Q表示命题“我去看电影”,R表示命题“在家里读书”,S
表示命题“在家看报”,命题符号化为:(?P?Q)∧(P?R∨S)
b)设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:?Q→P或?P→Q
c)设P表示命题“你走”,Q表示命题“我留下”,命题符号化为: Q→P
2.用谓词逻辑把下列命题符号化
a)设R(x)表示“x是实数”,Q(x)表示“x是有理数”,命题符号化为:
?x(R(x) ∧?Q(x)) 或??x(R(x) →Q(x))
b)设R(x)表示“x是实数”,E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为:
?x(R(x) ∧?E(x,0) →?y(R(y) ∧E(f(x,y),1))))
c)设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示
“x=y”, 命题符号化为:
F(f)??a(A(a)→?b(B(b) ∧ E(f(a),b) ∧?c(S(c) ∧ E(f(a),c) →E(a,b))))
二、简答题(共6道题,共32分)
1.(P→(Q→R))?(R→(Q→P))?(?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) 这是主合取范式
公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为
(?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R)
2.a) T b) F
3.?x(F(x)→G(x))→(?xF(x)→?xG(x)) ??x(F(x)→G(x))→(?yF(y)→?zG(z))
??x(F(x)→G(x))→?y?z(F(y)→G(z)) ??x?y?z((F(x)→G(x))→ (F(y)→G(z)))
4.a) 真命题。因为(A?B)-C=(A?B)?~C=(A?~C)?(B?~C)=(A-C)?(B-C)
b) 真命题。因为如果f是从集合A到集合B的入射函数,则|ranf|=|A|,且ranf?B,故命
题成立。
5.a) 52 b) 5!=120
6.B的最小元是b,无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合
是{a,b}、上确界是g、下确界是b.
7.K[S]=n; K[P(S)]=n2; K[N]=?0,K[N n]=?0, K[P(N)]=?; K[R]=?, K=[R×R]=
?,K[{0,1}N]= ?
三、证明题(共3小题,共计40分)
1. a) 证 (1)B P(附加条件)
(2)B →(A ∧?S) P
(3) A ∧?S T(1)(2) I
(4) A T(3) I
(5) A →(B ∧C) P
(6) B ∧C T(4)(5) I
(7) C T(6) I
(8) (E →?F)→?C P
(9) ?(E →?F) T(7)(8) I
(10) E ∧F T(9) E
(11) E T(10) I
(12) B →E CP
b) 证 (1) ?x ?R(x) P
(2) ?R(c) ES(1)
(3) ?x(Q(x)∨R(x)) P
(4) Q(c)∨R(c) US(3)
(5) Q(c) T(2)(4) I
(6) ?x(P(x)→?Q(x)) P
(7) P(c)→?Q(c) US(6)
(8) ?P(c) T(5)(7) I
(9) ?x ?P(x) EG(8)
2. 证 任取
<
任取<>∈R
<>∈R ?>∈R, 故R 是传递的。
综上所述R 是A ×B 上的等价关系。
3. 证 构造函数f :(0,1]→(a,b),f(x)=2
2b x a +,显然f 是入射函数 构造函数g: (a,b)→(0,1],a
b a x x g --=)(,显然g 是入射函数, 故(0,1]和(a,b)等势。 由于22122221??
? ??+++≥+++r m m m r m m m r r ΛΛ,所以22
r n r s ≥ 4. 证 设商集A/R 的r 个等价类的元素个数分别为m 1,m 2,…,m r ,由于一个划分对应一个等
价关系,m 1+m 2+…+m r =n , s m m m r =+++22221Λ
由于2
2122221??? ??+++≥+++r m m m r m m m r r ΛΛ(r 个数的平方的平均值大于等于这r 个数的平均值的平方),所以22
r
n r s ≥,即2n rs ≥ 四、应用题(10分)
解 把8个城市作为集合A 的元素,即A={a,b,c,d,e,,f,g,h},在A 上定义二元关系R ,
R={,,,
那么该问题即变为求R 的传递闭包。
利用Warshal 算法,求得t(R)=????????????
??????????????000000000111101000010000
0000000000110000001100000111100001111110 那么从城市x 出发能到达的城市为})(,|{}])[{)((y x R t y x y x I R t A ≠∧>∈<=-, 故有},,,,,{}])[{)((g f e d c b a I R t A =-
},,,{}])[{)((g f e d b I R t A =-
},{}])[{)((f e c I R t A =-
},{}])[{)((f e d I R t A =-
}{}])[{)((e f I R t A =-
},,,{}])[{)((f e d b g I R t A =-
φ=-=-}])[{)((}])[{)((e I R t e I R t A A
离散考试模拟试题及答案2
一、填空题
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=_____________________________________________________,
R2=______________________________________________________.
二、选择题
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}, 0 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 的相邻矩阵为???????
?????????0110110101110110010111110,则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)1000110011101111R 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)
正在阅读:
6.约书亚记04-05
鞋厂安全生产管理制度汇编09-22
初三物理电路故障的练习题A101-12
2015高考二模 内蒙古包头一中2015届高三第二次模拟考试文科综合06-24
华西儿童口腔医学试题(真题回忆)04-23
2词汇lexicology test 212-10
六年级英语语音专项练习题05-29
中国文学(2)离线作业05-10
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 教学内容
- 离散
- 模拟试题
- 答案
- 参考
- 数学
- 考试
- 详细
- 【精选5份合集】安徽省巢湖市2022-2022学年高二化学下学期期末监
- 新模式英语1unit5lesson2
- 汤显祖游园皂罗袍原文及翻译注释赏析
- 2011年中质协六西格玛黑带考试真题
- 2022年新高考英语二轮复习专题01 名词与冠词押题(教师版)
- 结合自身谈一谈运动与健康的认识
- 果汁推广方案简介-果汁饮料品牌网络营销方案简介
- 高一物理必修一学案全部
- 专科《学前儿童艺术教育》试题答案及评分标准
- 墙砖的施工工艺流程
- 师德师风自我剖析材料与师德师风自我反思剖析材料汇编
- 2011-2012学年浙江省瑞安中学高二下学期期末考试物理试卷(带解析
- 《土木工程材料》B卷参考答案
- 2012信号与系统试卷A
- 初中英语语法知识—状语从句的单元汇编及答案解析(5)
- 苏教版五年级下册语文全册教案
- 三国演义读后感开头与结尾
- 2010十大品牌电动车排行
- 云南记录仪项目可行性分析报告
- 美国九大客源市场旅游本底趋势线及危机评估