《离散数学》期末复习题答案 - 53551553740738151

v1 1 v0 4 7 5 1 v33 v4 2 v2 2 v5 6 解：如下图所示v0与v5之间的最短路径为：v0, v1, v2, v4 , v3, v5 最短路径值为1+2+1+3+2=9

20、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。

先根遍历：ABDEHCFIJGK 中根遍历：DBHEAIFJCGK 后根遍历：DHEBIJFKGCA

四、证明题（每题10分，共20分）

1、若R和S都是非空集A上的等价关系，证明R?S是A上的等价关系。

证明：?a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故x R?S x。从而R?S是自反的。

?a,b∈A，aR?Sb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。

故b R?S a。从而R?S是对称的。

?a,b,c∈A，a R?S b且b R?S c，即aRb，aSb，bRc且bSc。因为R和S都是A上的等

价关系，所以aRc且aSc。故a R?S c。从而R?S是传递的。 故R?S是A上的等价关系。

2、证明苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。 设： H(x)：x是人。M(x)：x是要死的。s：苏格拉底。本题要证明：(?x)(H(x)→M(x))∧H(s)?M(s) 证明：

⑴ (?x)(H(x)→M(x)) P ⑵ H(s)→M(s) US⑴

⑶ H(s) P ⑷ M(s) ⑵、⑶ 3、P→Q，┐Q?R，┐R，┐S?P?┐S 证明：

(1) ┐R 前提 (2) ┐Q?R 前提

(3) ┐Q （1），（2） (4) P→Q 前提

(5) ┐P （3），（4） (6) ┐S?P 前提

(7) ┐S （5），（6）

4、在群中，除单位元 e 外，不可能有别的幂等元。 因为e?e=e，所以e是幂等元。设a?G且a?a=a，则有a=e?a=(a –1 ?a)?a=a –1?(a?a)=a–1 ?a=e， 即a=e。

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 //蕴涵等值式 ?∧(┐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 已知前提 (2) ┐P→Q 由(1) (3) Q→S 已知前提 (4) ┐P→S 由(2) 和(3) (5) ┐S→P 由(4) (6) P→R 已知前提 (7) ┐S→R 由(5) 和(6) (8) S∨R 由(7)

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

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

(1) ┐(┐P) 反证法附加前提

(2) P 由(1) (3) P→┐Q 已知前提 (4) ┐Q 由(2)和(3) (5) Q∨┐R 已知前提 (6) ┐R 由(4)和(5) (7) R∧┐S 已知前提 (8) R 由 (7) (9) R∧┐R 由(6)和(8)，矛盾

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) 由(1) (3) ┐P(c) 由(2) ES (4) (?x)(P(x)∨Q(x)) 前提引入 (5) P(c)∨Q(c) 由(4) US (6) Q(c) 由(3)和(5) (7) (?x)Q(x) 由(6) EG

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