离散数学证明题

1、证明题1.用等值演算法证明下列等值式：（1）(PQ)(PQ)(PQ)（2）(PQ)(PQ)(PQ)(PQ)证明：（1）(PQ)(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ)(PP)(QQ)(PQ)(PQ)(PQ) （2）(PQ)(PQ)(PP)(PQ)(QP)(QQ)(PQ)(PQ)2构造下列推理的证明：（1）前提：，R 前提：。（2）前提：Q P, Q S , S M , MR前提：结论：PQ（3）前提：P (Q R) , S P , Q结论：S R（4）前提：(PQ) ( RS), (SM) U结论：P U（5）前提：P Q ,RQ , RS结论：P（6）前提：PQ ， P R

2、, Q S结论：RS证明：（1） R 前提引入 前提引入 析取三段论 附加规则 前提引入 拒取式 合取规则 置换规则（2） MR 前提引入 M 化简规则 S M 前提引入 (S M) (M S) 置换 M S 化简规则 S 假言推理 Q S 前提引入 (S Q) (Q S) 置换 S Q 化简规则 Q 假言推理(11) Q P 前提引入(12) P (11)假言推理(13) PQ (12) 合取（3） S P 前提引入 S 附加前提引入 P 假言推理 P (Q R) 前提引入 Q R 假言推理 Q 前提引入 R 假言推理 （4） P 附加前提引入 PQ 附加规则 (PQ) ( RS) 前提引入

3、 RS 假言推理 S 化简规则 SM 附加规则 (SM) U 前提引入 U 假言推理（5） P 结论否定引入 P Q 前提引入 Q 假言推理 RQ 前提引入 R 析取三段论 RS 前提引入 R 化简规则 RR 合取（6） (RS) 结论否定引入 RS 置换规则 R 化简规则 P R 前提引入 P 拒取 S 化简规则 Q S 前提引入 Q 拒取 PQ 合取 (PQ ) 置换规则(11) PQ 前提引入(12) (PQ )(PQ ) 11 合取3在命题逻辑中构造下列推理的证明：（1）如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不到颐和园去玩。今天是星期六。颐和园游人太

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

5、雨天，R：我看电影，S：我看书。前提：PQ, PR, RS结论： SQ证明： S 附加前提引入 RS 前提引入R 拒取式 PR 前提引入 P 拒取式 PQ前提引入 Q 析取三段论（3）首先将命题符号化：令P：小王是理科生，Q：小王是文科生，R：小王学好数学。前提:PR, QP, R结论：Q证明： PR前提引入 R前提引入 P 拒取式 QP 前提引入 Q 拒取式6.证明:A-B=A AB= 。(A-B)-C = (A-C)-(B-C)证明： 必要性。假设AB，必有x属于AB，则x属于A同时属于B，即x属于A但是x不属于A-B。与A-B=A矛盾。充分性。显然A-BA。任取xA，则如果x属于B，则x属于AB，与AB=矛盾。因此x必不属于B，即x属于A-B。从而证明了AA-B。命题得证。(A-B)-C = (AB)C= ABC;(A-C)-(B-C) = (AC)(BC)= (AC)(BC)= (ACB)(ACC)= (ACB)= ABC.(A-B)-C = (A-C)-(B-C)7设R是A上的二元关系，试证：R是传递的当且仅当R，其中表示RR。（1）设R传递，（x，y），$tA使 ，R（因为R R） R传递 R R （2）设R，若，R 则， R，R