用户: 不萌/数理逻辑/命题逻辑

其实命题逻辑一上来应该讨论一些哲学问题, 但做数学的人对于这些一般来说不太感兴趣, 所以我们就直接忽略掉 “为什么” 这些符号都是这么些意思, 而直接使用这些符号, 再去说这些逻辑符号满足这些性质, 从而搭建起命题逻辑的地基. (相较于哲学可能会更加追问比如说 “为什么蕴涵这一连词是这么定义的” 等等问题)

命题逻辑一上来都是给一套语言, 我们所关注的是这套语言能不能系统地 (独立于个人意志), 规定合理地 (规定对错), 以及在前提的合理性和结论的合理性之间有效 (简洁而准确), 完备地保持一致性和可靠性.

在这一部分乃至整个逻辑学中, 十分重要的内容是区分与研究形式语言在 语义和 句法上的差异性与联系.

1命题逻辑语言

语言是一串符号满足一些条件的排列, 那么命题逻辑语言的符号集如下:

定义 1.1 (命题逻辑语言的符号集).

•	逻辑符号: $()\neg \to$; 其中除了 () 以外的逻辑符号也称为命题连接词, 也简称连词
•	命题符号: 对于每一个自然数 $n\in \mathbb{N}$, 有一个命题符号 $A_n$.

注 1.2.

•	其实从我们日常生活中的推理来说, 符合直觉的常用连词除了 $\neg$(非, 表示否定), $\to$(蕴涵) 以外, 还有 $\leftrightarrow$(等价, 同) $\wedge$(合取, 与) $\vee$(析取, 或). 这里只写这两个是因为这两个都符合直觉, 而且用它们就能够充分表示所有的命题逻辑语句 (等值意义下).
•	这也说明了其实这样的符号选取不是唯一的, 不过都差异不大.

命题逻辑的符号集合记作 $\Sigma$:$$\Sigma =\left\{(,),\neg ,\to ,A_n|n\in \mathbb{N}\right\}$$

于是我们可以记 ${\Sigma }^{\ast }$ 是 $\Sigma$ 上所有有限长度符号串的集合, 并可以由此唯一定义每一个符号串的长度. 我们在这一部分会将一个长为 $|s|$ 的符号串 $s$ 记作$$s=⟨s_1,\dots ,s_{|s|}⟩$$我们还可以在 ${\Sigma }^{\ast }$ 上定义连接的运算 $\ast$,$$s\ast t=⟨s_1,\dots ,s_{|s|},t_1,\dots ,t_{|t|}⟩$$这是满足结合律并且不满足交换律的运算.

定义 1.3 (命题语言与命题表达式). ${\Sigma }^{\ast }$ 的一个子集 $L$ 是一个准语言当且仅当满足以下条件:

(a)	所有的命题符号都是一个合法句子, 即 $⟨A_n⟩\in L$
(b)	对于一个合法句子取非是合法操作, 即如果 $s\in L$, 那么 $⟨(\neg ⟩\ast s\ast ⟨)⟩\in L$
(c)	将两个合法句子用蕴涵相连是合法操作, 即如果 $s,t\in L$, 那么 $⟨(⟩\ast s\ast ⟨\to ⟩\ast t\ast ⟨)⟩\in L$.

我们定义命题语言 ${\mathcal{L}}_0$ 是最小的准语言, 即对于任意一个准语言 $L$ 都包含 ${\mathcal{L}}_0$, 以后会称其中的元素为命题表达式.

注 1.4.

•	这一部分我们制定了一些语法规则, 告诉我们哪些说的话是有意义的, 哪些只是嗷呜乱叫.
•	虽然上面说得奇形怪状的, 但简而言之就是在 $s,t$ 合法的情况下 $(\neg s),(s\to t)$ 也是合法的句子, 之所以这样写是因为我们希望写成集合里面的操作.
•	在此前我们说以后可能会用到的其它符号, 在后续会定义它们的用法, 其实就是将 $\to$ 改成其它几个符号, 不过在语言定义的初期, 我们先不这么做.

定理 1.5. 命题语言 ${\mathcal{L}}_0$ 是所有准语言的交.

证明. 只需要证明所有准语言的交也是准语言.

$\square$

定义 1.6 (可读性). 假设 $\phi \in {\mathcal{L}}_0$, 那么以下三个条件必恰居其一:

(a)	$\phi =⟨A_n⟩(n\in \mathbb{N})$;
(b)	$\phi =⟨(\neg ⟩\ast \psi \ast ⟨)⟩$ 且 $\psi \in {\mathcal{L}}_0$;
(c)	$\phi =⟨(⟩\ast {\psi }_1\ast ⟨\to ⟩\ast {\psi }_2\ast ⟨)⟩$ 且 ${\psi }_1,{\psi }_2\in {\mathcal{L}}_0$.

证明. 只要证明 ${\mathcal{L}}_0$ 中满足以上三个条件的所有命题表达式构成的子集合是准语言.

$\square$

定理 1.7 (唯一可读性). 假设 $\phi \in {\mathcal{L}}_0$, 那么以下三个条件必恰居其一:

(a)	$\phi =⟨A_n⟩(n\in \mathbb{N})$ 且 $n$ 唯一确定;
(b)	$\phi =⟨(\neg ⟩\ast \psi \ast ⟨)⟩$ 且 $\psi \in {\mathcal{L}}_0$ 是唯一确定的;
(c)	$\phi =⟨(⟩\ast {\psi }_1\ast ⟨\to ⟩\ast {\psi }_2\ast ⟨)⟩$ 且 ${\psi }_1,{\psi }_2\in {\mathcal{L}}_0$ 都是唯一确定的.

证明. 根据可读性引理1.6, 只要证明唯一性, 而唯一性由以下的引理给出.

引理 1.8. 若 $\phi \in {\mathcal{L}}_0$, 那么没有 $\phi$ 的真前缀会在 ${\mathcal{L}}_0$ 中.

引理的证明使用对于命题表达式的长度归纳法, 并且反复使用可读性引理.

当 $\phi$ 长度为 1 时, 不存在真前缀.

当 $\phi$ 长度为 $n>1$ 时, 假设每个长度小于 $n$ 的表达式都已满足结论. 根据可读性引理1.6, $\phi$ 是 $(\neg \psi )$ 或者 $({\psi }_1\to {\psi }_2)$.

第一种情况:$\phi$ 是 $(\neg \psi )$ 时, 我们认识到如果存在一个真前缀 $s$ 是表达式, 一定以 $⟨(,\neg ⟩$ 开头. 继续对 $s$ 使用可读性引理:$s$ 不能是命题符号; $s$ 如果是 $({\psi }_1\to {\psi }_2)$, 就意味着 ${\psi }_1$ 以 $\neg$ 开头, 但是它应该以 $($ 开头或者是命题表达式, 矛盾; $s$ 如果是 $(\neg \theta )$, 这也就意味着 $\theta$ 是 $\psi$ 的真前缀语句, 矛盾!

第二种情况:$\phi$ 是一个蕴涵式 $({\psi }_1\to {\psi }_2)$ 假设 $s$ 是 $\phi$ 的一个前缀, 根据可读性引理, $s$ 不可为命题符号; $s$ 是否定式时说明 ${\psi }_1$ 以 $\neg$ 开头, 亦不成立; $s$ 是蕴涵式 $({\theta }_1\to {\theta }_2)$ 时, ${\theta }_1$ 与 ${\phi }_1$ 互相不为对方的真前缀, 因此相同, 同理 ${\theta }_2$ 与 ${\phi }_2$ 相同.

$\square$

2逻辑赋值

这一部分我们来考虑命题逻辑的语义内容, 就是要确定命题表达式的真假: 什么时候 ${\mathcal{L}}_0$ 中的表达式有什么样的真假赋值?

定义 2.1 (真假赋值). 一个 ${\mathcal{L}}_0$ 的真假赋值 $\nu$ 是一个从命题符号集合 $\left\{A_n|n\in \mathbb{N}\right\}$ 到真假值集合 $T,F$ 的一个映射.

定义 2.2 (两个连词的赋值规则).

(1)	定义 $H_{\neg }:\{T,F\}\to \{T,F\}$ 如下: $$H_{\neg }(T)=F,H_{\neg }(F)=T;$$
(2)	定义 $H_{\to }:\{T,F{\}}^2\to \{T,F\}$ 如下: $$H_{\to }(T,T)=T,H_{\to }(T,F)=F,H_{\to }(F,T)=T,H_{\to }(F,F)=T;$$

定理 2.3 (唯一扩张定理). 对于每一个关于 ${\mathcal{L}}_0$ 的赋值 $\nu$, 都可以唯一扩张为 ${\mathcal{L}}_0$ 到 $\{T,F\}$ 的映射 $\bar{\nu }$:

1.	$\bar{\nu }(A_n)=\nu (A_n)$;
2.	$\bar{\nu }((\neg \psi ))=H_{\neg }(\bar{\nu }(\psi ))$;
3.	$\bar{\nu }(({\psi }_1\to {\psi }_2))=H_{\to }(\bar{\nu }({\psi }_1),\bar{\nu }({\psi }_2))$.

证明. 根据唯一可读性定理, 对于结构进行归纳, 具体过程留作思考 $♣$.

$\square$

定理 2.4 (局部确定性). 设 $\phi \in {\mathcal{L}}_0$ 是一个命题表达式. 再设 $\nu$ 和 $\mu$ 是两个关于 ${\mathcal{L}}_0$ 的赋值, 且对于在 $\phi$ 中出现的每一个命题符号, 两个赋值的取值都是一致的. 那么两个赋值的扩张在这个命题表达式上的取值也相等.

证明. 根据唯一可读性定理, 对于结构进行归纳, 具体过程留作思考 $♣$.

$\square$

以上的定义与定理几乎都是符合直觉的, 可能不符合直觉的只有 $\to$ 的赋值规则, 当前提为假时整个命题表达式为真. 事实上, 这一情况也符合数学直觉, 随意看一些例子: "$当x>2时,x^2>4$", 这个式子从直觉上来说就很对, 那么当 $x=0,3,-5$ 它都当然是对的.