命题逻辑的一种代数观点

  1. 2周前
    2周前aleph0 重新编辑

    鉴于知乎文章编辑器的糟糕表现,我现在把这篇短文搬运过来。

    这篇短文会对经典/直觉主义逻辑做一个简短的回顾,然后再用格论复读一遍。文章的内容只是我最近一段时间零碎笔记的整理,所以里面可能会有很多非标准的定义(以及很多本可避免的,重复琐碎的叙述)。文中出现错误也是难以避免的,欢迎斧正。

    我们假定集合论作为基础是不言自明的,并在此基础上讨论逻辑系统。当然,这种限制并非一定需要,我们大可以换为在更一般的基础理论上讨论;这里使用集合论只是一种文化上的沿袭和从简便的角度出发的一种取舍。我们希望,从最最混乱的体系(自然,某种意义上也是最一般的)出发,逐步构建出命题逻辑的结构。

    定义1. 我们把任意一个非空集合 $A$ 叫做字母表;我们记 $\mathrm{String}(A)=\bigcup_{n \in \mathbb{N}}{A^n}$ 为字母表 $A$ 生成的字符串构成的集合(注意,我们这里做约定:$ \mathbb{N}=\{0,1,2,\dots\} $,即,我们允许空字符串的存在)。

    定义2. (经典)命题逻辑的合法字符串集, $\mathrm{Form}(L_0)$ ,是集合 $\mathrm{String}(A \cup \{\to,\lnot\})$ 满足下列条件的一个子集(我们做约定, $A$ 是一个可数无限集);其中 $A$ 的元素被称为命题符号, $\to,\lnot$ 被称为逻辑连词符号。

    $\bullet$ $\to$ 前后两个符号是合法语素
    $\bullet$ $\lnot$ 后的符号是合法语素
    $\bullet$ 合法语素的前后是逻辑连词符号,或者没有没有别的符号

    除此之外,我们还额外加入括号。括号不视为字符串的元素,而应视为字符串的属性。括号加在 $ p\to q$ , $\lnot p$ 前后,其中 $p,q$ 是任意合法语素。
    合法语素是单个命题符号,或任何成对括号间的字串
    注 我们可以完全抛弃繁琐的(但是自然的)括号定义,比如波兰记法;选择自然记法的原因和我们选择集合论作为基础的原因类似。

    定义3. (经典)命题逻辑系统, $\mathcal{L}_0$ ,是 $\mathrm{Form}(L_0)$ 满足如下条件的一个子集:假设 $\alpha,\beta,\gamma$ 是任意合法语素,

    (THEN-1) $\alpha \to (\beta \to \alpha) \in \mathcal{L}_0$
    (THEN-2)$(\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to (\alpha \to \gamma)) \in \mathcal{L}_0$
    (CP) $((\lnot\beta) \to (\lnot \alpha)) \to ( \alpha \to \beta) \in \mathcal{L}_0$
    (MP)如果 $\alpha \in \mathcal{L}_0$ 且 $\alpha \to\beta \in \mathcal{L}_0$ ,那么 $\beta \in \mathcal{L}_0$
    $\mathcal{L}_0$ 的元素被称为(经典)命题逻辑的定理

    定理1. 以下皆为(经典)命题逻辑的定理:假设 $\alpha,\beta,\gamma$ 是任意合法语素,

    (ID) $\alpha \to \alpha$
    (DN) $\alpha \to \lnot(\lnot\alpha)$ 且 $\lnot(\lnot\alpha) \to \alpha$
    (NOT-1)$ (\alpha \to (\lnot \alpha)) \to (\lnot \alpha)$
    (NOT-2) $\lnot \alpha \to (\alpha \to \beta)$
    (mL) $(\alpha \to \beta)\to ((\alpha \to (\lnot \beta)) \to (\lnot \alpha))$
    证明. (ID)

    (THEN-1)$\alpha \to ((\alpha \to \alpha) \to \alpha) \in \mathcal{L}_0$
    (THEN-2)$(\alpha \to ((\alpha \to \alpha) \to \alpha)) \to ((\alpha \to (\alpha \to \alpha)) \to (\alpha \to \alpha)) \in \mathcal{L}_0$
    (MP:1,2)$(\alpha \to (\alpha \to \alpha)) \to (\alpha \to \alpha) \in \mathcal{L}_0$
    (THEN-1)$(\alpha \to (\alpha \to \alpha)) \in \mathcal{L}_0$
    (MP:4,3)$\alpha \to \alpha \in \mathcal{L}_0$ 证毕.
    其余证明暂略

    定理2. 我们有以下论断成立:假设 $\alpha,\beta,\gamma$ 是任意合法语素,

    (Cmp)如果 $\alpha \to \beta \in \mathcal{L}_0$ 且 $\beta \to \gamma \in \mathcal{L}_0$ ,那么 $\alpha \to \gamma \in \mathcal{L}_0$
    (DT)如果 $\alpha \in \mathcal{L}_0$ 且 $\beta \in \mathcal{L}_0$ ,那么 $\alpha \to \beta \in \mathcal{L}_0$
    证明. (Cmp)

    (假设) $\beta \to \gamma \in \mathcal{L}_0$
    (THEN-1) $(\beta \to \gamma) \to (\alpha \to (\beta \to \gamma)) \in \mathcal{L}_0$
    (MP:1,2) $\alpha \to (\beta \to \gamma) \in \mathcal{L}_0$
    (THEN-2) $(\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to (\alpha \to \gamma)) \in \mathcal{L}_0$
    (MP:3,4)$ (\alpha \to \beta) \to (\alpha \to \gamma) \in \mathcal{L}_0$
    (假设) $\alpha \to \beta \in \mathcal{L}_0$
    (MP:6,5) $\alpha \to \gamma \in \mathcal{L}_0$ 证毕.
    (DT)

    (假设) $\beta \in \mathcal{L}_0$
    (THEN-1)$ \beta\to (\alpha \to \beta) \in \mathcal{L}_0$
    (MP:1,2) $\alpha \to \beta\in \mathcal{L}_0$ 证毕.

    定义4. 为简略起见,我们在命题逻辑里增加二元逻辑连词符号 $\land,\lor$ ;也就是说,我们现在考虑 $\mathrm{String}(A \cup \{\to,\lnot,\land,\lor\})\big/ \sim$ 的合法字符串集,其中合法是指

    $\bullet$ $\to,\land,\lor$ 前后两个符号是合法语素
    $\bullet$ $\lnot$ 后的符号是合法语素
    $\bullet$ 合法语素的前后是逻辑连词符号
    $\bullet$ 额外加入括号;括号加在 $p\to q$ , $p\land q$ , $p\lor q$ , $\lnot p$ 前后,其中 $p,q$ 是任意合法语素。
    等价关系 $\sim$ 是指

    $$p\land q\sim\lnot(p \to (\lnot q))$$
    $$p\lor q\sim(\lnot p) \to q$$
    我们仍让把其记为 $\mathrm{Form}(L_0) $。这样的记法不会产生歧义,因为我们本质上只是将原来字符串的某些部分“改写”为了更加紧凑的形式;当我们需要时,随时可以通过以上的等价关系,将所有包含 $\land$ 和 $\lor$ 的字串替换为只包含 $\to $和 $\lnot $ 的字串,并且仍然是合法的。

    定义5. (经典)命题逻辑系统, $\mathcal{L}_0$ ,仍然相似地定义为 $\mathrm{Form}(L_0)$ 满足条件(THEN-1)(THEN-2)(CP)(MP)的子集。

    定理3. 利用刚刚定义的新逻辑连词,我们可以把以下(经典)命题逻辑的定理写为更紧凑的形式:假设 $\alpha,\beta,\gamma$ 是任意合法语素,

    (AND-1) $(\alpha\land\beta)\to \alpha $
    (AND-2)$ (\alpha\land\beta)\to \beta $
    (OR-1) $\alpha \to (\alpha\lor\beta)$
    (OR-2)$ \beta \to (\alpha\lor\beta)$
    (EM) $\alpha \lor (\lnot \alpha)$
    (GLB) $(\alpha \to \beta) \to ((\alpha \to \gamma)\to (\alpha \to (\beta \land \gamma)))$
    (LUB) $(\alpha \to \gamma) \to ((\beta \to \gamma)\to ((\alpha \lor \beta )\to \gamma))$

    定理4. 我们还有以下论断成立:假设 $\alpha,\beta,\gamma$ 是任意合法语素,

    (AND-CMT) $\alpha \land \beta \in \mathcal{L}_0$ 当且仅当 $\beta \land \alpha \in \mathcal{L}_0$
    (AND-AST)$(\alpha \land \beta)\land \gamma \in \mathcal{L}_0$ 当且仅当 $\alpha \land(\beta \land \gamma) \in \mathcal{L}_0$
    (AND-IDP) $\alpha \land \alpha \in \mathcal{L}_0$ 当且仅当 $\alpha \in \mathcal{L}_0$
    (OR-CMT) $\alpha \lor \beta \in \mathcal{L}_0$ 当且仅当 $\beta \lor \alpha \in \mathcal{L}_0$
    (OR-AST)$(\alpha \lor \beta)\lor \gamma \in \mathcal{L}_0$ 当且仅当 $\alpha \lor(\beta\lor \gamma)\in \mathcal{L}_0$
    (OR-IDP) $\alpha \lor \alpha \in \mathcal{L}_0$ 当且仅当 $\alpha \in \mathcal{L}_0$
    (AND-OR) $(\alpha \lor \beta)\land \gamma \in \mathcal{L}_0$ 当且仅当 $(\alpha \land\gamma) \lor(\beta\land \gamma)\in \mathcal{L}_0$
    (OR-AND) $(\alpha \land \beta)\lor \gamma \in \mathcal{L}_0$ 当且仅当 $(\alpha \lor\gamma) \land(\beta\lor \gamma)\in \mathcal{L}_0$
    (AND-Ad-THEN)$(\alpha \land \beta)\to \gamma \in \mathcal{L}_0$ 当且仅当 $\alpha \to (\beta\to \gamma) \in \mathcal{L}_0$

    我们暂时放下这些定理的证明。接下来我们要提到命题逻辑的两个核心概念:逻辑后继语义后继。我们将会看到,在(经典)命题逻辑的世界里,这两个概念是完全等价的(soundness/completeness)。我们还会定义理论的自洽性可满足性,在命题逻辑中,一个理论可满足当且仅当其任意有限子集是可满足的(compactness)。

    定义6. 假设 $\alpha \in \mathrm{Form}(L_0)$ 且 $\Gamma \subseteq \mathrm{Form}(L_0)$ ,那么一个从 $\Gamma$ 到 $\alpha$ 的证明是指一个有限长度的合法字符串列 $\phi_0,\phi_1,\dots,\phi_{n-1},\phi_n=\alpha$ ,满足

    $\bullet$ $\phi_i \in \mathcal{L}_0$ ,其中 $0 \leq i \leq n$
    或$\bullet$ $\phi_i \in\Gamma$ ,其中 $0 \leq i \leq n$
    或$\bullet$ 对于 $0 \leq k \leq n$ ,存在 $0 \leq i,j < k$ 使得 $\phi_j=\phi_i \to \phi_k$

    定义7. 我们定义一个 $\mathrm{Form}(L_0)$ 子集与 $\mathrm{Form}(L_0)$ 中元素的二元关系,逻辑后继 $\vdash$ : $\Gamma \vdash \alpha$ 当且仅当存在一个从 $\Gamma$ 到 $\alpha$ 的证明。我们定义 $\Gamma \subseteq \mathrm{Form}(L_0)$ 的逻辑闭包为 $\overline{\Gamma}:=\{\phi\in \mathrm{Form}(L_0):\Gamma \vdash \phi\}$ 。

    注 我们这里并不讨论证明存在的唯一性。事实上,一般证明的存在并非是唯一的,而且它们之间的区别可能是非平凡的。对于不同证明更加深入的讨论,可以在证明论中找到。

    不难看出, $\overline{\varnothing}=\mathcal{L}_0$ 且 $\overline{\mathrm{Form}(L_0)}=\mathrm{Form}(L_0)$ 。我们常把 $\varnothing \vdash \phi$ 简记为 $\vdash \phi$ ,把 $\Gamma\cup\{\alpha_1,\dots,\alpha_n\} \vdash \beta$ 简记为 $\Gamma,\alpha_1,\dots,\alpha_n \vdash \beta$ 。

    定理5. 我们有以下逻辑推演规则:

    (Ass)如果 $\phi \in \Gamma$ ,那么 $\Gamma \vdash \phi$
    (MP)如果 $\Gamma \vdash \phi$ 且 $\Gamma' \vdash (\phi \to \chi)$ ,那么 $\Gamma \cup \Gamma' \vdash\chi$
    (DT)如果 $\Gamma,\phi \vdash \chi$ ,那么 $\Gamma \vdash (\phi \to \chi)$
    (CP)如果 $\Gamma,\lnot \phi \vdash \chi$ 且 $\Gamma', \lnot \phi \vdash (\lnot \chi)$ ,那么 $\Gamma \cup \Gamma' \vdash\phi$

    定义8. 一个预序集是一个集合 $P$ 和其上的一个满足一下条件的二元关系 $\preceq$ :

    $\bullet$ 对于任意 $a \in P$ , $a \preceq a$
    $\bullet$ 对于任意 $a,b,c \in P$ ,$a \preceq b$ 且 $b \preceq c$ 则 $a \preceq c$
    一个偏序集 $(P,\preceq )$ 是二元关系满足如下条件的预序集:

    对于任意 $a,b \in P$ , $a \preceq b$ 且 $b \preceq a$ 则 $a=b$
    任意预序集都可以通过约掉等价关系: $a \sim b$ 当且仅当 $a \preceq b$ 且 $b \preceq a$ ,来成为偏序集(顺便一提,这个构造有泛性质)。预序集和偏序集都可以看作是范畴,其中对象就是原集合的元素,而态射可以定义为:

    $$\mathrm{Hom}_P(a,b):=\cases{\{*\},& $a \preceq b$ \\ \varnothing, & $a \not \preceq b$}$$

    如果一个偏序集 $P$ 存在极大元和极小元,那么它被称为有界的:即存在 $0,1 \in P$ 使得对于任意 $a \in P$ , $0 \preceq a \preceq 1$ (对于预序集,我们同样可以讨论极大极小元,但是这时它们不是唯一的;对于偏序集,如果极大极小元存在,那么它们总是唯一的)。

    如果一个偏序集 $P$ 的任意子集都存在上界和下界,那么它被称为完备的:即,对于任意 $\Delta \subseteq P$ ,存在 $\sup\Delta$ , $\inf\Delta$ 使得对于任意 $a \in \Delta$ , $\inf\Delta \preceq a \preceq \sup\Delta$ ,且对于任意 $b,c \in P$ ,如果对于任意 $a \in \Delta$ , $b\preceq a \preceq c$ 成立,那么 $b \preceq \inf\Delta \preceq a \preceq \sup\Delta \preceq c$ 。

    定义9. 一个是一个集合 $L$ 及其上的两个满足如下关系的二元运算 $\land, \lor$ :对于任意 $a,b,c \in L$ :

    $a \land b = b \land a$
    $(a \land b) \land c =a \land ( b \land c)$
    $a \lor b = b \lor a$
    $(a \lor b) \lor c =a \lor ( b \lor c)$
    $a \lor ( a \land b) =a $
    $a \land ( a \lor b) =a $
    $a \land a =a$
    $a \lor a=a $
    注 最后两条幂等律可以由两条吸收律推导出: $a \land a = a \land (a \lor ( a \land b)) =a $ , $a \lor a = a \lor (a \land ( a \lor b)) =a $ 。

    如果一个格 $L$ 存在两个运算幺元,那么它被成为有界的:即存在 $0,1 \in L$ 使得对于任意 $a \in L$

    $1 \land a =a \land 1 =a$
    $0 \lor a =a \lor 0 =a$
    如果格 $L$ 的两个运算还满足下面两个条件,那么它被称为分配的(事实上,只需要一个条件即可推出另一个):对于任意 $a,b,c \in L$

    $a \land(b \lor c) = (a \land b) \lor(a \land c)$
    $a \lor(b \land c) = (a \lor b) \land(a \lor c)$
    对于一个有界格 $L$ ,两个元素 $a,b \in L$ 如果满足 $a \land b=0$ 且 $a \lor b=1$ ,那么它们被称为是互补的(我们这里没有要求唯一性)。如果 $L$ 中的每个元素都能找到与其互补的元素,那么 $L$ 被称为是互补的。

    一个分配、互补的有界格又被称作布尔代数

    注 对于布尔代数,互补的元素是唯一存在的;与 $a \in L$ 互补的元素记为 $\lnot a$ 。

    格 $(L,\wedge,\vee )$ 同时是一个偏序集:对于 $a,b \in L$ ,我们让 $a \preceq b$ 成立当且仅当 $a \land b=a$ 或 $a \lor b =b$ 。由于吸收律,这两种定义是等价的:一方面, $a \land b =a$ 则 $b =b \lor (b \land a) = (a \land b) \lor b=a \lor b$ ;另一方面, $a \lor b= b$ 则 $a =a \land (a \lor b) = a \land b$ 。很容易验证如此定义的 $\preceq$ 的确是一个偏序关系。

    那么,是否任意偏序集都能赋予格的代数结构呢?答案是否定的。对于具有格结构的偏序集,其任意二元子集都有上界和下界存在:即, $\sup\{a,b\}=a \lor b$ 和 $\inf\{a,b\}=a \land b$ 。根据归纳,我们可知,具有格结构的偏序集存在任意有限非空子集的上下界。可以验证,对于任意偏序集,存在任意有限非空子集的上下界是其上存在格结构的充分必要条件。

    格是序结构与代数结构相容的数学对象。在研究格时,我们可以运用序理论或代数的工具;这给我们带来的很大的便利(顺便一提,范畴可以看作是格的推广:事实上,从格到范畴,我们放宽了态射数量的限制;当然,另一方面我们也放宽了对象数据大小的限制)。

    定理6. $\mathrm{Form}(L_0)$ 可以看作一个预序集,其上的预序关系 $\leq$ 定义为:对于任意 $a,b \in \mathrm{Form}(L_0)$ , $a \leq b$ 当且仅当 $a\land b \vdash a$ 且 $a \vdash a \land b$ (前一个条件总是成立的);等价地,我们可以定义 $a \leq b$ 当且仅当 $a\lor b \vdash a$ 且 $a \vdash a \lor b$ (后一个条件总是成立);或者,最简单地,定义为 $a \vdash b$ 。约掉等价关系后(双边逻辑后继),我们得到了一个偏序集,记为 $L_0$ (经典命题逻辑语言)。

    定理7. 经典命题逻辑语言, $L_0$ ,是一个完备的布尔代数。

    证明. 我们主要验证这几件事:极大元由恒真命题给出(我们马上就会定义赋值,从而解释这个名字的来历;现在我们不妨取其为命题 $\alpha \to (\beta \to \alpha)$ 的等价类,其中 $\alpha, \beta$ 是任意合法语素),极小元由恒假命题给出(类似地,我们不妨取为命题 $(\lnot \alpha) \land \alpha$ 的等价类,其中 $\alpha$ 是任意合法语素),给定任意命题 $\alpha, \beta$ ,交并补运算由最直观的方式给出:$[\alpha] \land [\beta]:= [\alpha \land \beta]$,$[\alpha] \lor [\beta]:= [\alpha \lor \beta]$,$\lnot[\alpha]:= [\lnot \alpha]$,注意这里等价类外面的是 $L_0$ 的格运算,等价类里面的是我们已经定义的逻辑连词。
    $\bullet$ 存在任意命题 $p$ 到 $\alpha \to (\beta \to \alpha)$ 的证明。事实上由于 $\alpha \to (\beta \to \alpha)$ 总是存在于 $\mathrm{Form}(L_0)$ ,这是MP的直接推论。
    $\bullet$ 存在 $(\lnot \alpha) \land \alpha$ 到任意命题 $p$ 的证明。我们可以给出如下证明:

    1. (由NOT-2,参见定理1)$ \vdash \not \alpha \to (\alpha \to p)$
    2. (由AND-Ad-THEN,参见定理4) $\not \alpha \to (\alpha \to p) \vdash (\lnot \alpha) \land \alpha \to p$
    3. (由Ass)$(\lnot \alpha) \land \alpha \vdash (\lnot \alpha) \land \alpha$
    4. (由MP 3,2)$(\lnot \alpha) \land \alpha, ((\lnot \alpha) \land \alpha \to p) \vdash p$

    $\bullet$ 对于验证交、并运算的性质,参考定理3、定理4中给出的结果;对于验证补运算的性质,注意到恒假命题(极小元) $[(\lnot a) \land a]=[\lnot a] \land [a]$ ,同时定理4中EM(排中律)给出 $[(\lnot a) \lor a]=[\lnot a] \lor [a]$是极大元;由补的唯一性,$[\lnot a] =\lnot [a]$ 。
    证毕.

    定义10. 我们现在观察(完备)二元布尔代数 $2=\{\bot,\top\}$ ,其中偏序关系记为 $\to$ ,二元运算 $\land, \lor$ ,取补运算 $\lnot$ :

    $\bot \to \top$
    $\bot \to \bot$
    $\top \to \top$
    $\lnot\bot = \top$ 且 $\bot = \lnot \top$
    $\bot \land \bot =\bot$
    $\bot \land \top = \top \land \bot=\bot$
    $\top \land \top =\top$
    $\bot \lor \bot =\bot$
    $\bot \lor \top = \top \lor \bot=\top$
    $\top \lor \top =\top$
    $\bot$ 是极小元
    $\top$ 是极大元

    定义11. 一个经典命题逻辑的赋值,是指一个保持布尔代数结构的同态: $v: L_0 \to 2$ 。所有经典命题逻辑的赋值构成的空间记为 $2^{L_0}$ 。

    定义12. 记 $(B,\land,\lor,\lnot,\top,\bot)$ 为一个布尔代数。一个非空子集 $F \subseteq B$ 如果满足以下条件,那么它被称作布尔代数 $B$ 的一个滤子

    $\bullet$ $\top \in F$
    $\bullet$ 如果 $a,b \in F$ ,那么 $a \land b \in F$
    $\bullet$ 如果 $a \in F$ ,那么对于任意 $b \in B$ , $a \lor b \in F$

    定理8. 每个赋值 $v$ 都确定了一个 $L_0$ 的滤子, $v^{-1}(\top)$ 。
    证明. 注意赋值都是布尔代数的同态,我们有:
    $\bullet$ $v(\top)=\top$,即 $\top \in v^{-1}(\top)$
    $\bullet$ 如果 $a,b \in v^{-1}(\top)$ ,那么 $v(a)=v(b)=\top$。所以 $v(a \land b)=v(a) \land v(b)=\top \land \top = \top$,也即 $a \land b \in v^{-1}(\top)$
    $\bullet$ 如果 $a \in v^{-1}(\top)$($v(a)=\top$) ,那么对于任意 $b \in L_0$ , $v(a \lor b)=v(a) \lor v(b) = \top \lor v(b) = \top$,也即 $a \lor b \in v^{-1}(\top)$
    证毕.

    定义13. 我们现在定义语义后继, $\models$ :如果 $\Gamma \subseteq \mathrm{Form}(L_0)$ 且 $\phi \in \mathrm{Form}(L_0)$ ,我们用 $[\phi],[\Gamma]$ 来表示其在 $L_0$ 中相应的等价类/等价类集;那么 $\Gamma \models \phi$ 成立当且仅当,对于任意赋值 $v \in 2^{L_0}$ ,$[\Gamma] \subseteq v^{-1}(\top)$ 可推导出 $[\phi] \in v^{-1}(\top)$ 。特别地,我们把 $\varnothing \models \phi$ 简记为 $\models \phi$ ;当且仅当对于任意赋值 $v \in 2^{L_0} [\phi] \in v^{-1}(\top)$ 总是成立,这个论断是对的。

    (待更)

  2. 有一本书叫An Algebraic Introduction to Mathematical Logic,不知道楼主参考了多少?

  3. @monad 这都是我自己写的,术语也是我瞎编的......学校倒是有开一门相关的课,链接在这里B1.1 Logic

 

后才能发言