离散数学知识梳理

一张思维导图带你了解数理逻辑离散数学知识点，帮助正在学习离散数学的同学们！知识点包括五种基本联结词、命题、等价公式、证明命题公式相等的常用方法、范式、推理。

数理逻辑

• 五种基本联结词
  • 非
    • 不是
  • 交
    • 并且，也
  • 并
    • 或者
  • 蕴含（P→Q）
    • 如果P就Q
    • 因为P所以Q
    • 只要P就Q
    • P仅当Q
    • 只有Q才P
    • 除非Q才P
    • 除非Q否则非P
    • 没有Q就没有P
  • 双蕴含
    • 当且仅当
    • 如果....则...反之亦然
• 命题
  • 定义要素
    • 陈述句
    • 具有确切真值
    • 真值仅有两种
    • 非悖论
    • 不能出现变量
  • 命题类型
    • 原子命题
    • 复合命题
      • 组成
        • 原子命题
        • ......若干
  • 命题公式
    • 组成要素
      • 命题变元
      • 逻辑联结词
      • 类似于命题的函数
    • 真值判断
      • 真值表法
    • 分类
      • 永真公式（重言式）
      • 永假公式（矛盾式）
      • 可满足公式
• 等价公式
  • 德摩根律
  • 假言易位（蕴含否定）
  • 等价式（双蕴含变换）
  • 鬼谬论（蕴含矛盾）
  • 等价否定（双蕴含否定）
• 证明命题公式相等的常用方法
  • 利用基本等价关系化简
  • 利用代入定理
    • 该方法用于证明永真或永假居多
  • 真值表方法
  • 利用替换定理
• 范式
  • 子句=析取式=若干个命题或命题公式取并集
    • 有限个短语的析取=析取范式
  • 短语=合取=若干个命题或命题公式取交集
    • 有限个子句的合取=合取范式
  • 计算方法
    • 基本等价关系
    • 德摩根率
    • 分配律
      • 建议用数字逻辑的符号进行运算再化回离散数学的符号
    • 真值表法
    • 利用主析取范式和主合取范式的关系
• 推理
  • 定义
    • 通过前提为真的假设下得出子结论，再利用子结论与其他结论相结合得出新子结论，直到得出答案
  • 方法
    • 前提取交后蕴含结果，证明永真
    • 演绎法
    • （根据要求的结果附加新前提）CP规则
    • 反证法
• 注意Q是P的必要条件，Q，P的前后顺序要注意
• 联结词的完备集（非重点）
• 当每一个元素都出现了每一个命题的原或否，则称主_取范式