命题

命题是指具有确切真值的判断语义；

  • 原子命题：无法分解为更简单命题的命题；
  • 复合命题：可以继续被分解的命题；

命题应该用大写的字母表示；

联结词

联结词 表示 真值
否定联结词 为真当且仅当为假
合取联结词 为真当且仅当均为真
析取联结词 为真当且仅当其一为真
蕴含联结词 为假当且仅当为真，为假
等价联结词 为真当且仅当同为真或者同为假

进一步，复合命题可以表示为原子命题和联结词的组成；

命题公式

对于一个常值命题而言，它的真值不是真就是假；

对于一个任意的，没有赋予内容的原子命题，称其为命题变量，如果它没有确切的真值，真值取决于命题的内容；

命题公式可由如下规则生成：

  • 命题变元本身是一个公式；
  • 若是一个公式，则也是公式；
  • 若是一个公式，则也是公式；
  • 联结词的使用有限次；

对于是含有命题变元的公式，记为

指定的一组真值，称这组真值是的一个解释;

分类

对于命题公式;

  • 重言式：若的所有解释下真值为真；
  • 矛盾式：若的所有解释下真值为假；
  • 可满足式：至少存在一种解释,使得在下为真；

若对于两个命题公式,它们出现的命题变元为,对于个每一种解释，的真值相同，称是等价的，记作;

  • 显然不是联结词，而是一种等价关系；
  • 满足自反性，对称性，传递性；
  • 当为重言式时，

对于等价关系可以暴力的使用真值表加以验证；

代入定理：

对于命题公式,对于任意的命题公式;

如果是重言式或者矛盾式，

对于也是重言式或者矛盾式；

替换定理

设Ｇ是Ｇ的子公式，Ｈ是任意的命题公式，在Ｇ中凡出现Ｇ_1，处都 以替换，由此得到新的命题公式Ｈ，若,则

范式

文字：命题变元，或者命题变元的否定；

子句：有限个文字的析取式

短语：有限个文字的合取式

析取范式：有限个短语的析取式；

合取范式：有限个短语的合取式；

主析取范式：每一个短语都是最小项；

定理：对于任意的命题公式，都存在与其等价的析取范式和合取范式；

proof:可分为如下三步逐步转化：

  1. 消去等价关系和蕴含关系

  2. 将否定移动到命题变元前面

  3. 重复利用分配律

推理理论

形式证明：

  • 前提：已知的命题公式；
  • 结论：从前提出发利用推理规则推出的命题公式

通过形式证明可以的出有效结论，我们不关心前提时都为真，只关注推理的真实性；

对于公式，称为的逻辑结果，当且仅当对于任意的解释，若同时满足,则满足，记作

  • 此时称这个是有效的，
  • 称为一组前提；
  • 称为结论，或者逻辑结果；