《《离散数学》试题及答案》由会员分享，可在线阅读，更多相关《《离散数学》试题及答案（8页珍藏版）》请在金锄头文库上搜索。
1、一、填空题一、填空题 1 设集合 A,B，其中 A1,2,3, B= 1,2, 则 A - B_3_; (A) - (B) _ 3,1,3,2,3,1,2,3._ .2. 设有限集合 A, |A| = n, 则 |(AA)| = _2n2_.3. 设集合 A = a, b, B = 1, 2, 则从 A 到 B 的所有映射是_1= (a,1), (b,1), 2= (a,2),(b,2),3= (a,1), (b,2), 4= (a,2), (b,1)_ _, 其中双射的是_a3,a4_.4. 已知命题公式 G(PQ)R，则 G 的主析取范式是_(PQR)_.6 设 A、B 为两个集合, A=
2、 1,2,4, B = 3,4, 则从 AB_4_; AB_1234_;AB _12_ .2.7. 设 R 是集合 A 上的等价关系，则 R 所具有的关系的三个特性是_自反性；对称性；传递性.3.8. 设命题公式 G(P(QR)，则使公式 G 为真的解释有_，_, _.4.9. 设集合 A1,2,3,4, A 上的关系 R1 = (1,4),(2,3),(3,2), R2 = (2,1),(3,2),(4,3), 则R1R2 = _(1,3),(2,2),(3,1); _,R2R1 =_(2,4),(3,3),(4,2); _,R12 =_(2,2),(3,3)._.10. 设有限集 A, B
3、，|A| = m, |B| = n, 则| |(AB)| = _2mn_.5.11 设 A,B,R 是三个集合，其中 R 是实数集，A = x | -1x1, xR, B = x | 0x 6 (D)下午有会吗？5 设 I 是如下一个解释：Da,b, 0 1 0 1b) P(b,a) P(b,b) P(a,),(aaP则在解释 I 下取真值为 1 的公式是( d ).(A)xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)xyP(x,y). 6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( c ). (A)(1,2,2,3,4,5) (B)(1,2,3
4、,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6). 7. 设 G、H 是一阶逻辑公式，P 是一个谓词，GxP(x), HxP(x),则一阶逻辑公式 GH 是( c ). (A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式. 8 设命题公式 G(PQ)，HP(QP)，则 G 与 H 的关系是( a )。 (A)GH (B)HG (C)GH (D)以上都不是. 9 设 A, B 为集合，当( d )时 ABB. (A)AB(B)AB(C)BA(D)AB. 10 设集合 A = 1,2,3,4, A 上的关系 R(1,1),(2,3),(2,4),(3,4),
5、则 R 具有( b )。 (A)自反性 (B)传递性(C)对称性 (D)以上答案都不对 三、计算证明题三、计算证明题1.设集合 A1, 2, 3, 4, 6, 8, 9, 12，R 为整除关系。(1) 画出半序集(A,R)的哈斯图；(2)124836129124836129(3) 写出 A 的子集 B = 3,6,9,12的上界，下界，最小上界，最大下界；(2) B 无上界，也无最小上界。下界 1, 3; 最大下界是 3.123456(4) 写出 A 的最大元，最小元，极大元，极小元。A 无最大元，最小元是 1，极大元 8, 12, 90+; 极小元是 1.2.设集合 A1, 2, 3, 4，
6、A 上的关系 R(x,y) | x, yA 且 x y, 求 (1) 画出 R 的关系图；.R = (1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1) (2) (2) 写出 R 的关系矩阵.1000 1100 1110 1111RM 3.设 R 是实数集合，,是 R 上的三个映射，(x) = x+3, (x) = 2x, (x) x/4,试求复 合映射，, , ，.(1)(x)(x)+32x+32x+3.(2)(x)(x)+3(x+3)+3x+6,(3)(x)(x)+3x/4+3, (4)(x)(x)/42x/4 =
7、x/2,(5)()+32x/4+3x/2+3.4. 设 I 是如下一个解释：D = 2, 3, abf (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);P(a, f (a)P(b, f (b) = P(3, f (3)P(2, f (2)= P(3, 2)P(2, 3)= 10= 0.1 2 3 4 (2) xy P (y, x).xy P (y, x) = x (P (2, x)P (3, x) = (P (2, 2)P (3, 2)(P (2, 3)P (3, 3)= (01)(01)= 11=
8、 1.5. 设集合 A1, 2, 4, 6, 8, 12，R 为 A 上整除关系。 (1) 画出半序集(A,R)的哈斯图；(2) 写出 A 的最大元，最小元，极大元，极小元；无最大元，最小元 1，极大元 8, 12; 极小元是 1.(3) 写出 A 的子集 B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.B 无上界，无最小上界。下界 1, 2; 最大下界 2.6. 设命题公式 G = (PQ)(Q(PR), 求 G 的主析取范式。G = (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(QP)(QR)= (PQR)(PQR)(PQR)(PQR)(
9、PQR)(PQR)= (PQR)(PQR)(PQR)(PQR)(PQR)= m3m4m5m6m7 = (3, 4, 5, 6, 7).7. (9 分)设一阶逻辑公式：G = (xP(x)yQ(y)xR(x)，把 G 化成前束范式.24168122416812G = (xP(x)yQ(y)xR(x)= (xP(x)yQ(y)xR(x)= (xP(x)yQ(y)xR(x)= (xP(x)yQ(y)zR(z)= xyz(P(x)Q(y)R(z)9. 设 R 是集合 A = a, b, c, d. R 是 A 上的二元关系, R = (a,b), (b,a), (b,c), (c,d),(1) 求出
10、r(R), s(R), t(R)；(1) r(R)RIA(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2)画出 r(R), s(R), t(R)的关系图.关系图:11. 通过求主析取范式判断下列命题公式是否等价：(1) G = (PQ)(PQR) (2) H = (P(QR)(Q(PR)G(P
11、Q)(PQR)(PQR)(PQR)(PQR)m6m7m3 (3, 6, 7)H = (P(QR)(Q(PR)(PQ)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m6m3m7bacdr(R)bacds(R)bacdt(R)bacdr(R)bacdr(R)bacds(R)bacds(R)bacdt(R)bacdt(R) (3, 6, 7)G,H 的主析取范式相同，所以 G = H.13. 设 R 和 S 是集合 Aa, b, c, d上的关系，其中 R(a, a),(a, c),(b, c),(c, d), S(a, b),(b, c),(b,
12、 d),(d, d).(1) 试写出 R 和 S 的关系矩阵；(1) 0000100001000101RM1000000011000010SM(2) 计算 RS, RS, R1, S1R1.RS(a, b),(c, d),RS(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d), R1(a, a),(c, a),(c, b),(d, c),S1R1(b, a),(d, c).四四 证明题证明题1. 利用形式演绎法证明：PQ, RS, PR蕴涵 QS。1. 证明：PQ, RS, PR蕴涵 QS(1) PRP(2) RPQ(1)(3) PQP(4) RQQ(2)(3)(5) QRQ(4)(6) RSP(7) QSQ(5)(6)(8) QSQ(7)2. 设 A,B 为任意集合，证明：(A-B)-C = A-(BC).证明：(A-B)-C = (AB)C = A(BC)= A(BC)= A-(BC)3. (本题 10 分)利用形式演绎法证明：AB, CB, CD蕴涵 AD。证明：AB, CB, CD蕴涵 AD(1) AD(附加)(2) ABP(3) BQ(1)(2)(4) CBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 AB, CB, C
