离散数学证明题(共5页).doc

精选优质文档-倾情为你奉上证明题1.用等值演算法证明下列等值式：（1）(P«Q)Û(PQ)(PQ)（2）(PQ)(PQ)Û(PQ)(PQ)证明：（1）(P«Q)Û(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 , 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) 前提引入 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）如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不到颐和园去玩。今天是星期六。颐和园游人太多。所以我们到圆明园玩。（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：明天是雨天，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-BÍA。任取xA，则如果x属于B，则x属于AB，与AB=矛盾。因此x必不属于B，即x属于A-B。从而证明了AÍA-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，其中表示R°R。（1）设R传递，"（x，y），$tA使 <x，t>，<t，y>R（因为R °R） R传递 <x，y>R ÍR （2）设ÍR，若<x，t>，<t，y>R 则<x，y>， ÍR，<x，y>R。 即R传递。8设A是集合，是A上的二元关系，证明：若是自反的和对称的，则也是自反的和对称的。证明: (1) 是A上的自反关系 是A上的自反关系又 是A上的对称关系 是A上的对称关系专心-专注-专业