离散证明题集锦.docx

离散证明题集锦 一．命题逻辑 例：给出┐ (P∧Q)? (┐P∨┐ Q)的真值表 P Q ┐ (P∧ Q) ? (┐P∨┐ Q) 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 0 步骤 ② ① ③ ① ② ① 一般说来， n 个命题变元组成的命题公式共有 2n 种真值指派。 定理 1：任何两个重言式的合取或析取，仍然是重言式。 证明：设 A、B为两个重言式，则 A∧B和 A∨B的真值分别等于 T ∧T和 T∨T。 定理 2：对一个重言式的同一分量都用任何一个命题公式置换， 所得命题公式仍为一个重言式。 (即代入规则) 证明：由于重言式的真值与分量的真值指派无关，故对同一分量 以任何一个命题公式置换后，重言式的真值不变 定理 3：设 A、B是两个命题公式， A B当且仅当 A? B 是一 个重言式。(前面已证) 证明：若 A B，则对于 A、B所包含的分量的任意指派， A、B 均 取相同的真值， 即 A? B是一个重言式； 若A? B是一个重言式， 即 对于分量的任意指派， A、B 均取相同的真值，即 A B 定理 1：设 A1 是命题公式 A 的子公式，若 A1 B1，则若将 A 中的 A1用B1来替换，得到公式 B ，则 B与A等价，即A B.(替 换规则 )。 证明： 因为对变元的任一组指派， A1与 B1真值相同，故以 B1 取代 A1后，公式B与公式 A相对于变元的任一指派的真值也必相同， 所以 A B。 证明下列命题公式 (可以利用基本等价式 ) Q→(P∨(P∧Q)) Q→P (P∧ Q)∨ (P∧┐ Q) P (P→Q)→ (Q∨R) P∨Q∨R P∧┐ Q∨Q P∨Q 解： 1.原式 Q→ (P∨ P) ∧ (P∨ Q) Q→P∧(P∨Q) Q→P 原式 ((P∧ Q)∨ P) ∧((P∧Q) ∨┐Q) (P∨ P) ∧ (P∨Q) ∧(P ∨┐Q) ∧(Q∨┐ Q) P∧(P∨Q) ∧(P∨┐ Q) P∧P P 原式 ┐(┐ P∨Q)∨(Q∨R) (P∧┐ Q) ∨(Q∨R) (P∨Q∨R) ∧ (Q∨┐ Q∨R) P∨ Q∨ R(零率) 原式 ( P∧┐ Q)∨Q (P∨Q)∧(┐Q∨Q) P∨Q(运算次序 优先级：┐，∧，∨，→， ? ) 例: 求证: (P →Q) ∨ ┐ (P →Q) 为永真式。 解：原式 (┐P∨Q)∨( P∧┐Q) (┐P∨Q∨P) ∧(┐ P∨Q∨ ┐Q) T 例： 求证┐ Q∧(P→Q) ┐P 证法 1：前件真推导后件真 证法 2：后件假推导前件假 证法 3：定义 定理：设 P、Q为任意两个命题公式， P Q 的充分必要条件是 P Q 且 Q P。 证明：若 P Q，则 P? Q 为重言式，即 P→Q 和 Q→P 是重言式；若 有P Q且 Q P，则 P→Q和Q→P是重言式，即 P? Q为重言式 例 已知 A是 B的充分条件, B是C的必要条件，C是D的必要条件 , D 是 B 的必要条件 , 问： A是 D的什么条件 B是 D的什么条件 解 已知 A B, C B, D C, B D, 故有 (1) A B, B D, 所以 A D, 即 A是 D的充分条件 (2) D C, C B, 所以 D B, 又因为 B D, 所以 B D, 即 B是 D的 充要条件。 定理：如果 A B，则 A* B*。 证明：设 P1,P2,?,Pn 是出现在命题公式 A、B中的原子变元，因为 A B，即： A(P1,P2,?,Pn)? B(P1,P2?, ,Pn)是一个重言式。故有： A(┐P1,┐P2,?,┐Pn)? B(┐P1,┐P2,?,┐Pn)是一个重言式。即 A(┐ P1,┐P2,?,┐ Pn) B(┐P1,┐P2,?,┐Pn) ┐A* ┐B* ，即 A* B* 例 判断下面各推理是否正确 . 如果天气凉快 ,小王就不去游泳 .天气凉快 ,所以小王没去游泳 . 如果我上街 ,我一定去新华书店 .我没上街 .所以我没去新华书店 . 解: 解上述类型的推理问题 ,应先将命题符号化 ,然后写出前提、结论 和推理的形式结构 ,最后进行判断 . P：天气凉快 ; Q：小王去游泳 . 前提： P→ Q, P. 结论： Q. 推理的形式结构为 ((P→ Q)∧ P)→ Q. (*) 判断 (*)是否为重言式 . 真值表法 真值表的最后一列全为 1,因而(*)是重言式.所以推理正确 . ②等价演算法 (P→ Q)∧ P)→ Q 1. ③主析取范式法 ((P→ Q)∧ P)→ Q m0∨m1∨m2∨m3 由② ,③同样能判断推理正确 . P：我上街 ; Q：我去新华书店 . 前提： P→Q, P. 结论： Q. 推理的形式结