发布时间 : 星期三 文章中国石油大学大学《离散数学》期末复习题和答案更新完毕开始阅读d2c35471970590c69ec3d5bbfd0a79563d1ed4ea
四、证明题（每题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是幂等元。设a?G且a?a=a.则有a=e?a=(a ?a)?a=a ?(a?a)=a ?a=e. 即a=e。
-1-1
5、设R和S是二元关系.证明：(R?S)-1=R?S
–1
–1–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＝{
证明：(1) 对任意的x ∈ A.有x－x=0可被k整除。所以
(3)设x.y.z ∈ A.若
⑴((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
已知前提 由(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) R∧┐S (8) R
已知前提 由 (7)
由(6)和(8).矛盾
(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? (a?b) =(a? a)?b =1?b= b 所以x=a ? b是方程 a?x=b 的解。
其次证明唯一性.如果有另一解c.则必有
-1
-1
-1
a? c = b= a? (a-1?b).由消去律可知c =a-1 ? b 。
同理可证 y?a=b 有唯一解 y= b? a
欢迎您的光临，Word文档下载后可修改编辑双击可删除页眉页脚谢谢！希望您提出您宝贵的意见，你的意见是我进步的动力。赠语；、如果我们做与不做都会有人笑，如果做不好与做得好还会有人笑，那么我们索性就做得更好，来给人笑吧！、现在你不玩命的学，以后命玩你。、我不知道年少轻狂，我只知道胜者为王。、不要做金钱、权利的奴隶；应学会做“金钱、权利”的主人。、什么时候离光明最近？那就是你觉得黑暗太黑的时候。、最值得欣赏的风景，是自己奋斗的足迹。 7、压力不是有人比你努力，而是那些比你牛×几倍的人依然比你努力。-1
. .