离散数学考试题详细答案

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

2、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的函数当且仅当对于每个aC A存在唯一的be B,使得f(a)=b.设F表示“f是从A到B的函数"，A(x)表示“xC A”，B(x)表示“xC B”，E(x,y)表示“x=y”，命题符号化为：F(f)

3、? Va(A一三b(B(b) AE(f(a),b) aVc(S(c) a E(f(a),c) - E(a,b)、简答题(共6道题，共32分)1.求命题公式(P 一 (Q-R)(R- (Q-P)的主析取范式、主合取范式，并写出所有成真赋值。(5分)(P- (Q-R)(R一 (Q-P)( P(P QR) 一 (PQQR)(PR)(PQ R)Q R) 一(P,g、 R)(P(P Q R)(Q R)八(P处R)( PP Q R)这是主合取范式P QR).QR)公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为(Pa Q R)( Pa QR)(P Q RPaQx R)(P

4、a Qy R)(P Q R2.设个体域为1,2,3,求下列命题的真值(4分)a) xy(x+y=4)b) yx (x+y=4)a) T b) F3.求 x(F(x) 一G(x) 一( xF(x) 一 xG(x)的前束范式。(4 分)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 .判断下面命题的真假，并说明原因。(每小题2分，共4分)a)(AB) C=(A-B)(A-C)b)若f是从集合A到集合B

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

6、 b,无最大兀、极大兀是d和e、极小兀是 上确界是g、下确界是b.7 .已知有限集S=a1,a2,an,N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R X R,o,1 N (写出即可)(6 分)KS=n;KP(S)= 2n ; KN=0KN n=0, KP(N)=; KR=, K=R X R=,K0,1 Nl=三、证明题(共3小题，共计40分)1.使用构造性证明，证明下面推理的有效性。(每小题5分，共10分)a) 2 (BAC),(E 一 F) 一b) x(P(x) -Q(x),a)证(1) B P(C, Bf(AA S) x(Q(x) VR(x),

7、附加条件)BfEx R(x)x P(x)(2) B-(AA S) P(3) A AS T(1)(2) I(4) A T(3) I一 (BAC)P(6) BC(8) (E(9)(10) E(11) E(12) B b)证(1)(2)(3)(4) Q(c)(5) Q(c)(6)(7) P(c)(8)(9)A C T(4)(5) IT(6) I一F) 一C P(E - F)T(8) IA F T(9) ET(10) I一 ECPx R(x)PR(c) ES(1)x(Q(x) V R(x) PV R(c) US(3)T(2)(4) Ix(P(x) -Q(x) P一 Q(c)US(6)P(c) T(5)

8、 Ix P(x)EG(8)2.设Ri是A上的等价关系，R2是B上的等价关系，A丰 且Bw ，关系R满足： <<x1,y1>,<x2,y2>> C R,当且仅当 < x 1, x2> C Ri且<y 1,y2> C R2。试证明：R 是 AXB 上的 等价关系。(10分)证任取<x,y>,<x,y>CAXB xCA yCB <x,x> C Ri<y,y> R2 <<x,y>,<x,y>> CR,故 R是自反的任取 <<x,y >,<

9、;u,v>>,<<x,y >,<u,v>> C R <x,u> C Ri<y,v> 6 R2 <u,x> C Ri<v,y> e R2 <<u,v>,<x,y>> C R.故R是对称的。任取 <<x,y >,<u,v>>,<<u,v>,<s,t>>CR<<x,y >,<u,v>>,<<u,v>,<s,t>> CR <

10、x,u> C Ri <y,v>R2<u,s> C R1<v,t> C R2(<x,u> £ Ri <u,s> £ R1) (<y,v> £ R2<v,t> £ R2) <x,s> Ri <y,t> £ R2 <<x,y>,<s,t>>e r,故r是传递的。综上所述R是AX B上的等价关系。3.用伯恩斯坦定理证明(0,1和(a,b)等势。(10分)ab证 构造函数f: (0,1 一(a,b) , f

11、(x)= -x+ ，显然f是入射函数22x - a构造函数g: (a,b) 一(0,1 , g(x)=，显然g是入射函数,b a故(0,1和(a,b)等势。22.2由于-m2 mr_r22s n,所以一> r r4.设R是集合A上的等价关系，A的元素个数为n, R作为集合有s个元素，若A关于R的商集A/R有r个元素，证明：rs>n2o （10分）证 设商集A/R的r个等价类的元素个数分别为mi,m2,mr,由于一个划分对应一个等价关系，mi+m2+mr=n, m2m1m2 一 一 mr由于-2rim1+m2 +mr |! （r个数的平方的平均值大于等于这r个数的平均值的平方），所以

12、2n 口口2> ,即 rs > nr四、应用题（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.对每一个城市求出从它出发 所能够到达的所有其他城市。解 把8个城市作为集合 A的元素，即A=a,b,c,d,e,f,g,h,在A上定义二元关系R, <x,y>C R当且仅当从x到y有直接连接的道路，即R=<a,b>,<a,c>,<b,g>,<g,b>,<c,f&

13、gt;,<f,e>,<b,d>,<d,f> 那么该问题即变为求 R的传递闭包。利用 Warshal算法，求得t（R尸11110 11110 0 110 0 0 110 0 0 0 0 0 0 0 10 0 0 11110 0 0 0 0 0那么从城市x出发能到达的城市为(t(R) I a)x =y|< x,y* t(R)AX# y,故有(t(R) -I A)a =b,c,d,e, f,g (t(R) -lA)b =d,e, f,g(t(R) Ta)c =e, f(t(R) -lA)d =e,f(t(R) TA)f =e(t(R) TA)g =b,d,e

14、, f(t(R) -lA)e =(t(R) - A)e=离散数学考试题答案一、命题符号化(共 6小题，每小题3分，共计18分)1 .用命题逻辑把下列命题符号化a)设P表示命题“上午下雨” ，Q表示命题“我去看电影” ，R表示命题“在家里读书” ，S表示命题“在家看报”，命题符号化为：(P? Q (P? R S)b)设P表示命题“我今天进城” ，Q表示命题“天下雨"，命题符号化为：CH P或P-Qc)设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至ij B的函数” “x=y"，命题符号化为：,A(x)表布 “ x C A ”，B(x)表不“ xC B”,E(x,y)表不F？ Va(A一三b(B(b)八 E(f(a),b)A Vc(S(c) A E(f(a),c) - E(a,b)二、简答题(共6道题，共32分)1. (P - (Q-R)(P(PaQ

16、-x(R - (Q-P)QR) 一 (PP QR)(PR)(PR)(R)(PR)(PQP Q R)R)这是主合取范式QR)- PR)1PQQR).R)公式的所有成真赋值为(PaQxR)(P Q R2. a) T b) F000,001,010,100,101,111,故主析取范式为PaQR)(Pa QxR)(PQxR)3.x(F(x) x(F(x)G(x) 一(一 G(x)一xF(x) 一 xG(x) y z(F(y) - G(z)x(F(x) - G(x) 一( x y z(F(x)yF(y) - zG(z)>G(x) 一 (F(y)G(z)4.a)b)真命题。(B-C)真命题。因为(

17、AB) C= (A B)因为如果f是从集合A到集合BC= (AC)(B C) = (A-C)的入射函数，则|ranf|=|A|,且ranf B,故5.6.命题成立。a) 52 b) 5!=120B的最小元是b,无最大元、极大元是d和e、极小元是b、上界集合是g、下界集合是a,b、上确界是g、下确界是b.7. KS=n;KP(S)= 2 n ; KN=0,KN n=。, KP(N)=； KR=, K=R X R尸,K0,1上三、证明题(共3小题，共计40分)i.a)证(i) BP(附加条件)(2) B-(AAS) P(3) AA ST(i)(2) I(4) AT(3) I(5) A一 (BAC)

18、 P(6) BACT(4)(5) ICT(6) I(8) (E一 FF) 一 C P(9)(JF) 丁I(i0) EA FT(9) E(ii) ET(i0) I(i2) B一 ECPb)证(i)x R(x)P(2)R(c)ES(i)(3)x(Q(x) V R(x) P(4) Q(c)V R(c)US(3)(5) Q(c)T(2)(4) I(6)x(P(x) 一Q(x) P P(c)一 Q(c)US(6)(8)P(c)T(5)(7) I(9)x P(x)EG(8)2.证任取<x,y>,<x,y>CAXB xCA yCB <x,x> C Ri <y,y&g

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

20、;<x,y >,<u,v>>,<<u,v>,<s,t>> CR <x,u> Ri<y,v> C R2<u,s> C Ri <v,t> C R2(<x,u> £ Ri<u,s> £ Ri) (<y,v> £ R2 <v,t> £ R2) <x,s> Ri <y,t> £ R2<<x,y>,<s,t>>e r,故r是传递的。综上所述R是AX B上的等价关系。ab 一3.证 构造函数f: (0,i 一(a,b) , f(x)= x+ ，显然f是入射函数22x -a构造函数g: (a,b) 一(0,i , g(x)=，显然g是入射函