2022离散数学证明题_离散数学证明题答案_1.docx
2022离散数学证明题_离散数学证明题答案 离散数学证明题由我整理，希望给你工作、学习、生活带来便利，猜你可能喜爱“离散数学证明题答案”。 证明题 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）前提：Ø(P®Q)®Ø(RÚS)，(Q®P)ÚØR，R 前提：PQ。 （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前提引入 (Q®P)ÚØR前提引入 Q®P析取三段论 RÚS附加规则 Ø(P®Q)®Ø(RÚS)前提引入 P®Q拒取式 (P®Q)Ù(Q®P)合取规则 PQ置换规则 （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 (13) PQ （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） (11)假言推理 (12) 合取前提引入附加前提引入 假言推理 前提引入 假言推理前提引入假言推理附加前提引入附加规则前提引入 假言推理化简规则附加规则前提引入 假言推理结论否定引入前提引入 假言推理前提引入析取三段论前提引入化简规则合取 (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证明： 假言推理 P前提引入 P (Q R )前提引入 Q R假言推理 R析取三段论 （2）首先将命题符号化：令P：明天是晴天， Q：明天是雨天， R：我看电影， S：我看书。 S Q前提引入S前提引入 Q 前提：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是传递的当且仅当R2ÍR，其中R2表示R°R。 （1）设R传递，"（x，y）R2，$tA使 ，R（因为R2R °R） R传递 R R2 ÍR （2）设R2ÍR，若，R 则R2， R2 ÍR，R。 即R传递。 8设A是集合，R1,R2是A上的二元关系，证明： 若R1,R2是自反的和对称的，则R1UR2也是自反的和对称的。 证明: (1) R1,R2是A上的自反关系 IAÍR1ÙIAÍR2 IAÍR1UR2 R1UR2是A上的自反关系 又 R1,R2是A上的对称关系 R1=R1-1ÙR2=R2-1 (R1UR2)-1-1-1=R1UR2=R1UR2 R1UR2 是A上的对称关系 离散数学证明题 离散数学证明题离散数学证明题:链为安排格证明设a,b均是链A的元素，因为链中随意两个元素均可比较，即有ab或ab，假如ab，则a,b的最大下界是a,最小上界是b，假如ba，则a,b的最大. 电大离散数学证明题参考题 五、证明题1设G是一个n阶无向简洁图，n是大于等于3的奇数证明图G与它的补图G中的奇数度顶点个数相等 证明：设G=<V,E>，=<V,E¢>则E¢是由n阶无向完全图Kn的边删去E所得到的所以对于随意结点. 离散数学历年考试证明题 1、试证明集合等式AÇ (BÈC)=(AÇB) È (AÇC)证明：设S=A(BC)，T=(AB)(AC)，若xS，则xA且xBC，即 xA且xB 或 xA且xC，也即xAB 或 xAC ，即 xT，所以SÍT反之，若x. 离散数学证明题解题方法 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学以探讨离散量的结构和相互间的关系为主要目标，其探讨对象一般地是有限个或可数个元素，因此他充. 离散数学 离散数学试题（A卷答案）一、（10分）（1）证明(P®Q)(Q®R)Þ(P®R) （2）求(PQ)®R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。 解：（1）因为(P®Q)(Q®R)®(P®R) ÛØ(ØPQ)(ØQR)(ØP. 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第12页 共12页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页第 12 页 共 12 页
