离散数学证明题.docx

离散数学证明题

第一篇：离散数学证明题证明题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）前提：(PQ)(RS)，(QP)R，R前提：PQ。（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前提引入②(QP)R前提引入③QP①②析取三段论④RS①附加规则⑤(PQ)(RS)前提引入⑥PQ④⑤拒取式⑦(PQ)(QP)③⑥合取规则⑧PQ⑦置换规则（2）①M∧R前提引入②M①化简规则③SM前提引入④(S→M)∧(M→S)③置换⑤M→S④化简规则⑥S②⑥假言推理⑦QS前提引入⑧(S→Q)∧(Q→S)⑦置换⑨S→Q⑧化简规则⑩Q⑥⑨假言推理(11)Q→P前提引入(12)P(13)P∧Q（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⑤┐R⑥R∧┐S⑦R⑧R∧┐R（6）⑩(11)假言推理⑩(12)合取前提引入附加前提引入①②假言推理前提引入③④假言推理前提引入⑤⑥假言推理附加前提引入①附加规则前提引入②③假言推理④化简规则⑤附加规则前提引入⑥⑦假言推理结论否定引入前提引入①②假言推理前提引入③④析取三段论前提引入⑥化简规则⑤⑦合取①┐(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）明天是晴天，或是雨天；若明天是晴天，我就去看电影；若我看电影，我就不看书。所以，如果我看书，则明天是雨天。（3）如果小王是理科学生，他必学好数学；如果小王不是文科生，他必是理科生；小王没学好数学。所以，小王是文科生。解：（1）首先将命题符号化：设P:今天是星期六；Q:我们到颐和园去玩；R:我们到圆明园去玩；S:颐和园游人多。前提：P→(Q∨R),S→┐Q,P,S结论：R证明：①②假言推理④P前提引入⑤P→(Q∨R)前提引入⑥Q∨R④⑤假言推理⑦R③⑥析取三段论（2）首先将命题符号化：令P：明天是晴天，Q：明天是雨天，R：我看电影，S：我看书。①S→┐Q前提引入②S前提引入③┐Q前提：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⑤Q6.证明:前提引入前提引入①②拒取式前提引入③④拒取式①A-B=AA∩B=Φ。②(A-B)-C=(A-C)-(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)-C=(A-C)-(B-C)7．设R是A上的二元关系，试证：R是传递的当且仅当R2R，其中R2表示RR。（1）设R传递，（x，y）∈R2，t∈A使，∈R（因为R2＝RR）∵R传递∴∈R∴R2R（2）设R2R，若，∈R则∈R2，∵R2R，∴∈R。即R传递