中国石油大学大学《离散数学》期末复习题及答案

所以

.

6、证明：((Q∧S)→R)∧(S→(P∨R)) = (S∧(P→Q))→R. 证明：

左边：((Q∧S)→R)∧(S→(P∨R)) =(┐(Q∧S)∨R)∧(┐S∨(P∨R)) =(┐Q∨┐S∨R)∧(┐S∨P∨R) =(┐Q∨┐S∨R)∧(┐S∨P∨R) 右边：(S∧(P→Q))→R = ┐(S∧(┐P∨Q))∨R = (┐S∨(P∧┐Q))∨R = (┐Q∨┐S∨R)∧(┐S∨P∨R)

所以 ((Q∧S) → R)∧(S→ (P∨R)) = (S∧(P→Q))→R.

7、设I是整数集合，k是正整数，I上的关系R＝{|x, y ∈ I，且x－y可被k整除}，证明R是等价关系。

证明：(1) 对任意的x ∈ A，有x－x=0可被k整除。所以 ∈ R，即R具有自反性。 (2) 对任意的x，y ∈ A， ∈ R，即x－y可被k整除，设x－y=km，则y－x=－km，显然y－x可被k整除。所以 ∈ R，即R具有对称性。

(3)设x，y，z ∈ A，若 ∈ R， ∈ R，即x－y可被k整除，y－z可被k整除，设x－y=km，y－z=kn，则x－z=k(m+n)，即x－z可被k整除。所以 ∈ R，即R具有传递性。

综上所述， R具有自反性、对称性和传递性，故R是等价关系。 8、证明：

⑴((p→q)→r)? ((┐q∧p)∨r) ⑵p→(q→r)? ┐r→(q→┐p) 证明：

⑴ ((p→q)→r) ?

((┐p∨q)→r)

//蕴涵等值式

???

(┐(┐p∨q))∨r (p∧(┐q))∨r ((┐q∧p)∨r)

//蕴涵等值式 //德·摩根律 //交换律

⑵p→(q→r)? ┐r→(q→┐p) ?┐p∨(q→r)

//蕴涵等值式 //蕴涵等值式 //结合律与交换律 //蕴涵等值式 //蕴涵等值式

?┐p∨(┐q∨r) ?r∨(┐q∨┐p) ?r∨(q→┐p)

?┐r→(q→┐p)

9、证明(P∨Q) ∧(P→R) ∧(Q→S)?S∨R 证明：

(1) P∨Q

已知前提 由(1) 已知前提 由(2) 和(3) 由(4) 已知前提 由(5) 和(6) 由(7)

(2) ┐P→Q (3) Q→S

(4) ┐P→S (5) ┐S→P (6) P→R

(7) ┐S→R (8) S∨R

10、证明P→ ┐Q，Q∨┐R，R∧┐S? ┐P

证明用反证法，把┐(┐P)作为附加前提加入到前提的集合中去，证明由此导致矛盾。

(1) ┐(┐P)

(2) P

反证法附加前提 由(1) 已知前提

由(2)和(3)

(3) P→┐Q (4) ┐Q

(5) Q∨┐R (6) ┐R

已知前提 由(4)和(5) 已知前提 由 (7)

由(6)和(8)，矛盾

(7) R∧┐S (8) R

(9) R∧┐R

11、证 (?x)(P(x)∨Q(x)) ?┐(?x)P(x) →(?x)Q(x) CP规则：要证S?R→C ，也就是证明(S∧R) ?C

(1) ┐(?x)P(x) (2) (?x)┐P(x) (3) ┐P(c)

前提引入 由(1) 由(2) ES 前提引入 由(4) US 由(3)和(5) 由(6) EG

(4) (?x)(P(x)∨Q(x)) (5) P(c)∨Q(c) (6) Q(c)

(7) (?x)Q(x)

12、证明定理：设是群，对于任意a, b∈G，则方程a?x=b与y?a=b ，在群内有唯一解。

证明：因为a? (a-1?b) =(a? a-1)?b =1?b= b 所以x=a-1 ? b是方程 a?x=b 的解。 其次证明唯一性，如果有另一解c，则必有 a? c = b= a? (a-1?b)，由消去律可知c =a-1 ? b 。 同理可证 y?a=b 有唯一解 y= b? a-1