數學證明/邏輯

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

真值和陳述

我們在數學中經常遇到陳述。

定義。 (陳述) 一個陳述是一個可以判斷為真或假（但不能同時為真假）的陳述句，其真值為真（用$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$”。
• 數學中的“或”的含義可能與英語單詞“or”的含義不同。在數學中，“或”是 包含性的，即 $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$ 和 $Q$ 為假時，$P\lor Q$ 為假，否則為真。

否定

定義： 一個命題 $P$ 的 否定，記作 $\sim P$，是一個真值與 $P$ 相反的命題。

備註。

• $~P$ 讀作“非 P”，命題 $P$ 的否定也可以直接用“非 $P$”或“並非 $P$”來表達。
• 另一個常見的符號是 $\lnot P$ 來表示命題 $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$ 為真且 $Q$ 為假時，條件語句 $P\to 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 行）。

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

示例。 假設 Bob 正在上一個叫做 MATH1001 的數學課程。MATH1001 的課程老師警告 Bob，如果他在這門課程的期末考試中不及格，那麼他將無法透過這門課程。令 $P$ 表示語句“Bob 在 MATH1001 的期末考試中不及格”，而 $Q$ 表示語句“Bob 無法透過 MATH1001”。那麼，課程老師的陳述是“$P\to Q$”。

為了使課程老師的陳述為真，要麼 Bob 確實在 MATH1001 的期末考試中不及格，並且他確實無法透過這門課程，要麼 Bob 通過了 MATH1001 的期末考試。在後一種情況下，無論 Bob 是否透過 MATH1001 都無關緊要，因為如果 Bob 通過了 MATH1001 的期末考試，課程老師不會承諾任何事情 。

為了使課程老師的陳述為假，唯一的情況是 Bob 在 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\leftrightarrow Q$ 為真時，$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$ 為 充分條件，因為當 $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)$