標籤: 暫無標籤

德摩根定理是講解關於交集,並集和補集的關係:也叫做對偶原則.

1 德摩根定理 -德摩根定理 (DeMorgan's Theorem)

  通用叫法為「德摩根定律」
  發展歷程與表達形式
  奧古斯都·德·摩根首先發現了在命題邏輯中存在著下面這些關係:
  非(P 且 Q)=(非 P)或(非 Q)
  非(P 或 Q)=(非 P)且(非 Q)

2 德摩根定理 -德摩根定理的表達形式

  形式邏輯中此定律表達形式:
  \neg(P\wedge Q)=(\neg P)\vee(\neg Q)
  \neg(P\vee Q)=(\neg P)\wedge(\neg Q)
  在集合論中:
  (A\cap B)^C=A^C\cup B^C
  (A\cup B)^C=A^C\cap B^C.
  有關於交集,並集和補集的關係:
  Cu(A∩B)=CUA∪CuB
  Cu(A∪B)=CuA∩CuB
  注:u表示全集.
  在經典命題邏輯的外延中,此二元性依然有效(即對於任意的邏輯運算符,我們都能找他它的對偶),由於存在於調節否定關係的恆等式中,人們總會引入作為一個算符的德·摩根對偶的另一個算符。這導致了基於傳統邏輯的邏輯學的一個重要性質,即否定範式的存在性:任何公式等價於另外一個公式,其中否定僅出現在作用於公式中非邏輯的原子時。否定常型的存在推進了許多應用,例如在數字電路設計中該性質用於操縱邏輯門,以及在形式邏輯中該性質是尋找一個公式的合取範式和析取範式的必要條件;電腦程序員們則用它們將一個類似於IF ... AND (... OR ...) THEN ... 這樣的複雜語句轉變為其對等形式;它們也同樣經常用於初等概率論中的計算。
  我們將基於基本命題p, q的任意命題算符P(p, q, ...)的對偶定義為:
  \neg \mbox^d(\neg p, \neg q, ...).
  該概念可以推廣到邏輯量詞上,例如全稱量詞和存在量詞互為對偶:
  \forall x \, P(x) \equiv \neg \exists x \, \neg P(x),
  「對所有x,P(x)皆成立」等價於「不存在x,使P(x)不成立」;
  \exists x \, P(x) \equiv \neg \forall x \, \neg P(x).
  「存在x,使P(x)成立」等價於「並非對所有x,P(x)都不成立」。
  為對德·摩根定律敘述這些量詞的二元性,設置一個在其域D中具有少量元素的模型,例如
  D = {a, b, c}.
  則
  \forall x \, P(x) \equiv P(a) \wedge P(b) \wedge P(c)
  「對所有x,P(x)成立」等價於「P(a)成立」且「P(b)成立」且「P(c)成立」
  以及
  \exists x \, P(x) \equiv P(a) \vee P(b) \vee P(c).
  「存在x,使P(x)成立」等價於「P(a)成立」或「P(b)成立」或「P(c)成立」
  但,應用德·摩根定律,
  P(a) \wedge P(b) \wedge P(c) \equiv \neg (\neg P(a) \vee \neg P(b) \vee \neg P(c))
  「『P(a)成立』且『P(b)成立』且『P(c)成立』」等價於「非(『P(a)不成立』或『P(b)不成立』或『P(c)不成立』)」
  以及
  P(a) \vee P(b) \vee P(c) \equiv \neg (\neg P(a) \wedge \neg P(b) \wedge \neg P(c)),
  「『P(a)成立』或『P(b)成立』或『P(c)成立』」等價於「非(『P(a)不成立』且『P(b)不成立』且『P(c)不成立』)」

3 德摩根定理 -檢驗模型中量詞的二元性

  從而,量詞的二元性可進一步延伸到模態邏輯中的方塊和菱形算符:
  \Box p \equiv \neg \Diamond \neg p,
  \Diamond p \equiv \neg \Box \neg p.
  在其用於可能性和必然性的真勢模態的應用中,亞里士多德注意到該情況,以及在正規模態邏輯的情況中,這些模態算符對量化的關係可藉助按關係語義設置模型來理解。

4 德摩根定理 -德摩根定理的證明

  設x屬於Cu(A∪B),則x屬於u卻不屬於A∪B
  所以x屬於u卻不屬於A,也不屬於B,
  故x屬於CuA和CuB,
  故X屬於CuA∩CuB,
  反過來,式子仍然成立。
  同理,另一式也成立。

相關評論

同義詞:暫無同義詞