命题逻辑的推理结构.pdfVIP

计算机科学MOOC课程群 离散数学基础   • 推理的形式结构  − 例：  » 前提1: 如果今天是周五，那么我们有数理逻辑课。  » 前提2: 今天是周五。  » 结论: 今天我们有数理逻辑课。  » 形式化：P ：今天是周五。Q ：今天我们有数理逻辑课。  » 前提1 ：P→Q  » 前提2 ：P  » 结论：Q  • 定义：条件式推理结构  − 将例子中的两个前提记为  (P→Q)∧P，结论记为 Q ，上述推理过程可表述为：       (P→Q)∧P|→ Q    或    (P→Q)∧P ├ Q     称为条件式推理结构。  − 记号 ” ├” 读成 ”推出”  − (P→Q)∧P ├ Q 经常写成  (P→Q), P ├ Q  • 定义：推理结构的有效性  − 设命题公式  H、C ，若当  H  为真时，C 必为真，则称推理结构  H ├ C  是有效 的（或是正确的） 推理形式。否则，称推理结构  H ├ C 不是有效的（或是 无效的）推理形式。  » H ├ C 有效，即在  H 上的任何令  H  的真值为 T  的解释下，C  的真值均 为 T 。  » H ├ C 无效，即至少存在一个令  H  的真值为 T 而 C的真值为  F  的解释。  » 推广到有  n 个前提  H , H , …, H 的情形，可令  1 2 n                   H= H ∧H ∧…∧H 1 2   n    将推理的形式结构写成  H ├C ；     如果定义 Γ = {H , H , …, H }，可写成 Γ ├C 。  1 2 n   − 例：  P, (P→Q) ├ Q 是有效的推理结构。  » 由下面的真值表可见，穷尽所有的解释，只有第4行令  P∧(P→Q)=T。而对 应此解释，Q=T。  P  Q P→Q P∧(P→Q) F F T F F T T F T F F F T T T T − 例： ¬Q, (P→Q) ├ ¬P 是有效的推理结构。  » 由真值表可见，只有第1行解释令 ¬Q∧(P→Q)=T。而对应此解释， ¬P =T  。  P  Q ¬Q P→Q ¬Q ∧(P→Q) ¬P F F T T T T F T F T F T T F T F F F T T F T F F − 例： ¬P, (P→Q) ├¬Q 不是有效的推理结构。  » 由其真值表可见，存在第2行解释令 ¬P∧(P→Q)=T。而对应此解释，¬Q =F  。  P  Q ¬Q P→Q ¬Q ∧(P→Q) ¬P F F T T T T F T F T F T T F