3.10 笛摩根定律

寫條件時常會遇到這種情況：你想判斷的「正面」條件很難直接寫，但它的「反面」（相反情況）卻很好想。 這時有一個好用的工具——笛摩根定律（De Morgan's laws）——可以幫你把「反面」乾淨地翻回「正面」。

¶兩條定律

先看兩個生活例子。假設「兩科都及格」的意思是「國文及格 && 數學及格」。那什麼情況不算兩科都及格？——只要國文沒過 || 數學沒過，就不算了（任一科沒過就不行）。

反過來，假設「今天有吃到東西」的意思是「中午有吃 || 晚上有吃」（吃到一餐就算）。那什麼情況算整天都沒吃？——中午沒吃 && 晚上沒吃（兩餐都沒吃）。

把上面的「國文及格」「數學及格」換成任意兩個條件（我們用 P、Q 當代號——你可以把它想成任何一個「會成立或不成立」的判斷，例如 x > 0、score >= 60），就得到笛摩根定律。它講的是「否定（!）碰到 && 或 || 時會怎麼變」：

• !(P && Q) 等於 !P || !Q — 「不是（P 且 Q）」＝「非 P 或 非 Q」
• !(P || Q) 等於 !P && !Q — 「不是（P 或 Q）」＝「非 P 且 非 Q」

用白話說：

• 「不是（兩個都成立）」＝「至少有一個不成立」。
• 「不是（有任一個成立）」＝「兩個都不成立」。

重點：否定穿過括號時，裡面每一項都要取反，而且 && 和 || 會互換。

¶用真值表驗證

不用死背，列一張真值表就能確認第一條定律成立（T＝true、F＝false）：

兩欄結果一模一樣，!(P && Q) 和 !P || !Q 確實相等。（第二條定律你可以自己照樣列一張表驗證。）

¶例題：兩區間是否重疊

來看一道乍看「條件很不直覺」的題目——區間重疊判斷（rangeintc）：

數線上有兩個閉區間 [a_1, b_1] 和 [a_2, b_2]，問它們有沒有共同的點（是否重疊）。

先看懂題目用詞：閉區間 [a, b] 指的是數線上「從 a 到 b、包含兩個端點 a 和 b」的整段範圍——中括號 [ ] 就是「含端點」的記號。區間題幾乎都會用這個詞，務必分清楚含不含端點（呼應 3.2 說的邊界問題）。

「重疊」要直接寫成條件並不好想。但「不重疊」超好想：兩個區間完全錯開時才不重疊，也就是其中一個整個落在另一個的左邊：

• 區間 1 整個在區間 2 左邊：b1 < a2（區間 1 的右端比區間 2 的左端還小）
• 區間 2 整個在區間 1 左邊：b2 < a1

所以：

不重疊  =  (b1 < a2) || (b2 < a1)

而「重疊」就是「不重疊」的相反，加個 ! 即可。這時笛摩根定律登場，把 ! 翻進括號：

重疊 = !( (b1 < a2) || (b2 < a1) )
     = !(b1 < a2) && !(b2 < a1)     ← 笛摩根：! 穿過，|| 變 &&
     = (b1 >= a2) && (b2 >= a1)     ← 把每項的 < 取反成 >=

於是就得到那個「看起來很不直覺、卻絕對正確」的寫法：

int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;

// 重疊 = 不是「兩區間完全錯開」，用笛摩根化簡後就是這一行
if (b1 >= a2 && b2 >= a1) {
    cout << "Yes\n";
} else {
    cout << "No\n";
}

以後遇到「正面難寫、反面好想」的條件，就先寫反面、再用笛摩根定律翻成正面——又快又不容易錯。

¶動手試試看

先在紙上用笛摩根定律驗證：!(x >= 0 && x <= 100) 展開後等於 x < 0 || x > 100（想想看它的意思是「不在 0 到 100 之間」）。接著把 區間重疊判斷（rangeintc） 寫出來並通過。