离散数学证明题

证明题 1.用等值演算法证明下列等值式： （1）┐(PQ)(P∨Q)∧┐(P∧Q) （2）(P∧┐Q)∨(┐P∧Q)(P∨Q)∧┐(P∧Q) 证明：（1） ┐(PQ) ┐((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）前提： ， ，R 前提： 。 （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                  前提引入 ②       前提引入 ③             ①②析取三段论 ④                 ①附加规则 ⑤   前提引入 ⑥               ④⑤拒取式 ⑦     ③⑥合取规则 ⑧                 ⑦置换规则 （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                        ⑩ (11)假言推理 (13) P∧Q                    ⑩ (12) 合取 （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） ① ┐(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 证明： ① S → ┐Q          前提引入 ②  S                  前提引入 ③ ┐Q                ① ②假言推理 ④ P                  前提引入 ⑤ P →(Q ∨ R )      前提引入 ⑥ Q ∨ R              ④⑤假言推理 ⑦ R                  ③⑥析取三段论          （2）首先将命题符号化：令P：明天是晴天， Q：明天是雨天， R：我看电影， S：我看书。 前提：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-BA。任取x∈A，则如果x属于B，则x属于A∩B，与A∩B=Φ矛盾。因此x必不属于B，即x属于A-B。从而证明了AA-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是传递的当且仅当 R，其中 表示RR。 （1）设R传递，（x，y）∈ ，t∈A使 ，∈R（因为 ＝R R） ∵R传递 ∴∈R ∴ R （2）设 R，若，∈R 则∈ ， ∵ R，∴∈R。 即R传递。 8．设A是集合， 是A上的二元关系，证明： 若 是自反的和对称的，则 也是自反的和对称的。 证明: (1)∵ 是A上的自反关系 ∴ ∴ ∴ 是A上的自反关系 又∵ 是A上的对称关系 ∴ ∴ 是A上的对称关系