第4章 連接詞、量詞與論域
4.1 把句子的作用範圍寫出來
命題是已有明確真假意義的敘述。P∧Q表示兩者皆真；P∨Q表示至少一者真；¬P表示P為假。本書的P⇒Q只有在P真而Q假時為假，其餘情形為真；P⇔Q則要求兩者真假相同。
這是古典命題邏輯的用法。「若P則Q」在此不另外保證時間先後或因果機制。日常語言的「或」有時只許一邊，數學裡若要排除同時成立，必須另外說明。
4.2 全稱與存在
∀x∈D，P(x)表示D裡每個x都滿足P；∃x∈D，P(x)表示至少一個合格x滿足P。要否定全稱，只需合格反例；要否定存在，則必須說明每個合格對象都失敗。
在古典邏輯下，¬(∀x∈D，P(x))等價於∃x∈D，¬P(x)；¬(∃x∈D，P(x))等價於∀x∈D，¬P(x)。否定量詞時，量詞改變，內部性質也要否定，不能只把「每個」換成「不是每個」就停止。
4.3 例題
例題1 蘊涵與逆命題
令P為「n是4的倍數」、Q為「n是偶數」，論域為ℤ。P⇒Q成立，因為4k=2(2k)。逆命題Q⇒P卻不成立：n=2使Q真、P假。
所以知道某個充分條件能得到結論，不表示該條件也必要。用真值表觀察時，要找的是命題實際能出現的合格輸入，而不是把題意和任意代號的因果關係混在一起。
例題2 有兩個量詞時怎麼否定
否定「∀x∈ℝ，∃y∈ℝ，使y>x」。最外層全稱先變存在，內層存在再變全稱，最後把y>x否定成y≤x，因此否定句是「∃x∈ℝ，∀y∈ℝ，都有y≤x」。
原句為真，因為對任意x都可取y=x+1。否定句要求有一個實數能壓住全部實數，與這個構造衝突。y可以依賴已選的x，不能偷偷要求同一個y適用全部x。
例題3 量詞順序不同
「∀x∈ℤ，∃y∈ℤ，使y=x+1」為真，見證是依x決定的y=x+1。「∃y∈ℤ，∀x∈ℤ，使y=x+1」則為假。
若第二句為真，把x=0代入會得y=1，把x=1代入又得y=2，無法由同一個y同時滿足。量詞換序改變了見證可依賴哪些對象。
例題4 空論域與空真
設D=∅。「∀x∈D，x²<0」為真，因為沒有屬於D而違反性質的x；「∃x∈D，x²<0」為假，因為連一個可交出的見證都沒有。
這不表示有某個平方負數的對象存在。全稱句本身不保證D非空；若命題需要存在輸入，應把D≠∅另列為條件。
4.4 變數不能離開它的範圍
寫「∃x∈ℤ，使x²=4」時，x受到存在量詞約束，整句不指定x究竟是2還是−2。證明時可以選一個合格見證，但不能把臨時選的符號帶出作用範圍，宣稱它對另一個無關全稱句仍適用。
分配量詞也要小心。∀x(P(x)∧Q(x))等價於(∀xP(x))∧(∀xQ(x))；∃x(P(x)∧Q(x))卻不一般等價於(∃xP(x))∧(∃xQ(x))，因為後者兩個見證可能不是同一個。
4.5 練習
- B05-C04-Q01 寫出¬(P∧Q)的等價形式，並說明與¬P∧¬Q的差別。
- B05-C04-Q02 把¬(P⇒Q)寫成只含∧與否定的形式。
- B05-C04-Q03 否定「每個整數都大於0」，並判斷原句真假。
- B05-C04-Q04 否定「存在實數x使x²<0」，並判斷原句真假。
- B05-C04-Q05 否定「∀x∈ℝ，∃y∈ℝ，使x+y=0」，並給出原句的見證規則。
- B05-C04-Q06 判斷「∃y∈ℝ，∀x∈ℝ，使x+y=0」並證明。
- B05-C04-Q07 在D={0,1}上，P(x)為x=0、Q(x)為x=1。比較∃x(P(x)∧Q(x))與(∃xP(x))∧(∃xQ(x))。
- B05-C04-Q08 在D=∅上，判斷∀x∈D，x=x與∃x∈D，x=x。
- B05-C04-Q09 證明∀x∈D(P(x)∧Q(x))等價於(∀x∈DP(x))∧(∀x∈DQ(x))，包含空論域。
- B05-C04-Q10 對任意命題P、Q，P⇒Q與¬Q⇒¬P是否同真？用失敗條件說明。
4.6 完整解答
Q01
等價形式是¬P∨¬Q，意思是至少有一邊失敗。¬P∧¬Q卻要求兩邊都失敗，強得多。例如P真、Q假時，¬(P∧Q)真，而¬P∧¬Q假，足以說明兩式不等價。
Q02
¬(P⇒Q)等價於P∧¬Q。理由是蘊涵恰在P真、Q假時失敗，因此它的否定恰好挑出這一列。不是把P、Q各自同時否定成¬P⇒¬Q。
Q03
否定句是「存在整數n，使n≤0」。原句為假，取n=0便得到否定句所需的合格見證。只說「有些整數不大於0」也可以，但必須保留整數論域。
Q04
否定句是「對每個實數x，都有x²≥0」。這個否定句為真，因為實數平方非負，所以原存在句為假。不能只找到x=1使平方非負，就宣稱所有見證都不可能。
Q05
否定為「∃x∈ℝ，∀y∈ℝ，都有x+y≠0」。原句則為真：對任意已給的x，取y=−x，仍為實數且x+y=0。見證明確依賴x，量詞順序因此不可交換。
Q06
為假。假設存在這樣同一個y，取x=0得到y=0，取x=1又得到y=−1，互相矛盾。兩次選x都在要求的實數論域內，而且針對的是同一個假設中的y。
Q07
前者為假，因為D內沒有元素同時等於0又等於1。後者為真：P的見證取0，Q的見證取1。後者並未要求兩次交出相同見證，這就是差別。
Q08
全稱句為真，因為沒有反例；存在句為假，因為沒有見證。性質x=x雖在通常論域總是真的，也不會替空集合創造元素。
Q09
若左式成立，任意x同時有P(x)、Q(x)，因此分別得到兩個全稱句。若右式成立，對任意x∈D，可各自套用兩句，合得P(x)∧Q(x)。若D空，兩邊涉及的全稱句都真，仍同真；證明不需要偷偷假設D裡有一個固定元素。
Q10
同真。P⇒Q唯一的失敗條件是P真、Q假；¬Q⇒¬P的失敗條件是¬Q真、¬P假，也就是Q假、P真，正好相同。因此兩句對每個真值配置都相等。第6章會用這項等價改變證明路線。
4.7 本章回看
否定句要保留原論域，見證要保留依賴順序。接下來把這些句法規則放入完整證明，而不只停在真值表上。