德摩根定律

維基百科,自由的百科全書
跳到: 導覽搜尋

命題邏輯邏輯代數中,德摩根定律De Morgan's laws(或稱笛摩根定理對偶律)是關於命題邏輯規律的一對法則[1]

奧古斯塔斯·德摩根首先發現了在命題邏輯中存在着下面這些關係:

非()等價於(非)或(非
非()等價於(非)且(非

德摩根定律在數理邏輯的定理推演中,在計算機的邏輯設計中以及數學集合運算中都起着重要的作用[1]。他的發現影響了喬治·布爾從事的邏輯問題代數解法的研究,這鞏固了德摩根作為該規律的發現者的地位,儘管亞里士多德也曾注意到類似現象、且這也為古希臘與中世紀的邏輯學家熟知(引自Bocheński《形式邏輯歷史》)。

形式表示[編輯]

形式邏輯中此定律表達形式:

在集合論中:

詳細解釋[編輯]

在經典命題邏輯的外延中,此二元性依然有效(即對於任意的邏輯運算符,我們都能找他它的對偶),由於存在於調節否定關係的恆等式中,人們總會引入作為一個算符的德摩根對偶的另一個算符。這導致了基於傳統邏輯的邏輯學的一個重要性質,即否定範式的存在性:任何公式等價於另外一個公式,其中否定僅出現在作用於公式中非邏輯的原子時。否定常型的存在推進了許多應用,例如在數字電路設計中該性質用於操縱邏輯門,以及在形式邏輯中該性質是尋找一個公式的合取範式析取範式的必要條件;電腦程式員們則用它們將一個類似於IF ... AND (... OR ...) THEN ... 這樣的複雜語句轉變為其對等形式;它們也同樣經常用於初等概率論中的計算。

我們將基於基本命題p, q的任意命題算符P(p, q, ...)的對偶定義為:

該概念可以推廣到邏輯量詞上,例如全稱量詞存在量詞互為對偶:

「對所有x,P(x)皆成立」等價於「不存在x,使P(x)不成立」;
「存在x,使P(x)成立」等價於「並非對所有x,P(x)都不成立」。

為對德摩根定律敘述這些量詞的二元性,設置一個在其域D中具有少量元素的模型,例如

D = {a, b, c}.

「對所有x,P(x)成立」等價於「P(a)成立」且「P(b)成立」且「P(c)成立」

以及

「存在x,使P(x)成立」等價於「P(a)成立」或「P(b)成立」或「P(c)成立」

但,應用德摩根定律,

「『P(a)成立』且『P(b)成立』且『P(c)成立』」等價於「非(『P(a)不成立』或『P(b)不成立』或『P(c)不成立』)」

以及

「『P(a)成立』或『P(b)成立』或『P(c)成立』」等價於「非(『P(a)不成立』且『P(b)不成立』且『P(c)不成立』)」

檢驗模型中量詞的二元性。

從而,量詞的二元性可進一步延伸到模態邏輯中的方塊菱形算符:

在其用於可能性和必然性的真勢模態的應用中,亞里士多德注意到該情況,以及在正規模態邏輯的情況中,這些模態算符對量化的關係可藉助按關係語義設置模型來理解。

參見[編輯]

注釋與參考資料[編輯]

引用[編輯]

  • 「應注意到一個析取命題的對立命題是由該析取命題各部分的對立內容構成的一個合取命題」 ——奧卡姆的威廉著,《邏輯學論文》

參考文獻[編輯]

  1. ^ 1.0 1.1 《數學辭海》編輯委員會 (編). 德·摩根定律. 數學辭海 第六卷. 太原: 山西教育出版社 等: 543. 2002. ISBN 7-5440-2401-6. 

外部連結[編輯]