數學證明/邏輯

正如在引言中討論的那樣，邏輯語句不同於普通英語。 我們將討論“或”、“與”、“如果”、“僅當”之類的概念。（在這裡我想指出，在大多數數學論文中，在指代自己時使用“我們”是可以接受的。這被認為是禮貌的，既不會命令聽眾做某事，也不會將他們排除在討論之外。）

真值和語句

我們在數學中經常遇到語句。

定義。 (語句) 一個語句 是一個陳述句，要麼是真要麼是假（但不能兩者兼而有之），它的真值 是真（用$T$ 表示）或假（用$F$ 表示）。

例子。 考慮以下句子

1. 數字 9 是偶數。
2. $1<2$.
3. 數學很容易。
4. 如何解$x^{2}+2x-3=0$?
5. 請閱讀這本書。

• 上面 1 和 2 句是語句（即使 1 句是假的）。
• 3、4 和 5 句不是語句，因為它們不是陳述句，我們無法確定它們是真是假。

• 特別是，3 句是觀點，4 句是問題，5 句是命令。因此，它們都不是陳述句。

練習。

句子“$\pi$的小數展開式中第 123 位是 3”是一個語句嗎？

	是。
	否。

對於那些不是語句的句子，其中有一種特殊的句子型別，即開放語句。

定義。 (開放語句) 一個開放語句 是一個句子的真值取決於某些變數的輸入。

備註。

• 由於真值可能會隨著輸入的改變而改變，因此我們無法確定開放語句的真值（我們不能說它總是真或總是假）。

例子。 考慮句子$P(x):x=2$ ($:$ 讀作“使得”）。

• 當$x=2$時，該句子為真，否則為假。
• 該句子是一個開放語句。

為了表示一些語句真值的所有可能組合，我們通常將它們列在一個表中，稱為真值表。

示例.（兩個命題的真值表）對於兩個命題 $P$ 和 $Q$，它們的真值表如下：$${\begin{array}{|c|c|}P&Q\\\hline T&T\\T&F\\F&T\\F&F\\\end{array}}$$，$P$ 和 $Q$ 的真值共有四種可能的組合。

示例.（三個命題的真值表）對於三個命題 $P$，$Q$ 和 $R$，它們的真值表如下：$${\begin{array}{|c|c|c|}P&Q&R\\\hline T&T&T\\T&T&F\\T&F&T\\T&F&F\\F&T&T\\F&T&F\\F&F&T\\F&F&F\\\end{array}}$$，$P$，$Q$ 和 $R$ 的真值共有八種可能的組合。

備註。

• 一般來說，$\underbrace {2\times \dotsb \times 2} _{n{\text{ times}}}=2^{n}$ 種可能的 $n$ 個命題的真值組合，因為每個命題都有兩種可能的真值。
• 三個命題的真值表看起來可能很複雜，如果你不夠小心，可能會遺漏（或重複）真值表中的一些組合。因此，這裡有一些構建這種真值表的建議：

• 對於 $P$，從上到下寫四個 $T$，然後是四個 $F$；
• 對於 $Q$，從上到下寫以下模式：$TTFFTTFF$；
• 對於 $R$，從上到下以這種模式書寫：$TFTFTFTF$.

合取、析取和否定

在本節中，我們將討論一些將兩個語句合併成一個語句的方法（合取和析取），類似於 數學證明/集合論導論#集合運算，其中兩個集合被合併成一個集合。此外，我們還將討論一種將語句更改為另一個語句的方法（否定）。

合取

定義。 （合取）語句 $P$ 和 $Q$ 的 合取，記為 $P\land Q$，是一個當 兩個 $P$ 和 $Q$ 都為真時為真，否則為假。

備註。

• $P\land Q$ 讀作 "P 且 Q"，語句 $P$ 和 $Q$ 的合取也可以直接用 "$P$ 且 $Q$" 來表達。

示例。 （$P\land Q$ 的真值表）$P\land Q$ 的真值表（根據 $P$ 和 $Q$ 的真值可能組合表示）為 $${\begin{array}{|c|c|c|}P&Q&P\land Q\\\hline T&T&T\\T&F&F\\F&T&F\\F&F&F\\\end{array}}$$

• 我們可以看到，$P\land Q$ 只有當 同時 $P$ 和 $Q$ 都為真時才為真，否則為假。

析取

定義. (析取) 語句 $P$ 和 $Q$ 的 析取，記作 $P\lor Q$，是一個語句，只有當 同時 $P$ 和 $Q$ 都為假時才為假，否則為真。

備註。

• 也就是說，$P\lor Q$ 當 至少 $P$ 和 $Q$ 之一為真時才為真，否則為假。
• $P\lor Q$ 讀作 "P 或 Q"，語句 $P$ 和 $Q$ 的析取也可以直接用 "$P$ 或 $Q$" 來表達。
• "或" 在數學中的含義可能與 "或" 作為英語單詞的含義不同。在數學中，"或" 是 包含性 的，即 $P$ 或 $Q$ 表示 $P$ 或 $Q$ 或兩者都成立。然而，作為英語單詞，"或" 可能是 排斥性 的，即 $P$ 或 $Q$ 表示 $P$ 或 $Q$ 但不能兩者都成立。例如，當有人說 "我今天下午要去圖書館或去公園" 時，我們理解為 "我要麼去圖書館，要麼去公園，但不能兩者都去"。

示例。 ($P\lor Q$ 的真值表) $P\lor Q$ 的真值表是 $${\begin{array}{|c|c|c|}P&Q&P\lor Q\\\hline T&T&T\\T&F&T\\F&T&T\\F&F&F\\\end{array}}$$

• 我們可以看到，$P\lor Q$ 只有當 兩者 $P$ 和 $Q$ 都為假時才為假，其他情況都為真。

否定

定義。 語句 $P$ 的 否定，記為 $\sim P$，是一個真值與 $P$ 相反的語句。

備註。

• $~P$ 讀作 "非 P"，語句 $P$ 的否定也可以直接用 "非 $P$" 或 "不是 $P$" 來表達。
• 語句 $P$ 否定的另一種常用記法是 $\lnot P$。
• 我們將表達語句否定的過程稱為 否定 語句。

示例。 ($\sim P$ 的真值表) $\sim P$ 的真值表是 $${\begin{array}{|c|c|}P&\sim P\\\hline T&F\\F&T\\\end{array}}$$

• 我們可以看到，$\sim P$ 的真值總是與 $P$ 相反。

要否定一個陳述，我們通常會在陳述中新增“不”字，或從陳述中刪除“不”字。例如，陳述“數字 4 是偶數。”的否定是“數字 4 不是 偶數。”，而陳述“數字 1 不是質數。”的否定是“數字 1 不是 質數。”

練習。 完成以下真值表：$${\begin{array}{|c|c|c|c|c|c|}P&Q&\sim P&\sim Q&P\lor Q&(\sim P)\lor (\sim Q)&\sim (P\lor Q)\\\hline T&T\\T&F\\F&T\\F&F\\\end{array}}$$

答案

$${\begin{array}{|c|c|c|c|c|c|}P&Q&\sim P&\sim Q&P\lor Q&(\sim P)\lor (\sim Q)&\sim (P\lor Q)\\\hline T&T&{\color {red}F}&{\color {red}F}&{\color {red}T}&{\color {red}F}&{\color {red}F}\\T&F&{\color {red}F}&{\color {red}T}&{\color {red}T}&{\color {red}T}&{\color {red}F}\\F&T&{\color {red}T}&{\color {red}F}&{\color {red}T}&{\color {red}T}&{\color {red}F}\\F&F&{\color {red}T}&{\color {red}T}&{\color {red}F}&{\color {red}T}&{\color {red}T}\\\end{array}}$$

• 我們可以觀察到，在一些$P$和$Q$的真值組合中，$(\sim P)\lor (\sim Q)$和$\sim (P\lor Q)$的真值是不同的。

練習。 令$P$為陳述“數字 3 是偶數”，而$Q$為陳述“數字${\sqrt {2}}$是無理數。”

寫下（用文字）$P$和$Q$的每個否定的形式 不要使用“不”字。

答案

• 對 $P$ 的否定可以是“數字 3 是奇數”。
• 對 $Q$ 的否定可以是“數字 ${\sqrt {2}}$ 是有理數”。

練習。 令 $P$ 為語句 $3>5.$，$Q$ 為語句 $3<2.$。

(a) 語句 $\sim (P\land Q)$ 為真還是假？

(b) 語句 $\sim (P\lor Q)$ 為真還是假？

(c) 語句 $(\sim P)\land (\sim Q)$ 為真還是假？

(d) 語句 $(\sim P)\lor (\sim Q)$ 為真還是假？

答案

• 首先，我們可以看到 $P$ 和 $Q$ 都是假命題。

(a) 由於 $P\land Q$ 是假命題，答案為 真。

(b) 由於 $P\lor Q$ 是假命題，答案為 真。

(c),(d) 由於 $\sim P$ 和 $\sim Q$ 都是真命題，(c) 和 (d) 的答案都是 真。

條件句

除了以上幾種構成新語句的方式之外，我們還有一種非常常見的構成方式，即“如果-那麼組合”。使用“如果-那麼組合”構成的語句被稱為條件句。

定義。 (條件語句) 兩個語句 $P$ 和 $Q$ 的 條件語句 是指“如果 $P$ 那麼 $Q$”，記作 $P\to Q$。 $P$ 和 $Q$ 分別被稱為條件語句的 假設 和 結論。 條件語句 $P\to Q$ 當 $P$ 為真而 $Q$ 為假時為 假，其他情況下為 真。

示例。 ($P\to Q$ 的真值表) $P\to Q$ 的真值表為 $${\begin{array}{|c|c|c|}P&Q&P\to Q\\\hline T&T&T\\T&F&F\\F&T&T\\F&F&T\\\end{array}}$$

• 我們可以觀察到，特別地，即使假設 $P$ 為假，根據定義 ，條件語句 $P\to Q$ 為真。
• 另一個觀察是，當結論為真時，無論假設是真還是假，條件語句都必須為真（參見第 1 行和第 3 行）。

為了更直觀地理解為什麼當假設為假時，條件語句始終為真，請考慮以下示例。

示例。 假設鮑勃正在修一門名為 MATH1001 的數學課程。MATH1001 的課程講師警告鮑勃，如果他在這門課程的期末考試中不及格，那麼他將在這門課程中不及格。令 $P$ 表示“鮑勃在 MATH1001 的期末考試中不及格”，而 $Q$ 表示“鮑勃在 MATH1001 中不及格”。那麼，課程講師所說的話是“$P\to Q$”。

為了使課程講師所說的話為真，要麼 鮑勃確實在 MATH1001 的期末考試中不及格，並且他確實在這門課程中不及格，要麼 鮑勃通過了 MATH1001 的期末考試。在後一種情況下，鮑勃是否在 MATH1001 中不及格並不重要，因為課程講師並沒有承諾如果鮑勃通過了 MATH1001 的期末考試會發生什麼 。

為了使課程講師所說的話為假，唯一的情況是鮑勃在 MATH1001 的期末考試中不及格，但他仍然通過了 MATH1001 ($P$ 為真，而 $Q$ 為假)（這表明講師在撒謊！）。

逆否命題和雙條件語句

在討論了 條件句 $P$ 和 $Q$ 之後，我們將討論 雙條件句 $P$ 和 $Q$。顧名思義，雙條件句包含 兩個 條件句。除了 $P\to Q$ 之外，另一個條件句是 $Q\to P$，稱為條件句 $P\to Q$ 的 逆命題。

在數學中，給定條件句 $P\to Q$ 為真，我們通常想知道它的 逆命題 $Q\to P$ 是否也為真 。

示例. 上一個例子中課程講師所做陳述的逆命題是“如果 Bob 在 MATH1001 中不及格，那麼他在 MATH1001 的期末考試中不及格。”

定義. (雙條件句) 兩個語句 $P$ 和 $Q$ 的 雙條件句，記為 $P\leftrightarrow Q$，是指 $(P\to Q)\land (Q\to P)$，也就是說，“如果 $P$ 那麼 $Q$” 和“如果 $Q$ 那麼 $P$”。

備註。

• 我們也可以寫成 $P$ 當且僅當 $Q$。

• 為了更清楚地理解“當且僅當”這個短語，請考慮以下內容
• $P$ 當且僅當 $Q$ 可以解釋為 "$P$ 如果 $Q$ 並且 $P$ 僅當 $Q$”。
• 對於 "$P$ 如果 $Q$"，應該很容易接受它意味著“如果 $Q$ 那麼 $P$”。
• 對於 "$P$ 僅當 $Q$"，這意味著 $P$ 只能在 $Q$ 為真時為真。也就是說，$Q$ 是 $P$ 的 必要條件。因此，我們可以推斷，當 $P$ 為真時，$Q$ 必須為真（否則 $P$ 不可能為真）。因此，"$P$ 僅當 $Q$" 意味著“如果 $P$ 那麼 $Q$”。

示例。 ($P\leftrightarrow Q$ 的真值表）$P\leftrightarrow Q$ 的真值表為 $${\begin{array}{|c|c|c|}P&Q&P\to Q&Q\to P&P\leftrightarrow Q\\\hline T&T&T&T&T\\T&F&F&T&F\\F&T&T&F&F\\F&F&T&T&T\\\end{array}}$$

• 我們可以看到，當 $P$ 和 $Q$ 具有 相同 的真值（即 $P$ 和 $Q$ 均為真，或者 $P$ 和 $Q$ 均為假），否則為假。

蘊涵和邏輯等價

當條件語句 $P\to Q$ 為 真 時，我們可以說“$P$ 蘊涵 $Q$”，記作 $P\Rightarrow Q$。另一方面，當 $P$ 不 蘊涵 $Q$，即 $P\to Q$ 為 假 時，我們記作 $P\nRightarrow Q$.

我們有其他幾種等價的說法來表達“$P$ 蘊涵 $Q$”，即

• $P$ 是 充分條件 $Q$ (或簡而言之，$P$ 對於 $Q$ 是充分的)

• 我們稱 $P$ 對於 $Q$ 是充分的，因為當 $P$ 蘊涵 $Q$ 時，“$P$ 為真”就充分 足以推斷出“$Q$ 為真”。

• $Q$ 是 $P$ 的 必要條件 (或簡而言之，$Q$ 對於 $P$ 是必要的)

• 我們將 $Q$ 稱為 必要 條件，對於 $P$，因為當 $P$ 蘊含 $Q$ 時，當結果 $Q$ 為假時，假設不可能為真（否則條件 $P\to Q$ 將為假）。這解釋了 必要 性，“$Q$ 為真”。

當 $P\Rightarrow Q$ 時，我們經常想知道 $P\to Q$ 的 逆命題 是否為真，即我們是否擁有 $Q\Rightarrow P$ 。

在 $P\Rightarrow Q$ 但 $Q\nRightarrow P$ 的情況下，我們有多種等效的方法來表達這一點

• $P$ 是 充分但非必要 條件，對於 $Q$。

• 從之前的解釋中，當我們說 $P$ 對 $Q$ 是必要的，我們的意思是 $Q\Rightarrow P$。因此，當 $P$ 對 $Q$ 是 充分的 但 非必要的，我們的意思是 ${\color {blue}P\Rightarrow Q}$ 以及 ${\color {red}Q\nRightarrow P}$。

• $P$ 是一個 更強的條件 比 $Q$ （或者 $P$ 比 $Q$ 更強）。

在 $P\Rightarrow Q$ 和 $Q\Rightarrow P$ 都為真的情況下，雙條件語句 $P\leftrightarrow Q$ 也為真，我們用 $P\Leftrightarrow Q$ 表示。還有多種等價的方式來表達這一點。

• $P$ 與 $Q$ 邏輯等價。

• 我們說它們是 邏輯 等價的，因為它們始終具有相同的真值（因為 $P\leftrightarrow Q$ 為真），這與 邏輯 相關。

• "$P$ 當且僅當 $Q$"（為真）。

• 回想一下，我們也使用 "$P$ 當且僅當 $Q$" 來表示 雙條件 $P\leftrightarrow Q$。因此，從技術上講，我們應該寫 "$P$ 當且僅當 $Q$" 在 $P\Leftrightarrow Q$ 為真的情況下是真的。然而，我們很少在實踐中這樣寫，通常會省略“是真的”這句話，因為它使表示式更復雜。因此，當我們在這種情況下寫 "$P$ 當且僅當 $Q$" 時，我們的意思是雙條件為真，而沒有明確地說出來。
• 通常，當我們只寫 "$P$ 當且僅當 $Q$" 時，我們有邏輯等價的含義 $P\Leftrightarrow Q$，而不是語句 $P\leftrightarrow Q$。如果我們真的想要後者的含義，我們應該說明 "$P$ 當且僅當 $Q$" 指的是一個 語句。

• $P$ 是 必要且充分 的 $Q$。

• 按照之前的解釋，$P$ 是 必要 且 充分 的 $Q$ 意味著 ${\color {blue}Q\Rightarrow P}$ 和 ${\color {red}P\Rightarrow Q}$。

定理. (關於合取、析取和否定的某些規律) 在以下內容中，$P$，$Q$ 和 $R$ 是任意命題。

• ${\big (}\sim (\sim P){\big )}\Leftrightarrow P$ (雙重否定)
• $P\land Q\Leftrightarrow Q\land P$ (合取的交換律)
• $P\lor Q\Leftrightarrow Q\lor P$ (析取的交換律)
• $P\land (Q\land R)\Leftrightarrow (P\land Q)\land R$ (合取的結合律)
• $P\lor (Q\lor R)\Leftrightarrow (P\lor Q)\lor R$ (析取的結合律)
• $P\lor (Q\land R)\Leftrightarrow (P\lor Q)\land (P\lor R)$ (分配律)
• $P\land (Q\lor R)\Leftrightarrow (P\land Q)\lor (P\land R)$ (分配律)
• ${\big (}\sim (P\land Q){\big )}\Leftrightarrow (\sim P)\lor (\sim Q)$ (德摩根定律)
• ${\big (}\sim (P\lor Q){\big )}\Leftrightarrow (\sim P)\land (\sim Q)$ (德摩根定律)

證明. 它們可以使用真值表來證明。

$\Box$

備註。

• 你可以觀察到，集合論中也有一些類似的結果（甚至有些名字相同！），在關於集合論的章節中討論。這是因為關於集合論的章節中討論的結果實際上是從上面相應的結論幾乎直接證明出來的。

定理. （條件語句與析取語句的橋樑）語句 $P\to Q$ 和 $(\sim P)\lor Q$ 在邏輯上是等價的。

證明. 可以使用以下真值表來證明：$${\begin{array}{|c|c|c|c|c|}P&Q&\sim P&P\to Q&(\sim P)\lor Q\\\hline T&T&F&T&T\\T&F&F&F&F\\F&T&T&T&T\\F&F&T&T&T\\\end{array}}$$

$\Box$

定理. （條件語句與其逆否命題的邏輯等價）條件語句 $P\to Q$ 的逆否命題被定義為另一個條件語句 $(\sim Q)\to (\sim P)$，它們在邏輯上是等價的。

證明. 利用條件語句與析取語句的橋樑和一些其他定律，可以證明如下：$$P\to Q\Leftrightarrow (\sim P)\lor Q\Leftrightarrow Q\lor (\sim P)\Leftrightarrow {\big (}\sim (\sim Q){\big )}\lor (\sim P)\Leftrightarrow (\sim Q)\to (\sim P).$$

$\Box$

備註。

• 當我們“突然”兩次否定 $Q$ 時，似乎有些“令人驚訝”。實際上，當我們思考如何證明邏輯等價時，我們不會直接從無中生有地進行這樣的操作。相反，在觀察到 $P\to Q\Leftrightarrow (\sim P)\lor Q$ 和 $(\sim Q)\to (\sim P)\Leftrightarrow {\big (}\sim (\sim Q){\big )}\lor (\sim P)$ 之後，我們才“被激發”這樣做。因此，我們從某種程度上來說，是以“三明治”的方式（從左到右和從右到左同時進行）完成了上述一系列等價關係。這可能對其他類似的證明很有用。
• 這個結果對於後面將要討論的逆否命題證明法非常重要。

重言式和矛盾式

在定義重言式和矛盾式之前，我們首先需要介紹一些術語。在前面的章節中，我們已經討論了符號 $\sim ,\lor ,\land ,\to$ 和 $\leftrightarrow$ 的含義。這些符號有時被稱為 邏輯聯結詞，我們可以用 邏輯聯結詞 來構建一些複雜的語句。這些語句由至少一個給定的（或組成）語句（通常用 $P,Q,R$ 等表示）和至少一個邏輯聯結片語成，被稱為 複合語句。

定義。 （重言式和矛盾式） 一個 複合語句 $S$ 稱為 重言式 （矛盾式），如果對於構成 $S$ 的組成語句的每個可能的真值組合，它都 為真 （為假）。

備註。

• 我們用 $\mathbf {T}$ 表示重言式，用 $\mathbf {F}$ 表示矛盾式。
• 當一個語句 $S$ 是重言式時，我們也可以寫成 $S\Leftrightarrow \mathbf {T}$，因為這意味著 $S$ 和 $\mathbf {T}$ 始終具有相同的真值，並且因為 $\mathbf {T}$ 的真值始終為真，因此 $S$ 的真值也始終為真，即 $S$ 是重言式。

• 因此，當我們想要證明一個語句 $S$ 始終為真 時，一種方法是證明 $S\Leftrightarrow \mathbf {T}$。例如，如果我們想要證明 $P\to Q$ 和 $(\sim Q)\to (\sim P)$ 在邏輯上是等價的，我們可以證明 $\left[{\big (}P\to Q{\big )}\leftrightarrow {\big (}(\sim Q)\to (\sim P){\big )}\right]\Leftrightarrow \mathbf {T}$。

例子。 令 $P$ 為任意語句。那麼，

• $P\lor (\sim P)$ 是重言式。
• $P\land (\sim P)$ 是矛盾式。

這是因為 $P\lor (\sim P)$ 的真值表是 $${\begin{array}{|c|c|c|}P&\sim P&P\lor (\sim P)\\\hline T&F&T\\F&T&T\\\end{array}}$$，而 $P\land (\sim P)$ 的真值表是 $${\begin{array}{|c|c|c|}P&\sim P&P\land (\sim P)\\\hline T&F&F\\F&T&F\\\end{array}}.$$

示例。 設 $P$ 和 $Q$ 是任意命題。那麼，$(P\land Q)\to (P\lor Q)$ 是一個永真式，因為它的真值表是 $${\begin{array}{|c|c|c|c|c|}P&Q&P\land Q&P\lor Q&(P\land Q)\to (P\lor Q)\\\hline T&T&T&T&T\\T&F&F&T&T\\F&T&F&T&T\\F&F&F&F&T\\\end{array}}.$$

練習。 以下是關於此示例的一些進一步問題。

1 示例中命題的逆命題，$(P\lor Q)\to (P\land Q)$，是永真式，矛盾式，還是既非永真式也非矛盾式？

	永真式。
	矛盾式。
	既非永真式也非矛盾式。

2 示例中命題的否定，$\sim {\big (}(P\land Q)\to (P\lor Q){\big )}$，是永真式，矛盾式，還是既非永真式也非矛盾式？

	永真式。
	矛盾式。
	既非永真式也非矛盾式。

3 示例中命題的逆否命題，${\big (}\sim (P\lor Q){\big )}\to {\big (}\sim (P\land Q){\big )}$，是永真式，矛盾式，還是既非永真式也非矛盾式？

	永真式。
	矛盾式。
	既非永真式也非矛盾式。

證明 $(P\land Q)\to (P\lor Q)$ 是一個永真式，無需使用真值表。

答案

由於 $$(P\land Q)\to (P\lor Q)\Leftrightarrow {\big (}\sim (P\land Q){\big )}\lor (P\lor Q)\Leftrightarrow {\big (}(\sim P)\lor (\sim Q){\big )}\lor (P\lor Q)\Leftrightarrow {\big (}(\sim P)\lor P{\big )}\lor {\big (}(\sim Q)\lor Q{\big )}\Leftrightarrow \mathbf {T} \lor \mathbf {T} \Leftrightarrow \mathbf {T} ,$$ 給定的條件句是一個永真式。

一位學生聲稱 $(P\lor Q)\to (P\land Q)$ 是一個矛盾句，並用以下論證來支援他的觀點：

由於 $(P\lor Q)\to (P\land Q)\Leftrightarrow {\big (}\sim (P\lor Q){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land (\sim Q)){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land P){\big )}\lor {\big (}(\sim Q)\land Q{\big )}\Leftrightarrow \mathbf {F} \lor \mathbf {F} \Leftrightarrow \mathbf {F}$，這個條件句是矛盾句。

評價他的說法。

答案

• 他的說法是錯誤的。
• 步驟 ${\big (}(\sim P)\land (\sim Q)){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land P){\big )}\lor {\big (}(\sim Q)\land Q{\big )}$ 是不正確的，因為我們應該在這裡使用分配律而不是結合律，並且我們不能在這裡對兩種型別的邏輯連線符應用結合律。
• 事實上，如上述問題所示，條件句 $(P\lor Q)\to (P\land Q)$ 既不是永真式也不是矛盾句。

定理。（關於永真式和矛盾句的定律）設 $P$ 是一個任意的命題。那麼，

• $P\lor \mathbf {T} \Leftrightarrow \mathbf {T}$.
• $P\land \mathbf {T} \Leftrightarrow P$.
• $P\lor \mathbf {F} \Leftrightarrow P$.
• $P\land \mathbf {F} \Leftrightarrow F$.
• $(\sim \mathbf {T} )\Leftrightarrow \mathbf {F}$.
• $(\sim \mathbf {F} )\Leftrightarrow \mathbf {T}$.

證明. 它們可以使用真值表來證明。

$\Box$

量詞

回顧一下，一個 開放語句 是一個語句，其真值取決於某些變數的輸入。在本節中，我們將討論一種使用量詞來將開放語句轉換為語句的方法，而這種轉換得到的語句被稱為量化語句。例如，考慮語句“每個實數的平方是非負的”。它可以被改寫為“對於每個實數 $x$，$x^{2}\geq 0$”。我們可以讓 $P(x)$ 為 開放語句 “$x^{2}\geq 0$”。然後，它可以進一步改寫為“對於每個實數 $x$，$P(x)$”。在這種情況下，我們可以觀察到一個開放語句 ($P(x)$) 如何被轉換為一個語句（對於每個實數 $x$，$P(x)$），而短語“對於每個”是一種 全稱量詞。其他也是全稱量詞的短語包括“對於每一個”，“對於所有”和“無論何時”。全稱量詞通常用 $\forall$（一個倒置的“A”）來表示。在引入這個符號後，我們提到的語句可以進一步改寫為“$\forall x\in \mathbb {R} ,x^{2}\geq 0$”（我們在這裡也使用了一些集合符號）。

一般來說，我們可以使用全稱量詞將一個開語句 $P(x)$ 轉換為一個語句，即 "$\forall x\in S,P(x)$"，其中 $S$ 是一個（全集）集合（或域），它限制了輸入 $x$。

除了全稱量詞之外，將開語句轉換為語句的另一種方法是使用 存在量詞。每個短語 "存在"、"有"、"至少有一個"、"對於某些" 、"對於至少一個" 都被稱為 存在量詞，並用 $\exists$（反轉的 "E"）表示。例如，我們可以將語句 "某個實數的平方為負數" 改寫為 "$\exists x\in \mathbb {R} ,x^{2}<0.$"（這是錯誤的）。

一般來說，我們可以使用存在量詞將一個開語句 $P(x)$ 轉換為一個語句，即 "$\exists x\in S,P(x)$"，其中 $S$ 是一個（全集）集合（或域），它限制了輸入 $x$。

另一個與 存在 量詞相關的量詞是 唯一存在量詞。每個短語 "存在唯一的"、"正好有一個"、"對於唯一的"、"對於正好一個" 都被稱為 唯一存在量詞，並用 $\exists !$ 表示。例如，我們可以將語句 "存在唯一的實數 $x$ 使得 $2x=0$。" 改寫為 "$\exists !x\in \mathbb {R} ,2x=0$"。我們可以用存在量詞和全稱量詞來表示唯一存在量詞，透過 定義 "$\exists !x\in S,P(x)$" 為 $$\left(\exists x\in S,P(x)\right)\land \left(\forall x_{1},x_{2}\in S,P(x_{1})\land P(x_{2})\to x_{1}=x_{2}\right)$$，其中左括號是存在部分，右括號是唯一部分。換句話說，這個表示式意味著

存在一個 $x\in S$ 使得 $P(x)$ 成立，並且對於所有 $x_{1},x_{2}\in S$，如果 $P(x_{1})$ 且 $P(x_{2})$ 成立，那麼 $x_{1}=x_{2}$ （即 $x_{1}$ 和 $x_{2}$ 實際上指的是同一個東西，因此存在 唯一一個 $x$ 使得 $P(x)$ 成立）。

一般來說，我們需要像上面一樣分別證明存在性和唯一性來證明涉及唯一存在量詞的命題。

量化命題的否定

例： 命題 "$\exists A\subseteq U,A=U$" 可以用文字 (部分) 表達為“存在一個集合 $A\subseteq U$ 使得 $A=U$。”

練習： 用文字 (部分) 寫下這個命題的 否定。（提示："$n\geq 1$” （$n$ 是一個非負整數）的否定是什麼？因此，“存在至少一個 $x\in S$ 使得 $P(x)$” 的否定是什麼？

答案

• 提示中，“$n\geq 1$ ($n$ 是一個非負整數)”的否定是 “$n=0$”，而“至少存在一個 $x\in S$ 使得 $P(x)$”的否定因此是 “不存在 $x\in S$ 使得 $P(x)$”。它也可以等價地表示為“對於每個 $x\in S$，$P(x)$ 均不滿足”，或 $\forall x\in S,\sim P(x)$。
• 受提示啟發，該陳述的否定可以寫成“對於每個集合 $A\subseteq U$，$A\neq U$”。

從這個例子中，我們可以看到，語句 "$\exists x\in S,P(x)$" 的否定在邏輯上等價於 "$\forall x\in S,\sim P(x)$"。現在，我們自然想知道語句 "$\forall x\in S,P(x)$" 的否定。考慮這種情況：當 $P(x)$ 不是對每個 $x\in S$ 都為真時，這意味著 $P(x)$ 對 至少一個 $x\in S$ 是假的。換句話說，$\exists x\in S,\sim P(x)$。因此，我們知道語句 "$\forall x\in S,P(x)$" 的否定在邏輯上等價於 $\exists x\in S,\sim P(x)$.

包含多個量詞的量化語句

一個量化語句可以包含多個量詞。當這種量化語句中只使用一種型別的量詞時，情況會更簡單。例如，考慮語句“對於每個實數 $x$ 以及對於每個實數 $y$，$xy$ 都是實數”。它可以寫成“$\forall x\in \mathbb {R} ,\forall y\in \mathbb {R} ,xy\in \mathbb {R}$”。當我們互換“$\forall x\in \mathbb {R}$”和“$\forall y\in \mathbb {R}$”時，語句的含義不受影響（語句仍然意味著“兩個任意實數的乘積是一個實數”。） 因此，我們可以簡單地將語句寫成“$\forall x,y\in \mathbb {R} ,xy\in \mathbb {R}$” 沒有任何歧義。

對於包含兩個存在量詞的示例，考慮語句“存在一個實數 $x$ 和一個實數 $y$ 使得 $xy$ 是實數”。它可以寫成“$\exists x\in \mathbb {R} ,\exists y\in \mathbb {R} ,xy\in \mathbb {R}$”。類似地，互換“$\exists x\in \mathbb {R}$”和“$\exists y\in \mathbb {R}$” 不會影響語句的含義（語句仍然意味著“對於至少一對實數 $x$ 和 $y$，$xy$ 是實數”。） 因此，我們可以簡單地將語句寫成“$\exists x,y\in \mathbb {R} ,xy\in \mathbb {R}$” 沒有任何歧義。

然而，當這兩種型別的量詞都用於這樣的量化語句時，事情就會變得更加複雜。例如，考慮語句“對於每個整數 $x$，存在一個整數 $y$ 使得 $y<x$。” 這也可以寫成“$\forall x\in \mathbb {Z} ,\exists y\in \mathbb {Z} ,y<x$”。這意味著對於每個整數，我們都可以找到一個（嚴格）更小的整數，我們可以看到這是一個真命題。例如，如果你選擇 $x=13$，我可以選擇 $y=-99,0$ 或者 $12$。事實上，對於你選擇的整數 $x$，我總是可以將我的 $y$ 選擇為 $x-1$，使得 $y<x$。

讓我們看看如果我們交換“$\forall x\in \mathbb {Z}$” 和 “$\exists y\in \mathbb {Z}$” 會發生什麼。這個語句就變成了 $\exists y\in \mathbb {Z} ,\forall x\in \mathbb {Z} ,y<x$，這意味著存在一個整數 $y$，使得它（嚴格地）小於所有整數 $x$！這是錯誤的，因為例如，沒有一個整數（嚴格地）小於它自身（它本身就是一個整數）。在這個例子中，我們可以看到，交換全稱量詞和存在量詞的位置會改變語句的含義。因此，清楚地理解包含全稱量詞和存在量詞的量化語句的含義非常重要。為了便於理解，這裡有一些閱讀此類語句的技巧。

對於與量詞 $\exists$ 關聯的變數，它可能取決於語句中前面介紹的變數，但必須獨立於語句中後面介紹的變數。

What does it mean? For example, consider the above example. In the first case, we have $\forall x\in \mathbb {Z} ,\exists y\in \mathbb {Z} ,y<x.$. Then, since the variable $x$ appears earlier than the variable $y$ which associated to $\exists$, $y$ may depend on $x$ (This is similar to the case in English. In a sentence, a thing may depend on other things mentioned earlier.). For instance, when you choose $x=13$, and I choose $y=12$. Then, $y<x$. However, if you change your choice to $x=9$, then my $y=12$ does not work, and I need to change my $y$ to, say, 8 so that $y<x$. Then, we can see that $y$ depends on $x$ in this case. In the second case, we have $\exists y\in \mathbb {Z} ,\forall x\in Z,y<x$. In this case, the variable $x$ appears later than the variable $y$. Hence, the variable $y$ must be independent from from $x$. That is, when such $y$ is determined, it needs to satisfy $y<x$ for each $x$ chosen, and the $y$ cannot change depend on what $x$ is. Indeed, $y$ cannot possibly depend on $x$, since $y$ is supposed to be determined when $x$ is not even introduced!

練習

在以下問題中，$P,Q,R,S$ 是命題。

A. 為以下每個命題構造真值表，並給出它的逆命題和否命題

1. $\sim P\to Q$
2. $P\to (\sim Q)$
3. $(P\lor Q)\to R$
4. $(P\land Q)\to (R\lor S)$
5. $(R\to S)\to (P\to Q)$

B. 對以下語句進行否定

1. $P\land Q$
2. $(P\lor Q)\land (R\land S)$
3. $(P\land \sim Q)\lor (\sim R\lor S)$