数理逻辑

Posted on

数理逻辑

命题

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

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

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

联结词

联结词 表示 真值
否定联结词 $\neg P$ $\neg P$为真当且仅当$ P$为假
合取联结词 $P \wedge Q$ $P\wedge Q$为真当且仅当$P,Q$均为真
析取联结词 $P\vee Q$ $P\vee Q$为真当且仅当$P,Q$其一为真
蕴含联结词 $P\to Q$ $P\to Q$为假当且仅当$P$为真，$Q$为假
等价联结词 $P\lrarr Q$ $P\lrarr Q$为真当且仅当$P,Q$同为真或者同为假

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

命题公式

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

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

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

  • 命题变元本身是一个公式；
  • 若$G$是一个公式，则$\neg G$也是公式；
  • 若$G,H$是一个公式，则$(G\wedge H),(G\vee H),(G\to H),(G\lrarr H)$也是公式；
  • 联结词的使用有限次；

对于$G$是含有命题变元$P_1,P_2,…,P_n$的公式，记为$G(P_1,P_2,…,P_n)$

指定$P_1,P_2,…,P_n$的一组真值，称这组真值是$G$的一个解释$I$;

分类

对于命题公式$G$;

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

若对于两个命题公式$G,H$,它们出现的命题变元为$P_1,…,P_n$,对于$2^n$个每一种解释，$G,H$的真值相同，称$G,H$是等价的，记作$G=H$;

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

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

代入定理：

对于命题公式$G(P_1,…,P_n)$,对于任意的命题公式$G_i(P_1,…,P_n),1\le i\le n$;

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

对于$G(G_1,…,G_n)=G’(P_1,…,P_n)$也是重言式或者矛盾式；

替换定理

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

范式

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

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

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

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

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

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

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

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

  1. 消去等价关系和蕴含关系
    $$
    (G\to H)=(\neg G \vee H)\
    (G\lrarr H)=(\neg G\vee H)\wedge (G\vee \neg H)
    $$

  2. 将否定移动到命题变元前面
    $$
    \neg \neg G=G\
    \neg(G\wedge H)=\neg G\vee \neg H\
    \neg(G\vee H)=\neg G\wedge \neg H
    $$

  3. 重复利用分配律
    $$
    G\wedge(H\vee S)=(G\vee H)\wedge(G\vee S)\
    G\vee(H\wedge S)=(G\wedge H)\vee(G\wedge S)
    $$

推理理论

形式证明：

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

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

对于公式$G_1,G_2,…,G_n,H$，称$H$为$G_1,G_2,…,G_n$的逻辑结果，当且仅当对于任意的解释$I$，若$I$同时满足$G_1,G_2,…,G_n$,则$I$满足$H$，记作$G_1,G_2,…,G_n\Rarr H$

  • 此时称这个$G_1,G_2,…,G_n\Rarr H$是有效的，
  • 称$G_1,G_2,…,G_n$为一组前提；
  • 称$H$为结论，或者逻辑结果；