115 年 國立中正大學哲學系碩士班《初階邏輯試題》

本題主要在考驗考生對於英文敘述轉換為符號邏輯命題公式的能力。轉換時需注意「原子敘述」的定義，以及各個邏輯聯結詞（否定、聯言、選言、條件、雙條件）在英文中的對應說法。

核心觀念： 英文敘述與邏輯聯結詞的對應關係。

解題步驟：

1. 定義原子敘述： 針對題目中的每個簡單的、無法再分解的句子，指定一個大寫英文字母代表。
2. 辨識邏輯聯結詞： 找出英文敘述中表達邏輯關係的詞語（如 "not", "and", "if...then...", "only if", "it is not the case that" 等）。
3. 轉換為符號公式： 根據辨識出的聯結詞與原子敘述，寫出對應的邏輯符號公式。

---

(a) Paul is not kind.

• 原子敘述： 設 $P$ 代表「Paul is kind.」（Paul 是善良的）。
• 邏輯聯結詞： "not" 表示否定（negation）。
• 轉換： 對原子敘述 $P$ 加上否定，得到 $\neg P$。

【答案】$\neg P$

---

(b) Jack runs and Mary doesn't sit.

• 原子敘述：
  • 設 $J$ 代表「Jack runs.」（Jack 跑步）。
  • 設 $M$ 代表「Mary sits.」（Mary 坐著）。
• 邏輯聯結詞：
  • "and" 表示聯言（conjunction），$\land$。
  • "doesn't sit" 表示對「Mary sits」的否定，$\neg M$。
• 轉換： 將兩部分聯結起來，得到 $J \land \neg M$。

【答案】$J \land \neg M$

---

(c) It is not the case that if Janet doesn't like popcorn, Gary does not like it either.

• 原子敘述：
  • 設 $J$ 代表「Janet likes popcorn.」（Janet 喜歡爆米花）。
  • 設 $G$ 代表「Gary likes popcorn.」（Gary 喜歡爆米花）。
• 邏輯聯結詞：

本題考驗使用真值表判斷一組命題公式的聯集是否可滿足（satisfiable）的能力。一個命題集合是可滿足的，當且僅當存在至少一種該集合中所有命題公式同時為真的真值賦值。

核心觀念： 可滿足性（Satisfiability）與真值表。

解題步驟：

1. 列出所有原子命題： 找出公式中出現的所有原子命題變數（$P, Q, R$）。
2. 建構真值表： 根據原子命題的數量（本題為 3 個），列出所有可能的真值組合（$2^3 = 8$ 種）。
3. 計算各公式的真值： 依據真值表逐一計算每個原子命題和複雜命題在各種真值組合下的真值。
4. 判斷可滿足性： 檢查是否有任何一行（真值組合）使得所有給定的命題公式（1, 2, 3, 4）都為真。如果存在這樣的一行，則該集合是可滿足的；否則，則是不可滿足的。

真值表建構：

$P$	$Q$	$R$	$\neg Q$	$P \lor \neg Q$ (1)	$\neg P$	$\neg P \lor R$ (2)	$\neg Q \land R$ (3)	$Q$ (4)
T	T	T	F	T	F	T	F	T
T	T	F	F	T	F	F	F	T
T	F	T	T	T	F	T	T	F

本題考驗考生使用演繹證明（Deductive Proof）或自然演繹（Natural Deduction）等非真值表方法，來證明一個論證的有效性。論證有效性意味著，如果前提為真，則結論必然為真。

核心觀念： 論證有效性、演繹證明規則。

解題步驟：

我們將使用自然演繹法來證明此論證的有效性。我們需要從給定的前提推導出結論。

前提：

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

結論：
$(R \lor S)$

證明過程：

我們將逐行列出推導步驟，並註明所使用的規則及其依據。

1. $(P \rightarrow Q) \land (Q \rightarrow R)$ （前提 1）
2. $\neg Q$ （前提 2）
3. $P \lor S$ （前提 3）
4. $P \rightarrow Q$ （$\land$ 消除規則，來自 1）
5. $Q \rightarrow R$ （$\land$ 消除規則，來自 1）
6. $\neg P$ （$\neg$ 導入規則，來自 2 和 4。假設 $P$ 為真，則由 4 可得 $Q$ 為真，這與前提 2 $\neg Q$ 矛盾，故 $P$ 必為假，即 $\neg P$ 為真。）
   • 詳細步驟（歸謬證法或否定後件）：
     • 假設 $P$ （為了 $\neg$ 導入）
     • $Q$ （$\rightarrow$ 消除規則，來自 4 和假設 $P$）
     • $Q \land \neg Q$ （$\land$ 導入規則，來自 2 和上一步）
     • $\neg P$ （$\neg$ 導入規則，來自假設 $P$ 和上一步）
7. $S$ （$\lor$ 消除規則，來自 3 和 6。由 3 知 $P \lor S$ 為真。若 $P$ 為假（由 6 知 $\neg P$），則 $S$ 必須為真。）
   • 詳細步驟（析取排除）：
     • 我們有 $P \lor S$ (3) 和 $\neg P$ (6)。
     • Case 1: Assume $P$. From (4), we get $Q$. This contradicts (2) $\neg Q$. So $P$ cannot be true.
     • Case 2: Assume $\neg P$. From (3) $P \lor S$ and $\neg P$, we can conclude $S$.

本題考驗考生將英文敘述轉換為一階邏輯（First-Order Logic, FOL）公式的能力，並需理解量詞（全稱量詞 $\forall$ 和存在量詞 $\exists$）以及符號化關係（$L(a,b)$ 表示 $a$ loves $b$）。

核心觀念： 量詞、關係符號、否定、聯言、選言、條件句在邏輯中的對應。

解題步驟：

1. 定義原子關係與個體： 根據題目指示，$L(a, b)$ 表示 "$a$ loves $b$"。同時，需要定義題目中出現的人名（個體常項）對應的符號。
   • John：$j$
   • Mary：$m$
   • Jane：$n$
   • Joe：$o$
2. 分析每個敘述： 逐一分析各個英文敘述，找出其邏輯結構，並使用量詞和邏輯聯結詞進行符號化。

---

(a) John doesn't love Mary.

• 分析： 這是一個關於特定個體（John, Mary）的關係，並且是「不愛」的否定。
• 符號化：
  • 「John loves Mary」表示為 $L(j, m)$。
  • 「John doesn't love Mary」是其否定，即 $\neg L(j, m)$。

【答案】$\neg L(j, m)$

---

(b) Neither Jane nor Joe loves Mary.

• 分析： 這表示「Jane 不愛 Mary」且「Joe 不愛 Mary」。
• 符號化：
  • 「Jane loves Mary」表示為 $L(n, m)$。
  • 「Jane doesn't love Mary」表示為 $\neg L(n, m)$。
  • 「Joe loves Mary」表示為 $L(o, m)$。
  • 「Joe doesn't love Mary」表示為 $\neg L(o, m)$。

本題考驗考生運用一階邏輯的證明技巧，來證明論證的有效性。這需要對量詞規則（全稱量詞和存在量詞的引入與消除）以及命題邏輯的推理規則有深入的理解。

核心觀念： 一階邏輯的證明、量詞規則、否定、聯言、選言、條件句的推理。

---

(a) Prove the validity of:

1. $\neg (\exists x) (Px \rightarrow \neg Qx)$
2. $(\exists x) \neg Qx$
   $\therefore (\exists x) \neg Px$

證明系統： 自然演繹（Natural Deduction）

證明過程：

我們需要從前提 1 和 2 推導出結論 $(\exists x) \neg Px$。

1. $\neg (\exists x) (Px \rightarrow \neg Qx)$ （前提 1）

2. $(\exists x) \neg Qx$ （前提 2）

3. $\neg \neg (\exists x) (Px \rightarrow \neg Qx)$ （雙重否定，來自 1）

4. $(\exists x) (Px \rightarrow \neg Qx)$ （雙重否定消除，來自 3）

   • 解釋： 前提 1 說明「不存在一個 $x$ 使得 $Px \rightarrow \neg Qx$」。這等價於「對於所有 $x$， $Px \rightarrow \neg Qx$ 不成立」，但這不直接是我們要的。
   • 更直接的理解： 前提 1 說「並非存在某個 $x$ 使得 $Px \rightarrow \neg Qx$」。這意味著，任何一個 $x$ 都不能滿足 $Px \rightarrow \neg Qx$。
   • 轉換為全稱量詞： $\neg (\exists x) \phi(x)$ 等價於 $(\forall x) \neg \phi(x)$。
   • 所以，從前提 1，我們可以推導出：$(\forall x) \neg (Px \rightarrow \neg Qx)$。
   • 我們將使用這個轉換後的命題進行證明。

   修正證明過程，使用 $(\forall x) \neg (Px \rightarrow \neg Qx)$：

5. $(\forall x) \neg (Px \rightarrow \neg Qx)$ （由前提 1 轉換而來，即 $\neg (\exists x) (Px \rightarrow \neg Qx) \equiv (\forall x) \neg (Px \rightarrow \neg Qx)$）

6. $(\exists x) \neg Qx$ （前提 2）

7. $\neg Qk$ （存在量詞消除，來自 2，其中 $k$ 是一個特定的個體，代表某個 $\neg Qx$ 為真的 $x$）

8. $\neg (Pk \rightarrow \neg Qk)$ （全稱量詞消除，來自 1，對特定的個體 $k$）

9. $\neg (\neg Pk \lor \neg Qk)$ （條件句轉換：$A \rightarrow B \equiv \neg A \lor B$）

10. $\neg \neg Pk \land \neg \neg Qk$ （德摩根定律，來自 5）

11. $Pk \land \neg \neg Qk$ （雙重否定消除，來自 6）

12. $Pk$ （聯言消除，來自 7）

13. $\neg \neg Qk$ （聯言消除，來自 7）

14. $Qk$ （雙重否定消除，來自 9）

    • 這裡出現問題： 我們從前提 1 推導出 $Pk$ (8)，但從前提 2 推導出 $\neg Qk$ (3)。如果我們繼續，從 8 和 3，我們無法直接得到 $(\exists x) \neg Px$。
    • 檢查前提 1 的轉換： $\neg (\exists x) (Px \rightarrow \neg Qx)$。這表示「不存在一個 $x$ 使得 $Px \rightarrow \neg Qx$」。
    • 另一種思路： 考慮 $\neg (Px \rightarrow \neg Qx)$。這等價於 $\neg (\neg Px \lor \neg Qx)$，再根據德摩根定律，等於 $\neg \neg Px \land \neg \neg Qx$，即 $Px \land Qx$。
    • 所以，前提 1 $\neg (\exists x) (Px \rightarrow \neg Qx)$ 實際上等價於 $(\forall x) (Px \land Qx)$。
    • 讓我們用這個等價式重新證明：

    重新證明過程：

15. $(\forall x) (Px \land Qx)$ （由前提 1 轉換而來：$\neg (\exists x) (Px \rightarrow \neg Qx) \equiv (\forall x) \neg (Px \rightarrow \neg Qx) \equiv (\forall x) \neg (\neg Px \lor \neg Qx) \equiv (\forall x) (\neg \neg Px \land \neg \neg Qx) \equiv (\forall x) (Px \land Qx)$）

16. $(\exists x) \neg Qx$ （前提 2）

17. $Pa \land Qa$ （全稱量詞消除，來自 1，對某個個體 $a$）

18. $\neg Qb$ （存在量詞消除，來自 2，對某個個體 $b$）

19. $Pa$ （聯言消除，來自 3）

20. $Qa$ （聯言消除，來自 3）

    • 問題： 我們得到了 $Qa$ (6) 和 $\neg Qb$ (4)。這兩個個體 $a$ 和 $b$ 不一定是相同的。如果 $a=b$，則會產生矛盾 $Qa \land \neg Qa$，這意味著前提 1 和 2 是不相容的，論證無效。但題目要求證明有效性，所以我們假設前提是相容的。
    • 仔細檢查轉換： $\neg (\exists x) (Px \rightarrow \neg Qx)$。這意味著「沒有 $x$ 使得 $Px \rightarrow \neg Qx$」。
    • 考慮 $\neg (Px \rightarrow \neg Qx)$。根據 $\neg (A \rightarrow B) \equiv A \land \neg B$，我們得到 $Px \land \neg (\neg Qx)$，即 $Px \land Qx$。
    • 所以，前提 1 $\neg (\exists x) (Px \rightarrow \neg Qx)$ 確實等價於 $(\forall x) (Px \land Qx)$。

    再檢查前提 2： $(\exists x) \neg Qx$。這表示「存在某個 $x$ 使得 $\neg Qx$」。
    結論： $(\exists x) \neg Px$。這表示「存在某個 $x$ 使得 $\neg Px$」。

本題考驗考生如何證明一階邏輯論證的「無效性」（invalidity）。要證明一個論證無效，必須找到一個反例（counterexample），即存在一種解釋（Interpretation），使得所有前提都為真，但結論為假。

核心觀念： 論證無效性、反例、解釋、模型。

---

Argument 1:

1. $(\forall x)(Px \rightarrow Qx)$
2. $(\forall x)(\neg Fx \rightarrow Gx)$
   $\therefore (\exists x)(Px \cdot Rx)$

證明無效性：尋找反例

我們需要找到一個模型（Domain, Interpretation）使得前提 1 和 2 為真，但結論 $(\exists x)(Px \cdot Rx)$ 為假。
結論 $(\exists x)(Px \cdot Rx)$ 為假，等價於其否定 $(\forall x) \neg (Px \cdot Rx)$ 為真。
根據德摩根定律，這又等價於 $(\forall x)(\neg Px \lor \neg Rx)$。

考慮一個簡單的模型：

• Domain (領域): $\{a\}$ （只包含一個元素 $a$）
• Interpretation (解釋):
  • $P$: $Pa$ 為假 (False)
  • $Q$: $Qa$ 為真 (True)
  • $F$: $Fa$ 為假 (False)
  • $G$: $Ga$ 為真 (True)
  • $R$: $Ra$ 為假 (False)

檢查前提：

1. 前提 1：$(\forall x)(Px \rightarrow Qx)$

   • 在這個 Domain 中，我們只需要檢查 $x=a$。
   • $Pa \rightarrow Qa$。因為 $Pa$ 是假的，而 $Qa$ 是真的，所以 $F \rightarrow T$ 是真的。
   • 前提 1 為真。

2. 前提 2：$(\forall x)(\neg Fx \rightarrow Gx)$

   • 我們只需要檢查 $x=a$。
   • $\neg Fa \rightarrow Ga$。因為 $Fa$ 是假的，所以 $\neg Fa$ 是真的。$Ga$ 是真的。
   • $T \rightarrow T$ 是真的。
   • 前提 2 為真。

檢查結論：

• 結論：$(\exists x)(Px \cdot Rx)$
  • 我們需要檢查 $(\exists x)(Px \cdot Rx)$ 是否為真。
  • 在 Domain $\{a\}$ 中，我們只需要看 $x=a$ 的情況。
  • $Pa \cdot Ra$。因為 $Pa$ 是假的 (F)，$Ra$ 是假的 (F)，所以 $F \cdot F$ 是假的。
  • 因此，$(\exists x)(Px \cdot Rx)$ 在這個模型下為假。

結論：
我們找到了一個模型（Domain={a}, P(a)=F, Q(a)=T, F(a)=F, G(a)=T, R(a)=F），使得前提 1 和 2 都為真，但結論為假。因此，此論證是無效的。

【答案】無效。

---

Argument 2:

1. $(\exists x)(\exists y)(Rxy \rightarrow \neg Ryx)$
   $\therefore (\exists x)(\exists y)\neg(\neg Rxy \lor Ryx)$

證明無效性：尋找反例

我們需要找到一個模型使得前提為真，但結論為假。
結論是 $(\exists x)(\exists y)\neg(\neg Rxy \lor Ryx)$。
其否定是 $(\forall x)(\forall y)\neg(\neg(\neg Rxy \lor Ryx))$。
這等價於 $(\forall x)(\forall y)(\neg Rxy \lor Ryx)$。

考慮一個簡單的模型：

• Domain (領域): $\{a, b\}$
• Interpretation (解釋):
  • $Rab$ 為真 (True)
  • $Rba$ 為真 (True)
  • 對於其他所有 $x, y$ 的組合，$Rxy$ 為假 (False)。

檢查前提：

1. 前提 1：$(\exists x)(\exists y)(Rxy \rightarrow \neg Ryx)$
   • 我們需要找到至少一對 $(x, y)$ 使得 $Rxy \rightarrow \neg Ryx$ 為真。
   • 考慮 $(x, y) = (a, b)$。
   • $Rab \rightarrow \neg Rba$。
   • 根據我們的解釋，$Rab$ 為真 (T)，$Rba$ 為真 (T)。
   • 所以 $\neg Rba$ 為假 (F)。

本題考驗考生對集合論中「子集」概念的理解，特別是針對包含集合作為元素的集合。

核心觀念： 子集（Subset）、空集（Empty Set）、集合的集合。

題目給定的集合：
$S = \{\{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$

我們需要找出 $S$ 的所有子集。
一個集合 $A$ 是集合 $B$ 的子集，如果 $A$ 中的每一個元素都同時是 $B$ 的元素。

首先，我們需要明確 $S$ 的元素是什麼。
$S$ 的元素是兩個集合：

• 元素 1：$E_1 = \{\emptyset\}$
• 元素 2：$E_2 = \{\emptyset, \{\emptyset\}\}$

所以，$S = \{E_1, E_2\}$。

現在，我們要找出 $S$ 的所有子集。一個有 $n$ 個元素的集合，其子集的數量是 $2^n$。
集合 $S$ 有 2 個元素 ($E_1$ 和 $E_2$)，所以它應該有 $2^2 = 4$ 個子集。

我們要列出所有可能的組合，其中每個組合的元素都必須是 $S$ 的元素。

1. 空集： 任何集合的子集都包含空集 $\emptyset$。

   • 子集 1: $\emptyset$

2. 包含一個元素的子集：

   • 包含元素 $E_1$：$\{\{\emptyset\}\}$ (注意：這是包含 $E_1$ 的集合，所以外面還有一層大括號)
   • 包含元素 $E_2$：$\{\{\emptyset, \{\emptyset\}\}\}$ (這是包含 $E_2$ 的集合)