离散数学证明题

发布时间：2020-03-03 21:52:56 来源：范文大全收藏本文下载本文手机版

证明题

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

⑤ Q

6.证明: 前提引入前提引入 ①②拒取式前提引入 ③④拒取式

①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传递。

8．设A是集合，R1,R2是A上的二元关系，证明：

若R1,R2是自反的和对称的，则R1R2也是自反的和对称的。

证明:

(1)∵ R1,R2是A上的自反关系

∴ IAR1IAR2

∴IAR1R2

∴ R1R2是A上的自反关系

又∵ R1,R2是A上的对称关系

∴ R1R11R2R21

(R1R2)111R1R2R1R2∴ R1R2 是A上的对称关系

将本文的Word文档下载到电脑，方便编辑。

推荐度：

点击下载文档

相关专题离散数学证明题答案证明

相关范文推荐