命题逻辑

$T$-代数

$T$-代数也是一个代数系统，它的集合为一个由一些函数构成的集合 $T$，而它的运算为 $\mathrm{ar}$，其中 $\mathrm{ar}(x)$ 是函数 $x\in T$ 的参数个数。而定义在集合 $A$ 上的 $T$-代数则是让 $A$ 参与 $T$ 中函数的运算。

$T$-代数 $A$ 的子代数 $B$ 满足：

1. 集合 $B\in A$；
2. $B$ 关于 $T$ 中的函数满足封闭性。

NOTE

由定义可知，从 $A$ 随便取一个子集不一定是子代数。

$⟨X{⟩}_T$ 表示 $T$-代数 $A$ 的、包含 $X\subseteq A$ 的最小子代数。

$T$-代数上也可以定义同态映射，就是对于每个函数 $t\in T$ 和参数 $x$ 都满足 $\phi (t_A(x))=t_B(x)$。如果存在同态映射是满射，则两个 $T$-代数同态。

自由 $T$-代数

集合 $X$ 生成的自由 $T$-代数是对任何 $T$-代数保有 $X$ 关于 $T$ 的运算性质的代数，代表所有能被 $X$ 和 $T$ 表示出来的东西。这个自由 $T$-代数的集合不一定是 $X$，但是它和 $X$ 以及 $T$ 都有关系。

例如，取 $T:=\{F,\to \}$ 可以构造出一个 $X$ 生成的自由 $T-$代数 $P:=\bigcup P_n$，其中

$$\begin{array}{rl}{P}_0& :=\{F,x_1,\cdots \}\\ P_1& :=\{(\to ,a_i,a_j):a_i,a_j\in P_0\}\\ P_2& :=\{(\to ,a_i,a_j):\{a_i,a_j\}=\{P_1,P_0\}\}\\ & \cdots \end{array}$$

总之，$P_n:=\{(\to ,a_i,a_j):a_i\in P_x,a_j\in P_y,x+y=n-1\}$。它表示了一个由所有有 $n$ 个“$\to$”符号的表达式构成的集合。这个特定的自由 $T$-代数叫作命题代数 $P(X)$。

NOTE

命题代数中的零元运算 $F$ 含义是“假”。

“$T$ 字”是自由 $T$-代数的元素，而“字”是同态映射后的 $T$-代数的元素。对应到命题代数中，也就是 “$T$ 字” 是命题，“字”是真/假。无论是 $T$ 字还是字，都可以按照 $T$ 中函数的运算规则进行运算。

命题演算

赋值与指派

• 命题的赋值：命题代数 $P(X)$ 到同余类 ${\mathbb{Z}}_2$ 的同态映射 $v$ 叫作对 $P(X)$ 的赋值。当 $v(p)=1$ 时称 $p$ 为真，否则称 $p$ 为假。
• 命题变元的指派：$v_0$ 将命题变元集合 $X$ 映射到 ${\mathbb{Z}}_2$ 上。

指派可以唯一地扩张为命题的赋值。意思是，给变量赋值之后就可以唯一地知道每个命题是真是假。

• 语义蕴涵：$A\models p$ 表示对所有使得 $v(A)=1$ 的赋值，都有 $v(p)=1$。
• 逻辑蕴含：$A⊢p$ 表示存在从 $A$ 导出 $p$ 的证明。
• 重言式 $\models p$ 表示 $\varnothing \models p$，定理 $⊢p$ 表示 $\varnothing ⊢p$。

另一种记号：

• $A\models p⟺p\in \mathrm{Con}(a)$
• $A⊢p⟺p\in \mathrm{Ded}(a)$

NOTE

语义蕴涵和逻辑蕴涵的实质区别在于，语义蕴涵是根据一系列赋值得到的，而逻辑蕴涵是根据一系列推理规则得到的。因此，如果构造出一个合适的推理规则来描述某个赋值，则基于这种赋值的语义蕴涵与基于这种推理规则的逻辑蕴涵应该是等价的。

但是由于有不完备性定理，所以无法构造出满足要求的推理规则，即无论怎样构造，都会有一些命题无法证明。

IMPORTANT

$A\models p$ 本身不是一个命题。

析取范式与合取范式

• 析取范式：${\bigvee }_i\left({\bigwedge }_j{x}_{ij}\right)$，最常用，若干个与都可以
• 合取范式：${\bigwedge }_i\left({\bigvee }_j{x}_{ij}\right)$

任一种都可以表达所有的命题。

TIP

一般通过真值表写出析取范式，然后可以把析取范式转换成合取范式：取真值表中的其他项，把变量的真假反过来、$\vee$ 和 $\wedge$ 反过来就是合取范式。

证明方法

1. 用定义证明 $$\begin{array}{rl}\neg p& \stackrel{\mathrm{def}}{=}p\to F\\ p\vee q& \stackrel{\mathrm{def}}{=}\neg p\to q\\ p\wedge q& \stackrel{\mathrm{def}}{=}\neg (\neg p\vee \neg q)\\ p\leftrightarrow q& \stackrel{\mathrm{def}}{=}(p\to q)\wedge (q\to p)\end{array}$$
2. 用真值表证明
3. 用演算规则证明 $$\begin{array}{rlrl}v(p\to q)& =v(p)\to v(q)& & =1+v(p)(1+v(q))\\ v(\neg p)& =v(p\to F)& & =1+v(p)\\ v(p\vee q)& =v(\neg p\to q)& & =v(p)+v(q)+v(p)v(q)\\ v(p\wedge q)& =v(\neg (\neg p\vee \neg q))& & =v(p)v(q)\\ v(p\leftrightarrow q)& =v((p\to q)\wedge (q\to p))& & =1+v(p)+v(q)\end{array}$$
4. 用公理证明 $$\begin{array}{rl}{\mathcal{A}}_1& :=p\to (q\to p)\\ {\mathcal{A}}_2& :=(p\to (q\to r))\to ((p\to q)\to (p\to r))\\ {\mathcal{A}}_3& :=\neg \neg p\to p\\ MP& :=\{p,p\to q\}⊢q\end{array}$$
5. 演绎定理：$A⊢p\to q⟺A\cup \{p\}⊢q$，用来把 $⊢$ 在式子中左右移动。

NOTE

这里的 $+$ 和 $\cdot$ 都是布尔代数中定义的运算。其中 $+$ 是异或，$\cdot$ 是与。同时也是 ${\mathbb{Z}}_2$ 上的加法和乘法运算。

WARNING

要求证明逻辑蕴涵时，才能使用公理和定理；要求证明语义蕴涵时，才能使用演算规则或者真值表。无论哪种证明，都可以使用符号的定义。

NOTE

注意到公理都是重言式。

NOTE

$p\vee q\stackrel{\mathrm{def}}{=}\neg p\to q$ 这条式子就是 2-SAT 算法建图的依据。

语义的完备性

逻辑 $L:=\mathrm{Prop}(X)$ 由 $P(X)$ 和 $v$ 和证明序列集组成。

逻辑系统可能具有这些性质：

• 协调性：$/⊢F$
• 可靠性：$A⊢p⟹A\models p$
• 完备性：$A\models p⟹A⊢p$

如果有限步内总可以判断 $p$ 是否为重言式，则称逻辑 $L$ 是有效性 可判定的。

如果有限步内总可以判断 $p$ 是否为定理，则称逻辑 $L$ 是可证明性 可判定的。

有几个性质：

• 可靠性定理：在 $P(X)$ 上，$A⊢p⟹A\models p$
• 协调性定理：$F$ 不是 $\mathrm{Prop}(X)$ 的定理

称 $A\subseteq P(X)$ 是协调的当且仅当 $A⊢F$。

IMPORTANT

$F\notin X$ 但是 $F\in P(X)$ 并且 $F\in T_0\subset T$。

• 可满足性定理：设 $A$ 是 $P(X)$ 的协调子集，则存在赋值 $v$ 使得 $v(A)\subseteq \{1\}$。
• 完备性定理：若 $\mathrm{Prop}(X)$ 中有 $A\models p$ 则 $A⊢p$。

NOTE

完备性定理假设了 $A\models p$ 才能让 $p$ 可证明。这与不完备性不矛盾，因为不完备性说的是一定有命题无法被证明，并没有讨论它是否是重言式。

• $\mathrm{Prop}(X)$ 是有效性可判定的。
• $\mathrm{Prop}(X)$ 是可证明性可判定的。