在這一章裏，我們對命題邏輯的基本概念給出嚴格的表述，並對這些概念做進一步的討論和說明。

離開了證明就沒有當代邏輯。讀者從這一章起開始學習寫證明。無論讀者原來對證明是否陌生，也無論讀者是否認爲證明全不足道，若要想眞懂點邏輯而不只是侃點邏輯，那就不能繞過一個個定理及其證明。

眞值指派和公式的眞值

對象語言裏的符號和公式

邏輯學家們常喜歡不把對象語言明明白白地寫下來，而只是用我們熟悉的語言來描述它們。在§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}$ 上的（或命題變號的）「字典順序」或「字母表」。

賦值、眞、滿足關係

語言 $\mathscr{L}_{0}$ 的解釋叫做「眞值指派」（truth valuation, truth assignment）。

（$\mathbf{Pr}$ 中 $n$ 個命題的眞值指派組合類型共 ${\prod_{i=1}^{n}} (C_{2}^{1})_i = 2^{n}$ 種。）

確定公式眞值的這類定義通常被稱作「眞之定義（眞理定義）」（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.

由上述定義可知下列等值式成立：

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.$

§2.5（P.85）中引入的一些基本語義概念，都是用眞值表刻畫的。眞值表刻畫在某種程度上依賴於讀者對圖形的直觀。下面我們不借助這種直觀，僅僅運用眞值指派和滿足關係這些概念，對§2.5（P.85）中引入的基本語義概念進行嚴格的定義。

重言蘊涵、重言等值與可滿足性

「邏輯蘊涵」是邏輯學的核心觀念之一，我們將在後續章節中討論它，這裏先討論它在命題邏輯中的簡單形式——「重言蘊涵」。在不產生歧義時，我們將省略前綴 「$\mathscr{L}_0$-」。

重言蘊涵

在§2.5.1（P.87）中，$\lbrace \varphi_0,\cdots,\varphi_n \rbrace$ 重言蘊涵（tautologically implies） $\psi$ 當且僅當在 $\varphi_0,\cdots,\varphi_n$ 與 $\psi$ 的聯合眞值表中，沒有一行是 $\varphi_0,\cdots,\varphi_n$ 都眞而 $\psi$ 假。這是其聯合眞值表角度的定義。下面我們從賦值與滿足出發，重新嚴格刻畫重言蘊涵。

當 $\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.$

Note 3.0
定義 3.3 和§2.5.1（P.87）中重言蘊涵的眞值表刻畫有所不同。不同之處有以下兩點：

1. $\Gamma$ 在這裏可以是無窮集合，而在重言蘊涵等概念的眞值表刻畫中，$\Gamma$ 被限定爲有窮集合。
2. 眞值指派要對所有命題變號給出眞值，並且在定義重言蘊涵等語義概念時，定義涉及的眞值指派顯然有無窮多個；而用眞值表刻畫這些基本語義概念時，只需考慮給定公式中出現的有窮多個命題變號的眞假，而且這些命題變號的可能取值組合也只有有窮多個。

從現在起，讀者要學習證明。我們先證明一些簡單的命題，且給出的證明也儘量詳細。讀者應對照定義來閱讀以下的例子、命題及其證明，同時不要忽略本章後面的證明練習。

例 3.0
對所有公式 $\varphi$ 和 $\psi$，$\varphi \vee \psi, \neg \varphi \vDash_{0} \psi.$
證明：令 $\sigma$ 爲任意眞值指派。假設 $\sigma \vDash \varphi \lor \psi$ 且 $\sigma \vDash \neg \varphi$（以下證明 $\sigma \vDash \psi$）根據眞之定義，由假設 $\sigma \vDash \varphi \lor \psi$ 得知或者 $\sigma \vDash \varphi $或者 $\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.$ ▗

例 3.1
對所有公式 $\varphi, \psi$ 和 $\chi$，$\varphi \rightarrow \psi, \psi \rightarrow \chi \vDash_{0} \varphi \rightarrow \chi.$
證明：令 $\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.$ ▗

命題 3.0 之證明：對每個眞值指派 $\sigma$，如果 $\sigma \vDash \Gamma$，那麼根據定義 3.2，$\sigma$ 滿足 $\Gamma$ 中所有公式，由 $\varphi \in \Gamma$ 得到 $\sigma \vDash \varphi.$ 所以，根據重言蘊涵的定義，$\Gamma \vDash_{0} \varphi.$ ▗

命題 3.1 之證明：

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.$（「當且僅當」證法之例） ▗

命題 3.2 之證明：令 $\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 .$ ▗

重言等值

在§2.5.2（P.87）中，任意公式 $\varphi$ 與 $\psi$ 重言等值（tautologically equivalent） 當且僅當在 $\varphi$ 與 $\psi$ 聯合眞值表的任意一行中，$\varphi$ 與 $\psi$ 有同樣的眞值。其賦值視角的定義如下：

易見：如果 $\varphi$ 與 $\psi$ 重言等值，那麼對每個眞值指派 $\sigma$，$\sigma \vDash \varphi$ 當且僅當 $\sigma \vDash \psi;$ 反之亦然。

例 3.2
對任意公式 $\varphi$ 和 $\psi$，$\varphi \rightarrow \psi$ 與 $\neg\varphi \lor \psi$ 重言等值。
證明：令 $\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$ 重言等值。▗

例 3.3
對任意公式 $\varphi$ 和 $\psi$，$\varphi \leftrightarrow \psi$ 與 $(\varphi \land \psi) \lor (\neg\varphi \land \neg\psi)$ 重言等值。
證明：令 $\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)$ 重言等值。 ▗

命題 3.3 之證明：設 $\Gamma \vDash_{0} \varphi$ 並且 $\varphi$ 與 $\psi$ 重言等值。令 $\sigma$ 爲任意眞值指派。如果 $\sigma \vDash \Gamma$，那麼由 $\Gamma \vDash_{0} \varphi$ 和重言蘊涵的定義得知 $\sigma \vDash \varphi$，再由重言等值的定義得到 $\sigma \vDash \psi.$ 所以，再根據重言蘊涵定義，$\Gamma \vDash_{0} \psi.$ ▗

命題 3.4 之證明：設 $\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.$ 根據此假設和重言蘊涵的定義，

（i）對每個眞值指派 $\sigma_1$，如果 $\sigma_1 \vDash \varphi$ 則 $\sigma_1 \vDash \psi.$

（ii）對每個眞值指派 $\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$ 重言等值。▗

可滿足性

在§2.5.3（P.88）中，從聯合眞值表角度看，任意有窮公式集 $\Gamma$ 可滿足（satisfiable）當且僅當 $\Gamma$ 中公式的聯合眞值表中存在某一行，在該行裏 $\Gamma$ 中的公式的眞值都是 1. 下面我們從賦值與滿足出發，重新嚴格刻畫重言蘊涵。

Note 3.1 與注 3.0（P.101）中提到的情況類似，定義 3.4 和定義 3.5 不同於§2.5.2（P.87）和§2.5.3（P.88）中重言等值和可滿足性的真值表刻畫。關於重言等值，其定義和真值表刻畫的不同是注 3.0 中講的第二點；而關於可滿足性，其定義和真值表刻畫的不同是注 3.0 中講的兩點。

例 3.4
設 $\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$ 可滿足。
證明：令 $\sigma$ 爲如下定義的眞值指派：

（i） $\sigma(p)=\sigma(r)=\sigma(s)=\sigma(r^{\prime})=1$

（ii）$\sigma(q)=\sigma(s^{\prime})=0$

（iii）對所有與 $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}.$ 所以 $ \sigma \vDash s^{\prime} \leftrightarrow(\neg q \rightarrow \neg s).$

綜上所述， $\sigma \vDash \Gamma.$ ▗

例 3.5
設 $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$ 可滿足。

證明：令 $\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.$ ▗

命題 3.5 之證明：假設 $\Gamma$ 不可滿足且令 $\varphi$ 爲任意公式。假如 $\Gamma \nvDash_{0} \varphi$，那麼就存在眞值指派 $\sigma$ 使得 $\sigma \vDash \Gamma$ 且 $\sigma \nvDash \varphi$，但這是不可能的，因爲 $\Gamma$ 不可滿足。▗

命題 3.6 之證明：只證第一部分。設 $\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$ 不可滿足。 ▗

重言式、矛盾式與或然式

在§2.5.4（P.88）中，重言式、矛盾式與或然式曾被以眞值表的方式刻畫，下面從賦值角度嚴格刻畫這組概念。

Note 3.2 與重言蘊涵、重言等值和可滿足性等概念的情況類似，定義 3.6-3.8 有別於§2.5.4（P.88）中對重言式等概念的眞值表刻畫：眞值指派要對所有命題變號給出眞值，並且重言式等的定義涉及的眞值指派顯然有無窮多個；這些概念的眞值表刻畫卻不同，它們只考慮公式中出現的有窮多個命題變號的眞假，而這些命題變號的可能取值組合也只有有窮多個。

例 3.6
對任意公式 $\varphi$，$\varphi \lor \varphi \rightarrow \varphi$ 是重言式。
證明：令 $\sigma$ 爲任意眞值指派。如果 $\sigma \vDash \varphi \lor \varphi$，那麼根據眞理定義，$\sigma \vDash \varphi$，進而 $\sigma \vDash \varphi \lor \varphi \rightarrow \varphi.$ 由重言式的定義知，$\varphi \lor \varphi \rightarrow \varphi$ 是重言式。▗

例 3.7
對任意公式 $\varphi, \psi$，$\neg(\varphi \rightarrow \psi) \rightarrow \varphi \land \neg \psi$ 是重言式。
證明：令 $\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$ 是重言式。▗

例 3.8
對任意公式 $\varphi$ 和 $\psi$，$\varphi \land \neg (\varphi \lor \psi)$ 是矛盾式。
證明：令 $\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)$ 是矛盾式。▗

例 3.9
對任意公式 $\varphi$，$\neg(\varphi \rightarrow \neg (\varphi \rightarrow \neg\varphi))$ 是矛盾式。
證明：令 $\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))$ 是矛盾式。▗

例 3.10
對所有不同的命題變號 $p$ 和 $q$，$p \land \neg q$ 是或然式。
證明：令 $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$ 是或然式。 ▗

例 3.11
對所有不同的命題變號 $p$ 和 $q$，$p \rightarrow \neg q$ 是或然式。
證明：令 $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$ 是或然式。 ▗

下列命題是對上述概念的簡單運用。以下僅列出部分命題的證明，剩餘的命題證明留作習題。

命題 3.8 第二條的歸納證明中，歸納假設是：

對所有的 $\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).$

基本語義概念的簡單應用就講這些，希望讀者完成本章後面的證明練習。做證明可幫助讀者準確地理解和掌握上述基本語義概念，更可以幫助培養準確表達思想和仔細推敲論據的習慣。

代入

代入（substitution）是對公式做變形處理的一種方式。在本書的命題邏輯範圍內，「代入」總是指對命題變號的代入。

關於代入的直觀說明

令 $\varphi$ 和 $\psi$ 爲任意公式，$p$ 爲任意命題變項。所謂用 $\psi$ 代入 $\varphi$ 中的 $p$，是指用 $\psi$ 替換 $p$ 在 $\varphi$ 中的每一處出現，其結果記爲 $\varphi(\psi/p).$\footnote{出現可以嚴格定義。另外，在這裏記爲 $\varphi(\psi/p)$的，在有些作者那裏記爲 $\varphi(p/\psi).$ 注意 $p$ 和 $\psi$ 的位置在兩種記法中正好相反。這兩種記法各有好處，我們這裏的選擇根據僅僅是習慣。}

例 3.12
令 $\varphi_{0}=q \rightarrow r, \varphi_{1}=p \vee r $ 且 $\varphi_{2}=p \rightarrow \neg p \vee q.$ 則有：

1. $\varphi_{0}(q / p)=q \rightarrow r$
2. $\varphi_{1}(q / p)=q \vee r$
3. $\varphi_{2}(q / p)=q \rightarrow \neg q \vee q$
4. $\varphi_{2}(\neg p / p)=\neg p \rightarrow \neg \neg p \vee q$
5. $\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$
2. $\varphi(p \wedge q / p, p / q)=p \wedge q \rightarrow \neg(p \wedge q) \wedge p$
3. $\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$）而得到的。可見，同時代入的結果和先後代入的結果是不同的。

代入的定義

如果我們只考慮具體的代入操作，那麼關於代入的上述說明差不多已經夠了，但這個說明顯然不夠嚴格。我們約定：在無特別說明時，我們用不同的符號表示不同的命題變號。代入的嚴格定義如下：

爲簡化敍述，定義 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}).$

如果換個方式來講定義 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_{0}(\mathfrak{s}{0}), \varphi{1}(\mathfrak{s}{0}), \varphi{2}(\mathfrak{s}{0}), \varphi{2}(\mathfrak{s}{1}) $ 和 $\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 正是對這種直觀說法的一個準確表述。

命題 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 是如何把「有關」和「無關」這種模糊說法改進爲準確的說法的？注意這類問題一定有好處。）▗

上述證明中用到了基於公式複雜度的歸納證明方法。

要想說明上面那個直觀想法的正確性，前提是對「有關」「無關」等做出清楚而準確的刻畫。很多學生善於聯想和發揮，卻不善於清楚和準確。清楚和準確往往不易做到，有時甚至不必要。但如果想把能講好的道理講好，首先要有把想法講清楚講準確的本領。倘若一個理論中的每個命題都「本身就是說不清的」，那它也就沒什麼道理好講。當然，清楚和準確只是做好理論工作的必要條件，不是充分條件。

代入的複合

這裏的名稱和記法（稍有改動）來自 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$，而這個代入正是前兩個代入的複合。

這個猜想的確是眞的。

讀過「關於代入的直觀說明」（§3.2.0（P.107）），一般人就明白如何做代入，即「會做」了。爲什麼還要談代入的嚴格定義甚至代入的複合呢？千萬不要因爲這些是「末節」或「小技」就不屑一顧。正是這種「末節」和「小技」的積累，使人們能超越「會做」而進入對深層問題的討論。試想：假如對代入的理解僅停留在「會做」的水平，那麼我們如何證明「多次代入的結果都可通過一次代入得到」這個猜想呢？現在用「末節」和「小技」得到的這個結論，以後可以用於解決更深更難的問題。

代入的語義性質

這裏我們討論公式的不同代入結果在眞值指派下的值，比如說，$\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)。下面幾個命題說的正是這類事，不過比這更一般。

證明：令 $\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}$ 且 $\varphi(\mathfrak{s}^{\prime})=\chi_{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 \vDash \lambda(\mathfrak{s})$ 當且僅當 $\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}).$ ▗

證明：設 $\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 \vDash \varphi(\mathfrak{s}) $ 當且僅當 $\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}$ 的命題變號，是因爲它涉及的眞值指派只有一個。

證明：設 $\varphi$ 爲任意公式，$q_{0}, \cdots, q_{n}$ 爲任意命題變號，並設 $r_{1}, \cdots, r_{m}(m \geqslant 0) $ 爲 $\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})$ 而 $\varphi(\chi_{0} / q_{0}, \cdots, \chi_{n} / q_{n}, r_{1} / r_{1}, \cdots, 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}).$ ▗

最後，我們來看關於「置換」的語義定理。

證明：設 $\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）:

當 $\Gamma=\varnothing$ 時，上述推論成爲：

推論 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}$ 來自式 (\ref{eq:dairu-tuilun-3.5})

\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^{})$ 重言等值。我們由式 (\ref{eq:dairu-tuilun-3.7})知道，這就是在說 $\varphi$ 與 $\varphi_{0}^{\prime}, \varphi_{1}^{\prime}$ 和 $\varphi_{2}^{\prime}$ 都重言等值，與前面由推論 3.5 得出的結論完全一樣。

注意，推論 3.5 是「等值置換」語義形式的常見說法，而推論 3.3-3.4 在應用方面比推論 3.5 更方便。

眞值指派與眞值表

我們對重言蘊涵和重言式等概念曾給出兩個不同的說明：一個是§2.5（P.85） 中的眞值表刻畫，另一個是在§3.1（P.101）中用眞值指派給出的定義。爲避免混淆，我們用這些概念的「嚴格定義」來指§3.1（P.101）中的定義，用這些概念的「眞值表刻畫」指§2.5（P.85）中的說明。這一節我們討論的主要內容是這些概念的嚴格定義和眞值表刻畫的等價性。

從這一節起，我們將較多地使用眞值函數這個概念。

眞值函數

前面說過，眞值函數是從眞值集到眞值集的函數，而且眞值函數聯結詞就是以眞值函數爲其解釋的聯結詞。第一點很容易理解，但第二點也許不太明顯，我們先對它做一點說明。

顯然，下列函數都是眞值函數（其中 $x, y \in \lbrace 1,0\rbrace$）：

事實上，用眞值指派 $\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$ 個，這裏自然畫不下它們的眞值表。

對部分命題變號的賦值

爲了便於討論，我們引入另一種賦值概念。這種賦值很像是眞值指派，不過它只對給定的部分命題變號指派了眞值，而對其他命題變號（如果有的話）沒做任何指派。

對每個命題變號的非空集合 $A$ 我們定義「$A$-公式」和「$A$-賦值」如下。（「$A$-公式」和「$A$-賦值」等都不是流行的術語。）

這裏對命題變號集 $A$ 的限制只是「非空」，從而 $A$ 可以是有窮集也可以是無窮集，甚至可以就是 $\mathbf{Pr}$（由此可知，眞值指派都是 $\mathbf{Pr}$-賦值）。但是，如果 $A \ne \mathbf{Pr}$，我們把賦值稱作對部分命題變號的賦值。下面是關於這個概念的一個有用事實：如果 $A$ 是出現在某個眞值表中的所有命題變號的集合，那麼該表中命題變號的每一個可能取值組合就是一個 $A$-賦值。（參見§2.4.2（P.84）關於命題變號的可能取值組合的討論。）

對比定義 3.14 和式 3.13 後很容易看出，$A$-賦值只給出 $A$-公式的眞值，而眞值指派給出所有 $\mathscr{L}_0$-公式的眞值，但僅就 $A$-公式來說，這兩個定義確定公式眞值的方法是完全一樣的。

兩種描述方式的等價性

重言蘊涵等概念的嚴格定義和它們的眞值表刻畫有明顯的區別。比如說重言式，按照它的嚴格定義，一公式是否重言式的問題涉及無窮多眞值指派，每個眞值指派又涉及無窮多命題變號的眞值；而按照它的眞值表刻畫，一公式是否重言式的問題，卻只涉及某個有窮的命題變號集合 $A$ 和有窮多個 $A$-賦值。儘管如此，「嚴格定義」和「眞值表刻畫」在下述意義上是等價的：滿足「嚴格定義」的一定滿足「眞值表刻畫」，而滿足「眞值表刻畫」的也一定滿足「嚴格定義」。下面我們提供這種等價性的證明。

藉助直觀，人們會有以下猜測：

一個公式 $\varphi$ 在一眞值指派 $\sigma$ 下的值，應只與 $\sigma$ 指派給 $\varphi$ 中出現的命題變號的值有關，或者說，與 $\sigma$ 指派給其他命題變號的值無關。

運用 $A$-賦值的概念，我們可以將上述猜測表述爲下述命題。

證明：施歸納於公式的複雜度，我們證明對每個 $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$-賦值這一概念。如果不用這個概念，我們可以將前述猜測表述爲下述命題。

證明：令 $\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，可以輕鬆地證明下述命題，其中的「重言蘊涵」和「重言式」等，都是在「嚴格定義」的意義上使用的。

證明：我們證明：$\Gamma \nvDash_{0} \varphi$ 當且僅當存在一個 $A$-賦值 $\tau$ 使得 $\tau \vDash \Gamma$ 且 $
\tau \nvDash \varphi.$ 設 $\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）

證明：根據命題 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.$ ▗

命題 \ref{prop:104-in-p96} 中的另外兩條留作練習（見習題 3.20）

範式

範式是具有某種特殊形式的公式，這種特殊形式幫助我們認識公式的一些性質和關係，而且在機器證明中也有應用。

合取範式

一個公式是合取範式（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$
2. $\neg p \vee q$
3. $q \vee \neg p$
4. $\neg p \vee \neg q \vee r$
5. $p \wedge q \wedge r$
6. $(\neg p \vee \neg r) \wedge(\neg q \vee \neg r)$

易見：不同的公式可以有相同的合取範式，而同一個公式也可以有不同的合取範式。

析取範式

—個公式是析取範式（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})$ 都或是命題變號，或是命題變號的否定。粗略地說，析取範式是個析取式，而其析取支都是命題變號或其否定的合取式。\footnote{\textcite{wang-1981-PopularLecturesMathematical}中把命題變號或其否定的合取式稱作「簡單合取」。}對所有公式 $\varphi$ 和 $\psi$，$\psi$ 是 $\varphi$ 的析取範式當且僅當下列條件成立：

1. $\psi$ 是析取範式，
2. $\psi$ 與 $\varphi$ 重言等值。

例 3.22 下列公式都是析取範式

1. $p$
2. $\neg p \lor q$
3. $p \land \neg q \land r \land \neg p$
4. $(p \lor \neg q) \lor \neg p$
5. $(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$
2. $\neg p \vee q$
3. $q \vee \neg p$
4. $\neg p \vee \neg q \vee r$
5. $p \wedge q \wedge r$
6. $(\neg p \land \neg r) \lor \neg r$

易見：不同的公式可以有相同的析取範式，而同一個公式也可以有不同的析取範式。比較例 3.20 和例 3.22 以及例 3.21 和例 3.23，可知一個公式的析取範式與它的合取範式也可以是同一個公式。讀者應對照定義，檢查上述例子中的合取範式和析取範式，以求準確把握範式的概念。

範式定理

由於範式在形式方面的特點，很多時候處理範式比處理一般公式要容易。比如，要確定一個合取範式 $\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。

如果每個公式都有它的合取範式和析取範式，那麼很多關於公式的問題就可以歸結爲範式的問題，從而降低解決這些問題的難度。事實上，每一個公式都既有它的合取範式也有它的析取範式。我們先來看公式的析取範式的存在問題。

這個命題有時被稱作析取範式存在定理。我們這裏不做嚴格的證明，只給出找到任給公式的析取範式的一個方法。對證明有興趣的讀者可以參照命題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 \leqslant 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$ 的一個析取範式。

下面我們來看公式的合取範式的存在問題。

這個命題有時被稱作合取範式存在定理。與上述類似，我們這裏不做嚴格的證明，只給出找到任給公式的合取範式的一個方法。（參見習題 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$ 的一個析取範式。

在上面講解公式的範式存在問題時，我們使用了眞值表方法，即語義的方法。假如我們求公式的範式僅僅是要判斷給定公式是否重言式（或矛盾式），那麼用上述方法求範式無疑是事倍功半。這是因爲，在寫出給定公式的範式之前，我們先構造了該公式的眞值表，而從這個眞值表我們已經知道該公式是否重言式（或矛盾式）。不過，上面的講解只是說明任何公式都存在合取範式和析取範式，而且只是用我們已經學會的眞值表方法。事實上，求範式的方法不僅是語義的方法，而範式的存在問題也並不就是判斷重言式或矛盾式的問題。

函數完全性

眞值函數在形式語言中的表達

顯然，眞值函數可以有無窮多。在如此多的函數中，有些明顯可以用其他眞值函數來合成或複合（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）中的說明。）

注意：定義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}$-公式對眞值函數的「表達」和「函數完全性」的定義如下：

注意：我們並沒有像本節一開始談論的那樣，把可以合成所有眞值函數的眞值函數集定義爲函數完全的。定義 3.17 中既沒有談眞值函數的集合，也沒有談眞值函數的合成——它談的是眞值函數聯結詞的集合以及眞值函數在有這些聯結詞的語言裏的表達。但這兩種談法的結果是一樣的，雖然我們不做證明。

如果一集眞值函數聯結詞 $\mathbb{C}$ 有函數完全性，那麼用 $\mathbb{C}$ 做初始聯結詞的命題邏輯語言就有了完善的表達力。在這樣的語言中，任何一個眞值函數聯結詞都可以由 $\mathbb{C}$ 中的聯結詞來定義，就像任何一個眞值函數都可以由解釋 $\mathbb{C}$ 中聯結詞的眞值函數來定義一樣。

具有函數完全性的幾組眞值函數聯結詞

這一小節裏我們討論具有函數完全性的幾個眞值函數聯結詞的集合。

命題 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}$ 中可表達。▗

證明：易證對所有 $\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}$ 中可表達。▗

證明：根據定理 3.5、定義 3.17 和定義 3.18 得證。▗

函數完全的眞值函數聯結詞的集合，可以只有兩個元素，比如 $\lbrace \neg, \lor\rbrace$，也可以只有一個元素。英文中有兩個一元聯結詞 “not-both”（NAND） 和 “neither-nor”（NOR），我們用 “$\mid$” 和 “$\mid\mid$” 來表示它們。算上 $\veebar$ 與這兩個聯結詞，基本眞值表 2.1（P.82）便成爲如下擴展的眞值表：

可以證明，$\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} $$

本章習題

習題 3.0：證明：對所有公式集 $\Gamma$ 和 $\Delta$，以及所有公式 $\phi$ 與 $\psi$，

1. 如果 $\Gamma \vDash_{0} \phi$，那麼 $\Gamma \cup \Delta \vDash_{0} \phi$;
2. 如果 $\Gamma \vDash_{0} \phi \vee \psi$ 並且 $\Delta \vDash_{0} \neg \phi$，那麼 $\Gamma \cup \Delta \vDash_{0} \psi$;
3. 如果 $\Gamma \vDash_{0} \phi$　且 $\Delta \vDash_{0} \phi \rightarrow \psi$，那麼 $\Gamma \cup \Delta \vDash_{0} \psi$.

習題 3.1
設 $\Delta \vDash_{0} \phi$ 並且 $\phi \vDash_{0} \psi$. 證明：$\Delta \vDash_{0} \psi$.

習題 3.2 證明對所有公式 $\phi, \psi, \chi$，下述命題成立：

1. $\phi, \phi \rightarrow \psi \vDash_{0} \psi$
2. $\phi \vee \psi, \neg \psi \vDash_{0} \phi$
3. $\phi \vee \psi, \neg \phi \vee \chi \vDash_{0} \psi \vee \chi$
4. $\phi \vee \psi \vDash_{0} \chi$ 當且僅當 $\phi \vDash_{0} \chi$ 且 $\psi \vDash_{0} \chi$.

習題 3.3 令 $\phi, \psi, \chi$ 爲任意公式。證明下列都是重言式：

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

習題 3.4 令 $\phi, \psi, \chi$ 爲任意公式。證明下列都是重言式：

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

習題 3.5 證明對所有公式 $\phi, \psi, \chi$，下列各組公式都是重言等值的：

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

習題 3.6 證明：對所有公式集 $\Gamma$ 和所有公式 $\phi$，

1. 如果 $\Gamma \vDash_{0} \phi$ 且 $\phi$不可滿足，那麼 $\Gamma$ 不可滿足。
2. 如果 $\Gamma$ 可滿足，那麼 $\lbrace \psi: \Gamma \vDash_{0} \psi\rbrace$ 也可滿足。

習題 3.7
完成命題 3.7（P.105）的證明。

習題 3.8 證明：對所有公式 $\phi$，

1. $\phi$ 是重言式當且僅當 $\neg \phi$ 不可滿足；
2. $\phi$ 是矛盾式當且僅當 $\phi$ 不可滿足；
3. $\phi$ 是或然式當且僅當 $\phi$ 和 $\neg \phi$ 都可滿足；
4. $\phi$ 是重言式當且僅當 $\neg \phi$ 是矛盾式；
5. $\phi$ 是矛盾式當且僅當 $\neg \phi$ 是重言式；
6. $\phi$ 是或然式當且僅當 $\neg \phi$ 是或然式。

習題 3.9 證明：對所有公式 $\phi$，

1. $\phi$ 是重言式當且僅當 $p_0 \lor \neg p_0$ 重言蘊涵 $\phi$.
2. $\phi$ 是矛盾式當且僅當 $\phi$ 重言蘊涵 $p_0 \land \neg p_0$.

習題 3.10
設 $\mathfrak{s}^{\prime}$ 和 $\mathfrak{s}^{\prime \prime}$ 都是有窮代入。證明：$\mathfrak{s}^{\prime}\mathfrak{s}^{\prime \prime}$ 也是有窮代入。

習題 3.11
設 $\phi$ 和 $\psi$ 爲任意公式，並設 $p$ 和 $q$ 爲任意命題變號，其中 $q$ 不在 $\phi$ 中出現。證明：$\phi(\psi / p)=\phi(q / p)(\psi / q)$.

習題 3.12
證明：對所有公式 $\phi$ 及其子公式 $\psi$，存在公式 $\chi$ 和命題變號 $p$ 使得 $\phi=\chi(\psi / p)$，並說明即使對同一個這樣的 $p$，$\chi$ 也不是唯一的。

習題 3.13
設 $\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$-公式$\phi$，$(\phi(\mathfrak{s}))^{\sigma}=(\phi(\mathfrak{s}^{\prime}))^{\sigma^{\prime}}$.

習題 3.14
試從習題 3.13 直接證明定理 3.0（P.112）。

習題 3.15
試從定理 3.1 直接證明定理 3.0（P.112）。

習題 3.16
證明推論 3.4（P.114）（提示：先將置換結果講清楚）；然後試用推論 3.4 直接證明推論 3.3。

習題 3.17
設 $\phi$ 爲重言式，並設 $\mathfrak{s}$ 爲任意代入。證明：$\phi(\mathfrak{s})$ 是重言式。

習題 3.18
運用重言蘊涵等語義概念的「嚴格定義」，證明習題 2.17（P.97）和習題 2.18（P.98）中的各個命題。

習題 3.19
完成命題 3.13（P.118）的證明

習題 3.20 證明下列命題：

習題 3.21 求下列公式的析取範式與合取範式：

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$

習題 3.22
證明範式存在定理，卽定理 3.2（P.120）和定理 3.3（P.121）

習題 3.23
證明：每個含 $n$ 個命題變號 $q_0, \cdots, q_{n-1}$ 的 $\mathscr{L}_0$-公式都表達一個 $n$ 元眞值函數。

習題 3.24
設 $\phi$ 和 $\psi$ 爲任意 $\mathscr{L}_0$-公式，其中出現的命題變號相同。證明：$\phi$ 與 $\psi$ 表達同一個眞值函數當且僅當 $\phi$ 與 $\psi$ 重言等值。

習題 3.25
證明：對每個 $\mathscr{L}_{\neg, \lor, \land}$-公式 $\phi$，

1. 存在 $\mathscr{L}_{\neg, \lor}$-公式 $\phi^{\prime}$，使得 $\phi$ 與 $\phi^{\prime}$ 重言等值並且 $\phi$ 與 $\phi^{\prime}$ 含相同的命題變號。
2. 存在 $\mathscr{L}_{\neg, \land}$-公式 $\phi^{\prime}$，使得 $\phi$ 與 $\phi^{\prime}$ 重言等值並且 $\phi$ 與 $\phi^{\prime}$ 含相同的命題變號。
3. 存在 $\mathscr{L}_{\neg, \rightarrow}$-公式 $\phi^{\prime}$，使得 $\phi$ 與 $\phi^{\prime}$ 重言等值並且 $\phi$ 與 $\phi^{\prime}$ 含相同的命題變號。

習題 3.26
證明：用 $\mid$ 定義 $\rightarrow$ 和 $\land$，用 $||$ 定義 $\lor$ 和 $\rightarrow$，並證明 $\lbrace \mid\rbrace$ 和 $\lbrace |\rbrace$ 分別都是函數完全的。

習題 3.27
證明：$\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.

習題 3.28
令 $\mathbb{F}=\lbrace f_{\neg}\rbrace \cup\lbrace f_{\vee, n}: n>0\rbrace \cup\lbrace f_{\wedge, n}: n>0\rbrace$. 證明：所有眞值函數都是 $\mathbb{F}$ 可定義的。

習題 3.29 證明：

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$-可定義的。

The article was recently updated on Saturday, March 18, 2023, 14:28:49 by 王小花.