数理逻辑

参考资料

• 电科大离散数学 - 标准离散数学 - 3
• 离散数学及其应用 - 翻译版, 包括 "离散数学" 和组合数学 / 初等数论 /... - 4

命题逻辑

• 命题
• 命题连结词 / 复合命题
• 真值表 / 命题化简
• 等价式
• 范式 / 主范式 / 析取范式 / 合取范式
  • \(\bigvee_{i=1}^{n} \left( \bigwedge_{j=1}^{m} l_{ij} \right)\)
• 可满足性

推理

• 根据已知命题的真值推出新的命题
• 直接证明
• 间接证明
  • 反证法 假设待证明的命题为假, 推出矛盾的命题
  • 等价证明法 证明待证明命题的逆否命题
• 非推理的证明
  • 构造证明 证明存在
  • 数学归纳法

谓词逻辑

• 个体词 / 谓词 / 量词
• 前束范式 所有的量词都在最左边且辖域覆盖全式
  • \(Q_1x_1 Q_2x_2 \cdots Q_nx_n \ \varphi\)
  • 其中 \(Q_i \in { \forall, \exists }\), \(\varphi\) 为不含量词的公式
• 解释 使全式为真的一组真值
• 推理规则
• 分情形证明法 (分类讨论) / 穷举法
• 全称证明 / 存在证明 (构造 / 非构造) / 唯一证明