文档介绍：.实用文档 .
离散数学试题 (B 卷答案 1〕
一、证明题〔 10 分〕
1)( P∧ ( Q∧ R)) ∨ (Q∧ R)∨ (P ∧ R) R
证明: 左端 ( P∧ Q∧R)∨((Q∨P)∧R)
(( P1 ， 2}] 〔10 分〕。
解： R-1 ={<y ， x>| x
， y N∧ y=x 2}
R*S={<x ， y>| x ， y
N∧ y=x2+1}
S*R={<x ， y>| x，y
N∧ y=〔 x+1
〕2} ， R {1 ， 2}= {<1 ， 1>， <2，4>} ， S[{1 ， 2}]={1 ，
4} 。
七、设 R={<a， b>，<b， c>，<c， a>} ，求 r(R) 、 s(R) 和 t(R) 〔 15 分〕。解： r(R)={<a ，b>， <b， c>， <c，a>， <a，a>， <b，b>， <c，c>} s(R)={<a ， b>，<b， c>， <c， a>，<b， a>，<c， b>，<a， c>}
.
.实用文档 .
R2= R 5={<a ， c>， <b， a>，<c， b>}
R3={<a ，a>， <b，b>， <c，b>}
R4={<a ，b>， <b，c>， <c，c>}
t(R)={<a ，b>，<b，c>，<c ，a>， <a，c>，<b，a>，，<a，a>，<b，b>，<c ，b>，<c，
c>}
八、证明整数集 I 上的模 m同余关系 R={<x，y>|x y(mod m)} 是等价关系。 其中， x y(mod
m)的含义是 x-y 可以被 m整除〔 15 分〕。
证明： 1〕 x∈ I ，因为〔 x-x 〕 /m=0，所以 x x(mod m) ，即 xRx。
2〕 x，y∈ I ，假设 xRy，那么 x y(mod m)，即〔 x-y 〕/m=k∈I ，所以〔 y - x〕/m=-k
I ，所以 y x(mod m) ，即 yRx。
3〕 x，y，z∈ I ，假设 xRy，yRz，那么〔 x-y 〕/m=u∈I ，〔 y-z 〕/m=v∈I ，于是〔 x-z 〕
/m=〔 x-y+y-z 〕 /m=u+v
∈ I ，因此 xRz。
九、假设 f:A → B 和 g:B → C是双射，那么〔 gf 〕-1 =f -1 g-1 〔10
分〕。
证明：因为 f 、 g 是双射，所以 gf ： A→C是双射，所以
gf 有逆函数〔 gf 〕 -1 ：C→ A。
同理可推 f -1 g-1 ： C→ A 是双射。
因为 <x， y>∈ f -1 g-1
存在 z〔<x， z>∈g-1
<z，y> ∈ f -1 〕 存在 z〔 <y， z>∈f
<z，
x>∈ g〕 <y， x>∈ gf
<x， y>∈〔 gf 〕 -1 ，所以〔 gf 〕-1 =f -1 g-1 。
离散数学试题 (B 卷答案 2〕
一、证明题〔 10 分〕
1)((P ∨ Q)∧ ( P∧ ( Q∨ R))) ∨( P∧ Q)∨ ( P∧ R) 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) x y( P( x) Q( y)) ( xP( x) yQ( y))
证明： x y( P( x) Q( y)) x y( P( x) ∨ Q( y))
x( P( x) ∨ yQ( y))
x P( x) ∨ yQ( y)
xP( x) ∨ yQ( y)
( xP( x) yQ( y))
二、求命题公式 ( P Q) (P ∨ Q) 的主析取范式和主合取范式〔 10 分〕
解： ( P Q) (P∨ Q) ( P Q)∨(P∨ Q)
.
.实用文档 .
(P∨Q)∨(P∨ Q)
( P∧ Q)∨ (P ∨ Q)
( P∨ P∨ Q)∧ ( Q∨ P∨ Q)
(P∨ Q)
M1
m0∨ m2∨ m3
三、推理证明题〔 10 分〕
1)(P (Q S)) ∧( R∨P) ∧Q R S
证明： (1)R
R