离散数学考试模拟试题及详细参考答案共四套.docx

1、离散数学考试模拟试题及详细参考答案共四套n N离散模拟答案 11 命题符号化（共 6 小题，每小题 3 分，共计 18 分）1. 用命题逻辑把下列命题符号化a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。b) 我今天进城，除非下雨。c) 仅当你走，我将留下。2. 用谓词逻辑把下列命题符号化a) 有些实数不是有理数b) 对于所有非零实数 x，总存在 y 使得 xy=1。c) f 是从 A 到 B 的函数当且仅当对于每个 aA 存在唯一的 bB，使得 f(a)=b.一、简答题（共 6 道题，共 32 分）1. 求 命 题 公 式 (P (Q R) (R (Q P)的 主 析 取 范 式

2、、 主 合 取 范 式 ， 并 写 出 所 有 成 真 赋值。（5 分）2. 设个体域为1,2,3，求下列命题的真值（4 分）a) x y(x+y=4)a) 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. 设有偏序集

3、，其哈斯图如图 1，求子集 B=b,d,e的最小元，最大元、极大元、 极小元、上界集合、下界集合、上确界、下确界，(5 分)f gd eb ca图 17. 已 知 有 限 集 S=a1,a2,an,N 为 自 然 数 集 合 ， R 为实 数 集 合 ， 求 下列 集 合 的 基 数S;P(S);N,N ;P(N);R,RR,o,1 （写出即可）(6 分)二、证明题（共 3 小题，共计 40 分）1. 使用构造性证明，证明下面推理的有效性。（每小题 5 分，共 10 分） a) A(BC),(E F) C, B(A S) BEb) x(P(x) Q(x), x(Q(x)R(x)， x R(x)

4、 x P(x)2. 设 R1是 A 上 的 等 价 关 系 ， R2是 B 上 的等 价 关 系 ， A 且 B ， 关 系 R 满 足 ：,R，当且仅当R1且R2。试证明：R 是 AB 上的等价关系。（10 分）3. 用伯恩斯坦定理证明（0,1和(a,b)等势。（10 分）24. 设 R 是集合 A 上的等 价关系， A 的元素 个数为 n， R 作 为集合有 s 个元 素，若 A 关于 R 的商集 A/R 有 r 个元素，证明：rsn 。（10 分）三、应用题（10 分）在 一 个 道 路 上 连 接 有 8 个 城 市 ， 分 别 标 记 为 a,b,c,d,e,f,g,h。 城 市 之

5、 间 的 直 接 连 接 的 道 路 是 单向的，有 ab, ac, bg, gb, cf, fe, bd, df.对每一个城市求出从它出发 所能够到达的所有其他城市。离散数学 考试题答案一、命题符号化（共 6 小题，每小题 3 分，共计 18 分）1. 用命题逻辑把下列命题符号化a) 设 P 表示命题“上午下雨”，Q 表示命题“我去看电影”，R 表示命题“在家里读书”，S 表示命题“在家看报”，命题符号化为：（ PQ） (PR S)b)c)2.a)b)设 P 表示命题“我今天进城”，Q 表示命题“天下雨”，命题符号化为： QP 或 PQ 设 P 表示命题“你走”，Q 表示命题“我留下”，命题

6、符号化为： QP用谓词逻辑把下列命题符号化设 R(x)表示“x 是实数”，Q(x)表示“x 是有理数”，命题符号化为： x(R(x) Q(x) 或 x(R(x) Q(x)设 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)表示“xA”, B(x)表示“xB”,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)二、简答题（共

7、 6 道题，共 32 分）1. (P(QR) (R(QP) （ 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) F3. x(F(x)G(x)( xF(x) xG(x) x(F(x)G(x)( yF(y) zG(z) x(F(x)G(

8、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!=1206. B 的最小元是 b，无最大元、极大元是 d 和 e、极小元是 b、上界集合是g、下界集合 是a,b、上确界是 g、下确界是 b.7. KS=n; KP(S)= 2 ; KN= 0,KN = 0, KP(N)= ; KR= , K=R R=Nx ,

9、K0,1 = 三、证明题（共 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(BC) P(6) BC T(4)(5) I (7) C T(6) I (8) (E F) C P(9) (E F) T(7)(8) I (10) EF T(9) E (11) E T(10) I (12) BE CPb) 证 (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

10、(x) P(7) P(c) Q(c) US(6)(8) P(c) T(5)(7) I (9) x P(x) EG(8)2. 证 任取,AB xA yB R1 R2 ,R，故 R 是自反的任取, R R1 R2 R1 R2 , R.故 R 是对称的。任取,R, R R1 R2 R1 R2 ( R1 R1) ( R2 R2) R1 R2 , R, 故 R是传递的。综上所述 R 是 AB 上的等价关系。3. 证 构造函数 f：（0,1(a,b)，f(x)=a b2 2,显然 f 是入射函数构造函数 g: (a,b)（0,1， g( x ) 故（0,1和(a,b)等势。x ab a,显然 g 是入射函

11、数，由于m1 m 2 r m2r m1 m 2 r mr 2，所以 r r224. 证设 商 集 A/R 的 r 个 等 价类 的 元素个 数 分别为 m1,m2,mr， 由 于一 个 划分对 应 一个 等价关系，m1+m2+mr=n， m1 m 2 m r s由 于2 21 2 r m2r m1 m2 r mr 2（ r 个 数 的 平 方 的 平 均 值 大 于 等于这 r 个数的平均值的平方），所以s nr r22，即 rs n2四、应用题（10 分）解 把 8 个城市作为集合 A 的元素，即 A=a,b,c,d,e,f,g,h，在 A 上定义二元关系 R， R 当且仅当从 x 到 y

12、有直接连接的道路，即 R=, 那么该问题即变为求 R 的传递闭包。利用 Warshal 算法，求得 t(R)= 000000001 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 那么从城市 x 出发能到达的城市为 ( t ( R ) IA) x y | x , y t ( R ) x y ，故有 ( t ( R ) IA)a b , c , d , e , f , g ( t ( R ) I( t ( R ) I( t (

13、 R ) I( t ( R ) I( t ( R ) IAAAAA)b d , e , f , g )c e , f )d e , f ) f e ) g b , d , e , f ( t ( R ) IA)e ( t ( R ) IA)e 离散考试模拟试题及答案 2一、填空题1 设集合 A,B，其中 A1,2,3, B= 1,2, 则 A - B_; (B) _ . (A) -22. 设有限集合 A, |A| = n, 则 | (AA)| = _.3. 设集合 A = a, b, B = 1, 2, 则从 A 到 B 的所有映射是_ _, 其中双射的是_.4.已 知 命 题 公 式G (P

14、 Q) R， 则G 的 主 析 取 范 式 是_.5.设 G 是 完全二叉 树，G 有 7 个点，其中 4 个 叶点，则 G 的 总度数为 _，分 枝点 数为_.6 设 A、 B 为 两 个 集 合 , A= 1,2,4, B = 3,4, 则 从 A B _; A B_;AB _ .7. 设 R 是集合 A 上的等价关系，则 R 所具有的关系的三个特性是_, _,_.8. 设命题公式 G (P (Q R)，则使公式 G 为真的解释有_，_,_.9. 设集合 A1,2,3,4, A 上的关系 R1= (1,4),(2,3),(3,2), R1= (2,1),(3,2),(4,3), 则R1 R

15、2= _,R2 R1=_,R1 =_.10. 设有限集 A, B，|A| = m, |B| = n, 则| | (A B)| = _.11 设 A,B,R 是三个集合，其中 R 是实数集，A = x | -1x1, x R, B = x | 0x 6 (D)下午有会吗？653 425 设 I 是如下一个解释：Da,b,P ( a , a ) P(a, b) P(b, a) P(b, b) 1 0 1 01则在解释 I 下取真值为 1 的公式是( ).(A) x yP(x,y) (B) x yP(x,y) (C) xP(x,x) (D) x yP(x,y). 6. 若供选择答案中的数值表示一个简

16、单图中各个顶点的度，能画出图的是( ). (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)，HP (Q P)，则 G 与 H 的关系是( )。(A)G H (B)H G (C)GH (D)以上都不是.9 设 A, B 为集合，当( )时 ABB.(A)AB (B)A

17、B (C)B A (D)AB .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,c12 命题 xG(x)取真值 1 的充分必要条件是( ).(A) 对任意 x，G(x)都取真值 1. (B)有一个 x0，使 G(x0)取真值 1.(C)有某些 x，使 G(x0)取真值 1. (D)以上答案都不对.13. 设 G 是连通平面图，有 5

18、 个顶点，6 个面，则 G 的边数是( ). (A) 9 条 (B) 5 条 (C) 6 条 (D) 11 条.14. 设 G 是 5 个顶点的完全图，则从 G 中删去( )条边可以得到树. (A)6 (B)5 (C)10 (D)4.15. 设图 G 的相邻矩阵为 01 11 11 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 ，则 G 的顶点数与边数分别为( ).1 1 1(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.三、计算证明题1.设集合 A1, 2, 3, 4, 6, 8, 9, 12，R 为整除关系。(1) 画出半序集(A,R)的哈斯

19、图；(2) 写出 A 的子集 B = 3,6,9,12的上界，下界，最小上界，最大下界； (3) 写出 A 的最大元，最小元，极大元，极小元。2.3.4.设集合 A1, 2, 3, 4，A 上的关系 R(x,y) | x, y A 且 x y, 求(1) 画出 R 的关系图；(2) 写出 R 的关系矩阵.设 R 是实数集合， , , 是R上的三个映射， (x) = x+3, (x) = 2x, (x) x/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

20、 0 0 1 1试求 (1) P(a, f (a)P(b, f (b);(2) x yP (y, x).5. 设集合 A1, 2, 4, 6, 8, 12，R 为 A 上整除关系。(1) 画出半序集(A,R)的哈斯图；(2) 写出 A 的最大元，最小元，极大元，极小元；(3) 写出 A 的子集 B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.6. 设命题公式 G = (PQ)(Q( PR), 求 G 的主析取范式。7. (9 分)设一阶逻辑公式：G = ( xP(x) yQ(y) xR(x)，把 G 化成前束范式.9. 设 R 是集合 A = a, b, c, d. R 是 A

21、 上的二元关系, 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 = (PQ)( PQR)(2) H = (P(QR)(Q( PR)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) 计算 RS, RS, R , S

22、R .四、证明题1. 利用形式演绎法证明：PQ, RS, PR蕴涵 QS。2. 设 A,B 为任意集合，证明：(A-B)-C = A-(BC).3. (本题 10 分)利用形式演绎法证明： AB, C B, CD蕴涵 AD。m n4. (本题 10 分)A, B 为两个任意集合，求证：A(AB) = (AB)B .参考答案一、填空题1. 3; 3,1,3,2,3,1,2,3.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 QR).5. 12, 3.6. 4, 1, 2, 3, 4, 1, 2