离散数学考试题详细答案

1、离散数学考试题 (后附详细答案 )一、命题符号化（共6 小题，每小题3 分，共计18 分）1. 用命题逻辑把下列命题符号化a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。设 P 表示命题“上午下雨” ， Q表示命题“我去看电影”， R表示命题“在家里读书”，S 表示命题“在家看报” ，命题符号化为： （P? Q）(P ? RS)b) 我今天进城，除非下雨。设 P 表示命题“我今天进城”，Q表示命题“天下雨” ，命题符号化为：QP 或P Qc) 仅当你走，我将留下。设 P 表示命题“你走” ， Q表示命题“我留下” ，命题符号化为：Q P2. 用谓词逻辑把下列命题符号化a) 有些实数不

2、是有理数设 R(x) 表示“ x 是实数”， Q(x) 表示“ x 是有理数”，命题符号化为：x(R(x)Q(x)或x(R(x)Q(x)b) 对于所有非零实数 x，总存在 y 使得 xy=1 。设 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 是从 A 到 B 的函数当且仅当对于每个aA 存在唯一的bB ，使得 f(a)=b.设 F(f) 表示 “f 是从 A 到 B 的函数” , A(x) 表示“ x A ”, B(x) 表示“ x B”,E(x,y) 表示“ x=y”,

3、命题符号化为：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) 的主析取范式、主合取范式，并写出所有成真赋值。（ 5 分）(P (Q R)(R (Q P)（PQR）(PQR)（(PQR）(PQR)(PQR) （PQR）).(（PQR）(PQR)(PQR)（PQR）)(P Q R)( 公式的所有成真赋值为（PQR（PQR)这是主合取范式000,001,010,100,101,111,故主析取范式为PQR（PQR（PQR（PQ R（PQ R2. 设个体域为 1,

4、2,3 ，求下列命题的真值（ 4 分）a)xy(x+y=4)b) y x (x+y=4)a) Tb) F3.求x(F(x)x(F(x) G(x) G(x) ( ( xF(x)xF(x) xG(x)xG(x)的前束范式。（ 4 分）x(F(x)G(x) (yF(y)zG(z)x(F(x)G(x) yz(F(y) G(z)xyz(F(x) G(x) (F(y)G(z)4.判断下面命题的真假，并说明原因。（每小题2 分，共 4 分）a)（AB ） C=(A-B)(A-C)b) 若 f 是从集合 A 到集合 B 的入射函数，则 |A| |B|a) 真命题。 因为（ AB ） C=（ AB）C=（ AC

5、）（Bb) 真命题。因为如果f 是从集合A 到集合 B 的入射函数，则C）=（A-C ）|ranf|=|A| ，且 ranf（B-C）B, 故命题成立。5. 设 A 是有穷集， |A|=5 ，问（每小题 2 分，共 4 分）a) A 上有多少种不同的等价关系？b) 从 A 到 A 的不同双射函数有多少个？a) 52b) 5!=1206. 设有偏序集 <A, >，其哈斯图如图 1，求子集 B=b,d,e 的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5 分)fgdebca图 1B 的最小元是 b，无最大元、极大元是 d 和 e、极小元是 b、上界集合是 g

6、、下界集合是 a,b 、上确界是 g、下确界是 b.7.已知有限集S=a 1,a 2, ,a n,N为自然数集合，R 为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R× R,o,1N（写出即可）(6 分)KS=n;KP(S)=2 n ;KN=0,KN n=0,KP(N)=;KR=, K=R × R=,K0,1N=三、证明题（共3 小题，共计40 分）1.使用构造性证明，证明下面推理的有效性。（每小题 5 分，共 10 分）a)A (B C),(E F) C, B (AS)BEb)x(P(x) Q(x),x(Q(x) R(x)，xR(x)xP(x)a)证

7、 （1）BP(附加条件 )（ 2） B(A S) P(3) A ST(1)(2) I(4) AT(3) I(5) A(B C)P(6)BCT(4)(5) I(7)CT(6) I(8)(E F)C P(9)(EF)T(7)(8) I(10) E FT(9) E(11) ET(10) I(12) B ECPb) 证 (1)xR(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)xP(x)EG(8)2.设 R1 是 A 上的

8、等价关系，R2 是 B 上的等价关系，A 且 B，关系R 满足：<<x 1,y1>,<x 2,y2>> R，当且仅当 < x 1, x 2> R1 且 <y 1,y2> R2。试证明： R 是 A × B 上的等价关系。（ 10 分）证 任取 <x,y >,<x,y > A × Bx Ay B<x,x> R1<y,y> R2<<x,y>,<x,y>> R，故 R 是自反的任取 <<x,y >,<u,v>

9、>,<<x,y >,<u,v>> R <x,u> R1<y,v> R2<u,x> R1<v,y> R2 <<u,v>,<x,y>> R.故 R 是对称的。任取 <<x,y >,<u,v>>,<<u,v>,<s,t>> R<<x,y >,<u,v>>,<<u,v>,<s,t>>R <x,u> R1 <y,v>

10、; R2<u,s> R1<v,t> R2(<x,u> R1 <u,s> R1)(<y,v> R2 <v,t> R2 ) <x,s> R 1<y,t> R2<<x,y>,<s,t>>R, 故 R是传递的。综上所述 R 是 A× B 上的等价关系。3.用伯恩斯坦定理证明（0,1 和(a,b)等势。（ 10 分）证 构造函数 f：（ 0,1 (a,b)， f(x)=ab是入射函数x, 显然 f22构造函数 g: (a,b)（ 0,1 ， g( x)xab, 显

11、然 g 是入射函数，a故（ 0,1 和 (a,b)等势。m12 m22mr2m1m22s n2mr由于rr，所以r r 24.设 R 是集合 A 上的等价关系，A 的元素个数为n，R 作为集合有s 个元素，若A 关于 R的商集 A/R有 r 个元素，证明： rsn2。（ 10 分）证 设商集 A/R的 r 个等价类的元素个数分别为m1,m2, ,mr ，由于一个划分对应一个等价关系， m1+m 2+ +m r=n， m12m22mr2sm12 m22mr2m1m2mr2（ r 个数的平方的平均值大于等于这由于rrsn 2，即rsn2r 个数的平均值的平方） ，所以r 2r四、应用题（ 10 分

12、）在一个道路上连接有8 个城市，分别标记为a,b,c,d,e,f,g,h 。城市之间的直接连接的道路是单向的，有 a b, a c, b g, g b, cf, f e, b d, d f. 对每一个城市求出从它出发所能够到达的所有其他城市。解 把 8个城市作为集合 A 的元素，即 A=a,b,c,d,e,f,g,h ，在 A 上定义二元关系R，<x,y >R 当且仅当从 x 到 y 有直接连接的道路，即R=<a,b>,<a,c>,<b,g>,<g,b>,<c,f>,<f,e>,<b,d>,<

13、d,f>那么该问题即变为求R 的传递闭包。011111100001111000001100利用 Warshal 算法，求得 t(R)=0000110000000000000010000101111000000000那么从城市 x 出发能到达的城市为(t( R)I A ) x y | x, y t( R) xy ，故有 (t( R) I A ) a b, c, d, e, f , g( t( R)I A )bd, e, f , g( t( R)I A )ce, f (t( R)I A )de, f ( t( R)I A ) f e( t( R)I A ) gb, d,e, f (t( R)

14、I A )e( t( R) I A )e离散数学考试题答案一、命题符号化（共6 小题，每小题3 分，共计18 分）1. 用命题逻辑把下列命题符号化a) 设 P 表示命题“上午下雨” ， Q 表示命题“我去看电影” ， R 表示命题“在家里读书” ， S表示命题“在家看报” ，命题符号化为： （P? Q）(P? RS)b)设P 表示命题“我今天进城”，Q表示命题“天下雨” ，命题符号化为：Q P或PQc) 设 P 表示命题“你走” ， Q表示命题“我留下” ，命题符号化为： Q P2. 用谓词逻辑把下列命题符号化a) 设 R(x) 表示“ x 是实数”， Q(x) 表示“ x 是有理数”，命题符

15、号化为：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)（PQR）(PQR)（(PQR

16、）(PQR)(PQR) （PQR）).(（PQR）(PQR)(PQR)（PQR）)(PQR)(PQR)这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（ PQR（PQR（PQR（PQR（PQR（P QR2.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(x) yz(F(y) G(z)xy z(F(x) G(x) (F(y) G(z)4.a) 真命题。因为（ AB） C=（AB）C=（AC）（ BC）=（ A-C ）（ B-C）b) 真命题。因为如果f 是从集合A

17、 到集合B 的入射函数，则|ranf|=|A| ，且ranfB, 故命题成立。5.a) 52b) 5!=1206. B 的最小元是 b，无最大元、极大元是 d 和 e、极小元是 b、上界集合是 g 、下界集合是a,b 、上确界是 g、下确界是 b.7.KS=n;KP(S)=2n ;KN=0,KN n =0,KP(N)=;KR=,K=R × R=,K0,1N=三、证明题（共3 小题，共计40 分）1.a) 证（ 1） BP(附加条件 )（ 2） B(A S) P(3)AST(1)(2) I(4)AT(3) I(5)A(BC) P(6)BCT(4)(5) I(7)CT(6) I(8)(E

18、 F)C P(9)(EF)T(7)(8) I(10) E FT(9) E(11) ET(10) I(12) B ECPb) 证 (1)xR(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)xP(x)EG(8)2. 证 任取 <x,y >,<x,y > A × Bx Ay B<x,x> R1<y,y> R2<<x,y>,<x,y>&g

19、t; R，故 R 是自反的任取 <<x,y >,<u,v>>,<<x,y >,<u,v>> R <x,u> R1<y,v> R2<u,x> R1<v,y> R2 <<u,v>,<x,y>> R.故 R 是对称的。任取 <<x,y >,<u,v>>,<<u,v>,<s,t>> R<<x,y >,<u,v>>,<<u,v>

20、;,<s,t>>R <x,u> R1 <y,v> R2<u,s> R1<v,t> R2(<x,u> R1<u,s> R1)(<y,v> R2 <v,t> R2 ) <x,s> R 1<y,t> R2<<x,y>,<s,t>>R, 故 R是传递的。综上所述 R 是 A× B 上的等价关系。3.证 构造函数 f：（ 0,1(a,b)ab， f(x)=x, 显然 f 是入射函数22构造函数 g: (a,b)（ 0,1xa， g( x), 显然 g 是入射函数，ba故（ 0,1 和 (a,b) 等势。m12 m22mr2m1m2mr2s n2由