命题逻辑的语义

2019-12-13 约 1150 字预计阅读 3 分钟

题记

本来这个系列的博客是打算上一两节课就更新一次，结果一转眼《计算机科学中的逻辑学》这门课已经结课了，打算花两天时间整理一遍，作为记录，也作为复习吧。

另外由于精力有限，很多地方没办法给出非常细致的证明，所以这个系列博客更多的是作为介绍性的博客，而非详尽的教程式的東西，如果想详细学习数理逻辑或者计算机逻辑学可以参考文末给出的教材。

Propositional logic as a formal language

一个对命题逻辑公式直观的感受是，一个命题逻辑公式是一个由字母表(alphabet) {p,q,r,…}∪{p1,p2,p3,…}∪{$\neg, \wedge, \vee, \rightarrow,(,)$} 组成的字符串(string)。但是这样是不够的，比如"$(\neg)() \vee p q \rightarrow$"这样的字符串对我么来说没有什么意义，所以需要严格定义一些公式，这样严格定义的公式是well-formed的(一个well-formed formula其实就是能够被称做formula的字符串，p.s. well-formed被翻译成"合式的”)。命题逻辑的well-formed的定义如下图所示：

判断一个公式是否well-formed的最简单的方法，就是画出公式的parse tree, 如下图是公式$((\neg(p \vee(q \rightarrow(\neg p)))) \wedge r)$的parse tree.

下图是一个非合式公式的parse tree.

Semantics of propositional logic

前提(premise) $\phi_{1}…$和结论(conclusion) $\psi$ 直接的关系有两大类，我们写成以下两种形式。

$\phi_1, \phi_2, \cdots, \phi_n \vdash \psi$ 关系①

$\phi_1, \phi_2, \cdots, \phi_n \vDash \psi$ 关系②

在关系①上：若要从前提证明结论，是语法层面的证明(即在上一篇博客介绍的自然推演规则下进行证明)，没有真假的判定。

在关系②上：若要从前提证明结论，是语义层面的证明(即真值表上，需要证若$\phi_1, \phi_2, \cdots, \phi_n$为T，则$\psi$也为T)，需要在实际空间(被称为语义空间)上证明。

命题逻辑具有可靠性(soundness)(即关系①成立那么关系②也成立)和完备性(completeness)(即若关系②成立，则关系①就成立)。

实际上我强烈建议关于这部分包括可靠性和完备性的证明看一下教材(在文末相关资料已经列出)，由于解释需要较长的篇幅，所以这里略去。

Normal form

决定$\vDash$有一些不同的方法，其中最原始的就是使用真值表进行判定，这种方法很费时，所以提出范式的概念。

范式(Normal form)本质上是用于加速算法的，相当于一种数据结构。这里我不详细介绍范式，给出一道例题体会一下即可。

基于下面的真值表构建CNF(合取范式)形式的公式：

目录

命题逻辑的语义

题记

Propositional logic as a formal language

Semantics of propositional logic

Normal form

相关资料