4 语义概念的严格刻画

… in mathematics a mere moral conviction, supported by a mass of successful applications, is not good enough.Gottlob Frege, The Foundations of Arithmetic, 1884. Trans. by J. I. Austin

在这一章里,我们对命题逻辑的基本概念给出严格的表述,并对这些概念做进一步的讨论和说明。

离开了证明就没有当代逻辑。读者从这一章起开始学习写证明。无论读者原来对证明是否陌生,也无论读者是否认为证明全不足道,若要想真懂点逻辑而不只是侃点逻辑,那就不能绕过一个个定理及其证明。

4.1 真值指派和公式的真值

4.1.1 对象语言里的符号和公式

逻辑学家们常喜欢不把对象语言明明白白地写下来,而只是用我们熟悉的语言来描述它们。在§2.3.0(P.79)中介绍 \(\mathscr{L}_0\)-符号时,我们说 \(\mathscr{L}_0\)-符号有命题变号 \(p_0, p_1,\cdots\) 和联结词 \(\neg, \land, \lor, \rightarrow, \leftrightarrow\) 等。这并不等于说,对象语言里的命题变号看上去都是某种字体的文字母表中第 16 个字母的小写形式,而且还有自然数下标。对象语言的命题变号到底什么样不是我们关心的问题,而这个语言中是否有表达自然数的符号更不是我们关心的问题——我们只是用我们的语言符号来表示那些命题变号,只是在我们的语言中把它们排成这样一个序列。类似地,对象语言中的否定号、蕴涵号是什么样子之类的问题都不是我们关心的问题。我们只是用 \(\neg\)\(\rightarrow\) 等分别表示它们。

虽然我们熟悉的语言都有文字符号,但毕竟不是所有的语言都一定要有文字符号。我们至少可以想像:在某个遥远的与世隔绝的地方,生活着一个非常原始的部落,这个部落的人们还没有发明文字语言,他们之间的交流只是通过口头语言、动作和表情等进行。如果我们要学习、谈论或研究他们的语言,那么我们就是把他们的语言当作对象语言,因而自然地不能强求对象语言必须有文字符号。明白了这一点,即使我们使用的所有符号都是元语言符号也没有什么难以理解的。

我们把 \(\mathscr{L}_0\) 的所有命题变号的集合记作 \(\mathbf{Pr}\),并把命题变号依下标排出的序 \(p_0, p_1, p_2,\cdots\) 称为 \(\mathbf{Pr}\) 上的(或命题变号的)「字典顺序」或「字母表」。

4.1.2 赋值、真、满足关系

语言 \(\mathscr{L}_{0}\) 的解释叫做「真值指派」(truth valuation, truth assignment)。

\(\mathbf{Pr}\)\(n\) 个命题的真值指派组合类型共 \({\prod_{i=1}^{n}} (C_{2}^{1})_i = 2^{n}\) 种。)

定义 4.1 (赋值) 一个赋值(或真值指派)是从 \(\mathbf{Pr}\)\(\lbrace 0, 1\rbrace\) 的函数 \(\sigma\),它对每个命题变号 \(p\) 指派一个真值 \(\sigma(p).\)

定义 4.2 (真) 对所有的 \(\mathscr{L}_0\)-公式 \(\varphi\),我们用 \(\varphi^\sigma\) 表示 \(\varphi\)\(\sigma\) 下的值。\(\varphi^\sigma\) 递归地定义如下(我们用「iff」表示「当且仅当」):

\[ \begin{array}{rcl} p_{n}^{\sigma}=1 & \text{iff} & \sigma(p_{n})= 1 ~(n \geqslant 0)\\ (\neg \psi)^{\sigma}=1 & \text{iff} & \psi^{\sigma} \neq 1 ~(\text {即}~ \psi^{\sigma}=0 ) \\ (\psi \vee \chi)^{\sigma}=1 & \text{iff} & \text {或者 }~ \psi^{\sigma}=1 \text { 或者 }~ \chi^{\sigma}=1 \\ (\psi \wedge \chi)^{\sigma}=1 & \text{iff} & \psi^{\sigma}=1 \text{ 并且 }~ \chi^{\sigma}=1 \\ (\psi \rightarrow \chi)^{\sigma}=1 & \text{iff} & \text {或者 }~ \psi^{\sigma} \neq 1 \text{ 或者 }~ \chi^{\sigma}=1 \\ (\psi \leftrightarrow \chi)^{\sigma}=1 & \text{iff} & \psi^{\sigma}=\chi^{\sigma} \end{array} \]

确定公式真值的这类定义通常被称作「真之定义(真理定义)」(truth definition)。对上述真理定义,我们有几点说明:

  1. 关于 \(\varphi^\sigma\) 的另一种等价的说法是把真值指派 \(\sigma\) 扩充成一个满足上述条件的从 \(\mathscr{L}_0\)-公式集到 \(\lbrace 0, 1\rbrace\) 的函数。
  2. 因真值指派就像是被指派为真的命题变号集合的特征函数(注:对任意集合 \(X\) 及其任意子集 \(Y\),从 \(X\)\(\lbrace 0, 1\rbrace\) 的函数 \(f\)\(Y\)特征函数当且仅当对每个 \(x \in X\),如果 \(x \in Y\)\(f(x) = 1\),并且如果 \(x \notin Y\)\(f(x) = 0.\) 在这种情况下,真值指派就成了真命题变号集合的特征函数。),人们常常把真值指派 \(\sigma\) 直接定义为 \(\mathbf{Pr}\) 的一个子集,亦即 \(\sigma \subseteq \mathbf{Pr}\) (或者 \(\sigma \in \mathscr{P}(\mathbf{Pr})\))(注:对任意集合 \(X\)\(\mathscr{P}(X)\) 表示 \(X\)幂集,即包含 \(X\) 的所有子集的集合 \(\lbrace Y: Y \subseteq X\rbrace\)。),而把 \(\varphi^\sigma\) 递归定义的第一行也相应改为「\(p_{n}^{\sigma}=1~\text{iff}~p_{n} \in \sigma (n \geqslant 0)\)」。
  3. 很多作者喜欢用「如果 \(\psi^{\sigma} = 1\) 那么 \(\chi^{\sigma} = 1\)」来替代上述递归定义第五行中的「或者 \(\psi^{\sigma} \neq 1\) 或者 \(\chi^{\sigma} = 1\)」。

对照基本真值表 2.1 和定义 3.1 中第二至第六行,易见两者在真值计算方面表达的内容是一样的。定义 3.1 确定了一个真值指派下各个公式的值,而下述「满足」定义说的是一个真值指派满足一个公式集当且仅当它使该集合中所有公式的值为 1.

定义 4.3 (满足) \(\Gamma\) 为任意 \(\mathscr{L}_0\)-公式集(可以是无穷集),并令 \(\sigma\) 为任意真值指派。 \(\sigma\) 满足 \(~\Gamma\)(符号表示:\(\sigma \vDash \Gamma\))当且仅当对每个 \(\varphi \in \Gamma\)\(\varphi^\sigma = 1.\) 我们用 \(\sigma \vDash \varphi\) 表示 \(\sigma \vDash \lbrace \varphi\rbrace\),并用 \(\sigma \nvDash \Gamma\)\(\sigma \nvDash \varphi\) 分别表示 \(\sigma \vDash \Gamma\)\(\sigma \vDash \varphi\) 不成立。

由上述定义可知下列等值式成立:

  1. \(\sigma \vDash \varphi\) 当且仅当 \(\varphi^\sigma = 1;\) (「\(\vDash\)」读作 “double-turnstile.”)
  2. \(\sigma \nvDash \varphi\) 当且仅当 \(\varphi^\sigma = 0;\)
  3. \(\sigma \vDash \Gamma\) 当且仅当对所有 \(\varphi \in \Gamma, \sigma \vDash \varphi;\)
  4. \(\sigma \nvDash \Gamma\) 当且仅当对某些 \(\varphi \in \Gamma, \sigma \nvDash \varphi.\)

\(\Gamma = \varnothing\)(空集)时,\(\Gamma\) 是否被一真值指派满足是一种「极限」情况。事实上,对每个真值指派 \(\sigma\) 都有 \(\sigma \vDash \varnothing.\) 这是因为,既然 \(\varnothing\) 是空集,那么就不存在 \(\varnothing\) 中的公式 \(\varphi\) 使得 \(\sigma \nvDash \varphi,\) 也就是说对每一个 \(\varphi \in \Gamma, \sigma \vDash \varphi.\)

3.6 中引入的一些基本语义概念,都是用真值表刻画的。真值表刻画在某种程度上依赖于读者对图形的直观。下面我们不借助这种直观,仅仅运用真值指派和满足关系这些概念,对 3.6 中引入的基本语义概念进行严格的定义。

4.2 重言蕴涵、重言等值与可满足性

「逻辑蕴涵」是逻辑学的核心观念之一,我们将在后续章节中讨论它,这里先讨论它在命题逻辑中的简单形式——「重言蕴涵」。在不产生歧义时,我们将省略前缀 「\(\mathscr{L}_0\)-」。

4.2.1 重言蕴涵

3.6 中,\(\lbrace \varphi_0,\cdots,\varphi_n \rbrace\) 重言蕴涵(tautologically implies) \(\psi\) 当且仅当在 \(\varphi_0,\cdots,\varphi_n\)\(\psi\) 的联合真值表中,没有一行是 \(\varphi_0,\cdots,\varphi_n\) 都真\(\psi\) 假。这是其联合真值表角度的定义。下面我们从赋值与满足出发,重新严格刻画重言蕴涵。

定义 4.4 (重言蕴涵) \(\Gamma\) 为任意公式集(可以是无穷的),并且 \(\varphi\) 为任意公式。 \(\Gamma \vDash_{0} \varphi\)\(\Gamma\) 重言蕴涵 \(\varphi\))当且仅当对每一个真值指派 \(\sigma\),如果 \(\sigma \vDash \Gamma\)\(\sigma \vDash \varphi.\) \(\varphi\)\(\Gamma\)重言后承当且仅当 \(\Gamma \vDash_{0} \varphi.\) (皆指 \(\mathscr{L}_{0}\) 中)

\(\Delta=\lbrace \varphi_0,\cdots,\varphi_n\rbrace\) 时,用 \(\varphi_0,\cdots,\varphi_n \vDash_{0} \varphi\) 表示 \(\Delta \vDash_{0} \varphi\),用 \(\Gamma, \varphi_0,\cdots,\varphi_n \vDash_{0} \varphi\) 表示 \(\Gamma \cup \Delta \vDash_{0} \varphi\)。当 \(\Delta=\varnothing\) 时,我们用 \(\vDash_{0} \varphi\) 表 示 \(\Delta \vDash_{0} \varphi.\)

Remark: 定义 4.43.6 中重言蕴涵的真值表刻画有所不同。不同之处有以下两点:

  1. \(\Gamma\) 在这里可以是无穷集合,而在重言蕴涵等概念的真值表刻画中,\(\Gamma\) 被限定为有穷集合。
  2. 真值指派要对所有命题变号给出真值,并且在定义重言蕴涵等语义概念时,定义涉及的真值指派显然有无穷多个;而用真值表刻画这些基本语义概念时,只需考虑给定公式中出现的有穷多个命题变号的真假,而且这些命题变号的可能取值组合也只有有穷多个。

从现在起,读者要学习证明。我们先证明一些简单的命题,且给出的证明也尽量详细。读者应对照定义来阅读以下的例子、命题及其证明,同时不要忽略本章后面的证明练习。

例 4.1 对所有公式 \(\varphi\)\(\psi\)\(\varphi \vee \psi, \neg \varphi \vDash_{0} \psi.\)
Proof: \(\sigma\) 为任意真值指派。假设 \(\sigma \vDash \varphi \lor \psi\)\(\sigma \vDash \neg \varphi\)(以下证明 \(\sigma \vDash \psi\))根据真之定义,由假设 \(\sigma \vDash \varphi \lor \psi\) 得知或者 $$或者 \(\sigma \vDash \psi\),再由假设 \(\sigma \vDash \neg \varphi\) 得知 \(\sigma \nvDash \varphi\),从而有 \(\sigma \vDash \psi\) 所以,对每个真值指派 \(\sigma\),如果 \(\sigma \vDash \varphi \lor \psi\)\(\sigma \vDash \neg \varphi\),那么 \(\sigma \vDash \psi.\) 根据重言蕴涵的定义\(\varphi \vee \psi, \neg \varphi \vDash_{0} \psi.\)
例 4.2 对所有公式 \(\varphi, \psi\)\(\chi\)\(\varphi \rightarrow \psi, \psi \rightarrow \chi \vDash_{0} \varphi \rightarrow \chi.\)
Proof: \(\sigma\) 为任意真值指派。假设(i)\(\sigma \vDash \varphi \rightarrow \psi\) 且(ii)\(\sigma \vDash \psi \rightarrow \chi\)(以下证明 \(\varphi \rightarrow \chi\))如果 \(\sigma \nvDash \varphi\),则 \(\varphi^\sigma \ne 1\),那么根据真理定义,\(\sigma \vDash \varphi \rightarrow \chi.\) 所以,假设(ii)\(\sigma \vDash \varphi.\) 根据真理定义和(iii),由(i)得到 \(\sigma \vDash \psi\),再由(ii)得到 \(\sigma \vDash \chi\),从而有 \(\sigma \vDash \varphi \rightarrow \chi.\)由此可知,对每个 \(\sigma\),如果 \(\sigma \vDash \varphi \rightarrow \psi\)\(\sigma \vDash \psi \rightarrow \chi\),那么 \(\sigma \vDash \varphi \rightarrow \chi.\) 根据重言蕴涵的定义\(\varphi \rightarrow \psi, \psi \rightarrow \chi \vDash_{0} \varphi \rightarrow \chi.\)
命题 4.1 对所有公式集 \(\Gamma\) 和所有公式 \(\varphi\),如果 \(\varphi \in \Gamma\)\(\Gamma \vDash_{0} \varphi.\)
Proof: 对每个真值指派 \(\sigma\),如果 \(\sigma \vDash \Gamma\),那么根据定义 3.2,\(\sigma\) 满足 \(\Gamma\) 中所有公式,由 \(\varphi \in \Gamma\) 得到 \(\sigma \vDash \varphi.\) 所以,根据重言蕴涵的定义\(\Gamma \vDash_{0} \varphi.\)
命题 4.2 对所有公式集 \(\Gamma\) 和所有公式 \(\varphi, \psi\)\(\Gamma, \varphi \vDash_{0} \psi\) 当且仅当 \(\Gamma \vDash_{0} \varphi \rightarrow \psi.\)

Proof:

  1. 假设 \(\Gamma \nvDash_{0} \varphi \rightarrow \psi.\) 根据重言蕴涵的定义,存在真值指派 \(\sigma\) 使得 \(\sigma \vDash \Gamma\) 并且 \(\sigma \nvDash \varphi \rightarrow \psi\),亦即 \(\sigma \vDash \varphi\)\(\sigma \nvDash \psi\),从而得到 \(\sigma \vDash \Gamma \cup \lbrace \varphi\rbrace\)\(\sigma \nvDash_{0} \psi.\) 再根据重言蕴涵的定义得知 \(\Gamma, \varphi \nvDash_{0} \psi.\)
  2. 假设 \(\Gamma \vDash_{0} \varphi \rightarrow \psi.\)\(\sigma\) 为任意真值指派。如果 \(\sigma \vDash \Gamma \cup\lbrace \varphi\rbrace\),则 \(\sigma \vDash \Gamma\)\(\sigma \vDash \varphi\),于是由假设和重言蕴涵的定义得知 \(\sigma \vDash \varphi \rightarrow \psi\)\(\sigma \vDash \varphi\),进而再由真理定义得到 \(\sigma \vDash \psi.\) 所以,根据重言蕴涵的定义,\(\Gamma, \varphi \vDash_{0} \psi.\)(「当且仅当」证法之例)
命题 4.3 对所有公式集 \(\Gamma, \varphi_0,\cdots,\varphi_n \vDash_{0} \psi\) 并且对所有 \(i \leqslant n\)\(\Delta \vDash_{0} \varphi_i.\) 我们有 \(\Gamma \cup \Delta \vDash_{0} \psi.\)
Proof: \(\sigma\) 为任意真值指派,并设 \(\sigma \vDash \Gamma \cup \Delta.\) 根据满足的定义,对所有的 \(\varphi \in \Gamma \cup \Delta\) 都有 \(\sigma \vDash \varphi\),因而对所有的 \(\varphi \in \Gamma\) 都有 \(\sigma \vDash \varphi\),并且对所有的 \(\varphi \in \Delta\) 都有 \(\sigma \vDash \varphi.\) 所以(i)\(\sigma \vDash \Gamma\),(ii)\(\sigma \vDash \Delta.\)\(i \leqslant n.\) 根据题设,\(\Delta \vDash_{0} \varphi_i;\) 再根据(ii)和重言蕴涵的定义, \(\sigma \vDash \varphi_i.\) 因为这对 \(i = 0,\cdots,n\) 都成立,所以由(i)和满足定义得到 \(\sigma \vDash \Gamma \cup \lbrace \varphi_0,\cdots,\varphi_n\rbrace\),再运用题设和重言蕴涵的定义,我们得到 \(\sigma \vDash \psi.\) 所以,由重言蕴涵的定义得知 \(\Gamma \cup \Delta \vDash_{0} \psi.\)

4.2.2 重言等值

在 §2.5.2(P.87)中,任意公式 \(\varphi\)\(\psi\) 重言等值(tautologically equivalent) 当且仅当在 \(\varphi\)\(\psi\) 联合真值表的任意一行中,\(\varphi\)\(\psi\) 有同样的真值。其赋值视角的定义如下:

定义 4.5 (重言等值) \(\mathscr{L}_{0}\)-公式 \(\varphi\)\(\psi\) 重言等值当且仅当对每个真值指派 \(\sigma\)\(\varphi^\sigma = \psi^\sigma.\)

易见:如果 \(\varphi\)\(\psi\) 重言等值,那么对每个真值指派 \(\sigma\)\(\sigma \vDash \varphi\) 当且仅当 \(\sigma \vDash \psi;\) 反之亦然。

例 4.3 对任意公式 \(\varphi\)\(\psi\)\(\varphi \rightarrow \psi\)\(\neg\varphi \lor \psi\) 重言等值。
Proof: \(\sigma\) 为任意真值指派。根据真理定义,\(\sigma \vDash \varphi \rightarrow \psi\) 当且仅当 \(\sigma \nvDash \varphi\) 或者 \(\sigma \vDash \psi\),当且仅当 \(\sigma \vDash \neg \varphi\) 或者 \(\sigma \vDash \psi\),当且仅当 \(\sigma \vDash \neg \varphi \lor \sigma \psi\)。根据重言等值定义,\(\varphi \rightarrow \psi\)\(\neg\varphi \lor \psi\) 重言等值。
例 4.4 对任意公式 \(\varphi\)\(\psi\)\(\varphi \leftrightarrow \psi\)\((\varphi \land \psi) \lor (\neg\varphi \land \neg\psi)\) 重言等值。

Proof: \(\sigma\) 为任意真值指派。根据真理定义,\(\sigma \vDash \varphi \leftrightarrow \psi\) 当且仅当:或者 \(\varphi^\sigma = \psi^\sigma = 1\),或者 \(\varphi^\sigma = \psi^\sigma = 0;\) 当且仅当 \(\sigma \vDash \varphi\)\(\sigma \vDash \psi\),或者 \(\sigma \nvDash \varphi\)\(\sigma \nvDash \psi.\) 于是由真理定义得到

\[ \begin{array}{rcl} \sigma \vDash \varphi \leftrightarrow \psi & \text{iff} & \text{或者}~ \sigma \vDash \varphi \land \psi ~\text{或者}~ \sigma \vDash \neg\varphi \land \neg\psi \\ & \text{iff} & \sigma \vDash (\varphi \land \psi) \lor (\neg\varphi \land \neg\psi) \end{array} \]

所以由重言等值的定义,\(\varphi \leftrightarrow \psi\)\((\varphi \land \psi) \lor (\neg\varphi \land \neg\psi)\) 重言等值。
例 4.5 对所有公式集 \(\Gamma\) 以及所有公式 \(\varphi\)\(\psi\),如果 \(\Gamma \vDash_{0} \varphi\) 并且 \(\varphi\)\(\psi\) 重言等值,那么 \(\Gamma \vDash_{0} \psi.\)
Proof: \(\Gamma \vDash_{0} \varphi\) 并且 \(\varphi\)\(\psi\) 重言等值。令 \(\sigma\) 为任意真值指派。如果 \(\sigma \vDash \Gamma\),那么由 \(\Gamma \vDash_{0} \varphi\) 和重言蕴涵的定义得知 \(\sigma \vDash \varphi\),再由重言等值的定义得到 \(\sigma \vDash \psi.\) 所以,再根据重言蕴涵定义,\(\Gamma \vDash_{0} \psi.\)
命题 4.4 对所有所有公式 \(\varphi\)\(\psi\)\(\varphi\)\(\psi\) 重言等值当且仅当 \(\varphi \vDash_{0} \psi\) 并且 \(\psi \vDash_{0} \varphi.\)

Proof: \(\varphi\)\(\psi\) 重言等值。对每一个真值指派 \(\sigma\),如果 \(\sigma \vDash \varphi\),那么由于 \(\varphi\)\(\psi\) 重言等值,可知 \(\sigma \vDash \psi.\) 这就是说,\(\varphi \vDash_{0} \psi.\) 同理可证 \(\psi \vDash_{0} \varphi.\)

\(\varphi \vDash_{0} \psi\)\(\psi \vDash_{0} \varphi.\) 根据此假设和重言蕴涵的定义,

  1. 对每个真值指派 \(\sigma_1\),如果 \(\sigma_1 \vDash \varphi\)\(\sigma_1 \vDash \psi.\)

  2. 对每个真值指派 \(\sigma_2\),如果 \(\sigma_2 \vDash \psi\)\(\sigma_2 \vDash \varphi.\)

\(\sigma\) 为任意真值指派。由(i)知:如果如果 \(\sigma \vDash \varphi\)\(\sigma \vDash \psi;\) 由(ii)知:如果 \(\sigma \vDash \psi\)\(\sigma \vDash \varphi.\) 从而 \(\sigma \vDash \varphi\) 当且仅当 \(\sigma \vDash \psi.\) 根据重言等值的定义,\(\varphi\)\(\psi\) 重言等值。

4.2.3 可满足性

在 §2.5.3(P.88)中,从联合真值表角度看,任意有穷公式集 \(\Gamma\) 可满足(satisfiable)当且仅当 \(\Gamma\) 中公式的联合真值表中存在某一行,在该行里 \(\Gamma\) 中的公式的真值都是 1. 下面我们从赋值与满足出发,重新严格刻画重言蕴涵。

定义 4.6 (可满足) \(\Gamma\) 为任意公式集(可以是无穷集),\(\varphi\) 为任意 \(\mathscr{L}_{0}\)-公式。\(\Gamma\) 是可满足的当且仅当存在一个真值指派 \(\sigma\) 使得 \(\sigma \vDash \Gamma;\) \(\varphi\) 是可满足的当且仅当 \(\lbrace \varphi\rbrace\) 是可满足的。\(\Gamma\)(或 \(\varphi\))是不可满足的当且仅当它不是可满足的。

Remark: 定义 4.43.6 中重言蕴涵的真值表刻画有所不同。不同之处有以下两点:

  1. \(\Gamma\) 在这里可以是无穷集合,而在重言蕴涵等概念的真值表刻画中,\(\Gamma\) 被限定为有穷集合。
  2. 真值指派要对所有命题变号给出真值,并且在定义重言蕴涵等语义概念时,定义涉及的真值指派显然有无穷多个;而用真值表刻画这些基本语义概念时,只需考虑给定公式中出现的有穷多个命题变号的真假,而且这些命题变号的可能取值组合也只有有穷多个。
例 4.6 \(\Gamma=\left\lbrace p \vee q, r \wedge s, p \rightarrow r \wedge r^{\prime}, s^{\prime} \leftrightarrow(\neg q \rightarrow \neg s)\right\rbrace.\) 我们有: \(\Gamma\) 可满足。

Proof: \(\sigma\) 为如下定义的真值指派:

  1. \(\sigma(p)=\sigma(r)=\sigma(s)=\sigma(r^{\prime})=1\)

  2. \(\sigma(q)=\sigma(s^{\prime})=0\)

  3. 对所有与 \(p, q, r, s, r^{\prime}\)\(s^{\prime}\) 不同的命题变号 \(p^{\prime}\)\(\sigma(p^{\prime})=0.\)

由真理定义和(i)知,\(\sigma \vDash p \vee q\)\(\sigma \vDash r \wedge s.\) 类似地, \(\sigma \vDash r \wedge r^{\prime}\) 进而 \(\sigma \vDash p \rightarrow r \wedge r^{\prime}.\) 由真理定义和(i)知 \(\sigma \not=\neg s\), 并由(ii)知 \(\sigma \vDash \neg q\),进而 \(\sigma \nvDash \neg q \rightarrow \neg s;\) 再由(ii)知 \(\sigma \nvDash s^{\prime}.\) 所以 $ s^{} (q s).$

综上所述, \(\sigma \vDash \Gamma.\)
例 4.7 \(q_{0}, q_{1},\cdots\) 为任意命题变号,满足对所有 \(i, j \geqslant 0\),如果 \(i \neq j\)\(q_{i} \neq q_{j};\) 并设 \(\Gamma=\left\lbrace q_{2k} \rightarrow \neg q_{2k+1}: k \geqslant 0\right\rbrace\)\(\Delta=\left\lbrace \neg q_{2k+1} \rightarrow q_{2k+2}: k \geqslant 0\right\rbrace\)。我们有:\(\left\lbrace q_{0}\right\rbrace \cup \Gamma \cup \Delta\) 可满足。

Proof: \(\sigma\) 为下列真值指派:对每个命题变号 \(p\)

\[ \sigma(p)= \left\lbrace \begin{array}{ll} 1 & \text{如果存在}~ k \geqslant 0 ~\text{使得}~ p=q_{2 k} \\ 0 & \text{否则} \end{array} \right. \]

显然,\(\sigma \vDash q_{0}.\) 对任意 \(k \geqslant 0\),由上述定义知 \(\sigma \nvDash q_{2k+1}\)\(\sigma \vDash q_{2k+2}\),从而根据真理定义,\(\sigma \vDash \neg q_{2k+1}\) 进而 \(\sigma \vDash q_{2k} \rightarrow \neg q_{2k+1}\)\(\sigma \vDash \neg q_{2k+1} \rightarrow q_{2k+2}.\) 所以,\(\sigma \vDash\left\lbrace q_{0}\right\rbrace \cup \Gamma \cup \Delta.\)
命题 4.5 对所有公式集 \(\Gamma\),如果 \(\Gamma\) 不可满足,那么对每个公式 \(\varphi\)\(\Gamma \vDash_{0} \varphi.\)
Proof: 假设 \(\Gamma\) 不可满足且令 \(\varphi\) 为任意公式。假如 \(\Gamma \nvDash_{0} \varphi\),那么就存在真值指派 \(\sigma\) 使得 \(\sigma \vDash \Gamma\)\(\sigma \nvDash \varphi\),但这是不可能的,因为 \(\Gamma\) 不可满足。
命题 4.6 对所有公式集 \(\Gamma\) 和所有公式 \(\varphi\)\(\Gamma \cup \lbrace \varphi\rbrace\) 不可满足当且仅当 \(\Gamma \vDash_{0} \neg \varphi\),并且 \(\Gamma \cup \lbrace \neg \varphi\rbrace\) 不可满足当且仅当 \(\Gamma \vDash_{0} \varphi.\)
Proof: 只证第一部分。设 \(\Gamma \cup \lbrace \varphi\rbrace\) 不可满足并令 \(\sigma\) 为任意真值指派。因为 \(\sigma \nvDash \Gamma \cup \lbrace \varphi\rbrace\) ,所以,如果 \(\sigma \vDash \Gamma\)\(\sigma \nvDash \varphi\),由真理定义得知,如果 \(\sigma \vDash \Gamma\)\(\sigma \vDash \neg \varphi\),进而由重言蕴涵定义得知 \(\Gamma \vDash_{0} \neg \varphi.\)\(\Gamma \vDash_{0} \neg \varphi\),令 \(\sigma\) 为任意真值指派。易见,如果 \(\sigma \vDash \Gamma\),则由重言蕴涵的定义知 \(\sigma \vDash \neg \varphi\),从而 \(\sigma \nvDash \varphi\),这就是说,\(\sigma \nvDash \Gamma \cup \lbrace \varphi\rbrace.\)\(\Gamma \cup \lbrace \varphi\rbrace\) 不可满足。

4.2.4 重言式、矛盾式与或然式

在 §2.5.4(P.88)中,重言式、矛盾式与或然式曾被以真值表的方式刻画,下面从赋值角度严格刻画这组概念。

定义 4.7 (重言式) 对任意 \(\mathscr{L}_{0}\)-公式 \(\varphi\)\(\varphi\) 是重言式当且仅当对每一个真值指派 \(\sigma\)\(\sigma \vDash \varphi.\)
定义 4.8 (矛盾式) 对任意 \(\mathscr{L}_{0}\)-公式 \(\varphi\)\(\varphi\) 矛盾式(或不可满足式)当且仅当对每一个真值指派 \(\sigma\)\(\sigma \nvDash \varphi.\)
定义 4.9 (或然式) 对任意 \(\mathscr{L}_{0}\)-公式 \(\varphi\)\(\varphi\) 或然式当且仅当对每一个真值指派 \(\sigma\) 使得 \(\sigma \vDash \varphi\)\(\sigma \nvDash \varphi\),并且存在一个真值指派 \(\sigma^\prime\),使得 \(\sigma^\prime \nvDash \varphi.\)

有别于 §2.5.4(P.88)中对重言式等概念的真值表刻画:真值指派要对所有命题变号给出真值,并且重言式等的定义涉及的真值指派显然有无穷多个;这些概念的真值表刻画却不同,它们只考虑公式中出现的有穷多个命题变号的真假,而这些命题变号的可能取值组合也只有有穷多个。

例 4.8 对任意公式 \(\varphi\)\(\varphi \lor \varphi \rightarrow \varphi\) 是重言式。
Proof: \(\sigma\) 为任意真值指派。如果 \(\sigma \vDash \varphi \lor \varphi\),那么根据真理定义,\(\sigma \vDash \varphi\),进而 \(\sigma \vDash \varphi \lor \varphi \rightarrow \varphi.\) 由重言式的定义知,\(\varphi \lor \varphi \rightarrow \varphi\) 是重言式。
例 4.9 对任意公式 \(\varphi, \psi\)\(\neg(\varphi \rightarrow \psi) \rightarrow \varphi \land \neg \psi\) 是重言式。
Proof: \(\sigma\) 为任意真值指派。假设 \(\sigma \vDash \neg(\varphi \rightarrow \psi).\) 根据真理定义,\(\sigma \nvDash \varphi \rightarrow \psi\),从而有 \(\sigma \vDash \varphi\)\(\sigma \nvDash \psi.\) 于是,\(\sigma \vDash \varphi\)\(\sigma \vDash \neg\psi\),进而 \(\sigma \vDash \varphi \land \neg \psi.\) 由此得知,对任意真值指派 \(\sigma\)\(\sigma \vDash \neg(\varphi \rightarrow \psi) \rightarrow \varphi \land \neg \psi.\) 根据重言式的定义,\(\neg(\varphi \rightarrow \psi) \rightarrow \varphi \land \neg \psi\) 是重言式。
例 4.10 对任意公式 \(\varphi\)\(\psi\)\(\varphi \land \neg (\varphi \lor \psi)\) 是矛盾式。
Proof: \(\sigma\) 为任意真值指派。根据真理定义,如果 \(\sigma \vDash \varphi \land \neg (\varphi \lor \psi)\),那么 \(\sigma \vDash \varphi\)\(\sigma \vDash \neg (\varphi \lor \psi)\),从而 \(\sigma \vDash \varphi\)\(\sigma \nvDash \varphi\),但这是不可能的。所以,\(\sigma \nvDash \varphi \land \neg (\varphi \lor \psi).\) 根据矛盾式的定义,\(\varphi \land \neg (\varphi \lor \psi)\) 是矛盾式。
例 4.11 对任意公式 \(\varphi\)\(\neg(\varphi \rightarrow \neg (\varphi \rightarrow \neg\varphi))\) 是矛盾式。
Proof: \(\sigma\) 为任意真值指派。假设 \(\sigma \vDash \neg(\varphi \rightarrow \neg (\varphi \rightarrow \neg\varphi)).\) 根据真理定义,我们有 \(\sigma \nvDash \varphi \rightarrow \neg (\varphi \rightarrow \neg\varphi)\),从而 \(\sigma \vDash \varphi\)\(\sigma \nvDash \neg (\varphi \rightarrow \neg\varphi)\),进而 \(\sigma \vDash \varphi \rightarrow \neg\varphi.\) 易见 \(\sigma \vDash \varphi\) 并且 \(\sigma \vDash \neg \varphi\),亦即 \(\sigma \vDash \varphi\) 并且 \(\sigma \nvDash \varphi\),但这是不可能的。所以,\(\sigma \nvDash \neg(\varphi \rightarrow \neg (\varphi \rightarrow \neg\varphi)).\) 根据矛盾式的定义,\(\neg(\varphi \rightarrow \neg (\varphi \rightarrow \neg\varphi))\) 是矛盾式。
例 4.12 对所有不同的命题变号 \(p\)\(q\)\(p \land \neg q\) 是或然式。
Proof: \(p\)\(q\) 为不同的命题变号。并且令 \(\sigma\) 为任意真值指派,满足 \(\sigma(p)=1\)\(\sigma(q)=0.\) 根据真理定义,\(\sigma \vDash p \land \neg q.\)\(\sigma^{\prime}\) 为任意真值指派,满足 \(\sigma^{\prime}(p)=0.\) 由于 \(\sigma^{\prime} \nvDash p\),所以根据真理定义,\(\sigma^{\prime} \nvDash p \land \neg q.\) 由或然式定义得知,\(p \land \neg q\) 是或然式。
例 4.13 对所有不同的命题变号 \(p\)\(q\)\(p \rightarrow \neg q\) 是或然式。
Proof: \(p\)\(q\) 为不同的命题变号。并且令 \(\sigma\)\(\sigma^{\prime}\) 为任意真值指派,满足 \(\sigma(p)=0\)\(\sigma^{\prime}(p)=\sigma^{\prime}(q)=1.\) 根据真理定义,易见 \(\sigma \vDash p \rightarrow \neg q\) 并且 \(\sigma^{\prime} \nvDash p \rightarrow \neg q.\) 由或然式定义得知,\(p \rightarrow \neg q\) 是或然式。

下列命题是对上述概念的简单运用。以下仅列出部分命题的证明,剩余的命题证明留作习题。

\(\varphi\)\(\varphi\) 为任意公式。我们有:

  1. \(\varphi \land \psi\) 是重言式当且仅当 \(\varphi\) 是重言式并且 \(\varphi\) 是重言式。 证明:设 \(\varphi \land \psi\) 是重言式。对每个真值指派 \(\sigma\),由假设和重言式的定义得知 \(\sigma \vDash \varphi \land \psi\),进而根据真理定义,\(\sigma \vDash \varphi.\) 所以 \(\varphi\) 是重言式。同理可证 \(\psi\) 是重言式。另一方面,设 \(\varphi\)\(\psi\) 都是重言式。对每个真值指派 \(\sigma\),由假设和重言式定义知 \(\sigma \vDash \varphi\)\(\sigma \vDash \psi\),再由真理定义知 \(\sigma \vDash \varphi \land \psi.\) 所以 \(\varphi \land \psi\) 是重言式。▗
  2. 如果 \(\varphi\)\(\psi\) 是重言式,那么 \(\varphi \lor \psi\) 是重言式;但逆命题不成立。 证明: 设 \(\varphi\)\(\psi\) 是重言式。第一种情况:\(\varphi\) 是重言式。对每个真值指派 \(\sigma\),既然 \(\varphi\) 是重言式,我们有 \(\sigma \vDash \varphi\),再由真理定义知 \(\sigma \vDash \varphi \lor \psi.\) 所以 \(\varphi \lor \psi\) 是重言式。第二种情况类似。逆命题不成立:当 \(\varphi = p\)\(\psi = \neg p\) 时,\(\varphi \lor \psi\) 是重言式,但 \(\varphi\)\(\psi\) 都不是重言式。▗
  3. 如果 \(\varphi \rightarrow \psi\) 是重言式,那么,或者 \(\varphi\) 不是重言式或者 \(\psi\) 是重言式;但逆命题不成立。 证明:设 \(\varphi \rightarrow \psi\) 是重言式。如果 \(\varphi\) 是重言式,那么,对每个真值指派 \(\sigma\)\(\sigma \vDash \varphi \rightarrow \psi\) 并且 \(\sigma \vDash \varphi\),从而由真理定义知 \(\sigma \vDash \psi\)。所以,或者 \(\varphi\) 不是重言式或者 \(\psi\) 是重言式。逆命题不成立:令 \(\varphi = p\)\(\psi = \neg p\) 。显然,\(\varphi\) 不是重言式,所以或者 \(\varphi\) 不是重言式或者 \(\psi\) 是重言式,但 \(\varphi \rightarrow \psi\) 却不是重言式。▗
  4. 如果 \(\varphi\) 是矛盾式或者 \(\psi\) 是重言式,那么 \(\varphi \rightarrow \psi\) 是重言式;但逆命题不成立。 证明:由真理定义易见,如果 \(\varphi\) 是矛盾式则 \(\varphi \rightarrow \psi\) 是重言式,并且如果 \(\psi\) 是重言式则 \(\varphi \rightarrow \psi\) 也是重言式。所以,如果 \(\varphi\) 是矛盾式或者 \(\psi\) 是重言式,那么 \(\varphi \rightarrow \psi\) 是重言式。逆命题不成立:令 \(\varphi=\psi=p.\) 显然,\(\varphi \rightarrow \psi\) 是重言式,但 \(\varphi\) 不是矛盾式, \(\psi\) 也不是重言式。▗
  5. \(\varphi \leftrightarrow \psi\) 是重言式当且仅当 \(\varphi \rightarrow \psi\)\(\psi \rightarrow \varphi\) 都是重言式。 证明:设 \(\varphi \leftrightarrow \psi\) 是重言式。对每个真值指派 \(\sigma\),如果 \(\sigma \vDash \varphi\),那么根据假设和真理定义, \(\sigma \vDash \psi.\) 所以,\(\varphi \rightarrow \psi\) 是重言式。同理可证,\(\psi \rightarrow \varphi\) 也是重言式。另一方面,设 \(\varphi \rightarrow \psi\)\(\psi \rightarrow \varphi\) 都是重言式。令 \(\sigma\) 为任意真值指派。根据假设和真理定义,如果 \(\sigma \vDash \varphi\)\(\sigma \vDash \psi\),并且如果 \(\sigma \nvDash \varphi\)\(\sigma \nvDash \psi;\) 于是有 \(\varphi^\sigma = \psi^\sigma\),再由真理定义得到 \(\varphi \leftrightarrow \psi.\) 所以,\(\varphi \leftrightarrow \psi\) 是重言式。 ▗
  6. 如果 \(\varphi \leftrightarrow \psi\) 是重言式,那么,\(\varphi\) 是重言式当且仅当 \(\psi\) 是重言式;但逆命题不成立。
  7. \(\varphi \lor \psi\) 是矛盾式当且仅当 \(\varphi\) 是矛盾式并且 \(\psi\) 都是矛盾式。
  8. 如果 \(\varphi\)\(\psi\) 是矛盾式,那么 \(\varphi \land \psi\) 是矛盾式;但逆命题不成立。
  9. \(\varphi \rightarrow \psi\) 是矛盾式当且仅当 \(\varphi\) 是重言式并且 \(\psi\) 是矛盾式。
  10. 如果 \(\varphi\)\(\psi\) 中一个是重言式另一个是矛盾式,那么 \(\varphi \leftrightarrow \psi\) 是矛盾式;但逆命题不成立。

\(\varphi, \psi\)\(\varphi_0,\cdots,\varphi_n\) 为任意公式。我们有:

  1. \(\varphi\) 是重言式当且仅当 \(\nvDash_{0} \varphi\)(即 \(\varnothing \nvDash_{0} \varphi\))。 证明:设 \(\varphi\) 是重言式。因为对所有真值指派 \(\sigma\) 都有 \(\sigma \vDash \varphi\),所以根据重言蕴涵的定义,\(\nvDash_{0} \varphi.\)\(\nvDash_{0} \varphi.\)\(\sigma\) 为任意真值指派。我们知道 \(\sigma \nvDash_{0} \varnothing\)(见定义 3.2 之解说),因而由假设 \(\varnothing \nvDash_{0} \varphi\) 和重言蕴涵定义得知 \(\sigma \vDash \varphi.\) 所以 \(\varphi\) 是重言式。▗
  2. \(\varphi \nvDash_{0} \psi\) 当且仅当 \(\varphi \rightarrow \psi\) 是重言式。 证明:由命题 可知,\(\varphi \vDash_{0} \psi\) 当且仅当 \(\vDash_{0} \varphi \rightarrow \psi\),再运用上一条结论得知,\(\varphi \vDash_{0} \psi\) 当且仅当 \(\varphi \rightarrow \psi\) 是重言式。▗
  3. \(\varphi_0,\cdots,\varphi_n \nvDash_{0} \psi\) 当且仅当 \(\nvDash_{0} \varphi_0 \rightarrow (\cdots\rightarrow(\varphi_n \rightarrow \psi)\cdots).\) 证明:施归纳于 \(n.\)\(n=0\) 时,由上条结论知本命题成立。假设当 \(n=k\) 时本条命题成立。由命题 3.1 知,\(\varphi_{0}, \cdots, \varphi_{k}, \varphi_{k+1} \vDash_{0} \psi\) 当且仅当 \(\varphi_{0}, \cdots, \varphi_{k} \vDash_{0} \varphi_{k+1} \rightarrow \psi\),再根据归纳假设,\(\varphi_{0}, \cdots, \varphi_{k} \vDash_{0} \varphi_{k+1} \rightarrow \psi\) 当且仅当 \(\vDash_{0} \varphi_{0} \rightarrow(\cdots \rightarrow(\varphi_{k} \rightarrow(\varphi_{k+1} \rightarrow \psi)) \cdots).\) 所以,\(\varphi_{0}, \cdots, \varphi_{k}, \varphi_{k+1} \vDash_{0} \psi\) 当且仅当 \(\vDash_{0} \varphi_{0} \rightarrow(\cdots \rightarrow(\varphi_{k} \rightarrow(\varphi_{k+1} \rightarrow \psi)) \cdots).\)
  4. \(\varphi \leftrightarrow \psi\) 是重言式当且仅当 \(\varphi\) 重言等值于 \(\psi.\) 证明:根据命题 3.4,\(\varphi\)\(\psi\) 重言等值当且仅当 \(\varphi \vDash_{0} \psi\) 并且 \(\psi \vDash_{0} \varphi\),再根据上述第一条,\(\varphi\)\(\psi\) 重言等值当且仅当 \(\varphi \rightarrow \psi\)\(\psi \rightarrow \varphi\) 都是重言式。最后,根据命题 3.7 第四条,\(\varphi\)\(\psi\) 重言等值当且仅当 \(\varphi \leftrightarrow \psi\) 是重言式。▗

第二条的归纳证明中,归纳假设是:

所有\(\varphi_{0}, \cdots, \varphi_{k}\)\(\psi\)\(\varphi_{0}, \cdots, \varphi_{k} \vDash_{0} \psi\) 当且仅当 \(\vDash_{0} \varphi_{0} \rightarrow(\cdots \rightarrow(\varphi_{k} \rightarrow \psi) \cdots).\)

其中「对所有的…」来自命题 3.8 的题设「令… 为任意公式」。既然归纳假设中的 \(\psi\) 可以是任意公式(如果愿意,可以把上述 \(\psi\) 都改写成 \(\chi\)),所以也可以是 \(\varphi_{k+1} \rightarrow \psi\) 这样的公式。于是我们由归纳假设得到 \(\varphi_{0}, \cdots, \varphi_{k} \vDash_{0} \varphi_{k+1} \rightarrow \psi\) 当且仅当 \(\vDash_{0} \varphi_{0} \rightarrow(\cdots \rightarrow(\varphi_{k} \rightarrow(\varphi_{k+1} \rightarrow \psi)) \cdots).\)

基本语义概念的简单应用就讲这些,希望读者完成本章后面的证明练习。做证明可帮助读者准确地理解和掌握上述基本语义概念,更可以帮助培养准确表达思想和仔细推敲论据的习惯。

4.3 代入

代入(substitution)是对公式做变形处理的一种方式。在本书的命题逻辑范围内,「代入」总是指对命题变号的代入。

4.3.1 关于代入的直观说明

\(\varphi\)\(\psi\) 为任意公式,\(p\) 为任意命题变项。所谓用 \(\psi\) 代入 \(\varphi\) 中的 \(p\),是指用 \(\psi\) 替换 \(p\)\(\varphi\) 中的每一处出现,其结果记为 \(\varphi(\psi/p).\)

例 3.12 令 $=q* r, =p r $ 且 \(\varphi_{2}=p \rightarrow \neg p \vee q.\) 则有: 1. \(\varphi_{0}(q / p)=q \rightarrow r\) 1. \(\varphi_{1}(q / p)=q \vee r\) 1. \(\varphi_{2}(q / p)=q \rightarrow \neg q \vee q\) 1. \(\varphi_{2}(\neg p / p)=\neg p \rightarrow \neg \neg p \vee q\) 1. \(\varphi_{2}(p \vee q / p)=p \vee q \rightarrow \neg(p \vee q) \vee q\)

如果我们同时用 \(\psi_0,\cdots,\psi_n\) 分别代入 \(\varphi\) 中的 \(p_0,\cdots,p_n\),其结果就记为 \(\varphi(\psi_0/p_0,\cdots,\psi_n/p_n).\)

例 3.13\(\varphi\)\(p \rightarrow \neg p \land q.\) 则有: 1. \(\varphi(q / p, p / q)=q \rightarrow \neg q \wedge p\) 1. \(\varphi(p \wedge q / p, p / q)=p \wedge q \rightarrow \neg(p \wedge q) \wedge p\) 1. \(\varphi(p \wedge q / p)(p / q)=(p \wedge q \rightarrow \neg(p \wedge q) \wedge q)(p / q)=p \wedge p \rightarrow \neg(p \wedge p) \wedge p\)

注意例 3.13 公式二和公式一的差别。公式二是\(p \wedge q\) 代入 \(\varphi\) 中的 \(p\) 而得到 \(\varphi(p \wedge q / p)\),再用 \(p\) 代入 \(\varphi(p \wedge q / p)\) 中的 \(q\) 而得到的;而公式一是用 \(p \wedge q\) 代入 \(\varphi\) 中的 \(p\)同时\(p\) 代入 \(\varphi\) 中的 \(q\)(不是 \(\varphi(p \wedge q / p)\) 中的 \(q\))而得到的。可见,同时代入的结果和先后代入的结果是不同的。

4.3.2 代入的定义

如果我们只考虑具体的代入操作,那么关于代入的上述说明差不多已经够了,但这个说明显然不够严格。我们约定:在无特别说明时,我们用不同的符号表示不同的命题变号。代入的严格定义如下:

{{% dtpc title=“☯定义 3.9【代入】” %}} 是从命题变号集到公式集的函数。我们用 \(\mathfrak{s}, \mathfrak{s}^{\prime}\) 等表示代入。设 \(\mathfrak{s}\) 是一个代入。对所有公式 \(\chi\),公式 \(\chi(\mathfrak{s})\)(「对 \(\chi\) 做代入 \(\mathfrak{s}\) 的结果」)递归地定义如下: > 1. 所有命题变号 \(p\)\(p(\mathfrak{s})=\mathfrak{s}(p);\) > 1. 对所有公式 \(\varphi\)\((\neg \varphi)(\mathfrak{s})=\neg(\varphi(\mathfrak{s}));\) > 1. 对所有公式 \(\varphi\)\(\psi\)\((\varphi \odot \psi)(\mathfrak{s})=\varphi(\mathfrak{s}) \odot \psi(\mathfrak{s})\),其中 \(\odot \in\lbrace \wedge, \vee, \rightarrow, \leftrightarrow\rbrace.\) {{% /dtpc %}}

为简化敍述,定义 3.9 引入「\(\color{red}\odot\)」符号。它指的是:对所有公式 \(\varphi\)\(\psi\)\((\varphi \wedge \psi)(\mathfrak{s})=\varphi(\mathfrak{s}) \wedge \psi(\mathfrak{s})\)\((\varphi \vee \psi)(\mathfrak{s})= \varphi(\mathfrak{s}) \vee \psi(\mathfrak{s})\)\((\varphi \rightarrow \psi)(\mathfrak{s})=\varphi(\mathfrak{s}) \rightarrow \psi(\mathfrak{s})\) 并且 \((\varphi \leftrightarrow \psi)(\mathfrak{s})=\varphi(\mathfrak{s}) \leftrightarrow \psi(\mathfrak{s}).\)

{{% dtpc title=“☯定义 3.10【有穷代入】” %}} 设代入 \(\mathfrak{s}\) 满足 \(\mathfrak{s}(q_{0})=\psi_{0}, \cdots, \mathfrak{s}(q_{n})=\psi_{n}\),并且 \(\mathfrak{s}(r)=r\) 对所有不是 \(q_{0}, \cdots, q_{n}\) 的命题变号 \(r\) 都成立。我们用 \(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n}\) 表示这个 \(\mathfrak{s}\),用 \(\varphi(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n})\) 来表示 \(\varphi(\mathfrak{s})\),并且称 \(\mathfrak{s}\)有穷代入。 {{% /dtpc %}}

如果换个方式来讲定义 3.9 的内容,那就是:每个代入 \(\mathfrak{s}\) 都可以唯一地扩充为一个满足下列(对应于定义 3.9 中)条件的公式集上的函数 \(\mathfrak{s}^{+}\)

  1. 所有命题变号 \(p\)\(\mathfrak{s}^{+}(p)=\mathfrak{s}(p);\)
  2. 对所有公式 \(\varphi\)\(\mathfrak{s}^{+}(\neg \varphi)=\neg\mathfrak{s}^{+}(\varphi);\)
  3. 对所有公式 \(\varphi\)\(\psi\)\(\mathfrak{s}^{+}(\varphi \odot \psi)=\mathfrak{s}^{+}(\varphi) \odot \mathfrak{s}^{+}(\psi)\)\(\odot \in\lbrace \wedge, \vee, \rightarrow, \leftrightarrow\rbrace.\)

我们之所以采用「\(\varphi(\mathfrak{s})\)」式的记法而非「\(\mathfrak{s}^{+}(\varphi)\)」式的记法,是因为前者通过定义 3.10 可以和代入的直观说明在记法上保持一致。

为了帮助读者理解定义 3.9-3.10,我们在下面两个例子中(大体上)一步步地计算代入结果。注意:我们将尽量省略括号。\(\theta \vee \lambda / p, \theta \wedge \neg \lambda / q\) 等就是 \((\theta \vee \lambda) / p,(\theta \wedge \neg \lambda) / q\) 等。

例 3.14\(\varphi_{0}=q \rightarrow r, \varphi_{1}=p \vee r\),且 \(\varphi_{2}=p \rightarrow \neg p \vee q;\) 并令 \(\mathfrak{s}_{0}\)\(q / p\)\(\mathfrak{s}_{1}\)\(p / p\)\(\mathfrak{s}_{2}\)\(p \vee q / p.\) 我们有:

\[\begin{align*} \checkmark \varphi_{0}\left(\mathfrak{s}_{0}\right) &=(q \rightarrow r)\left(\mathfrak{s}_{0}\right)=q\left(\mathfrak{s}_{0}\right) \rightarrow r\left(\mathfrak{s}_{0}\right)=q(q / p) \rightarrow r(q / p)=q \rightarrow r \\ \checkmark \varphi_{1}\left(\mathfrak{s}_{0}\right) &=(p \vee r)\left(\mathfrak{s}_{0}\right)=p\left(\mathfrak{s}_{0}\right) \vee r\left(\mathfrak{s}_{0}\right)=p(q / p) \vee r(q / p)=q \vee r \\ \checkmark \varphi_{2}\left(\mathfrak{s}_{0}\right) &=(p \rightarrow \neg p \vee q)\left(\mathfrak{s}_{0}\right)=p\left(\mathfrak{s}_{0}\right) \rightarrow(\neg p \vee q)\left(\mathfrak{s}_{0}\right) \\ &=p\left(\mathfrak{s}_{0}\right) \rightarrow(\neg p)\left(\mathfrak{s}_{0}\right) \vee q\left(\mathfrak{s}_{0}\right)=p\left(\mathfrak{s}_{0}\right) \rightarrow \neg p\left(\mathfrak{s}_{0}\right) \vee q\left(\mathfrak{s}_{0}\right) \\ &=p(q / p) \rightarrow \neg p(q / p) \vee q(q / p)=q \rightarrow \neg q \vee q \\ \checkmark \varphi_{2}\left(\mathfrak{s}_{1}\right) &=(p \rightarrow \neg p \vee q)\left(\mathfrak{s}_{1}\right)=p\left(\mathfrak{s}_{1}\right) \rightarrow \neg p\left(\mathfrak{s}_{1}\right) \vee q\left(\mathfrak{s}_{1}\right) \\ &=p(\neg p / p) \rightarrow \neg p(\neg p / p) \vee q(\neg p / p)=\neg p \rightarrow \neg \neg p \vee q \\ \checkmark \varphi_{2}\left(\mathfrak{s}_{2}\right) &=(p \rightarrow \neg p \vee q)\left(\mathfrak{s}_{2}\right)=p\left(\mathfrak{s}_{2}\right) \rightarrow \neg p\left(\mathfrak{s}_{2}\right) \vee q\left(\mathfrak{s}_{2}\right) \\ &=p(p \vee q / p) \rightarrow \neg p(p \vee q / p) \vee q(p \vee q / p)\\ &=p \vee q \rightarrow \neg (p \vee q) \vee q \end{align*}\]

根据定义 3.9,例 3.14 得到的 $(), (), (), () $ 和 \(\varphi_{2}(\mathfrak{s}_{2})\),与例 3.12 根据代入的直观说明得到的 \(\varphi_{0}(q / p), \varphi_{1}(q / p), \varphi_{2}(q / p), \varphi_{2}(\neg p / p)\)\(\varphi_{2}(p \vee q / p)\),是完全相同的。

例 3.15\(\varphi\)\(p \rightarrow \neg p \wedge q\),并令 \(\mathfrak{s}_{3}\)\(q/p, p/q\)

\(\mathfrak{s}_{4}\)\(p \wedge q/ p, p/q\)

\(\mathfrak{s}_{5}\)\(p \wedge q/p\)

\(\mathfrak{s}_{6}\)\(p/q.\) 我们有:

\[\begin{align*} \checkmark \varphi(\mathfrak{s}_{3}) &=(p \rightarrow \neg p \wedge q)(\mathfrak{s}_{3})=p(\mathfrak{s}_{3}) \rightarrow(\neg p \wedge q)(\mathfrak{s}_{3}) \\ &=p(\mathfrak{s}_{3}) \rightarrow \neg p(\mathfrak{s}_{3}) \wedge q(\mathfrak{s}_{3}) \\ &=p(q / p, p / q) \rightarrow \neg p(q / p, p / q) \wedge q(q / p, p / q) \\ &=q \rightarrow \neg q \wedge p \\ \checkmark \varphi(\mathfrak{s}_{4}) &=(p \rightarrow \neg p \wedge q)(\mathfrak{s}_{4})=p(\mathfrak{s}_{4}) \rightarrow \neg p(\mathfrak{s}_{4}) \wedge q(\mathfrak{s}_{4}) \\ &=p(p \wedge q / p, p / q) \rightarrow \neg p(p \wedge q / p, p / q) \wedge q(p \wedge q / p, p / q) \\ &=p \wedge q \rightarrow \neg(p \wedge q) \wedge p\\ \checkmark \varphi(\mathfrak{s}_{5})(\mathfrak{s}_{6}) &=(p \rightarrow \neg p \wedge q)(\mathfrak{s}_{5})(\mathfrak{s}_{6})=\left[p(\mathfrak{s}_{5}) \rightarrow \neg p(\mathfrak{s}_{5}) \wedge q(\mathfrak{s}_{5})\right](\mathfrak{s}_{6}) \\ &=[p(p \wedge q / p) \rightarrow \neg p(p \wedge q / p) \wedge q(p \wedge q / p)](\mathfrak{s}_{6}) \\ &=(p \wedge q \rightarrow \neg(p \wedge q) \wedge q)(\mathfrak{s}_{6}) \\ &=(p \wedge q)(\mathfrak{s}_{6}) \rightarrow(\neg(p \wedge q) \wedge q)(\mathfrak{s}_{6}) \\ &=p(\mathfrak{s}_{6}) \wedge q(\mathfrak{s}_{6}) \rightarrow \neg(p(\mathfrak{s}_{6}) \wedge q(\mathfrak{s}_{6})) \wedge q(\mathfrak{s}_{6}) \\ &=p(p / q) \wedge q(p / q) \rightarrow \neg(p(p / q) \wedge q(p / q)) \wedge q(p / q) \\ &=p \wedge p \rightarrow \neg(p \wedge p) \wedge p \end{align*}\]

注意:对所有公式 \(\varphi\),以及所有代入 \(\mathfrak{s}\)\(\mathfrak{s}^{\prime}\),因为 \(\varphi(\mathrm{s})\) 是对 \(\varphi\) 做代入 \(\mathfrak{s}\) 的结果,所以 \(\varphi(\mathfrak{s})(\mathfrak{s}^{\prime})\) 就是 \((\varphi(\mathfrak{s}))(\mathfrak{s}^{\prime}).\) 这可推广至更一般的情况。

易见,根据定义 3.9,例 3.15 得到的部分结果,与根据代入的直观说明在例 3.13 中得到的 \(\varphi(q / p, p / q), \varphi(p \wedge q / p, p / q)\)\(\varphi(p \wedge q / p)(p / q)\),是完全相同的。

如果 \(q\) 不在 \(\varphi\) 中出现,那么对任何代入 \(\mathfrak{s}\),无论 \(\mathfrak{s}(q)\) 是什么公式,似乎都应与 \(\varphi(\mathfrak{s})\) 无关。一般地,下述说法也似乎应该是对的:

对一个公式 \(\varphi\) 做代入 \(\mathfrak{s}\),其结 \(\varphi(\mathfrak{s})\) 应只与 \(\mathfrak{s}\) 指派给 \(\varphi\) 中出现的命题变号的值有关,或者说,与 \(\mathfrak{s}\) 指派给其他命题变号的值无关。

命题 3.9 正是对这种直观说法的一个准确表述。

{{% dtpc title=“☯命题 3.9” %}} 令 \(\varphi\) 为任意公式,并令 \(\mathfrak{s}\)\(\mathfrak{s}^{\prime}\) 为任意代入。设 \(\varphi\) 中出现的命题变号是在 \(q_{0}, \cdots, q_{n}\) 之中,并且 \(\mathfrak{s}(q_{0})=\mathfrak{s}^{\prime}(q_{0}), \cdots, \mathfrak{s}(q_{n})=\mathfrak{s}^{\prime}(q_{n}).\) 我们 有:\(\varphi(\mathfrak{s})=\varphi(\mathfrak{s}^{\prime}).\) {{% /dtpc %}}

命题 3.9 之证明: 施归纳于公式的复杂度,我们证明:对每个只含命题变号 \(q_{0}, \cdots, q_{n}\)的公式\(\varphi\)\(\varphi(\mathfrak{s})=\varphi(\mathfrak{s}^{\prime}).\) 归纳基始:\(\varphi=q_{i}(i \leqslant n).\) 由题设知 \(\mathfrak{s}(q_{i})=\mathfrak{s}^{\prime}(q_{i})\),即 \(\varphi(\mathfrak{s})=\varphi(\mathfrak{s}^{\prime}).\) 归纳步骤:设 \(\varphi=\neg \psi.\) 根据归纳假设,\(\psi(\mathfrak{s})=\psi(\mathfrak{s}^{\prime})\),再由定义 3.9 得到 \((\neg \psi)(\mathfrak{s})=\neg(\psi(\mathfrak{s}))=\neg(\psi(\mathfrak{s}^{\prime}))=(\neg \psi)(\mathfrak{s}^{\prime}).\)\(\varphi=\psi \odot \chi\),其中 \(\odot \in\lbrace \vee, \wedge, \rightarrow, \leftrightarrow\rbrace.\) 由归纳假设,\(\psi(\mathfrak{s})=\psi(\mathfrak{s}^{\prime})\)\(\chi(\mathfrak{s})=\chi(\mathfrak{s}^{\prime})\),因而有 \(\psi(\mathfrak{s}) \odot \chi(\mathfrak{s})=\psi(\mathfrak{s}^{\prime}) \odot \chi(\mathfrak{s}^{\prime})\),再由定义 3.9 得到 \((\psi \odot \chi)(\mathfrak{s})=(\psi \odot \chi)(\mathfrak{s}^{\prime}).\)(命题 3.9 是如何把「有关」和「无关」这种模糊说法改进为准确的说法的?注意这类问题一定有好处。)▗

上述证明中用到了基于公式复杂度的归纳证明方法。

要想说明上面那个直观想法的正确性,前提是对「有关」「无关」等做出清楚而准确的刻画。很多学生善于联想和发挥,却不善于清楚和准确。清楚和准确往往不易做到,有时甚至不必要。但如果想把能讲好的道理讲好,首先要有把想法讲清楚讲准确的本领。倘若一个理论中的每个命题都「本身就是说不清的」,那它也就没什么道理好讲。当然,清楚和准确只是做好理论工作的必要条件,不是充分条件。

4.3.3 代入的复合

{{% dtpc title=“☯定义 3.11【代入的复合】” %}} 设 \(\mathfrak{s}^{\prime}\)\(\mathfrak{s}^{\prime\prime}\) 为任意代入,我们用 \(\mathfrak{s}^{\prime}\mathfrak{s}^{\prime\prime}\) 来表示它们的复合,即满足下列条件的代入 \(\mathfrak{s}\): 1. 对任意命题变号 \(p\)\(\mathfrak{s}(p)=p(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime})\),即 \(\mathfrak{s}(p)=(\mathfrak{s}^{\prime}(p))(\mathfrak{s}^{\prime \prime}).\) 1. 并且我们用 \(\varphi(\mathfrak{s}^{\prime}\mathfrak{s}^{\prime\prime})\) 来表示 \(\varphi(\mathfrak{s}).\) {{% /dtpc %}}

这里的名称和记法(稍有改动)来自 Chagrov, Zakharyaschev[1997]。虽然 \(\mathfrak{s}^{\prime}\)\(\mathfrak{s}^{\prime\prime}\) 都是函数,而且我们也用「代入的复合」来称呼 \(\mathfrak{s}^{\prime}\mathfrak{s}^{\prime\prime}\),但 \(\mathfrak{s}^{\prime}\mathfrak{s}^{\prime\prime}\) 与通常数学中讨论的关系或函数的复合(composition)有所不同。\(\mathfrak{s}^{\prime}\mathfrak{s}^{\prime\prime}\) 既不是通常数学中的 \(\mathfrak{s}^{\prime}\circ \mathfrak{s}^{\prime\prime}\) 也不是 \(\mathfrak{s}^{\prime\prime}\circ \mathfrak{s}^{\prime}.\) 这是因为:\(\mathfrak{s}^{\prime}\)\(\mathfrak{s}^{\prime\prime}\) 的定义域都是命题变号集且其值域都是比命题变号集更大的公式集,而在数学中,要使 \(\mathfrak{s}^{\prime} \circ \mathfrak{s}^{\prime\prime}\)\(\mathfrak{s}^{\prime\prime} \circ \mathfrak{s}^{\prime}\) 成为函数的复合,\(\mathfrak{s}^{\prime}\)\(\mathfrak{s}^{\prime\prime}\) 的值域须是对方定义域的子集。

易见,如果 \(\mathfrak{s}^{\prime}\)\(\mathfrak{s}^{\prime\prime}\) 都是有穷代入,那么 \(\mathfrak{s}^{\prime}\mathfrak{s}^{\prime\prime}\) 也是有穷代入(见习题 3.10)。

根据各种各样的例子,人们自然地会猜想:

如果对一个公式 \(\varphi\) 做代入得到 \(\psi\),再对 \(\psi\) 做代入得到 \(\chi\),那么对 \(\varphi\) 做一次代入就可以得到 \(\chi\),而这个代入正是前两个代入的复合。

这个猜想的确是真的。

{{% dtpc title=“☯命题 3.10” %}} 对任意代入 \(\mathfrak{s}^{\prime}\)\(\mathfrak{s}^{\prime \prime}\),对任意公式 \(\varphi\)\(\varphi\left(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime}\right)=\varphi\left(\mathfrak{s}^{\prime}\right)\left(\mathfrak{s}^{\prime \prime}\right).\)

证明:施归纳于公式 \(\varphi\) 的复杂度。 归纳基始:设 \(\varphi\) 是命题变项 \(p.\) 根据定义 3.9 和定义 3.11, \(\varphi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=p(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})(p)=p(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime})=\varphi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime}).\) 归纳步聚 1:设 \(\varphi\)\(\neg \psi.\) 根据定义 3.9,\((\neg \psi)(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=\neg(\psi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime}))\)。由归纳假设知,\(\psi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=\psi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime})\),进而 \(\neg(\psi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime}))=\neg(\psi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime}))\),再由定义 3.9 得到 \(\neg(\psi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime}))=(\neg(\psi(\mathfrak{s}^{\prime}))(\mathfrak{s}^{\prime \prime}))=(\neg \psi)(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime}).\) 所以,\((\neg \psi)(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})= (\neg \psi)(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime}).\) 归纳步骤 2-5: 设 \(\varphi\)\(\psi \odot \chi\), 其中 \(\odot \in\lbrace \vee, \wedge, \rightarrow, \leftrightarrow\rbrace.\) 按定义 3.9,\((\psi \odot \chi)(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=\psi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime}) \odot \chi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime}).\) 根据归纳假设,\(\psi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=\psi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime})\) 并且 \(\chi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=\chi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime})\),从而 \(\psi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime}) \odot \chi(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=\psi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime}) \odot \chi(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime})\),再由定义 3.9 得到

\[\begin{align} \psi\left(\mathfrak{s}^{\prime}\right)\left(\mathfrak{s}^{\prime \prime}\right) \odot \chi\left(\mathfrak{s}^{\prime}\right)\left(\mathfrak{s}^{\prime \prime}\right) &= \left(\psi\left(\mathfrak{s}^{\prime}\right) \odot \chi\left(\mathfrak{s}^{\prime}\right)\right)\left(\mathfrak{s}^{\prime \prime}\right)\\ &= (\psi \odot \chi)\left(\mathfrak{s}^{\prime}\right)\left(\mathfrak{s}^{\prime \prime}\right) \end{align}\]

所以,\((\psi \odot \chi)(\mathfrak{s}^{\prime} \mathfrak{s}^{\prime \prime})=(\psi \odot \chi)(\mathfrak{s}^{\prime})(\mathfrak{s}^{\prime \prime}).\) ▗ {{% /dtpc %}}

读过「关于代入的直观说明」(§3.2.0(P.107)),一般人就明白如何做代入,即「会做」了。为什么还要谈代入的严格定义甚至代入的复合呢?千万不要因为这些是「末节」或「小技」就不屑一顾。正是这种「末节」和「小技」的积累,使人们能超越「会做」而进入对深层问题的讨论。试想:假如对代入的理解仅停留在「会做」的水平,那么我们如何证明「多次代入的结果都可通过一次代入得到」这个猜想呢?现在用「末节」和「小技」得到的这个结论,以后可以用于解决更深更难的问题。

4.3.4 代入的语义性质

这里我们讨论公式的不同代入结果在真值指派下的值,比如说,\(\varphi(\psi / p)\)\(\varphi(\chi/p)\)\(\sigma\) 下的值。不难猜测:如果 \(\psi^{\sigma}=p^{\sigma}\)\(\varphi^{\sigma}=(\varphi(\psi / p))^{\sigma}\),亦即在 \(\sigma\) 下,如果 \(\psi\)\(p\) 的值相同,那么无论对 \(\varphi\) 是否做代入\(\psi / p\), 其结果的值应该是一样的。一般地,公式 \(\varphi(\psi / p)\)\(\sigma\) 下的值与 \(\psi\)\(\sigma\) 下的值有关,但与 \(\psi\) 具体是哪个公式无关,也就是说,只要 \(\psi\)\(\chi\)\(\sigma\) 下的值相同, 那么无论是对 \(\varphi\) 做代入 \(\psi / p\) 还是做代入 \(\chi / p\),其结果在 \(\sigma\) 下的值都是一样的 (见推论 3.2)。下面几个命题说的正是这类事,不过比这更一般。

{{% dtpc title=“☯定理 3.0” %}} 设 \(\varphi\) 为任意公式,其中出现的命题变号只有 \(q_{0}, \cdots, q_{n}\),并设 \(\sigma\)\(\sigma^{\prime}\) 为任意真值指派,满足 \(\psi_{0}^{\sigma}=\chi_{0}^{\sigma^{\prime}}, \cdots, \psi_{n}^{\sigma}=\chi_{n}^{\sigma^{\prime}}.\) 我们有:\(\sigma \vDash \varphi(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n})\) 当且仅当 \(\sigma^{\prime} \vDash \varphi(\chi_{0} / q_{0}, \cdots, \chi_{n} / q_{n}).\) {{% /dtpc %}}

证明:\(\mathfrak{s}\)\(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n}\)\(\mathfrak{s}^{\prime}\)\(\chi_{0} / q_{0}, \cdots, \chi_{n} / q_{n}.\) 施归纳于公式的复杂度。 归纳基始\(\varphi=q_{i}(i \leqslant n).\) 显然有 \(\varphi(\mathfrak{s})=\psi_{i}\) 且 $(^{})=_{i} $,而根据题设 \(\psi_{i}^{\sigma}=\chi_{i}^{\sigma^{\prime}}\),我们有 \(\sigma \vDash \psi_{i}\) 当且仅当 \(\sigma^{\prime} \vDash \chi_{i}.\) 归纳步骤:设 \(\varphi=\neg \theta_{\circ}\) 根据归纳假设,\(\sigma \vDash \theta(\mathrm{s})\) 当且仅当 \(\sigma^{\prime} \vDash \theta(\mathrm{s}^{\prime})\),因而根据真理定义,\(\sigma \vDash \neg \theta(\mathfrak{s})\) 当且仅当 \(\sigma^{\prime} \vDash \neg \theta(\mathfrak{s}^{\prime})\),再由定义 3.9 知,\(\sigma \vDash(\neg \theta)(\mathfrak{s})\) 当且仅当 \(\sigma^{\prime} \vDash(\neg \theta)(\mathfrak{s}^{\prime}).\)\(\varphi=\theta \odot \lambda\),其中 \(\odot \in\lbrace \vee, \wedge, \rightarrow, \leftrightarrow\rbrace.\) 由归纳假设,\(\sigma \vDash \theta(\mathfrak{s})\) 当且仅当 \(\sigma^{\prime} \vDash \theta(\mathfrak{s}^{\prime})\),并且$ ()$ 当且仅当 \(\sigma^{\prime} \vDash \lambda(\mathfrak{s}^{\prime});\) 所以根据真理定义,\(\sigma \vDash \theta(\mathfrak{s}) \odot \lambda(\mathfrak{s})\) 当且仅当 \(\sigma^{\prime} \vDash \theta(\mathfrak{s}^{\prime}) \odot \lambda(\mathfrak{s}^{\prime})\),再由定义 3.9 知,\(\sigma \vDash(\theta \odot \lambda)(\mathfrak{s})\) 当且仅当 \(\sigma^{\prime} \vDash(\theta \odot \lambda)(\mathfrak{s}^{\prime}).\)

{{% dtpc title=“☯定理 3.1” %}} 令 \(\varphi\) 为任意公式,其中出现的命题变号都在 \(q_{0}, \cdots, q_{n}\) 之中。设 \(\sigma\)\(\sigma^{\prime}\) 为任意真值指派,满足 \(\sigma^{\prime}\left(q_{0}\right) = \psi_{0}^{\sigma}, \cdots, \sigma^{\prime}\left(q_{n}\right) = \psi_{n}^{\sigma}.\) 我们有:对任意代入 \(\mathfrak{s}\),如果 \(\mathfrak{s}\left(q_{0}\right) = \psi_{0}, \cdots, \mathfrak{s}\left(q_{n}\right) = \psi_{n}\),那么 \(\sigma \vDash \varphi(\mathfrak{s})\) 当且仅当 \(\sigma^{\prime} \vDash \varphi.\) {{% /dtpc %}}

证明:\(\mathfrak{s}\) 为任意代入,满足 \(\mathfrak{s}\left(q_{0}\right) = \psi_{0}, \cdots, \mathfrak{s}\left(q_{n}\right) = \psi_{n};\) 并令 \(\mathfrak{s}^{*}\) 为代入 \(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n}.\) 根据定理 3.0,\(\sigma \vDash \varphi\left(\mathfrak{s}^{*}\right)\) 当且仅当 \(\sigma^{\prime} \vDash \varphi\),再由命题 3.9 得知 \(\varphi(\mathfrak{s}) = \varphi\left(\mathfrak{s}^{*}\right).\) 所以,$() $ 当且仅当 \(\sigma^{\prime} \vDash \varphi.\)

定理 3.1 的一个推论是:对每个公式 \(\varphi\) 和每个代入 \(\mathfrak{s}\),如果 \(\varphi\) 是重言式,那么 \(\varphi(\mathfrak{s})\) 一定也是重言式。(见习题 3.17)

注意:定理 3.0 和定理 3.1 都要求 \(\varphi\) 中岀现的命题变号在 \(q_{0}, \cdots, q_{n}\) 之中,但下面的推论 3.2 并不这样要求。之所以推论 3.2 允许 \(\varphi\) 中出现不同于 \(q_{0}, \cdots, q_{n}\) 的命题变号,是因为它涉及的真值指派只有一个。

{{% dtpc title=“☯推论 3.2” %}} 设 \(\sigma\) 为任意真值指派,且对每个 \(i=0, \cdots, n\) 都有 \(\psi_{i}^{\sigma}=\chi_{i}^{\sigma}.\) 我们有:对所有公式 \(\varphi\) 和所有命题变号 \(q_{0}, \cdots, q_{n}, \sigma \vDash \varphi(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n})\) 当且仅当 \(\sigma \vDash \varphi(\chi_{0} / q_{0}, \cdots, \chi_{n} / q_{n}).\) {{% /dtpc %}}

证明:\(\varphi\) 为任意公式,\(q_{0}, \cdots, q_{n}\) 为任意命题变号,并设 $r_{1}, , r_{m}(m ) $ 为 \(\varphi\) 中出现的所有与 \(q_{0}, \cdots, q_{n}\) 不同的命题变号。根据题设和定理 3.0

\[ \begin{array}{rl} & \sigma \vDash \varphi(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n}, r_{1} / r_{1}, \cdots, r_{m} / r_{m}) \\ \text{iff} & \sigma \vDash \varphi(\chi_{0} / q_{0}, \cdots, \chi_{n} / q_{n}, r_{1} / r_{1}, \cdots, r_{m} / r_{m}) \end{array} \]

同时易见 \(\varphi(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n}, r_{1} / r_{1}, \cdots, r_{m} / r_{m})\) 就是 \(\varphi(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n})\) 而 $( / q{0}, , / q{n}, r_{1} / r_{1}, , r_{m} / r_{m}) $ 就是 \(\varphi(\chi_{0} / q_{0}, \cdots, \chi_{n} / q_{n}).\) 所以 \(\sigma \vDash \varphi(\psi_{0} / q_{0}, \cdots, \psi_{n} / q_{n})\) 当且仅当 \(\sigma \vDash \varphi(\chi_{0} / q_{0}, \cdots, \chi_{n} / q_{n}).\)

最后,我们来看关于「置换」的语义定理。

{{% dtpc title=“☯推论 3.3” %}} 设 \(\Gamma \vDash_{0} \psi \leftrightarrow \chi.\) 我们有:对每个公式 \(\varphi\) 和每个命题变号 \(p\)\(\Gamma \vDash_{0} \varphi(\psi / p) \leftrightarrow \varphi(\chi / p).\) {{% /dtpc %}}

证明:\(\varphi\) 为任意公式,\(p\) 为任意命题变号。令 \(\sigma\) 为任意真值指派,满足 \(\sigma \vDash \Gamma.\) 由题设和重言蕴涵的定义知 \(\sigma \vDash \psi \leftrightarrow \chi.\) 从而有 \(\psi^{\sigma}=\chi^{\sigma}.\) 根据推论 3.2,\(\sigma \vDash \varphi(\psi / p)\) 当且仅当 \(\sigma \vDash \varphi(\chi / p)\),进而 \(\sigma \vDash \varphi(\psi / p) \leftrightarrow \varphi(\chi / p).\) 由此 可知,\(\Gamma \vDash_{0} \varphi(\psi / p) \leftrightarrow \varphi(\chi / p).\)

\(\chi\) 置换 \(\varphi\) 中的 \(\psi\),是指用 \(\chi\) 替换 \(\psi\)\(\varphi\) 中的有穷多个出现,而这样得到的所有公式都称为 \(\varphi\)\(\chi/\psi\)-置换结果(简称置换结果)。推论 3.3 有时以下述形式出现,容易证明两者是等价的(见习题 3.16):

{{% dtpc title=“☯推论 3.4” %}} 设 \(\Gamma \vDash_{0} \psi \leftrightarrow \chi.\) 我们有:对 \(\varphi\) 的每个 \(\chi / \psi\)-置换结果 \(\varphi^{\prime}, \Gamma \vDash_{0} \varphi \leftrightarrow \varphi^{\prime}.\) {{% /dtpc %}}

\(\Gamma=\varnothing\) 时,上述推论成为:

{{% dtpc title=“☯推论 3.5” %}} 如果 \(\psi\)\(\chi\) 重言等值,那么 \(\varphi\) 与它的所有 \(\chi / \psi\)-置换结果都重言等值。 {{% /dtpc %}}

推论 3.5 常被称为等值置换的语义版本 (或形式)。我们来看一个例子:

\(\varphi=\neg p \vee \neg q \rightarrow r \wedge(\neg p \vee \neg q), \psi=\neg p \vee \neg q\) 并且 \(\chi=\neg(p \wedge q).\)\(\chi\) 置换 \(\varphi\)\(\psi\) 的结果可以是下面的任何一个:

\[\begin{align} \varphi_{0}^{\prime}&=\neg(p \wedge q) \rightarrow r \wedge(\neg p \vee \neg q) \nonumber \\ \varphi_{1}^{\prime}&=\neg p \vee \neg q \rightarrow r \wedge \neg(p \wedge q) \label{eq:dairu-tuilun-3.5}\\ \varphi_{2}^{\prime}&=\neg(p \wedge q) \rightarrow r \wedge \neg(p \wedge q) \nonumber \end{align}\]

\(\chi\)\(\psi\) 重言等值 (见习题 3.5), 所以根据推论 3.5,\(\varphi_{0}^{\prime}, \varphi_{1}^{\prime}\)\(\varphi_{2}^{\prime}\) 都与 \(\varphi\) 重言等值。

代入和置换有很大不同:从上面的例子可以看出,

  1. 对一个公式做代入,替换的只能是它的原子子公式(命题变号);而对一个公式做置换,替换的可以是它的任何子公式。
  2. 对一个公式做代入时,如果替换其中的某命题变号,则必须替换这一命题变号在该公式中的所有出现;但在对一公式做置换时,可以只替换该子公式的某些出现,而不替换它的另一些出现。

代入和置换又有紧密的联系。比如,我们说过推论 3.4 等价于推论 3.3,那就是说,一个使用「置换」来表达的命题(如推论 3.4),等价于一个使用「代入」而不使用「置换」来表达的命题(如推论 3.3)。我们再用上面的例子加以说明:

仍令 \(\varphi=\neg p \vee \neg q \rightarrow r \wedge(\neg p \vee \neg q), \psi=\neg p \vee \neg q\) 并且 \(\chi=\neg(p \wedge q).\)\(p^{*}\) 为任意一个与 \(p, q, r\) 都不同的命题变号,并且令

\[\begin{align*} \varphi_{0}&=p^{*} \rightarrow r \wedge(\neg p \vee \neg q) \\ \varphi_{1}&=\neg p \vee \neg q \rightarrow r \wedge p^{*} \\ \varphi_{2}&=p^{*} \rightarrow r \wedge p^{*} \end{align*}\]

易见下列等式成立,其中 \(\varphi_{0}^{\prime}, \varphi_{1}^{\prime}\)\(\varphi_{2}^{\prime}\) 来自式 ()

\[\begin{align} \varphi_{0}(\psi / p^{*})=\varphi_{1}(\psi / p^{*})=\varphi_{2}(\psi / p^{*})=\varphi \nonumber\\ \varphi_{0}(\chi / p^{*})=\neg(p \wedge q) \rightarrow r \wedge(\neg p \vee \neg q)=\varphi_{0}^{\prime} \nonumber \\ \varphi_{1}(\chi / p^{*})=\neg p \vee \neg q \rightarrow r \wedge \neg(p \wedge q)=\varphi_{1}^{\prime} \label{eq:dairu-tuilun-3.7}\\ \varphi_{2}(\chi / p^{*})=\neg(p \wedge q) \rightarrow r \wedge \neg(p \wedge q)=\varphi_{2}^{\prime} \nonumber \end{align}\]

因为 \(\psi\)\(\chi\) 重言等值,所以,根据推论 3.3(视 \(\Gamma\) 为空集),\(\varphi_{0}(\psi / p^{*}), \varphi_{1}(\psi / p^{*})\)\(\varphi_{2}(\psi / p^{*})\) 分别与 \(\varphi_{0}(\chi / p^{*}), \varphi_{1}(\chi / p^{*})\)\(\varphi_{2}(\chi / p^{*})\) 重言等值。我们由式 ()知道,这就是在说 \(\varphi\)\(\varphi_{0}^{\prime}, \varphi_{1}^{\prime}\)\(\varphi_{2}^{\prime}\) 都重言等值,与前面由推论 3.5 得出的结论完全一样。

注意,推论 3.5 是「等值置换」语义形式的常见说法,而推论 3.3-3.4 在应用方面比推论 3.5 更方便。

4.4 真值指派与真值表

我们对重言蕴涵和重言式等概念曾给出两个不同的说明:一个是§2.5(P.85) 中的真值表刻画,另一个是在§3.1(P.101)中用真值指派给出的定义。为避免混淆,我们用这些概念的「严格定义」来指§3.1(P.101)中的定义,用这些概念的「真值表刻画」指§2.5(P.85)中的说明。这一节我们讨论的主要内容是这些概念的严格定义和真值表刻画的等价性。

从这一节起,我们将较多地使用真值函数这个概念。

4.4.1 真值函数

前面说过,真值函数是从真值集到真值集的函数,而且真值函数联结词就是以真值函数为其解释的联结词。第一点很容易理解,但第二点也许不太明显,我们先对它做一点说明。

显然,下列函数都是真值函数(其中 \(x, y \in \lbrace 1,0\rbrace\)):

{{% freebox title=“真值函数联结词” %}}

\[\begin{align} f_{\neg}(x) &=\left\lbrace \begin{array}{ll} 1 & \text { 如果 }~ x=0 \\ 0 & \text { 否则 } \end{array}\right.\\ f_{\lor}(x, y) &=\left\lbrace \begin{array}{ll} 1 & \text { 如果 }~ x=1 \text { 或 } y=1 \\ 0 & \text { 否则 } \end{array}\right.\\ f_{\land}(x, y) &=\left\lbrace \begin{array}{ll} 1 & \text { 如果 }~ x=y=1 \\ 0 & \text { 否则 } \end{array}\right.\\ f_{\rightarrow}(x, y) &=\left\lbrace \begin{array}{ll} 1 & \text { 如果 }~ x=0 \text { 或 }~ y=1 \\ 0 & \text { 否则 } \end{array}\right.\\ f_{\leftrightarrow}(x, y) &=\left\lbrace \begin{array}{ll} 1 & \text { 如果 }~ x=y \\ 0 & \text { 否则 } \end{array}\right. \end{align}\]

若用真值表来表示这些函数,它们与基本真值表 2.1 完全对应:

\[ \begin{array}{cc|c|c|c|c|c} x & y & f_{\land}(x, y) & f_{\lor}(x, y) & f_{\rightarrow}(x, y) & f_{\leftrightarrow}(x, y) & f_{\neg}(x) \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0 & \\ 0 & 1 & 0 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 1 & \end{array} \]

{{% /freebox %}}

事实上,用真值指派 \(\sigma\) 对所有公式 \(\varphi\) 定义其真值 \(\varphi^\sigma\) 时(见定义 3.1),我们完全可以把定义写成下述形式:

\[ \begin{align*} p_{n}^{\sigma} &=\sigma(p_{n}) \quad(n \geqslant 0) \nonumber \\ (\neg \psi)^{\sigma} &=f_{\neg}(\psi^{\sigma}) \\ (\psi \odot \chi)^{\sigma} &=f_{\odot}(\psi^{\sigma}, \chi^{\sigma}) \quad(\odot \in\lbrace \vee, \wedge, \rightarrow, \leftrightarrow\rbrace)\nonumber \end{align*} \]

现在应该容易看出,这些真值函数正是 \(\neg, \wedge, \vee, \rightarrow, \leftrightarrow\) 这几个真值联结词的语义解释。比如,对于公式 \(p \lor q\) 来说,\(p\)\(q\) 各自都既可以解释为 1 也可以解释为 0,但 \(\lor\) 却不可以随便解释——它的解释是固定的真值函数 \(f_\lor.\) 类似地,\(\neg, \land, \rightarrow, \leftrightarrow\) 的解释分别是固定的真值函数 \(f_{\neg}, f_{\land}, f_{\rightarrow}\)\(f_{\leftrightarrow}.\)

对每个 \(n > 0\)\(n\) 元真值函数共有 \(2^{2^n}\) 个。比如,

例 3.18 一元的真值函数有 4 个,见下表(易见 \(f_{\neg} = g_3\)):

\[ \begin{array}{c|cccc} x & g_{1}(x) & g_{2}(x) & g_{3}(x) & g_{4}(x) \\ \hline 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{array} \]

例 3.19 二元的真值函数有 16 个,见下表(\(f_k\) 表示 \(f_{k}(x,y), k =1,\cdots,16\) ):

\[ \begin{array}{cc|cccccccccccccccc} x & y & f_{1} & f_{2} & f_{3} & f_{4} & f_{5} & f_{6} & f_{7} & f_{8} & f_{9} & f_{10} & f_{11} & f_{12} & f_{13} & f_{14} & f_{15} & f_{16} \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{array} \]

易见 \(f_{\lor}=f_2, f_{\rightarrow}=f_5, f_{\leftrightarrow}=f_7, f_{\land}=f_8.\) 三元和四元的真值函数等依此类推。三元真值函数有 \(2^{2^3}=256\) 个,而四元真值函数有 \(2^{2^4}=65536\) 个,这里自然画不下它们的真值表。

4.4.2 对部分命题变号的赋值

为了便于讨论,我们引入另一种赋值概念。这种赋值很像是真值指派,不过它只对给定的部分命题变号指派了真值,而对其他命题变号(如果有的话)没做任何指派。

对每个命题变号的非空集合 \(A\) 我们定义「\(A\)-公式」和「\(A\)-赋值」如下。(「\(A\)-公式」和「\(A\)-赋值」等都不是流行的术语。)

{{% dtpc title=“☯定义 3.12 \(A\)-公式” %}} 设 \(\varnothing \ne A \subseteq \mathbf{Pr}.\) \(A\)-公式是其中只出现属于 \(A\) 的命题变号的 \(\mathscr{L}_0\)-公式,其严格定义如下: > 1. \(A\) 中的毎个命题变号都是 \(A\)-公式; > 1. 如果 \(\varphi\)\(\psi\)\(A\)-公式,那么 \(\neg \varphi\)\((\varphi \odot \psi)\) 都是 \(A\)-公式,其中 \(\odot \in\lbrace \vee, \wedge, \rightarrow, \leftrightarrow\rbrace;\) > 1. 只有这些是 \(A\)-公式。 {{% /dtpc %}}

{{% dtpc title=“☯定义 3.13 \(A\)-赋值” %}} 设\(\varnothing \ne A \subseteq \mathbf{Pr}.\) 一个 \(A\)-赋值是从 \(A\)\(\lbrace 1,0\rbrace\) 的一个函数。 {{% /dtpc %}}

这里对命题变号集 \(A\) 的限制只是「非空」,从而 \(A\) 可以是有穷集也可以是无穷集,甚至可以就是 \(\mathbf{Pr}\)(由此可知,真值指派都是 \(\mathbf{Pr}\)-赋值)。但是,如果 \(A \ne \mathbf{Pr}\),我们把赋值称作对部分命题变号的赋值。下面是关于这个概念的一个有用事实:如果 \(A\) 是出现在某个真值表中的所有命题变号的集合,那么该表中命题变号的每一个可能取值组合就是一个 \(A\)-赋值。(参见§2.4.2(P.84)关于命题变号的可能取值组合的讨论。)

{{% dtpc title=“☯定义 3.14 \(A\)-赋值的递归定义” %}} 设 \(\varnothing \ne A \subseteq \mathbf{Pr}\),并设 \(\tau\) 为任意 \(A\)-赋值。对所有的 \(A\)-公式 \(\varphi\),我们用 \(\varphi^\tau\) 表示「\(\varphi\)\(\tau\) 下的值」。\(\varphi^\tau\) 递归地定义如下:

\[\begin{align*} p^{\tau} &=\tau(p) \quad(p \in A) \\ (\neg \varphi)^{\tau} &=f_{\neg}\left(\varphi^{\tau}\right) \\ (\varphi \odot \psi)^{\tau} &=f_{\odot}\left(\varphi^{\tau}, \psi^{\tau}\right) \quad(\odot \in\lbrace \vee, \wedge, \rightarrow, \leftrightarrow\rbrace) \end{align*}\]

{{% /dtpc %}}

对比定义 3.14 和式 3.13 后很容易看出,\(A\)-赋值只给出 \(A\)-公式的真值,而真值指派给出所有 \(\mathscr{L}_0\)-公式的真值,但仅就 \(A\)-公式来说,这两个定义确定公式真值的方法是完全一样的。

4.4.3 两种描述方式的等价性

重言蕴涵等概念的严格定义和它们的真值表刻画有明显的区别。比如说重言式,按照它的严格定义,一公式是否重言式的问题涉及无穷多真值指派,每个真值指派又涉及无穷多命题变号的真值;而按照它的真值表刻画,一公式是否重言式的问题,却只涉及某个有穷的命题变号集合 \(A\) 和有穷多个 \(A\)-赋值。尽管如此,「严格定义」和「真值表刻画」在下述意义上是等价的:满足「严格定义」的一定满足「真值表刻画」,而满足「真值表刻画」的也一定满足「严格定义」。下面我们提供这种等价性的证明。

借助直观,人们会有以下猜测:

一个公式 \(\varphi\) 在一真值指派 \(\sigma\) 下的值,应只与 \(\sigma\) 指派给 \(\varphi\) 中出现的命题变号的值有关,或者说,与 \(\sigma\) 指派给其他命题变号的值无关。

运用 \(A\)-赋值的概念,我们可以将上述猜测表述为下述命题。

{{% dtpc title=“☯命题 3.11” %}} 设 \(\varnothing \ne A \subseteq \mathbf{Pr}\),设 \(\sigma\) 为任意真值指派,并设 \(\tau\) 为任意 \(A\)-赋值,满足对每个 \(p \in A, \tau(p) = \sigma(p).\) 那么,对所有的 \(A\)-公式 \(\varphi\)\(\varphi^\sigma = \varphi^\tau.\) {{% /dtpc %}}

证明:施归纳于公式的复杂度,我们证明对每个 \(A\)-公式 \(\varphi, \varphi^{\sigma}=\varphi^{\tau}.\)

归纳基始\(\varphi=p \in A.\) 由题设知 \(\sigma(p)=\tau(p)\),即 \(\varphi^{\sigma}=\varphi^{\tau}.\)

归纳步骤:设 \(\varphi=\neg \psi.\) 由归纳假设知 \(\psi^{\sigma}=\psi^{\tau}\),于是根据 式 3.13 和定义 3.14 得到 \[(\neg \psi)^{\sigma}=f_{\neg}\left(\psi^{\sigma}\right)=f_{\neg}\left(\psi^{\tau}\right)=(\neg \psi)^{\tau}\]\(\varphi=\psi \odot \chi(\odot \in\lbrace \vee, \wedge, \rightarrow, \leftrightarrow\rbrace).\) 由归纳假设知 \(\psi^{\sigma}=\psi^{\tau}\)\(\chi^{\sigma}=\chi^{\tau}\),再根据式 3.13 和定义 3.14,我们有 \[(\psi \odot \chi)^{\sigma}=f_{\odot}\left(\psi^{\sigma}, \chi^{\sigma}\right)=f_{\odot}\left(\psi^{\tau}, \chi^{\tau}\right)=(\psi \odot \chi)^{\tau}\] 由此我们证明了,对每个 \(A\)-公式 \(\varphi\) 都有 \(\varphi^{\sigma}=\varphi^{\tau}.\)

命题 3.11 是对前述猜测的一种表述,其中使用了 \(A\)-赋值这一概念。如果不用这个概念,我们可以将前述猜测表述为下述命题。

{{% dtpc title=“☯命题 3.12” %}} 设 \(\varnothing \neq A \subseteq \mathbf{Pr}\),并设 \(\sigma\)\(\sigma^{\prime}\) 为任意真值指派,满足对每个 \(p \in A, \sigma(p)=\sigma^{\prime}(p).\) 那么,对所有的 \(A\)-公式 \(\varphi\)\(\varphi^{\sigma} = \varphi^{\sigma^{\prime}}.\) {{% /dtpc %}}

证明:\(\tau\)\(\sigma\) 限制到 \(A\) 的结果。(设 \(f\) 为从 \(X\)\(Y\) 的任意函数,并设 \(Z \subseteq X.\)\(f\) 限制到 \(Z\) 的结果是从 \(Z\)\(Y\) 的函数 \(g\),满足对每一个 \(x \in Z\) 都有 \(g(x) = f(x).\))对每个 \(A\)-公式 \(\varphi\),由题设和命题 3.11 知 \(\varphi^{\sigma}=\varphi^{\tau}\),再次运用题设和命题 3.11 即有 \(\varphi^{\tau}=\varphi^{\sigma^{\prime}}\),所以 \(\varphi^{\sigma}=\varphi^{\sigma^{\prime}}.\)

为了证明命题 3.12(尤其是在没引入 \(A\)-赋值概念的情况下),可以像证明命题 3.11 那样,施归纳于公式的复杂度,完成归纳基始和一个个归纳步骤。但是,直接应用命题 3.11 显然使命题 3.12 的证明更简单。在基本概念清楚之后,注意已证明的命题或定理,避免事事「从头做起」。

\(\tau\) 为任意 \(A\)-赋值,\(\Gamma\) 为任意 \(A\)-公式集。\(\tau \vDash \Gamma\) 当且仅当对每个 \(\varphi \in \Gamma\) 都有 \(\varphi^\tau = 1.\) 类似地,我们用 \(\tau \vDash \varphi\) 表示 \(\tau \vDash \lbrace \varphi\rbrace\),并用丁 \(\tau \nvDash \Gamma\)\(\tau \nvDash \varphi\) 分别表示 \(\tau \vDash \Gamma\)\(\tau \vDash \varphi\) 不成立。

运用命题 3.11,可以轻松地证明下述命题,其中的「重言蕴涵」和「重言式」等,都是在「严格定义」的意义上使用的。

{{% dtpc title=“☯命题 3.13” %}} 设 \(\varnothing \ne A \subseteq \mathbf{Pr}\),设 \(\varphi\)\(\psi\) 为任意的 \(A\)-公式,并设 \(\Gamma\) 为任意的\(A\)-公式集。我们有:

  1. \(\Gamma \vDash_{0} \varphi\) 当且仅当对所有的 \(A\)-赋值 \(\tau\),如果 \(\tau \vDash \Gamma\)\(\tau \vDash \varphi;\)
  2. \(\varphi\)\(\psi\) 重言等值当且仅当对每个 \(A\)-赋值 \(\tau, \varphi^{\tau}=\psi^{\tau};\)
  3. \(\Gamma\) 是可满足的当且仅当存在 \(A\)-赋值 \(\tau\) 使得 \(\tau \vDash \Gamma;\)
  4. \(\varphi\) 是重言式当且仅当对每个 \(A\)-赋值 \(\tau\) 都有 \(\varphi^{\tau}=1;\)
  5. \(\varphi\) 是矛盾式当且仅当对每个 \(A\)-赋值 \(\tau\) 都有 \(\varphi^{\tau}=0;\)
  6. \(\varphi\) 是或然式当且仅当存在 \(A\)-赋值 \(\tau\)\(\tau^{\prime}\) 使得 \(\varphi^{\tau}=1\)\(\varphi^{\tau^{\prime}}=0.\) {{% /dtpc %}}

证明:我们证明:\(\Gamma \nvDash_{0} \varphi\) 当且仅当存在一个 \(A\)-赋值 \(\tau\) 使得 \(\tau \vDash \Gamma\) 且 $ .$ 设 \(\Gamma \nvDash_{0} \varphi.\) 根据定义 3.3,存在一个真值指派 \(\sigma\) 使得 \(\sigma \vDash \Gamma\)\(\sigma \nvDash \varphi.\)\(\tau\)\(\sigma\) 限制到 \(A\) 的结果。显然 \(\tau\) 是个 \(A\)-赋值,而根据命题 3.11,\(\tau \vDash \Gamma\)\(\tau \nvDash \varphi.\) 反之,设存在 \(A\) -赋值 \(\tau\),满足 \(\tau \vDash \Gamma\)\(\tau \nvDash \varphi.\)\(\sigma\) 为这样一个真值指派:对每个 \(p \in A\)\(\sigma(p)=\tau(p)\),并且对每个命题变号 \(q \notin A, \sigma(q)=0.\) 根据命题 3.11,\(\sigma \vDash \Gamma\)\(\sigma \nvDash \varphi\),所以由定义 3.3 \(\Gamma \nvDash_{0} \varphi.\)

命题 3.13 其他条目的证明都与上述证明类似,都留作练习(见习题 3.19)。

如果把 \(\Gamma\) 限制为有穷集,并把 \(A\) 限制为 \(\Gamma\)\(\varphi\) 中(或 \(\varphi\)\(\psi\) 中)出现的命题变号的集合,那么命题 3.13 说的正是重言蕴涵等语义概念的严格定义等价于它们的真值表刻画。至此我们完成了对这一等价性的证明。不过,因为命题 3.11-3.13 中的 \(\Gamma\)\(A\) 都可以是无穷集,所以这些命题比上述等价性更具一般性。

下述命题是命题 3.13 的一个简单应用。(注意对比命题 3.7)

{{% dtpc title=“☯命题 3.14” %}} 令 \(\varphi\)\(\psi\) 为任意不含相同命题变号的公式。我们有:

  1. \(\varphi\lor \psi\) 是重言式当且仅当或者 \(\varphi\) 是重言式或者 \(\psi\) 是重言式。
  2. \(\varphi \rightarrow \psi\) 是重言式当且仅当或者 \(\varphi\) 是矛盾式或者 \(\psi\) 是重言式。
  3. \(\varphi \leftrightarrow \psi\) 是重言式当且仅当或者 \(\varphi\)\(\psi\) 都是矛盾式或者 \(\varphi\)\(\psi\) 都是重言式。 {{% /dtpc %}}

证明:根据命题 3.7条目一,只需假设 \(\varphi\)\(\psi\) 都不是重言式,而证明 \(\varphi\lor \psi\) 不是重言式。根据假设,存在真值指派 \(\sigma\)\(\sigma^\prime\),使得 \(\sigma \nvDash \varphi\) 并且 \(\sigma^\prime \nvDash \varphi\)。令 \(\sigma^*\) 为满足下述条件的任意真值指派:

\[ \sigma^{*}(p)=\left\lbrace \begin{array}{ll} \sigma(p) & \text{如果~} p \text{~出现在~} \varphi \text{~中} \\ \sigma^{\prime}(p) & \text{如果~} p \text{~出现在~} \psi \text{~中} \end{array}\right. \]

由于 \(\varphi\)\(\psi\) 不含相同的命题变号,易见满足上述条件的真值指派是存在的,于是根据命题 3.12,\(\sigma^* \nvDash \varphi\) 并且 \(\sigma^* \nvDash \psi\),进而 \(\sigma^* \nvDash \varphi \lor \psi.\)

命题 中的另外两条留作练习(见习题 3.20)

4.5 范式

范式是具有某种特殊形式的公式,这种特殊形式帮助我们认识公式的一些性质和关系,而且在机器证明中也有应用。

4.5.1 合取范式

一个公式是合取范式(of conjunctive normal form)如果它形如 \(\varphi_0 \land \cdots \land \varphi_n\) 并且对每一个 \(i \leqslant n\)\(\varphi_i\) 形如 \(\psi_0 \lor \cdots \lor \psi_{m_{i}}\),其中每个 \(\psi_j (j \leqslant m_{i})\) 都或是命题变号,或是命题变号的否定。粗略地说,合取范式是个合取式,而其合取支都是命题变号或其否定的析取式。(Wang[1981]中把命题变号或其否定的析取式称作「简单析取」。)对所有公式 \(\varphi\)\(\psi\)\(\psi\)\(\varphi\) 的合取范式当且仅当下列条件成立:

\(\psi\) 是合取范式, \(\psi\)\(\varphi\) 重言等值。

例 3.20 下列公式都是合取范式 > \(p\) > \(\neg p \lor q\) > \(p \land \neg q \land r \land \neg p\) > \((p \lor \neg q) \land \neg p\) > \((p \lor \neg q) \land(\neg p \lor r \lor q) \land(p \lor \neg r)\)

注意:合取范式定义中的 \(n\)\(m_i\) 等可以是任何自然数,并且它们之间可以没有任何关系。单个命题变号 \(p\) 之所以是合取范式,是因为合取范式的定义允许 \(n = 0\)\(m_0 = 0\) 的情况。\(\neg p \lor q\)\(n = 0\)\(m_0 = 1\) 时的情况,而 \(p \land \neg q \land r \land \neg p\)\(n = 3\)\(m_0,\cdots,m_3 = 0\) 时的情况。

例 3.21 下列编号公式是对应无编号公式的合取范式 > - \(p \rightarrow q\) > - \(\neg q \rightarrow \neg p\) > - \(p \rightarrow q\) > - \(p \wedge q \rightarrow r\) > - \(\neg(p \wedge r \rightarrow \neg q)\) > - \(p \vee q \rightarrow \neg r\) > 1. \(\neg p \vee q\) > 1. \(\neg p \vee q\) > 1. \(q \vee \neg p\) > 1. \(\neg p \vee \neg q \vee r\) > 1. \(p \wedge q \wedge r\) > 1. \((\neg p \vee \neg r) \wedge(\neg q \vee \neg r)\)

易见:不同的公式可以有相同的合取范式,而同一个公式也可以有不同的合取范式。

4.5.2 析取范式

—个公式是析取范式(of disjunctive normal form)如果它形如 \(\varphi_0 \lor \cdots \lor \varphi_n\) 并且对每一个 \(i \leqslant n\)\(\varphi_i\) 形如 \(\psi_0 \land \cdots \land \psi_{m_{i}}\),其中每个 \(\psi_j (j \leqslant m_{i})\) 都或是命题变号,或是命题变号的否定。粗略地说,析取范式是个析取式,而其析取支都是命题变号或其否定的合取式。对所有公式 \(\varphi\)\(\psi\)\(\psi\)\(\varphi\) 的析取范式当且仅当下列条件成立:

  1. \(\psi\) 是析取范式,
  2. \(\psi\)\(\varphi\) 重言等值。

例 3.22 下列公式都是析取范式 > 1. \(p\) > 1. \(\neg p \lor q\) > 1. \(p \land \neg q \land r \land \neg p\) > 1. \((p \lor \neg q) \lor \neg p\) > 1. \((p \land \neg q) \lor (\neg p \land r \land q) \land(p \land \neg r)\)

与前面的说明类似,\(p\) 之所以是析取范式,是因为析取范式的定义允许 \(n = 0\)\(m_0 = 0\) 的情况。\(\neg p \lor q\)\(n = 1\)\(m_0, m_1 = 0\) 时的情况,而 \(p \land \neg q \land r \land \neg p\)\(n = 0\)\(m_0 = 3\) 时的情况。

例 3.23 下列编号公式是对应无编号公式的析取范式 > - \(p \rightarrow q\) > - \(\neg q \rightarrow \neg p\) > - \(p \rightarrow q\) > - \(p \wedge q \rightarrow r\) > - \(\neg(p \wedge r \rightarrow \neg q)\) > - \(p \vee q \rightarrow \neg r\) > 1. \(\neg p \vee q\) > 1. \(\neg p \vee q\) > 1. \(q \vee \neg p\) > 1. \(\neg p \vee \neg q \vee r\) > 1. \(p \wedge q \wedge r\) > 1. \((\neg p \land \neg r) \lor \neg r\)

易见:不同的公式可以有相同的析取范式,而同一个公式也可以有不同的析取范式。比较例 3.20 和例 3.22 以及例 3.21 和例 3.23,可知一个公式的析取范式与它的合取范式也可以是同一个公式。读者应对照定义,检查上述例子中的合取范式和析取范式,以求准确把握范式的概念。

4.5.3 范式定理

由于范式在形式方面的特点,很多时候处理范式比处理一般公式要容易。比如,要确定一个合取范式 \(\varphi_0 \land \cdots \land \varphi_n\) 是否重言式,我们只需看每一个 \(\varphi_i(i \leqslant n)\) 中是否都有某个命题变号及其否定。满足这一条件的就是重言式,不满足的就不是重言式。类似地,要判断一个析取范式 \(\varphi_0 \lor \cdots \lor \varphi_n\) 是否矛盾式,我们只需看每一个 \(\varphi_i(i \leqslant n)\) 中是否都有某个命题变号及其否定。满足这一条件的就是矛盾式,不满足的就不是矛盾式。参见命题 3.7。

如果每个公式都有它的合取范式和析取范式,那么很多关于公式的问题就可以归结为范式的问题,从而降低解决这些问题的难度。事实上,每一个公式都既有它的合取范式也有它的析取范式。我们先来看公式的析取范式的存在问题。

{{% dtpc title=“☯定理 3.2【析取范式存在定理】” %}} 任何公式都有析取范式,亦即对每个公式 \(\varphi\),存在一个公式 \(\varphi^{\prime}\) 使得 \(\varphi^{\prime}\) 是析取范式并与 \(\varphi\) 重言等值。 {{% /dtpc %}}

这个命题有时被称作析取范式存在定理。我们这里不做严格的证明,只给出找到任给公式的析取范式的一个方法。对证明有兴趣的读者可以参照命题117的证明试着给出这个命题的证明。(参见习题 3.22)

考虑任意公式 \(\varphi.\)\(\varphi\) 中出现的命题变号为 \(q_0,\cdots,q_{n-1}\),并令 \(A = \lbrace q_0,\cdots,q_{n-1}\rbrace.\) 我们知道,\(A\)-赋值(亦即 \(q_0,\cdots,q_{n-1}\) 的可能取值组合)总共有 \(2^n\) 个。如果 \(\varphi\) 是矛盾式,我们令 \(\varphi^{\prime} = q_0 \land \neg q_0 \land q_1 \land \cdots \land q_{n-1}.\)\(\varphi^{\prime}\) 的选择有多种。我们这里选择的是的 \(q_0,\cdots,q_{n-1}\) 都出现的、尽可能简单的和矛盾的析取范式。)

易见 \(\varphi^{\prime}\) 是析取范式并与 \(\varphi\) 重言等值。假设 \(\varphi\) 不是矛盾式,并设 \(\tau_{0}, \cdots, \tau_{k} (k<2^{n})\) 为使得 \(\varphi\) 的值为 1 的全部 \(A\)-赋值。对每个 $i k $ 和每个 \(j < n\),定义 \(\theta_{j}^{i}\) 如下:

\[ \theta_{j}^{i}=\left\lbrace \begin{array}{ll} q_{j} & \text { 如果 }~ \tau_{i}\left(q_{j}\right)=1 \\ \neg q_{j} & \text { 如果 }~ \tau_{i}\left(q_{j}\right)=0 \end{array}\right. \]

并且对每个 \(i \leqslant k\),定义 \(\psi_{i}=\theta_{0}^{i} \wedge \cdots \wedge \theta_{n-1}^{i}.\) 最后令 \(\varphi^{\prime}=\psi_{0} \vee \cdots \vee \psi_{k}.\) 易见 \(\varphi^{\prime}\) 是析取范式,并且可以证明 \(\varphi^{\prime}\)\(\varphi\) 重言等值。

例 3.24 求公式 \((p \rightarrow q) \rightarrow q \land \neg r\) 的析取范式。 解:\(\varphi = (p \rightarrow q) \rightarrow q \land \neg r.\) \(\varphi\) 的真值表如下:

\[ \begin{array}{ccc|c|l} p & q & r & (p \rightarrow q) \rightarrow q \wedge \neg r & \text{令}\\ \hline 1 & 1 & 1 & ~~0 & \\ 1 & 1 & 0 & ~~1 & \psi_{1}=p \wedge q \wedge \neg r\\ 1 & 0 & 1 & ~~1 & \psi_{2}=p \wedge \neg q \wedge r\\ 1 & 0 & 0 & ~~1 & \psi_{3}=p \wedge \neg q \wedge \neg r\\ 0 & 1 & 1 & ~~0 & \\ 0 & 1 & 0 & ~~1 & \psi_{4}=\neg p \wedge q \wedge \neg r\\ 0 & 0 & 1 & ~~0 & \\ 0 & 0 & 0 & ~~0 & \end{array} \]

最后令 \(\varphi^{\prime}=\psi_{1} \vee \psi_{2} \vee \psi_{3} \vee \psi_{4}\),亦即 \[\varphi^{\prime}=(p \wedge q \wedge \neg r) \vee(p \wedge \neg q \wedge r) \vee(p \wedge \neg q \wedge \neg r) \vee(\neg p \wedge q \wedge \neg r).\]

可以证明,\(\varphi^{\prime}\)\(\varphi\) 的一个析取范式。

下面我们来看公式的合取范式的存在问题。

{{% dtpc title=“☯定理 3.3【合取范式存在定理】” %}} 任何公式都有合取范式,亦即对每个公式 \(\varphi\),存在一个公式 \(\varphi^{\prime}\) 使得 \(\varphi^{\prime}\) 是合取范式并与 \(\varphi\) 重言等值。 {{% /dtpc %}}

这个命题有时被称作合取范式存在定理。与上述类似,我们这里不做严格的证明,只给出找到任给公式的合取范式的一个方法。(参见习题 3.22)

考虑任意公式 \(\varphi.\)\(\varphi\) 中出现的命题变号为 \(q_0,\cdots,q_{n-1}\),并令 \(A = \lbrace q_0,\cdots,q_{n-1}\rbrace.\) 如果 \(\varphi\) 是重言式,我们令 \(\varphi^{\prime} = q_0 \lor \neg q_0 \lor q_1 \lor \cdots \lor q_{n-1}.\)\(\varphi^{\prime}\) 的选择有多种。我们这里选择的是的 \(q_0,\cdots,q_{n-1}\) 都出现的、尽可能简单的和重言的合取范式。)易见 \(\varphi^{\prime}\) 是合取范式并与 \(\varphi\) 重言等值。假设 \(\varphi\) 不是重言式,并设 \(\tau_{0}, \cdots, \tau_{k} (k<2^{n})\) 为使得 \(\varphi\) 的值为 0 的全部 \(A\)-赋值。对每个 \(i \leqslant k\) 和每个 \(j < n\),定义 \(\theta_{j}^{i}\) 如下:

\[ \theta_{j}^{i}=\left\lbrace \begin{array}{ll} q_{j} & \text { 如果 }~ \tau_{i}\left(q_{j}\right)=0 \\ \neg q_{j} & \text { 如果 }~ \tau_{i}\left(q_{j}\right)=1 \end{array}\right. \]

并且对每个 \(i \leqslant k\),定义 \(\psi_{i}=\theta_{0}^{i} \lor \cdots \lor \theta_{n-1}^{i}.\) 最后令 \(\varphi^{\prime}=\psi_{0} \land \cdots \land \psi_{k}.\) 易见 \(\varphi^{\prime}\) 是合取范式,并且可以证明 \(\varphi^{\prime}\)\(\varphi\) 重言等值。

例 3.25 求公式 \((p \rightarrow q) \rightarrow q \land \neg r\) 的析取范式。 解:\(\varphi = (p \rightarrow q) \rightarrow q \land \neg r.\) \(\varphi\) 的真值表如下:

\[ \begin{array}{ccc|c|l} p & q & r & (p \rightarrow q) \rightarrow q \wedge \neg r & \text{令}\\ \hline 1 & 1 & 1 & ~~0 & \psi_{1}=\neg p \lor \neg q \lor \neg r\\ 1 & 1 & 0 & ~~1 & \\ 1 & 0 & 1 & ~~1 & \\ 1 & 0 & 0 & ~~1 & \\ 0 & 1 & 1 & ~~0 & \psi_{2}=p \lor \neg q \lor \neg r\\ 0 & 1 & 0 & ~~1 & \\ 0 & 0 & 1 & ~~0 & \psi_{3}=p \lor q \lor \neg r\\ 0 & 0 & 0 & ~~0 & \psi_{4}=p \lor q \lor r \end{array} \]

最后令 \(\varphi^{\prime}=\psi_{1} \land \psi_{2} \land \psi_{3} \land \psi_{4}\),亦即 \[\varphi^{\prime}=(\neg p \lor \neg q \lor \neg r) \land (p \lor \neg q \lor \neg r) \land (p \lor q \lor \neg r) \land (p \lor q \lor r).\]

可以证明,\(\varphi^{\prime}\)\(\varphi\) 的一个析取范式。

在上面讲解公式的范式存在问题时,我们使用了真值表方法,即语义的方法。假如我们求公式的范式仅仅是要判断给定公式是否重言式(或矛盾式),那么用上述方法求范式无疑是事倍功半。这是因为,在写出给定公式的范式之前,我们先构造了该公式的真值表,而从这个真值表我们已经知道该公式是否重言式(或矛盾式)。不过,上面的讲解只是说明任何公式都存在合取范式和析取范式,而且只是用我们已经学会的真值表方法。事实上,求范式的方法不仅是语义的方法,而范式的存在问题也并不就是判断重言式或矛盾式的问题。

4.6 函数完全性

4.6.1 真值函数在形式语言中的表达

显然,真值函数可以有无穷多。在如此多的函数中,有些明显可以用其他真值函数来合成或复合(compose)。比如示例 3.19 中的 \(f_{16}\) 显然可以用 \(f_1\)\(f_\neg\) 来合成,亦即 \(f_{16}(x,y)=f_{\neg}(f_{1}(x,y))\)。那么,有没有一集真值函数(最好不要太多)可以合成所有的真值函数?如果有,哪些真值函数集可以合成所有的真值函数?简单地说,这就是「函数完全性」问题。

这样的问题当然是数学问题。我们寻找数学问题的解,部分地是因为它们往往有解。但我们关心函数完全性问题决不仅仅是因为它有解或很可能有解。函数完全性问题和形式语言的「表达力」有直接关系。\(\mathscr{L}_0\)-公式能表达什么?让我们来看两个例子。

先看公式 \(p \lor q.\) 当考虑公式的值时,命题变号 \(p\)\(q\) 是取值于 \(\lbrace 0, 1\rbrace\) 的变元,而一旦它们的取值确定了,\(p \lor q\) 的值(真值)也就经 \(f_\lor\) 唯一地确定了。在这个意义上,我们说 \(p \lor q\) 表达了真值函数 \(f_\lor.\)(假如我们一开始就把所有的析取式都写成 \(\lor (\varphi, \psi)\) 的样子,那么 \(\lor (p, q)\)\(f_{\lor}(x,y)\) 即使在形式上也非常接近。)

再来看公式 \((p \lor q) \land \neg(p \land q)\),我们可以把它记为 \(p \veebar q.\) \(p\)\(q\) 的取值(真值)一旦确定,\(p \veebar q\) 的值(真值)也就经 \(f_{\lor}, f_{\land}\)\(f_{\neg}\) 的某种复合(当然也是一个真值函数)唯一地确定了(参见式子 3.13 中第二和第三行)。在这个意义上,我们说 \(p \veebar q\) 表达了一个真值函数。事实上,\(\veebar\) 可以被当作一个真值函数联结词,即通常被称为「不相容析取」的联结词(the exclusive or,XOR),它的解释是示例 3.19 中的 \(f_{10}\),而这个函数显然可由 \(f_{\lor}, f_{\land}\)\(f_{\neg}\) 来合成:\(f_{10}(x, y)=f_{\land}(f_{\lor}(x, y), f_{\neg}(f_{\land}(x, y))).\)(参见 §12.2.1(P.198)中对「不相容选言推理」的介绍。)

下面我们来严格地定义 \(\mathscr{L}_0\)-公式对真值函数的表达。在这一节中,凡谈到命题变号 \(q_0, \cdots, q_n\) 时,我们总是假定它们是不同的命题变号,并且对所有 \(i, j \leqslant n\) 如果 \(i < j\),那么 \(q_i\) 按命题变号的字典顺序排在 \(q_j\) 之前。(参见§3.0.0(P.99)中的说明。)

{{% dtpc title=“☯定义 3.15【真值函数的表达】” %}} 设 \(\varphi\) 为含 \(n\) 个命题变号 \(q_0, \cdots, q_{n-1}\) 的任意 \(\mathscr{L}_0\)-公式,并且设 \(f\) 为任意的 \(n\) 元真值函数。\(\varphi\) 表达 \(f\) 当且仅当对所有的真值指派 \(\sigma\)\(\varphi^{\sigma}=f(q_{0}^{\sigma}, \cdots, q_{n-1}^{\sigma}).\) \(f\)\(\mathscr{L}_{0}\) 中可表达当且仅当有某个 \(\mathscr{L}_{0}\)-公式 \(\varphi\) 表达 \(f.\) {{% /dtpc %}}

注意:定义3.15 中的 \(q_0, \cdots, q_{n-1}\) 是根据命题变号集 \(\mathbf{Pr}\) 上固定的字典顺序排列的。这个限制的理由很简单:如果没有这条限制,含相同命题变号而又不重言等值的公式也可以「表达」同一个真值函数。

比如,假定我们将定义 3.15 中的这种限制去掉,那么 \(p \rightarrow q\) 可以「表达」\(f_{\rightarrow}\)(因为 \((p \rightarrow q)^{\sigma}= f_{\rightarrow}(p^{\sigma}, q^{\sigma})\) 对所有 \(\sigma\) 成立),\(q \rightarrow p\) 也可以「表达」(因为 \((q \rightarrow p)^{\sigma}=f_{\rightarrow}(q^{\sigma}, p^{\sigma})\) 对所有 \(\sigma\) 也成立)。当然,这并不是说,「表达」只能像我们上面那样定义。我们可以放弃对命题变号序列的那些限制,但我们必须同时放弃一类要求或想法,比如「含有相同命题变号的公式表达同一真值函数当且仅当它们重言等值」等等。

「表达」也可以相对于其他命题逻辑语言来定义。这里说的命题逻辑语言都与 \(\mathscr{L}_0\) 相似:它们有共同的命题变号(和括号),但有不同的联结词;公式形成规则相仿,真理定义也相仿(参见式子 3.13 和定义 3.14 ,其中「真值指派」和「对部分命题变号的赋值」意义不变),差别就在联结词及其语义解释。请读者补充这些命题逻辑语言的严格定义,以及关于它们公式真值的真理定义。我们约定:

语言 \(\mathscr{L}_{\odot}\) 中的真值函数联结词是

\[\odot_{1}, \cdots, \odot_{k},\]

\(\mathscr{L}_{\odot}\)-公式是只用命题变号和

\[\odot_{1}, \cdots, \odot_{k}\]

构造出来的合式的符号串。

\(\mathscr{L}_{\odot}\)-公式对真值函数的「表达」和「函数完全性」的定义如下:

{{% dtpc title=“☯定义 3.16【表达】” %}} 设 \(\varphi\) 为含 \(n\) 个命题变号 \(q_{0}, \cdots, q_{n-1}\) 的任意 \(\mathscr{L}_{\odot_{1}, \cdots, \odot_{k}}\)-公式,并设 \(f\) 为任意的 \(n\) 元真值函数。\(\varphi\)(在 \(\mathscr{L}_{\odot_{1}, \cdots, \odot_{k}}\) 中)表达 \(f\) 当且仅当对所有真值指派 \(\sigma\)\(\varphi^{\sigma}=f(q_{0}^{\sigma}, \cdots, q_{n-1}^{\sigma}).\) \(f\)\(\mathscr{L}_{\odot_{1}, \cdots, \odot_{k}}\) 中可表达当且仅当有某个 \(\mathscr{L}_{\odot_{1}, \cdots, \odot_{k}}\)-公式 \(\varphi\) 表达 \(f.\) {{% /dtpc %}}

{{% dtpc title=“☯定义 3.17【函数完全】” %}} 设 \(\mathbb{C}=\lbrace \odot_{1}, \cdots, \odot_{k}\rbrace\) 为真值函数联结词的集合。\(\mathbb{C}\) 是函数完全的当且仅当所有的真值函数都在 \(\mathscr{L}_{\odot_{1}, \cdots, \odot_{k}}\) 中可表达。 {{% /dtpc %}}

注意:我们并没有像本节一开始谈论的那样,把可以合成所有真值函数的真值函数集定义为函数完全的。定义 3.17 中既没有谈真值函数的集合,也没有谈真值函数的合成——它谈的是真值函数联结词的集合以及真值函数在有这些联结词的语言里的表达。但这两种谈法的结果是一样的,虽然我们不做证明。

{{% dtpc title=“☯定义 3.18【可定义】” %}} 设 \(\odot\) 为任意 \(n\) 元真值函数联结词,\(f_{\odot}\) 为其语义解释。\(\odot\)\(\lbrace \odot_{1}, \cdots, \odot_{k}\rbrace\) 可定义的当且仅当 \(f_{\odot}\)\(\mathscr{L}_{\odot_{1}, \cdots, \odot_{k}}\) 中可表达。 {{% /dtpc %}}

如果一集真值函数联结词 \(\mathbb{C}\) 有函数完全性,那么用 \(\mathbb{C}\) 做初始联结词的命题逻辑语言就有了完善的表达力。在这样的语言中,任何一个真值函数联结词都可以由 \(\mathbb{C}\) 中的联结词来定义,就像任何一个真值函数都可以由解释 \(\mathbb{C}\) 中联结词的真值函数来定义一样。

4.6.2 具有函数完全性的几组真值函数联结词

这一小节里我们讨论具有函数完全性的几个真值函数联结词的集合。

{{% dtpc title=“☯命题 3.15” %}} 所有真值函数都在 \(\mathscr{L}_{\neg, \lor, \land}\) 中可表达。 {{% /dtpc %}}

命题 3.15 之证明:令 \(f\) 为任意 \(n\) 元真值函数(\(n > 0\))。我们分两种情况讨论。

情况 I: 对所有的 \(a_{0}, \cdots, a_{n-1} \in \lbrace 0, 1\rbrace\) 都有 \(f(a_{0}, \cdots, a_{n-1})=0.\)\(\varphi=p_{0} \wedge \neg p_{0} \wedge p_{1} \wedge \cdots \wedge p_{n-1}.\) 易见对所有真值指派 \(\sigma\) 都有 \(\varphi^{\sigma}=0\),所以在情况 I 下,\(f\)\(\mathscr{L}_{\neg, \lor, \land}\) 中可表达。

情况 II: 存在 \(a_{0}, \cdots, a_{n-1} \in \lbrace 0, 1\rbrace\) 使得 \(f(a_{0}, \cdots, a_{n-1})=1.\)

\[\begin{equation} b_{0}^{0}, \cdots, b_{n-1}^{0}; \quad b_{0}^{1}, \cdots, b_{n-1}^{1} ; \quad \cdots ; \quad b_{0}^{k}, \cdots, b_{n-1}^{k} \end{equation}\]

\((k<2^{n})\) 为所有的真值序列 \(a_{0}, \cdots, a_{n-1} \in\lbrace 0, 1\rbrace\) 使得 \(f(a_{0}, \cdots, a_{n-1})=1.\) 对每个 \(i \leqslant k\)\(j < n\),令

\[ \theta_{j}^{i}=\left\lbrace \begin{array}{ll} p_{j} & \text { 如果 }~ b_{j}^{i}=1 \\ \neg p_{j} & \text { 如果 }~ b_{j}^{i}=0 \end{array}\right. \]

且对每个 \(i \leqslant k\),令 \(\psi_{i}=\theta_{0}^{i} \wedge \cdots \wedge \theta_{n-1}^{i}.\) 最后,令 \(\varphi=\psi_{0} \vee \cdots \vee \psi_{k}.\)

以下证明 \(\varphi\) 表达 \(f.\)\(\sigma\) 为任意真值指派。

\(f(p_{0}^{\sigma}, \cdots, p_{n-1}^{\sigma})=1.\) 易见式子 (10) 中某个序列 \(b_{0}^{i}, \cdots, b_{n-1}^{i}(i \leqslant k)\) 就是 \(p_{0}^{\sigma}, \cdots, p_{n-1}^{\sigma}.\)\(\theta_{j}^{i}\) 的定义知,对每个 \(j<n\),如果 \(p_{j}^{\sigma}=1\)\(\theta_{j}^{i}=p_{j}\),而如果 \(p_{j}^{\sigma}=0\)\(\theta_{j}^{i}=\neg p_{j}.\) 这就是说,对每个 \(j<n\) 都有 \((\theta_{j}^{i})^{\sigma}=1\),所以\(\psi_{i}^{\sigma}=1\),进而 \(\varphi^{\sigma}=1.\)

\(\varphi^{\sigma}=1.\) 根据 \(\varphi\) 的定义,存在 \(i \leqslant k\) 使得 \(\psi_{i}^{\sigma}=1\),从而对每个 \(j<n\) 都有 \((\theta_{j}^{i})^{\sigma}=1.\) 根据 \(\theta_{j}^{i}\) 的定义,如果 \(p_{j}^{\sigma}=1\)\(b_{j}^{i}=1\),并且如果 \(p_{j}^{\sigma}=0\),则 \(b_{j}^{i}=0.\) 这就是说,真值序列 \(p_{0}^{\sigma}, \cdots, p_{n-1}^{\sigma}\) 就是式子 (10) 中的 \(b_{0}^{i}, \cdots, b_{n-1}^{i} .\) 既然 \(f(b_{0}^{i}, \cdots, b_{n-1}^{i})=1\),我们有 \(f(p_{0}^{\sigma}, \cdots, p_{n-1}^{\sigma})=1.\)

综上所述,可知 \(f\)\(\mathscr{L}_{\neg, \lor, \land}\) 中可表达。▗

{{% dtpc title=“☯定理 3.4【函数完全性定理】” %}} 1. 所有真值函数都在 \(\mathscr{L}_{\neg, \lor}\) 中可表达 1. 所有真值函数都在 \(\mathscr{L}_{\neg, \land}\) 中可表达 1. 所有真值函数都在 \(\mathscr{L}_{\neg, \rightarrow}\) 中可表达 {{% /dtpc %}}

证明:易证对所有 \(\mathscr{L}_{0}\)-公式 \(\chi\)\(\chi^{\prime}\)\(\chi \wedge \chi^{\prime}\)\(\neg(\neg \chi \vee \neg \chi^{\prime})\) 重言等值(习题 3.5)。

因而对每个 \(\mathscr{L}_{\neg, \lor, \land}\)-公式 \(\varphi\),运用若干次推论 3.3 可以得到

\(\mathscr{L}_{\neg, \lor}\)-公式 \(\varphi^{\prime}\), 使得 \(\varphi\)\(\varphi^{\prime}\) 重言等值并且 \(\varphi\)\(\varphi^{\prime}\) 含相同的命题变号(习题 3.25)。

\(f\) 为任意 \(n\) 元真值函数。由命题 3.15 知有 \(\mathscr{L}_{\neg, \lor, \land}\)-公式 \(\varphi\) 表达 \(f\)

因而 \(\varphi\) 含命题变号 \(q_{0}, \cdots, q_{n-1}\),且对所有真值指派 \(\sigma\)\(\varphi^{\sigma}=f(q_{0}^{\sigma}, \cdots, q_{n-1}^{\sigma}).\) 由上述可知,存在 \(\mathscr{L}_{\neg, \lor}\)-公式 \(\psi\)\(\psi\) 含命题变号 \(q_{0}, \cdots, q_{n-1}\) 并且 \(\psi^{\sigma}= f\left(q_{0}^{\sigma}, \cdots, q_{n-1}^{\sigma}\right)\), 所以 \(f\)\(\mathscr{L}_{\neg, \lor}\) 中可表达。

因为 \(\chi \vee \chi^{\prime}\)\(\neg(\neg \chi \wedge \neg \chi^{\prime})\) 重言等值,所以类似可证所有真值函数都在 \(\mathscr{L}_{\neg, \land}\) 中可表达。

因为 \(\chi \vee \chi^{\prime}\)\(\neg \chi \rightarrow \chi^{\prime}\) 以及 \(\chi \wedge \chi^{\prime}\)\(\neg(\chi \rightarrow \neg \chi^{\prime})\) 分别重言等值,所以类似可证所有真值函数都在 \(\mathscr{L}_{\neg, \rightarrow}\) 中可表达。▗

{{% dtpc title=“☯定理 3.5【函数完全性定理】” %}} \(\lbrace \neg, \land\rbrace, \lbrace \neg, \land\rbrace, \lbrace \neg, \rightarrow\rbrace\) 各自都是函数完全的,并且各自都可定义所有的真值函数联结词。 {{% /dtpc %}}

证明:根据定理 3.5、定义 3.17 和定义 3.18 得证。▗

函数完全的真值函数联结词的集合,可以只有两个元素,比如 \(\lbrace \neg, \lor\rbrace\),也可以只有一个元素。文中有两个一元联结词 “not-both”(NAND) 和 “neither-nor”(NOR),我们用 “\(\mid\)” 和 “\(\mid\mid\)” 来表示它们。算上 \(\veebar\) 与这两个联结词,基本真值表 2.1(P.82)便成为如下扩展的真值表:

{{% freebox title=“扩展的基本真值表” %}}

\[ \begin{array}{cc|cccccccc} p & q & p \vee q & p \wedge q & p \rightarrow q & p \leftrightarrow q & p \veebar q & p \mid\mid q & p \mid q & \neg p\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & \end{array} \]

{{% /freebox %}}

可以证明,\(\lbrace \mid\rbrace, \lbrace || \rbrace\) 也分别都是函数完全的。我们不给详细证明,只陈述证明中用到的最关键事实:

\(\varphi \mid \varphi\) 可用来表示 \(\neg \varphi\)\((\varphi \mid \varphi) \mid (\psi \mid \psi)\) 可用来表示 \(\varphi \vee \psi\) 见下表:

\[ \begin{array}{c|c|c} \varphi & \neg \varphi & \varphi \mid \varphi \\ \hline 1 & 0 & 0 \\ 0 & 1 & 1 \end{array} \]

\[ \begin{array}{cc|c|c} \varphi & \psi & \varphi \vee \psi & (\varphi \mid \varphi) \mid (\psi \mid \psi) \\ \hline 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{array} \]

\(\varphi \| \varphi\) 可用来表示 \(\neg \varphi\)\((\varphi \| \varphi) \| (\psi \| \psi)\) 可用来表示 \(\varphi \wedge \psi\) 见下表:

\[ \begin{array}{c|c|c} \varphi & \neg \varphi & \varphi \| \varphi \\ \hline 1 & 0 & 0 \\ 0 & 1 & 1 \end{array} \]

\[ \begin{array}{cc|c|c} \varphi & \psi & \varphi \wedge \psi & (\varphi \| \varphi)\|(\psi \| \psi) \\ \hline 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \]

4.7 本章习题

练习 4.1 证明:对所有公式集 \(\Gamma\)\(\Delta\),以及所有公式 \(\varphi\)\(\psi\)

  1. 如果 \(\Gamma \vDash_{0} \varphi\),那么 \(\Gamma \cup \Delta \vDash_{0} \varphi\);
  2. 如果 \(\Gamma \vDash_{0} \varphi \vee \psi\) 并且 \(\Delta \vDash_{0} \neg \varphi\),那么 \(\Gamma \cup \Delta \vDash_{0} \psi\);
  3. 如果 \(\Gamma \vDash_{0} \varphi\) 且 \(\Delta \vDash_{0} \varphi \rightarrow \psi\),那么 \(\Gamma \cup \Delta \vDash_{0} \psi\).
练习 4.2 \(\Delta \vDash_{0} \varphi\) 并且 \(\varphi \vDash_{0} \psi\). 证明:\(\Delta \vDash_{0} \psi\).

练习 4.3 证明对所有公式 \(\varphi, \psi, \chi\),下述命题成立::

  1. \(\varphi, \varphi \rightarrow \psi \vDash_{0} \psi\)
  2. \(\varphi \vee \psi, \neg \psi \vDash_{0} \varphi\)
  3. \(\varphi \vee \psi, \neg \varphi \vee \chi \vDash_{0} \psi \vee \chi\)
  4. \(\varphi \vee \psi \vDash_{0} \chi\) 当且仅当 \(\varphi \vDash_{0} \chi\)\(\psi \vDash_{0} \chi\).

练习 4.4 \(\varphi, \psi, \chi\) 为任意公式。证明下列都是重言式:

  1. \(\varphi \rightarrow(\psi \rightarrow \varphi)\)
  2. \((\varphi \rightarrow(\psi \rightarrow \chi)) \rightarrow((\varphi \rightarrow \psi) \rightarrow(\varphi \rightarrow \chi))\)
  3. \(\varphi \wedge \psi \rightarrow \varphi\)
  4. \(\varphi \wedge \psi \rightarrow \psi\)
  5. \(\varphi \rightarrow(\psi \rightarrow \varphi \wedge \psi)\)
  6. \(\varphi \rightarrow \varphi \vee \psi\)
  7. \(\varphi \rightarrow \psi \vee \varphi\)
  8. \((\varphi \rightarrow \chi) \rightarrow((\psi \rightarrow \chi) \rightarrow(\varphi \vee \psi \rightarrow \chi))\)
  9. \((\varphi \rightarrow \psi) \rightarrow((\varphi \rightarrow \neg \psi) \rightarrow \neg \varphi)\)
  10. \(\neg \neg \varphi \rightarrow \varphi\)
  11. \((\varphi \leftrightarrow \psi) \rightarrow(\varphi \rightarrow \psi)\)
  12. \((\varphi \leftrightarrow \psi) \rightarrow(\psi \rightarrow \varphi)\)
  13. \((\varphi \rightarrow \psi) \rightarrow((\psi \rightarrow \varphi) \rightarrow(\varphi \leftrightarrow \psi))\)

练习 4.5 \(\varphi, \psi, \chi\) 为任意公式。证明下列都是重言式:

  1. \((\neg \varphi \rightarrow \psi) \rightarrow((\neg \varphi \rightarrow \neg \psi) \rightarrow \varphi)\)
  2. \((\neg \psi \rightarrow \neg \varphi) \rightarrow(\varphi \rightarrow \psi)\)
  3. \(((\varphi \rightarrow \psi) \rightarrow \varphi) \rightarrow \varphi\)
  4. \(\neg \varphi \rightarrow(\varphi \rightarrow \psi)\)
  5. \((\neg \varphi \rightarrow \varphi) \rightarrow \varphi\)
  6. \((\varphi \rightarrow \neg \varphi) \rightarrow \neg \varphi\)
  7. \((\varphi \leftrightarrow \psi) \leftrightarrow(\psi \leftrightarrow \varphi)\)
  8. \(((\varphi \leftrightarrow \chi) \leftrightarrow(\psi \leftrightarrow \varphi)) \leftrightarrow(\chi \leftrightarrow \psi)\)
  9. \((\varphi \leftrightarrow(\psi \leftrightarrow \chi)) \leftrightarrow((\varphi \leftrightarrow \psi) \leftrightarrow \chi)\)

练习 4.6 证明对所有公式 \(\varphi, \psi, \chi\),下列各组公式都是重言等值的:

  1. \(\varphi, \varphi \vee \varphi, \varphi \wedge \varphi\)
  2. \(\varphi, \neg \neg \varphi\)
  3. \(\varphi \vee \psi, \psi \vee \varphi\)
  4. \(\varphi \wedge \psi, \psi \wedge \varphi\)
  5. \(\varphi \vee(\psi \vee \chi),(\varphi \vee \psi) \vee \chi\)
  6. \(\varphi \wedge(\psi \wedge \chi),(\varphi \wedge \psi) \wedge \chi\)
  7. \(\neg(\varphi \vee \psi), \neg \varphi \wedge \neg \psi\)
  8. \(\varphi \vee \psi, \neg(\neg \varphi \wedge \neg \psi)\)
  9. \(\neg(\varphi \wedge \psi), \neg \varphi \vee \neg \psi\)
  10. \(\varphi \wedge \psi, \neg(\neg \varphi \vee \neg \psi)\)
  11. \(\varphi \rightarrow \psi, \neg \psi \rightarrow \neg \varphi\)
  12. \(\varphi \vee(\psi \wedge \chi),(\varphi \vee \psi) \wedge(\varphi \vee \chi)\)
  13. \(\varphi \wedge(\psi \vee \chi),(\varphi \wedge \psi) \vee(\varphi \wedge \chi)\)
  14. \(\varphi \rightarrow \psi, \neg \varphi \vee \psi\)
  15. \(\neg \varphi \rightarrow \psi, \varphi \vee \psi\)
  16. \(\varphi \leftrightarrow \psi,(\varphi \wedge \psi) \vee(\neg \varphi \wedge \neg \psi)\)
  17. \(\varphi \leftrightarrow \psi,(\varphi \rightarrow \psi) \wedge(\psi \rightarrow \varphi)\)
  18. \(\neg(\varphi \leftrightarrow \psi), \varphi \leftrightarrow \neg \psi, \neg \varphi \leftrightarrow \psi,(\varphi \wedge \neg \psi) \vee(\neg \varphi \wedge \psi)\)
  19. \(\varphi \rightarrow(\psi \rightarrow \chi), \varphi \wedge \psi \rightarrow \chi, \psi \rightarrow(\varphi \rightarrow \chi)\)
  20. \(\varphi \vee \psi \rightarrow \chi,(\varphi \rightarrow \chi) \wedge(\psi \rightarrow \chi)\)

练习 4.7 证明:对所有公式集 \(\Gamma\) 和所有公式 \(\varphi\)

  1. 如果 \(\Gamma \vDash_{0} \varphi\)\(\varphi\)不可满足,那么 \(\Gamma\) 不可满足。
  2. 如果 \(\Gamma\) 可满足,那么 \(\lbrace \psi: \Gamma \vDash_{0} \psi\rbrace\) 也可满足。
练习 4.8 完成命题 3.7(P.105)的证明。

练习 4.9 证明:对所有公式 \(\varphi\)

  1. \(\varphi\) 是重言式当且仅当 \(\neg \varphi\) 不可满足;
  2. \(\varphi\) 是矛盾式当且仅当 \(\varphi\) 不可满足;
  3. \(\varphi\) 是或然式当且仅当 \(\varphi\)\(\neg \varphi\) 都可满足;
  4. \(\varphi\) 是重言式当且仅当 \(\neg \varphi\) 是矛盾式;
  5. \(\varphi\) 是矛盾式当且仅当 \(\neg \varphi\) 是重言式;
  6. \(\varphi\) 是或然式当且仅当 \(\neg \varphi\) 是或然式。

练习 4.10 证明:对所有公式 \(\varphi\)

  1. \(\varphi\) 是重言式当且仅当 \(p_0 \lor \neg p_0\) 重言蕴涵 \(\varphi\).
  2. \(\varphi\) 是矛盾式当且仅当 \(\varphi\) 重言蕴涵 \(p_0 \land \neg p_0\).
练习 4.11 \(\mathfrak{s}^{\prime}\)\(\mathfrak{s}^{\prime \prime}\) 都是有穷代入。证明:\(\mathfrak{s}^{\prime}\mathfrak{s}^{\prime \prime}\) 也是有穷代入。
练习 4.12 \(\varphi\)\(\psi\) 为任意公式,并设 \(p\)\(q\) 为任意命题变号,其中 \(q\) 不在 \(\varphi\) 中出现。证明:\(\varphi(\psi / p)=\varphi(q / p)(\psi / q)\).
练习 4.13 证明:对所有公式 \(\varphi\) 及其子公式 \(\psi\),存在公式 \(\chi\) 和命题变号 \(p\) 使得 \(\varphi=\chi(\psi / p)\),并说明即使对同一个这样的 \(p\)\(\chi\) 也不是唯一的。
练习 4.14 \(\varnothing \neq A \subseteq \mathbf{Pr}\),设 \(\mathfrak{s}\)\(\mathfrak{s}^{\prime}\) 为任意代入,并设 \(\sigma\)\(\sigma^{\prime}\) 为任意真值指派,满足对每一个 \(p \in A,(\mathfrak{s}(p))^{\sigma}=\left(\mathfrak{s}^{\prime}(p)\right)^{\sigma^{\prime}}\). 证明:对所有 \(A\)-公式\(\varphi\)\((\varphi(\mathfrak{s}))^{\sigma}=(\varphi(\mathfrak{s}^{\prime}))^{\sigma^{\prime}}\).
练习 4.15 试从习题 3.13 直接证明定理 3.0(P.112)。
练习 4.16 试从定理 3.1 直接证明定理 3.0(P.112)。
练习 4.17 证明推论 3.4(P.114)(提示:先将置换结果讲清楚);然后试用推论 3.4 直接证明推论 3.3。
练习 4.18 \(\varphi\) 为重言式,并设 \(\mathfrak{s}\) 为任意代入。证明:\(\varphi(\mathfrak{s})\) 是重言式。
练习 4.19 运用重言蕴涵等语义概念的「严格定义」,证明习题 2.17(P.97)和习题 2.18(P.98)中的各个命题。
练习 4.20 完成命题 3.13(P.118)的证明。

练习 4.21 证明下列命题。设 \(\varphi\)\(\psi\) 为任意不含相同命题变号的公式。证明:

  1. \(\varphi \rightarrow \psi\) 是重言式当且仅当或者 \(\varphi\) 是矛盾式或者 \(\psi\) 是重言式。
  2. \(\varphi \leftrightarrow \psi\) 是重言式当且仅当或者 \(\varphi\)\(\psi\) 都是矛盾式或者 \(\varphi\)\(\psi\) 都是重言式。

练习 4.22 求下列公式的析取范式与合取范式:

  1. \(p \vee q \rightarrow p \wedge q\)
  2. \(p \wedge q \rightarrow(\neg r \rightarrow p)\)
  3. \((p \rightarrow q \wedge r) \rightarrow(\neg p \rightarrow \neg q \wedge \neg r)\)
  4. \((p \rightarrow q \vee \neg r) \leftrightarrow(r \rightarrow q \wedge \neg p)\)
  5. \(p \vee q \rightarrow(p \rightarrow \neg q)\)
  6. \((p \vee q) \wedge((r \rightarrow \neg p \wedge \neg q) \wedge(\neg r \rightarrow r))\)
  7. \((p \rightarrow \neg q \wedge r) \leftrightarrow(q \vee(\neg r \wedge p))\)
  8. \(((p \rightarrow q) \rightarrow p) \rightarrow q) \rightarrow r\)
练习 4.23 证明范式存在定理,即定理 3.2(P.120)和定理 3.3(P.121)
练习 4.24 证明:每个含 \(n\) 个命题变号 \(q_0, \cdots, q_{n-1}\)\(\mathscr{L}_0\)-公式都表达一个 \(n\) 元真值函数。
练习 4.25 \(\varphi\)\(\psi\) 为任意 \(\mathscr{L}_0\)-公式,其中出现的命题变号相同。证明:\(\varphi\)\(\psi\) 表达同一个真值函数当且仅当 \(\varphi\)\(\psi\) 重言等值。

练习 4.26 证明:对每个 \(\mathscr{L}_{\neg, \lor, \land}\)-公式 \(\varphi\), 1. 存在 \(\mathscr{L}_{\neg, \lor}\)-公式 \(\varphi^{\prime}\),使得 \(\varphi\)\(\varphi^{\prime}\) 重言等值并且 \(\varphi\)\(\varphi^{\prime}\) 含相同的命题变号。

  1. 存在 \(\mathscr{L}_{\neg, \land}\)-公式 \(\varphi^{\prime}\),使得 \(\varphi\)\(\varphi^{\prime}\) 重言等值并且 \(\varphi\)\(\varphi^{\prime}\) 含相同的命题变号。
  2. 存在 \(\mathscr{L}_{\neg, \rightarrow}\)-公式 \(\varphi^{\prime}\),使得 \(\varphi\)\(\varphi^{\prime}\) 重言等值并且 \(\varphi\)\(\varphi^{\prime}\) 含相同的命题变号。
练习 4.27 证明:用 \(\mid\) 定义 \(\rightarrow\)\(\land\),用 \(||\) 定义 \(\lor\)\(\rightarrow\),并证明 \(\lbrace \mid\rbrace\)\(\lbrace \|\rbrace\) 分别都是函数完全的。

练习 4.28 证明:\(\lbrace \neg \leftrightarrow\rbrace\) 不可定义 \(\lor\)\(\lbrace \neg \veebar\rbrace\) 不可定义 \(\land\),且 \(\lbrace \lor, \land, \rightarrow, \leftrightarrow\rbrace\) 不可定义 \(\neg\).

\(\mathbb{F}\) 为任意真值函数集合,并设 \(f\) 为任意真值函数。如果 \(f\) 可以由 \(\mathbb{F}\) 中的函数复合而成,我们就称 \(f\)\(\mathbb{F}\) 可定义的。下述习题的目的,是直接证明「函数版本」的函数完全性(见§3.5.0(P.122)开端处的说明)。这个证明应比 §3.5.1(P.124)中的证明「漂亮」,尽管思路可以差不多。熟悉函数复合的读者可以试做。

对每个自然数 \(n>0\),令 \(f_{\lor, n}\)\(n\) 元真值函数,使得对所有 \(a_{0}, \cdots, a_{n-1} \in\lbrace 0,1\rbrace\)\(f_{\lor, n}(a_{0}, \cdots, a_{n-1})=1\) 当且仅当 \(a_{0}, \cdots, a_{n-1}\) 中至少有一个是 1;并令 \(f_{\wedge, n}\)\(n\) 元真值函数,使得对所有 \(a_{0}, \cdots, a_{n-1} \in \lbrace 1, 0\rbrace\)\(f_{\wedge, n}(a_{0}, \cdots, a_{n-1})=1\) 当且仅当 \(a_{0}, \cdots, a_{n+1}\) 都是 1.
练习 4.29 \(\mathbb{F}=\lbrace f_{\neg}\rbrace \cup\lbrace f_{\vee, n}: n>0\rbrace \cup\lbrace f_{\wedge, n}: n>0\rbrace\). 证明:所有真值函数都是 \(\mathbb{F}\) 可定义的。

练习 4.30 证明:

  1. 所有真值函数都是 \(\lbrace f_{\neg}, f_{\lor}, f_{\wedge}\rbrace\)-可定义的;
  2. 所有真值函数都是 \(\lbrace f_{\neg}, f_{\lor}\rbrace\)-可定义的,都是 \(\lbrace f_{\neg}, f_{\wedge}\rbrace\)-可定义的,并且都是 \(\lbrace f_{\neg}, f_{\rightarrow}\rbrace\)-可定义的;
  3. 所有真值函数都是 \(\lbrace f_{\mid}\rbrace\)-可定义的,并且都是 \(\lbrace f_{\|}\rbrace\)-可定义的。



Editorial comments

有屁请在此处放,看看谁的屁更响。