第1-1讲 命题逻辑.ppt

第1-1章 命题逻辑 1-1-1 命题、逻辑联结词与真值表 1-1-2 命题公式与真值函数 1-1-1 命题、逻辑联结词与真值表 一、命题的基本概念 能判断真假而不是可真可假的陈述句。 真值：命题表达的判断结果。真值只取两个值：真或假。 真值为真的命题称为真命题，真值为假的命题称为假命题。 真命题表达的判断正确，假命题表达的判断错误。 任何命题的真值都是唯一的。  (16) 天气多好啊！ (17) 他来了吗？ (21) 我正在说假话。 例1 证明 R→S是P→(Q→S)， ￢R∨P，Q的有效结论。 证明： ⑷ P→(Q→S) ⑶ P ⑸ Q→S ⑹ Q ⑺ S ⑴ ￢R∨P P T⑴⑵I P T⑶⑷I 分离规则 P T⑸⑹I ⑻ R→S CP⑵⑺ ⑵ R P（附加前提） 分离规则 附加前提证明法 例1 证明 R→S是P→(Q→S)， ￢R∨P，Q的有效 结论。 令 S={P→(Q→S)， ￢R∨P，Q} 证明S演绎出R→S R →P P→(Q→S) R →P ? R→(Q→S) ￢R∨￢Q∨S (￢R∨S) ∨￢Q Q ? ￢R∨S R→S 中间结论 S演绎出R→S 的过程 演绎法与证明 (P→(Q→S)) ∧(￢R∨P) ∧Q ? R→S 是等价的。 基本蕴涵式 等价式 定理4.2 设S为公式集，B是一个公式，S能演绎 出B的充要条件是：B是S的逻辑结果。 定理4.3 设S为前提公式集合，B和C是两个公式， 若S∪{B}能演绎C，则S演绎出B →C。 设S={A1，A2，…， An }，则 S∪{B}= ={A1，A2，… ，An ，B}， 说明如果证明的结论是一个条件式，则可以将 前件作为前提之一，后件作为结论。 前件B称为附加前提，附加前提引入 反证法（归谬法） 定义4.3 设A1，A2，… An是n个命题公式，若A1∧A2∧… ∧An 是矛盾式，则称A1，A2，… ，An是不相容的。否则，称其为相容的。 取结论的否定作为前提引入到证明中，希望推出 矛盾的结论。 定理4.4 A1∧A2∧… ∧An?B当且仅当 A1，A2，… ，An ，￢B是不相容的。 A1∧A2∧… ∧An→B ? T A1∧A2∧… ∧An∧ ￢ B ? F 反证法（归谬法）的理论依据 ? ￢ (A1∧A2∧… ∧An)∨B ￢ (A1∧A2∧… ∧An∧ ￢ B) ? ? T ? T 例3 证明 S={A→B， ￢(B∨C)}演绎出￢A 采用反证法（归谬法） 证明： ⑴ A→B P ⑵ A P(否定结论引入) ⑶ B T⑴⑵I ⑷￢(B∨C) P ⑸￢B∧￢C T⑷E ⑹￢B T⑸I ⑺ B∧￢B ? F T⑶⑹E ⑻￢A 定理4.4 例2 证明 (P∨Q) ∧(P→R) ∧ (Q→S) ?S∨R ⑴ P∨Q 证明： ⑵ ￢P→Q P T⑴E ⑶ Q→S P ⑷ ￢P→S T⑵⑶I 假言三段论 ⑸ ￢S→P T⑷E ⑹ P→R P ⑺ ￢S→R T⑸⑹I 假言三段论 ⑻ S∨R T⑺E 使用反证法 ⑴ ￢ (S∨R) P ⑵ ￢ S∧ ￢ R T⑴E ⑸ P→ R P ⑶ ￢ S ⑷ ￢ R ⑺ Q→S P ⑹ ￢P T⑷ ⑸I ⑻ ￢Q T⑵I T⑵I T⑶⑺I ⑼ ￢P ∧￢Q ⑽ ￢(P ∨Q) ⑾ P ∨Q ⑿ ￢(P ∨Q) ∧ P ∨Q ? F 例2 反证法证明 (P∨Q) ∧(P→R) ∧ (Q→S) ?S∨R 论证的方法可以分为：真值表法，直接法，间接法 直接法：由一组前提经P规则，T规则演绎出有效结论 间接法: (1)附加前提证明法 (2)反证法（归谬法） 定义4.3 设P1,P2,…,Pn是A1，A2，… Am中出现的原子命题变元，若A1∧A2∧… ∧Am 是矛盾式，则称A1，A2，… ，Am是不相容的。否则，称其为相容的。 ⑴ P→R P ⑵ P∨Q→R∨Q T⑴I ⑶ Q→S P ⑷ R∨Q→R∨S T⑶I ⑸ P∨Q→R∨S T⑵⑷I ⑹ P∨Q P ⑻ R∨S T⑸⑹I 例2 证明 (P∨Q) ∧(P→R) ∧ (Q→S) ?S∨R 证明: 例5 “如果天下雨，春游就改期，如果没有球赛， 春游就不改期。结果没有球赛，所以没有下雨。” 证明这是有效的论断。 证明： 令 A:天下雨； B：春游改期； C：没有球赛 符号化前提和结论， 前提： A→B， C→￢B，C 结论： ￢A 例6 “如果学生学习努力，他们的父亲或母亲就 高兴。若母亲高兴，学