离散数学证明题.doc

《离散数学证明题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、证明题1.用等值演算法证明下列等值式：（1）┐(P«Q)Û(P∨Q)∧┐(P∧Q)（2）(P∧┐Q)∨(┐P∧Q)Û(P∨Q)∧┐(P∧Q)证明：（1）┐(P«Q)Û┐((P→Q)∧(Q→P))Û┐((┐P∨Q)∧(┐Q∨P))Û(P∧┐Q)∨(Q∧┐P)Û(P∨Q)∧(P∨┐P)∧(┐Q∨Q)∧(┐P∨┐Q)Û(P∨Q)∧┐(P∧Q)（2）(P∧┐Q)∨(┐P∧Q)Û(P∨┐P)∧(P∨Q)∧(┐Q∨┐P)∧(┐Q∨Q)Û(P∨Q)∧┐(P∧Q)2．构造下列推理的证明：（1）前提：，，R前提：。（2）

2、前提：Q→P,Q«S,S«M,M∧R前提：结论：P∧Q（3）前提：P→(Q→R),S→P,Q结论：S→R（4）前提：(P∨Q)→(R∧S),(S∨M)→U结论：P→U（5）前提：P→┐Q,┐R∨Q,R∧┐S结论：┐P（6）前提：P∨Q，P→R,Q→S结论：R∨S证明：（1）①R前提引入②前提引入③①②析取三段论④①附加规则⑤前提引入⑥④⑤拒取式⑦③⑥合取规则⑧⑦置换规则（2）①M∧R前提引入②M①化简规则③S«M前提引入④(S→M)∧(M→S)③置换⑤M→S④化简规则⑥S②⑥假言推理⑦Q«S前提引入⑧(

3、S→Q)∧(Q→S)⑦置换⑨S→Q⑧化简规则⑩Q⑥⑨假言推理(11)Q→P前提引入(12)P⑩(11)假言推理(13)P∧Q⑩(12)合取（3）①S→P前提引入②S附加前提引入③P①②假言推理④P→(Q→R)前提引入⑤Q→R③④假言推理⑥Q前提引入⑦R⑤⑥假言推理（4）①P附加前提引入②P∨Q①附加规则③(P∨Q)→(R∧S)前提引入④R∧S②③假言推理⑤S④化简规则⑥S∨M⑤附加规则⑦(S∨M)→U前提引入⑧U⑥⑦假言推理（5）①P结论否定引入②P→┐Q前提引入③┐Q①②假言推理④┐R∨Q前提引入⑤┐

4、R③④析取三段论⑥R∧┐S前提引入⑦R⑥化简规则⑧R∧┐R⑤⑦合取（6）①┐(R∨S)结论否定引入②┐R∧┐S①置换规则③┐R②化简规则④P→R前提引入⑤┐P③④拒取⑥┐S②化简规则⑦Q→S前提引入⑧┐Q⑥⑦拒取⑨┐P∧┐Q⑤⑧合取⑩┐(P∨Q)⑨置换规则(11)P∨Q前提引入(12)┐(P∨Q)∧(P∨Q)⑨11合取3．在命题逻辑中构造下列推理的证明：（1）如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不到颐和园去玩。今天是星期六。颐和园游人太多。所以我们到圆明园玩。（2）

5、明天是晴天，或是雨天；若明天是晴天，我就去看电影；若我看电影，我就不看书。所以，如果我看书，则明天是雨天。（3）如果小王是理科学生，他必学好数学；如果小王不是文科生，他必是理科生；小王没学好数学。所以，小王是文科生。解：（1）首先将命题符号化：设P:今天是星期六；Q:我们到颐和园去玩；R:我们到圆明园去玩；S:颐和园游人多。前提：P→(Q∨R),S→┐Q,P,S结论：R证明：①S→┐Q前提引入②S前提引入③┐Q①②假言推理④P前提引入⑤P→(Q∨R)前提引入⑥Q∨R④⑤假言推理⑦R③⑥析取三段论（2）首

6、先将命题符号化：令P：明天是晴天，Q：明天是雨天，R：我看电影，S：我看书。前提：P∨Q,P→R,R→┐S结论：S→Q证明：①S附加前提引入②R→┐S前提引入③┐R①②拒取式④P→R前提引入⑤┐P③④拒取式⑥P∨Q前提引入⑦Q⑤⑥析取三段论（3）首先将命题符号化：令P：小王是理科生，Q：小王是文科生，R：小王学好数学。前提:P→R,┐Q→P,┐R结论：Q证明：①P→R前提引入②┐R前提引入③┐P①②拒取式④┐Q→P前提引入⑤Q③④拒取式6.证明:①A-B=AÛA∩B=Φ。②(A-B)-C=(A-C)-(

7、B-C)证明：①必要性。假设A∩B≠Φ，必有x属于A∩B，则x属于A同时属于B，即x属于A但是x不属于A-B。与A-B=A矛盾。充分性。显然A-BÍA。任取x∈A，则如果x属于B，则x属于A∩B，与A∩B=Φ矛盾。因此x必不属于B，即x属于A-B。从而证明了AÍA-B。命题得证。②∵(A-B)-C=(A∩～B)∩～C=A∩～B∩～C;(A-C)-(B-C)=(A∩～C)∩～(B∩～C)=(A∩～C)∩(～B∪C)=(A∩～C∩～B)∪(A∩～C∩C)=(A∩～C∩～B)∪Φ=A∩～B∩～C.∴(A-B)

8、-C=(A-C)-(B-C)7．设R是A上的二元关系，试证：R是传递的当且仅当ÍR，其中表示R°R。（1）设R传递，"（x，y）∈，$t∈A使，∈R（因为＝R°R）∵R传递∴∈R∴ÍR（2）设ÍR，若，∈R则∈，∵ÍR，∴∈R。即R传递。8．设A是集合，是A上的二元关系，证明：若是自反的和对称的，则也是自反的和对称的。证明:(1)∵是A上的自反关系∴∴∴是A上的自反关系又