离散数学考试试题(A、B卷及答案)

.离散数学考试试题(a 卷及答案）一、证明题（10 分）1) (pq ac) ( apqc)( a( pq)c。pq=(p-q) 合取（ q-p）证明 : (pq ac) ( apq c)(pqa c) (a p q c)(pqa) (a p q) c 反用分配律( p q a) ( apq) c( a ( p q) (pq) c 再反用分配律( a ( pq) c( a ( pq)c2) (pq)pq。证明：(pq)(p q)(pq)pq。二、分别用真值表法和公式法求( p( q r) (p ( qr) 的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15 分）。主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由析取范式经等值演算法算得。证明：公式法：因为( p( q r) (p ( qr)(p q r) (p ( q r) (qr)(p q r) (pq) (p r) (qr) 分配律(p q r) (p qq) (p qr) (p rq) (p;. rr)为 4(p q r) (p qr) (pqr)m 4 m 5 m 6 使（非 p 析取 q析取 r）为 0 所赋真值，即100，二进制m0 m1 m2 m3 m7所以，公式 ( p( q r) (p ( qr) 为可满足式，其相应的成真赋值为000、001、 010、011、111：成假赋值为：100、101、110。00011110010111010011101111111001010101010011001001111111真值表法：pqrqrp( q r)p( qr)( p( q r) (p( qr)由真值表可知， 公式 ( p( q r) (p ( qr) 为可满足式， 其相应的成真赋值为 000、001、010、011、 111：成假赋值为：100、101、110。三、推理证明题（10 分）1）p q，q r， rsps。证明：(1) p附加前提(2) pqp(3) qt(1)(2)，i （析取三段论）(4)q rp(5) rt(3)(4)， i （析取三段论）(6) rsp(7) st(5)(6)， i （假言推理）(8) pscp2)x(p(x)q(y) r(x) ， xp(x)q(y) x(p(x) r(x)证明（ 1）xp(x) (2)p(a)(3)x(p(x)q(y) r(x)(4)p(a)q(y) r(a)(5)q(y) r(a) (6)q(y)(7)r(a)(8)p(a)(9)p(a) r(a)(10)x(p(x) r(x) (11)q(y) x(p(x) r(x)五、已知a、b、c 是三个集合，证明( a b) c ( a c) ( b c)（10 分） 证明：因为x ( a b) cx ( a b) cx ( a b) xc( x a x b) xc( x a xc) ( x b xc)x ( a c) x ( b c)x ( a c) ( b c)所以， ( a b) c ( a c) ( b c) 。八、证明整数集i 上的模 m同余关系r=|xy(mod m) 是等价关系。其中，x y(mod m)的含义是x-y可以被 m整除（ 15 分）。x(modm)=y(modm)证明： 1）x i ，因为（ x-x ） /m=0，所以 xx(mod m) ，即 xrx。2） x,y i ，若 xry，则 x y(mod m)，即（ x-y ）/m=k i ，所以（ y - x） /m=-k i ， 所以 yx(mod m) ，即 yrx。3） x,y,z i ，若 xry，yrz，则（ x-y ）/m=u i ，（y-z ）/m=v i ，于是（ x-z ）/m=-1（ x-y+y-z） /m=u+v i ，因此 xrz。g-1-1九、若 f:a b 和 g:b c 是双射，则（gf ） =f证明：（ 10 分）。-1-1 -1-1 -1-1-1因为 f 、g 是双射，所以gf ：a c 是双射，所以gf 有逆函数（ gf ） ： c a。同理可推 fg ： c a 是双射。因为 fg存在 z（ g f）存在 z（ f g） gf （ gf ） -1 , 所以（ gf ） -1 =f -1 g-1 。离散数学考试试题 (b 卷及答案）一、证明题（10 分）1)(p q)(p (qr) (pq) (pr)t证明 :左端(p q) (p (q r) (p q)(p r)( 摩根律 )(p q) (p q) (p r) (p q) (p r)( 分配律 )(p q) (p r) (p q) (p r) (等幂律 ) t( 代入 )2)xy( p( x)q( y)(xp( x)yq( y)证明：xy( p( x)q( y)xy(p( x) q( y)x(p( x) yq( y) xp( x) yq( y)xp( x) yq( y) (xp( x)yq( y)二、求命题公式(pq)(p q) 的主析取范式和主合取范式（10 分）解： (pq)(p q)(pq) (pq)三、推理证明题（10 分）(p q) (p q)(pq) (p q)(p pq) (q pq) (p q)m1析取要使之为假，即赋真值001，即 m1 m0 m2 m3使之为真1)(p(qs) (r p) qrs证明： (1)r(2)r pp(3)pt（ 1）（ 2）析取三段论(4)p(qs)p(5)qst（ 3）（ 4） i 假言推理(6)qp(7)s(8)rst（ 5）（ 6） i 假言推理cp2) x( a( x)yb( y) ，x( b( x)yc( y)xa( x)yc( y) 。证明： (1)x( a( x)yb( y)p(2)a( a)yb( y)t(1)es(3)x( b( x)yc( y)p(4)x( b( x)c( c )t(3)es(5) b( b )(6) a( a)c( c )t(4）us(7) a( a)b( b )c( c )t(2)ust(5)(6)i假言三段论(8)xa( x)c( c )t(7)ug(9)xa( x)yc( y)t(8)eg四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15 分）。解 ：设 p：今天天气好，q：考试准时进行，a( e) ： e 提前进入考场，个体域：考生的集合，则命题可符号化为：pxa( x) ，xa( x)qqp。(1) pxa( x)p(2) pxa( x)t(1) e(3) xa( x)pt(2) e(4) xa( x)qp(5)(xa( x)q) ( qxa( x)t(4) e(6) qxa( x)t(5) i(7) qpt(6)(3)i五、已知a、b、c 是三个集合，证明a(b c)=(a b) (a c) （ 10 分） 证明：xa （ b c）xa x（ b c）xa（ xb xc）（ xa xb）（ xa xc）x（ ab） xa cx（ ab）（ a c） a（ b c） =（ a b）（ a c）六、 a= x 1,x 2,x 3 ， b= y 1,y 2 ， r=, ，求其关系矩阵及关系图（ 10 分）。有就是 1，没就是 0七、设 r=,，求 r(r)、s(r) 和 t(r) ，并作出它们及 r 的关系图（ 15 分）。r(r)=,（自反闭包）s(r)=,（对称闭包）t(r)=,（传递闭包）九、设f：ab， g： bc， h：ca，证明：如果h g fia， f h g ib， g f h ic， 则 f、g、h 均为双射，并求出f 1、g 1 和 h1 （10 分）。解因 i a 恒等函数， 由 h g f ia 可得 f 是单射， h 是满射； 因 ib 恒等函数， 由 f h g i b 可得 g 是单射， f 是满射；因ic 恒等函数，由g f h ic 可得 h 是单射， g 是满射。从而 f、g、h 均为双射。 1 1 1由 h g f i a，得 f h g；由 f h g i b，得 g f h；由 gf hi c，得 h g f。五.(12分) 令 x=x1,x2,.,xm,y=y1,y2,.,yn,问:(1) 有多少不同的由x 到 y 的关系 ?(2) 有多少不同的由x 到 y 的影射 ?(3) 有多少不同的由x 到 y 的单射，双射 ?（ 12 分） 是个群， ug，定义 g中的运算“”为 ab=a*u-1*b ，对任意 a,b g， 求证： 也是个群。证明： 1）a,b g， ab=a*u-1*b g，运算是封闭的。2