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

核心觀念

本題考查條件句與雙條件句的真值定義：

• $P\to Q$ 只有在 $P$ 真、$Q$ 假時為假。
• $P\leftrightarrow Q$ 在 $P$ 與 $Q$ 同真或同假時為真。
• $\neg(P\leftrightarrow Q)$ 表示 $P$ 與 $Q$ 的真值不同。

解題方法

先依前件 $A\land E$ 是否為真分情況。若前件為假，整個條件句直接為真；若前件為真，則 $A$、$E$ 都為真，代入方括號中的雙條件句比較兩側。

1. 若 $A\land E$ 為假，則

因前件為假而為真。

核心觀念

本題考「關係的對稱性」與「個體同一性」是否能互相推出。若關係 $R$ 具有對稱性，便有：

這只表示兩個方向的關係都成立，並不表示 $x$ 與 $y$ 是同一個對象。

解題方法

檢查「必然推出」的主張時，可找一個符合前提、但結論不成立的反例。

令論域為 $\{1,2\}$，指定 $a=1$、$b=2$，並令 $R$ 包含有序對 $(1,2)$ 與 $(2,1)$。

核心觀念

一組公式 $\alpha,\beta,\gamma$ 不一致，表示不存在任何賦值能讓三者同時為真；也就是 $\alpha\land\beta\land\gamma$ 不可滿足。這不代表由它們組成的其他複合公式也不可滿足。

雙條件式 $P\leftrightarrow Q$ 在 $P$、$Q$ 同真或同假時為真。

解題方法

找一組不一致的公式，再找一個賦值，使題目中的複合公式為真，即可反駁「不能為真」的主張。令：

三者不一致，因為 $\alpha=p$ 與 $\gamma=\neg p$ 不可能同時為真。取賦值 $p=\mathrm{真}$、$q=\mathrm{假}$，則：

核心觀念

可滿足性是指存在一個模型，使公式為真。題目比較的是：

• $\forall x\forall y\,\alpha(x,y)$：同一個模型中，對所有 $x,y$ 的取值，$\alpha(x,y)$ 都成立。
• $\alpha(c,c)$：只要求存在一個模型，讓常數 $c$ 所指的對象代入 $x,y$ 後，$\alpha$ 成立。

因此，前者要求比後者強。又因為 $c$ 不出現在 $\alpha$ 中，可以在既有模型中任意指定 $c$ 的指涉，而不影響 $\alpha$ 的真值。

解題方法

若 $\forall x\forall y\,\alpha(x,y)$ 可滿足，取一個使它為真的模型，再把新常數 $c$ 指定為論域中的任一對象，就有 $\alpha(c,c)$ 為真。因此：

核心觀念

本題考量詞與蘊涵的範圍，以及兩個公式是否在所有解釋下真值相同。令

採用標準一階邏輯語意，量詞的論域非空。

解題方法

分別證明 $A\to B$ 與 $B\to A$。

若 $A$ 為真，且某個對象 $a,b$ 使 $P(a,b)$ 為真，則由 $A$ 可知，對 $x=a$ 存在一個對象 $c$，使得對所有 $z$，$P(a,z)\to Q(c)$ 成立。代入 $z=b$，因為 $P(a,b)$ 為真，故 $Q(c)$ 為真。因此，只要 $\exists x\exists zP(x,z)$ 為真，便能推出 $\exists yQ(y)$；若前件為假，整個蘊涵式也為真。所以 $A\to B$。

若 $B$ 為真，分兩種情況：

核心觀念

把「$S$ 的定理」理解為可由 $S$ 推出的句子，記作 $S\vdash\varphi$；「可由 $T$ 證明」則記作 $T\vdash\varphi$。題目主張：只要 $S$ 是無限集、$T$ 是 $S$ 的有限子集，就必定存在某個 $S$ 的定理不能由 $T$ 證明。

關鍵在於：$S$ 無限，並不代表 $S$ 含有無法由 $T$ 推出的內容。$S$ 裡的句子可以全是 $T$ 的推論。

解題方法

用反例否定「必定存在」的主張。取命題變項 $P,Q_1,Q_2,\ldots$，令

核心觀念

一致集是指其句子能同時為真；不一致集則沒有任何模型能使其中所有句子同時為真。兩個集合各自一致，不代表合併後仍一致：$S$ 與 $T$ 的句子可能只有合在一起時才產生矛盾。

本題的關鍵是區分「$S\cup T$ 不一致」與「$T$ 中有某一個句子單獨和 $S$ 矛盾」。前者不必然推出後者。

解題方法

取命題變項 $p,q$，令

$S$ 一致，因為例如 $p$、$q$ 都為假時，$\neg(p\land q)$ 為真。$T$ 也一致，因為 $p$、$q$ 都為真時，$T$ 中的句子同時為真。

但 $S\cup T$ 不一致：$p$ 與 $q$ 同時為真，會使 $p\land q$ 為真，與 $S$ 中的 $\neg(p\land q)$ 矛盾。

再檢查 $T$ 中的每個句子：

核心觀念

題目考查關係的傳遞性與有限模型。關係 $R$ 具有傳遞性，表示只要 $R(x,y)$ 與 $R(y,z)$ 都成立，就有 $R(x,z)$。

公式中的 $x\ne y$ 只要求每個對象都能找到一個不同於自己的對象，且兩者間有 $R$ 關係；它沒有要求 $R$ 必須是非自反的，也就是沒有禁止 $R(x,x)$。

解題方法

要判斷「沒有有限模型能滿足」是否為真，只要找出一個有限模型同時滿足兩個條件，就能否定這個說法。

取論域 $D=\{a,b\}$，並令 $R$ 為論域上的全關係：

逐一檢查：

1. 對 $x=a$，取 $y=b$；對 $x=b$，取 $y=a$。兩種情況都滿足 $x\ne y$ 且 $R(x,y)$，因此

核心觀念

本題考查將自然語言中的全稱量詞、條件句、合取與否定轉成一階邏輯。關鍵是把「已生育」與收入門檻分開處理，並把「十二萬元（含）以上」寫成大於或等於。

解題方法

以「夫妻」為論域，令：

• $H(x)$：$x$ 這對夫妻已生育。
• $I(x)$：$x$ 這對夫妻的月收入。
• $B(x)$：$x$ 這對夫妻每月可領取一萬元補助。

第一部分說，已生育且月收入低於十二萬元的夫妻可以領取補助；第二部分說，月收入達十二萬元以上的夫妻不得領取。因此可表示為：

核心觀念

本題考查「除非」句型的符號化，以及「至少兩個」的存在量詞表達。

採論域為所有人，定義：

• $P(x)$：$x$ 是哲學家
• $N(x)$：$x$ 在胡言亂語
• $A(x)$：$x$ 參加這場會議
• $M(x)$：$x$ 來自火星

「$P$ 除非 $Q$」可改寫為「若非 $Q$，則 $P$」，即 $\neg Q \to P$；等值於 $Q \lor P$。

解題方法

先將除非句的前後兩部分分開處理：

1. 「每位參加會議的人都來自火星」表示為
   $\forall x(A(x)\to M(x))$

2. 其否定表示「至少有一位參加會議的人不來自火星」：
   $\neg\forall x(A(x)\to M(x))$

核心觀念

本題考查命題聯結詞的可定義性：若某個聯結詞可由指定的聯結詞表示，兩者就必須對每一種真值指派都產生相同的真值。

把真值 $1$ 表示為真、$0$ 表示為假，並以 $\oplus$ 表示模 $2$ 加法。題目中的 $+$ 是異或，故：

三種允許使用的聯結詞可寫成：

這些真值函數都屬於仿射函數，也就是可寫成變數的異或，再與常數 $0$ 或 $1$ 異或。

解題方法

證明所有只用 $\neg$、$\leftrightarrow$、$+$ 組成的公式都只能表示仿射函數。

對公式的組成方式作歸納：

1. 基本命題 $A$、$B$ 本身是仿射函數。
2. 若公式表示仿射函數，對它取否定，就是再與 $1$ 異或，仍是仿射函數。
3. 若兩個公式都表示仿射函數，將它們以 $\leftrightarrow$ 或 $+$ 組合，依照上面的公式表示，結果仍是仿射函數。

因此，任何使用題目指定聯結詞寫成的公式，其真值函數都必須是仿射函數。

接著檢查蘊涵 $A\to B$。其真值表為：

核心觀念

本題考查一階述詞邏輯中的量詞否定，以及論證有效性的反例判定。

令：

• $S(x)$：$x$ 是聰明人
• $P(x)$：$x$ 是哲學家
• $W(x)$：$x$ 是苦命人

「並非所有的聰明人都是哲學家」可改寫為「有些聰明人不是哲學家」：

「所有哲學家都是苦命人」表示每一位哲學家都是苦命人。結論「有些聰明人不是苦命人」則表示至少存在一位聰明人不是苦命人。

解題方法

題目要求證明或反駁論證。若要反駁，只要找出一個情況，使兩個前提都為真，而結論為假。

取論域為只有一個人的集合 $\{a\}$，並設定：

核心觀念

本題考驗一階邏輯中量詞的使用、雙條件式 $A\leftrightarrow B$ 的真值，以及以反證法證明論證有效。雙條件式為真，表示左右兩邊同真或同假；由前兩個前提可推出存在一個使 $P$ 為假的對象。

解題方法

要證明前提蘊涵結論，可假設結論為假，檢查是否會與前提矛盾。結論是「若全體對象都滿足條件，則 $\neg S(x,b)$」；因此，若假設 $S(x,b)$ 為真，第三個前提會推出 $R(x)$。再由第一個前提得到 $Q(x)$，使結論前件中的兩個存在條件都成立。這會迫使每個對象都滿足 $P$，但第二個前提可推出至少有一個對象不滿足 $P$，於是形成矛盾。

推導

令 $x$ 的自由變項指派為任意對象 $a$。先由前兩個前提推出 $\exists z\neg Pz$。

由第二個前提，取一個見證 $c$，使得

由第一個前提可知 $Rc\leftrightarrow Qc$。

若 $Rc$ 為真，則 $Qc$ 為真。上式使 $\neg(Pc\leftrightarrow Qc)$ 為真，因此 $Pc$ 與 $Qc$ 不同；既然 $Qc$ 為真，便有 $\neg Pc$。

若 $Rc$ 為假，則 $Qc$ 為假。上式使 $\neg(Pc\leftrightarrow Qc)$ 為假，因此 $Pc\leftrightarrow Qc$ 為真；

核心觀念

要反駁「前提推出結論」的論證，只需找出一組真值指派，使所有前提為真、結論為假。這樣的指派稱為反例。

本題用到的真值條件如下：

• $P\leftrightarrow Q$ 為真，當且僅當 $P$ 與 $Q$ 同真同假。
• $P\to Q$ 為假，當且僅當 $P$ 真而 $Q$ 假。
• $P\lor Q$ 為假，當且僅當 $P$ 與 $Q$ 都假。

解題方法

要讓結論

為假，兩個析取項都必須為假。因此需要：

且

後一條表示 $B$ 與 $C$ 真值不同。

再看第一個前提：

它要求 $C$ 的真值與 $\neg(A\leftrightarrow B)$ 相同。取 $A$、$B$ 同為真，則 $A\leftrightarrow B$ 為真，故 $\neg(A\leftrightarrow B)$ 為假；令 $C$ 為假，第一個前提便為真。

核心觀念

本題要判斷公式是否為邏輯有效式。題目沒有前提，因此須證明：在每個非空論域、每種謂詞解釋下，公式都成立。

關鍵是條件句的真值：後件為真，或前件為假時，整個條件句都為真。本題採用論域非空的標準古典一階邏輯。

解題方法

先依是否存在一個對象 $c$ 使 $P(c)\to R(c)$ 為真，分成兩種情況。

情況一：存在 $c$ 使 $P(c)\to R(c)$ 為真

因論域非空，取任一對象 $a$ 作為 $z$。對任意 $y$，令 $x=c$。由於後件 $P(c)\to R(c)$ 為真，以下條件句必為真：

因此每個 $y$ 都有符合條件的 $x$，公式成立。

情況二：不存在任何 $c$ 使 $P(c)\to R(c)$ 為真

依古典邏輯，

核心觀念

本題考查一階邏輯中的全稱量化消去與存在量化消去，以及如何把前提中的存在見證代入目標結論。

第二個前提表示：每一條 $R$ 關係 $R(x,y)$，都能插入一個與 $x,y$ 皆不同的元素 $z$，使得 $R(x,z)$ 與 $R(z,y)$ 同時成立。因此，只要先由第一個前提取得一條 $R$ 關係，就能直接得到結論所需的三個元素與兩段關係。

解題方法與推導

先由第一個前提取任意元素 $a$。由全稱量化消去及存在量化消去，可取一個元素 $b$，使得：

將 $a,b$ 代入第二個前提。由全稱量化消去，再對其中的存在量化取見證 $c$，得到：