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

1是A的最小元，没有最大元，1是极小元，4、5、6都是A的极大元。

18、设集合A={a,b,c}，A上的关系R={, , }，求R的自反、对称、传递闭包。 r(R)={,,,,} s(R)={,,,,} t(R)={,,,}

19、求下图中顶点v0与v5之间的最短路径。 v1 1 4 7 5 1 v33 v4 2 v5 6 v0 2 v2 解：如下图所示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))

⑵ H(s)→M(s) ⑶ H(s) ⑷ M(s)

P US⑴ P ⑵、⑶

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。

5、设R和S是二元关系，证明：(R?S)-1=R-1?S-1 证明：

.

所以

.

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