證明題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) p11)假言推理
(13) p∧q12) 合取
（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上的對稱關係
離散數學歷年考試證明題
6 設連通圖g有k個奇數度的結點，證明在圖g中至少要新增條邊才能使其成為尤拉圖 證明 由定理3.1.2，任何圖中度數為奇數的結點必是偶數，可知k是偶數 又根據定理4.1.1的推論，圖g是尤拉圖的充分必要條件是圖g不含奇數度結點 因此只要在每對奇數度結點之間各加一條邊，使圖g的所有結點的度數變為偶數，...
離散證明題集錦
一 命題邏輯 例 給出 p q p q 的真值表 解 一般說來，n個命題變元組成的命題公式共有2n種真值指派。定理1 任何兩個重言式的合取或析取，仍然是重言式。證明 設a b為兩個重言式，則a b和a b的真值分別等於t t和t t。定理2 對乙個重言式的同一分量都用任何乙個命題公式置換，所得命題公...
離散數學模擬題及答案
離散數學試題 a捲及答案 一 證明題 10分 1 p q r q r p r r 證明 左端 p q r q p r p q r q p r p q r q p r p q q p r p q p q rt r 置換 r 2 x a x b x xa x xb x 證明 x a x b x x a ...