《离散数学考试题详细答案.pdf》由会员分享，可在线阅读，更多相关《离散数学考试题详细答案.pdf（7页珍藏版）》请在三一文库上搜索。
1、离散数学考试题 (后附详细答案 ) 一、命题符号化（共6 小题，每小题3 分，共计18 分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设 P表示命题“上午下雨” ，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示 命题“在家看报” ，命题符号化为： （P? Q ）(P? RS) b)我今天进城，除非下雨。 设 P表示命题“我今天进城”，Q表示命题“天下雨” ，命题符号化为：QP或PQ c)仅当你走，我将留下。 设 P表示命题“你走” ，Q表示命题“我留下” ，命题符号化为： QP 2.用谓词逻辑把下列命题符号化 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)表示“xA”, B(x) 表示“xB”,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(QR)(R(QP) 的主析取范式、主合取范式，并写出所有成真赋 值。 （5 分） (P (QR)(R(QP)（PQR ）(PQR) ( （PQR） (PQR)(PQR) （PQR） ). ( （P QR） (PQR) (P Q R) （PQR） ) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQ R（P QR（PQR（PQ R （P Q
4、R 2.设个体域为 1,2,3，求下列命题的真值（4 分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求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) a 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) 真命题
5、。 因为（AB）C=（AB）C=（AC）（BC）=（A-C ）（B-C） b) 真命题。因为如果f 是从集合A 到集合 B 的入射函数，则|ranf|=|A|，且 ranfB,故 命题成立。 5.设 A是有穷集， |A|=5 ，问（每小题2 分，共 4 分） a)A上有多少种不同的等价关系？ b)从 A到 A的不同双射函数有多少个？ a) 52 b) 5!=120 6.设有偏序集 ，其哈斯图如图1，求子集B=b,d,e的最小元，最大元、极大元、 极小元、上界集合、下界集合、上确界、下确界，(5 分) f g d e b c 图 1 B 的最小元是b， 无最大元、极大元是d 和 e、 极小元是b
6、、 上界集合是 g 、 下界集合是 a,b、 上确界是g、下确界是b. 7.已知有限集S=a1,a 2, ,an,N 为自然数集合，R 为实数集合，求下列集合的基数 S;P(S);N,N n;P(N);R,R R,o,1N （写出即可） (6 分) KS=n; KP(S)= n 2; KN= 0,KN n= 0, KP(N)=; KR=, K=R R= ,K0,1 N = 三、证明题（共3 小题，共计40 分） 1.使用构造性证明，证明下面推理的有效性。（每小题5 分，共 10 分） a)A(BC),(E F)C, B (AS)BE b)x(P(x) Q(x), x(Q(x) R(x) ，xR
7、(x) xP(x) a) 证（1）B P(附加条件 ) （2）B(AS) P (3) AS 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) (EF)C P (9) (EF) T(7)(8) I (10) EF T(9) E (11) E T(10) I (12) BE CP b) 证 (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(
8、c) US(6) (8) P(c) T(5)(7) I (9) xP(x) EG(8) 2.设 R1是 A 上的等价关系， R2是 B 上的等价关系，A且 B，关系R 满足： ,R，当且仅当 R1且R2。试证明： R 是 AB 上的 等价关系。（ 10 分） 证 任取 , ABxAy B R1R2, R， 故 R是自反的 任取 , , R R1 R2 R1 R2 , R. 故 R是对称的。 任取 ,R ,RR1 R2 R1 R2 ( R1 R1) ( R2 R2) R1 R2 , R, 故 R是传递的。 综上所述 R 是 A B 上的等价关系。 3.用伯恩斯坦定理证明（0,1 和(a,b)等势
9、。 （10 分） 证 构造函数f： （0,1 (a,b)，f(x)= 22 b x a , 显然 f 是入射函数 构造函数g: (a,b)（ 0,1 ， ab ax xg)(, 显然 g 是入射函数， 故（ 0,1 和 (a,b)等势。 由于 2 21 22 2 2 1 r mmm r mmm rr ，所以 2 2 r n r s 4.设 R 是集合 A 上的等价关系，A 的元素个数为n，R 作为集合有s个元素，若A 关于 R 的商集 A/R 有 r 个元素，证明：rsn 2。 （10 分） 证设商集 A/R 的 r 个等价类的元素个数分别为m1,m2,mr，由于一个划分对应一个等价 关系，
10、m1+m2+mr=n， smmm r 22 2 2 1 由于 2 21 22 2 2 1 r mmm r mmm rr （r 个数的平方的平均值大于等于这 r 个数的平均值的平方） ，所以 2 2 r n r s ，即 2 nrs 四、应用题（ 10 分） 在一个道路上连接有8 个城市，分别标记为a,b,c,d,e,f,g,h。城市之间的直接连接的道路是单 向的，有ab, a c, b g, g b, c f, fe, b d, d f. 对每一个城市求出从它出发 所能够到达的所有其他城市。 解 把 8 个城市作为集合A 的元素，即A=a,b,c,d,e,f,g,h ，在 A 上定义二元关系R
11、， R当且仅当从x 到 y 有直接连接的道路，即 R=, 那么该问题即变为求R 的传递闭包。 利用 Warshal 算法，求得t(R)= 00000000 01111010 00010000 00000000 00110000 00110000 01111000 01111110 那么从城市x 出发能到达的城市为)(,|)(yxRtyxyxIRt A ， 故有,)(gfedcbaIRt A ,)(gfedbIRt A ,)(fecIRt A ,)(fedIRt A )(efIRt A ,)(fedbgIRt A )()(eIRteIRt AA 离散数学考试题答案 一、命题符号化（共6 小题，每
12、小题3 分，共计18 分） 1.用命题逻辑把下列命题符号化 a)设 P 表示命题“上午下雨” ，Q表示命题“我去看电影”，R 表示命题“在家里读书”，S 表示命题“在家看报” ，命题符号化为： （P? Q ）(P? RS) b)设 P表示命题“我今天进城”，Q表示命题“天下雨” ，命题符号化为：Q P或P Q c)设 P表示命题“你走” ，Q表示命题“我留下” ，命题符号化为： QP 2.用谓词逻辑把下列命题符号化 a)设 R(x) 表示“ x 是实数”，Q(x) 表示“ x 是有理数”，命题符号化为： x(R(x) Q(x) 或x(R(x) Q(x) b)设 R(x) 表示“ x 是实数”，
13、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) 二、简答题（共6 道题，共 32 分） 1.(P (QR)(R(QP)（PQR ）(PQR) ( （PQR） (PQR)(PQR) （PQR） ). ( （P QR） (PQR) (P Q R)
14、 （PQR） ) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQ R（P QR（PQR（PQ 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) yz(F(y) G(z) xyz(F(x)G(x) (F(y) G(z) 4.a) 真命题。因为（AB） C=（AB）C=（AC）（BC）=（ A-C ） （ B-C） b) 真命题。因为如果f 是从集合A 到集合 B 的入射函数，则|ranf|
15、=|A|，且 ranfB,故 命题成立。 5.a) 52 b) 5!=120 6.B 的最小元是b，无最大元、极大元是d 和 e、极小元是b、上界集合是 g 、下界集合 是a,b、上确界是g、下确界是b. 7.KS=n; KP(S)= n 2; KN= 0,KN n= 0, KP(N)=; KR=, K=R R= ,K0,1 N = 三、证明题（共3 小题，共计40 分） 1.a) 证（1）B P(附加条件 ) （2）B(AS) P (3) AS 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) (EF)C
16、 P (9) (EF) T(7)(8) I (10) EF T(9) E (11) E T(10) I (12) BE CP b) 证 (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.证 任取 , ABxAy B R1R2, R， 故 R是自反的 任取 , , R R1 R2 R1 R2 , R. 故 R是对称的。 任取 ,R ,
17、RR1 R2 R1 R2 ( R1 R1) ( R2 R2) R1 R2 , R, 故 R是传递的。 综上所述 R 是 A B 上的等价关系。 3.证 构造函数f： （0,1 (a,b)，f(x)= 22 b x a ,显然 f 是入射函数 构造函数g: (a,b)（ 0,1 ， ab ax xg)(, 显然 g 是入射函数， 故（ 0,1 和 (a,b)等势。 由于 2 21 22 2 2 1 r mmm r mmm rr ，所以 2 2 r n r s 4.证设商集 A/R 的 r 个等价类的元素个数分别为m1,m2,mr， 由于一个划分对应一个等 价关系， m1+m2+mr=n， smm
18、m r 22 2 2 1 由于 2 21 22 2 2 1 r mmm r mmm rr （r 个数的平方的平均值大于等于这 r 个数的平均值的平方） ，所以 2 2 r n r s ，即 2 nrs 四、应用题（ 10 分） 解 把 8 个城市作为集合A 的元素，即A=a,b,c,d,e,f,g,h ，在 A 上定义二元关系R， R当且仅当从x 到 y 有直接连接的道路，即 R=, 那么该问题即变为求R 的传递闭包。 利用 Warshal 算法，求得t(R)= 00000000 01111010 00010000 00000000 00110000 00110000 01111000 01111110 那么从城市x 出发能到达的城市为)(,|)(yxRtyxyxIRt A ， 故有,)(gfedcbaIRt A ,)(gfedbIRt A ,)(fecIRt A ,)(fedIRt A )(efIRt A ,)(fedbgIRt A )()(eIRteIRt AA