邏輯連詞「非」與笛摩根定律 (The quantifier “not” and De Morgan’s laws)
邏輯連詞「非」與笛摩根定律(The quantifier “not” and De Morgan’s laws)
臺北市立和平高中黃俊瑋教師
〈數學述句與邏輯連詞〉一文中,介紹了數學敘述與重要的邏輯連詞「且」、「或」與「非」。其中的「非」具是否定的意思,其宣告某個特定的敘述句為假。當「且」、「或」與「非」這三個邏輯連詞進一步混合使用時,會擦出什麼樣的火花呢?
更具體而言,複合敘述 \(P\land Q\) 與 \(P\lor Q\) 的否定敘述又是什麼意思呢?
例如下列敘述句 (3是奇數)\(\land\)(2是質數) 的否定敘述為何意呢?
(3是奇數)\(\land\)(2是質數)代表的是「3是奇數」與「2是質數」需同時成立,
因此,只要兩者之中有一項不成立,或兩者都不成立,即否定了原敘述。
如此來,無論「(3不是奇數)\(\land\)(2是質數)」、「(3是奇數)\(\land\)(2不是質數)」
以及「(3不是奇數)\(\land\)(2不是質數)」都否定了原敘述「(3是奇數)\(\land\)(2不是質數)」;
換言之,「(3是奇數)\(\land\)(2不是質數)」的否定敘述「非(3是奇數\(\land\)2不是質數)」
包含了「非(3是奇數)\(\land\)(2不是質數)」、「(3是奇數)\(\land\)非(2不是質數)」
以及「非(3是奇數)\(\land\)非(2不是質數)」等情形。
因此,非「(3是奇數)\(\land\)(2不是質數)」之意等同於「非(3是奇數)\(\lor\)非(2不是質數)」之意。
一般而言,我們可以證明 \(\neg(P\land Q)\) 等價於 \(\neg P\lor \neg Q\)。
