命题逻辑

命题演算的形式符号

命题演算的形式符号为：

• 原子命题符号：$p_1,p_2,\cdots ,p_n,\cdots$，我们把所有原子命题符组成的集合称为 $At$
• 逻辑联结词：$\mathrm{\neg }$（否定词）、$\wedge$（合取词）、$\vee$（析取词）、$\to$（蕴含词）、$⟺$（等价）
• 括号：$()$

形式规则

形式符号是形式语言中最基本的符号，由它们可以组成有穷的符号串，称为形式表达式。有穷表达式的一个子集是合式公式，有时也称公式，这是我们最关心的一类表达式。

合式公式的定义：命题演算的合式公式可以利用递归定义

1. 原子命题符号是合式公式；
2. 若 $A$ 是合式公式，那么 $\mathrm{\neg }A$ 也是；
3. 如果 $A,B$ 都是合式公式，那么 $A\wedge B$、$A\vee B$ 和 $A\Rightarrow B$ 都是合式公式
4. 合式公式必须由有穷个 1～3 步得到。

所有合式公式组成的集合，称为 $PF$。我们规定联结词的结合强度为 $\mathrm{\neg }>\wedge >\Rightarrow$，这样可以省去很多括号。具体地，我们规定

• 最外层的括号可以省略；
• 否定符号外侧的括号可以省略，此时否定符与它右边的第一个合式公式结合；
• 应用合取和析取，按照最短的方式解释；
• 重复利用同一种联结词，从左到右计算。

我们可以将原子命题符号赋予意义，这样它就有了真假之分，我们通常用 $1$ 表示真，$0$ 表示假。同时，我们将逻辑联结词 $\mathrm{\neg }$（否定词）、$\wedge$（合取词）、$\vee$（析取词）、$\Rightarrow$（蕴含词）、$⟺$（等价）分别解释为“非”、“并且”、“或”、“蕴含”和“等价”（这里所谓解释即用自然语言去理解，方便对下文的真值表进行记忆），那么任何合式公式都能赋予一个真假，这一真假只取决于原子命题符号的真假和联结词的排列顺序。

对于一个合式公式 $A$，如果：

• 任意原子符号的赋值都能使 $A$ 为真，则称 $A$ 为永真公式或重言式。
• 如果不存在任何满足 $A$ 的一组赋值，那么称 $A$ 是永假的；否则，称 $A$ 为可满足的。

此外，如果设 $\mathrm{\Gamma }$ 是一个赋值的集合，$A$ 是一个公式，如果 $\mathrm{\Gamma }$ 中的所有赋值都能使 $A$ 为真，那么称 $A$ 是 $\mathrm{\Gamma }$ 的语义后承。

归纳法则 如果 $S$ 是一个包含所有命题符号的合式公式的集合，并且在上面 $5$ 种运算的作用下是封闭，那么 $S$ 是所有合式公式的集合。

真值指派

真值集合 $\{F,T\}$ 包含了两个不同的值，称为假和真。一个真值指派 $v$ 是指一个函数 $v:S\to \{F,T\}$，它为命题符号集合 $S$ 中的每一个符号指定了一个真值。而设 $\overline{S}$ 为 $S$ 通过 $5$ 种公式构造运算得到的合式公式的集合，那么我们也可以将函数 $v$ 扩展到 $\overline{v}$，得到 $\overline{v}:\overline{S}\to \{F,T\}$，其中 $\overline{v}$ 为 $\overline{S}$ 中的每一个合式公式指定了一个真值。下面的真值表展示了这种扩展过程

$\alpha$	$\beta$	$\mathrm{\neg }\alpha$	$\alpha \wedge \beta$	$\alpha \vee \beta$	$\alpha \Rightarrow \beta$	$\alpha ⟺\beta$
$T$	$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$	$T$

我们称一个真值指派 $v$ 满足合式公式 $\phi$ 当且仅当 $\overline{v}(\phi )=T$。

重言蕴含 对于一个合式公式的集合 $\mathrm{\Sigma }$ 和一个 合式公式 $\tau$，$\mathrm{\Sigma }$ 重言蕴含 $\tau$ 当且仅当对于任意的真值指派 $v$，如果 $v$ 满足 $\mathrm{\Sigma }$ 中的所有合式公式，那么 $v$ 也满足 $\tau$。$\mathrm{\Sigma }$ 重言蕴含 $\tau$ 记作 $\mathrm{\Sigma }\models \tau$。如果 $\mathrm{\Sigma }=\mathrm{\varnothing }$，那么 $\tau$ 为重言式。

例如，对于任意的合式公式 $A,B$，我们有$\{A,(A\Rightarrow B)\}\models B$。这翻译成自然语言就是经典的三段论。

紧致性定理 设 $\mathrm{\Sigma }$ 是一个合式公式的无限集合，如果对于 $\mathrm{\Sigma }$ 的任意有限子集 ${\mathrm{\Sigma }}_0$，${\mathrm{\Sigma }}_0$ 都有一个真值指派使得 ${\mathrm{\Sigma }}_0$ 中的所有合式公式都为真，那么 $\mathrm{\Sigma }$ 存在一个真值指派使得 $\mathrm{\Sigma }$ 中的所有合式公式都为真。

典型的重言式

我们可以利用一些典型的重言式来证明重言蕴含关系。这些重言式包括以下几组：

• 分配律
  • $A\wedge (B\vee C)⟺(A\wedge B)\vee (A\wedge C)$
  • $A\vee (B\wedge C)⟺(A\vee B)\wedge (A\vee C)$
• 否定
  • $\mathrm{\neg }\mathrm{\neg }A⟺A$
  • $\mathrm{\neg }(A\Rightarrow B)⟺A\wedge \mathrm{\neg }B$
  • $\mathrm{\neg }(A⟺B)⟺(A\wedge \mathrm{\neg }B)\vee (\mathrm{\neg }A\wedge B)$
• 德摩根律
  • $\mathrm{\neg }(A\wedge B)⟺\mathrm{\neg }A\vee \mathrm{\neg }B$
  • $\mathrm{\neg }(A\vee B)⟺\mathrm{\neg }A\wedge \mathrm{\neg }B$
• 其他的
  • 排中律：$A\vee \mathrm{\neg }A$
  • 蕴含：$A\Rightarrow B⟺\mathrm{\neg }A\vee B$
  • 矛盾律：$\mathrm{\neg }(A\wedge \mathrm{\neg }A)$
  • 逆否律：$A\Rightarrow B⟺\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$
  • 输出律：$((A\wedge B)\Rightarrow C)⟺(A\Rightarrow (B\Rightarrow C))$