離散數學 - 命題邏輯

---

---

數學邏輯的規則規定了推理數學陳述的方法。希臘哲學家亞里士多德是邏輯推理的先驅。邏輯推理為許多數學領域以及計算機科學提供了理論基礎。它在計算機科學中有很多實際應用，例如計算機器的設計、人工智慧、程式語言的資料結構的定義等。

命題邏輯關注的是可以分配真值“真”和“假”的陳述。目的是分析這些陳述，無論是單獨還是組合的方式。

命題邏輯 - 定義

命題是具有真值“真”或真值“假”的宣告性語句的集合。命題由命題變數和連線片語成。我們用大寫字母（A、B 等）表示命題變數。連線詞連線命題變數。

下面給出了一些命題的例子：

• "人是凡人"，它返回真值“真”
• "12 + 9 = 3 – 2"，它返回真值“假”

以下不是命題：

• "A 小於 2"。這是因為除非我們給 A 一個特定的值，否則我們無法說該語句是真還是假。

連線詞

在命題邏輯中，我們通常使用五個連線詞，它們是：

• 或 ($\lor$)

• 與 ($\land$)

• 非/否定 ($\lnot$)

• 蘊涵/如果-那麼 ($\rightarrow$)

• 當且僅當 ($\Leftrightarrow$).

或 ($\lor$) - 兩個命題 A 和 B 的或運算（寫成 $A \lor B$）如果命題變數 A 或 B 中至少有一個為真，則為真。

真值表如下：

與 ($\land$) - 兩個命題 A 和 B 的與運算（寫成 $A \land B$）如果命題變數 A 和 B 都為真，則為真。

真值表如下：

否定 ($\lnot$) - 命題 A 的否定（寫成 $\lnot A$）當 A 為真時為假，當 A 為假時為真。

真值表如下：

蘊涵/如果-那麼 ($\rightarrow$) - 蘊涵 $A \rightarrow B$ 是命題“如果 A，那麼 B”。如果 A 為真而 B 為假，則它為假。其餘情況為真。

真值表如下：

當且僅當 ($ \Leftrightarrow $) - $A \Leftrightarrow B$ 是雙條件邏輯連線詞，當 p 和 q 相同時為真，即兩者都為假或兩者都為真。

真值表如下：

重言式

重言式是對於其命題變數的每個值始終為真的公式。

示例 - 證明 $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ 是重言式

真值表如下：

我們可以看到 $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ 的每個值都是“真”，所以它是重言式。

矛盾

矛盾是對於其命題變數的每個值始終為假的公式。

示例 - 證明 $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ 是矛盾

真值表如下：

我們可以看到 $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ 的每個值都是“假”，所以它是矛盾。

或然

或然是對於其命題變數的每個值都有一些真值和一些假值的公式。

示例 - 證明 $(A \lor B) \land (\lnot A)$ 是或然

真值表如下：

我們可以看到 $(A \lor B) \land (\lnot A)$ 的每個值都既有“真”又有“假”，所以它是或然。

命題等價

如果滿足以下兩個條件中的任何一個，則兩個語句 X 和 Y 在邏輯上是等價的：

• 每個語句的真值表具有相同的真值。

• 雙條件語句 $X \Leftrightarrow Y$ 是重言式。

示例 - 證明 $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ 是等價的

使用第一種方法（匹配真值表）進行測試

在這裡，我們可以看到 $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ 的真值相同，因此這些語句是等價的。

使用第二種方法（雙條件）進行測試

由於 $\lbrack \lnot (A \lor B) \rbrack \Leftrightarrow \lbrack (\lnot A ) \land (\lnot B) \rbrack$ 是重言式，因此這些語句是等價的。

逆命題、否命題和逆否命題

蘊涵/如果-那麼 $(\rightarrow)$ 也稱為條件語句。它有兩個部分：

• 假設，p
• 結論，q

如前所述，它表示為 $p \rightarrow q$。

條件語句示例 - “如果你做作業，你就不會受到懲罰。” 這裡，“你做作業”是假設 p，“你不會受到懲罰”是結論 q。

逆命題 - 條件語句的逆命題是對假設和結論的否定。如果語句是“如果 p，那麼 q”，則逆命題將是“如果非 p，那麼非 q”。因此，$p \rightarrow q$ 的逆命題是 $ \lnot p \rightarrow \lnot q$。

示例 - “如果你做作業，你就不會受到懲罰”的逆命題是“如果你不做作業，你就會受到懲罰”。

否命題 - 條件語句的否命題是透過交換假設和結論來計算的。如果語句是“如果 p，那麼 q”，則否命題將是“如果 q，那麼 p”。$p \rightarrow q$ 的否命題是 $q \rightarrow p$。

示例 - “如果你做作業，你就不會受到懲罰”的否命題是“如果你不會受到懲罰，你就會做作業”。

逆否命題 - 條件語句的逆否命題是透過交換逆命題的假設和結論來計算的。如果語句是“如果 p，那麼 q”，則逆否命題將是“如果非 q，那麼非 p”。$p \rightarrow q$ 的逆否命題是 $\lnot q \rightarrow \lnot p$。

示例 - “如果你做作業，你就不會受到懲罰”的逆否命題是“如果你受到懲罰，你就沒有做作業”。

對偶原理

對偶原理指出，對於任何真語句，透過將並集改為交集（反之亦然）並將全集改為空集（反之亦然）獲得的對偶語句也為真。如果任何語句的對偶是語句本身，則稱之為自對偶語句。

示例 - $(A \cap B ) \cup C$ 的對偶是 $(A \cup B) \cap C$

正規化

我們可以將任何命題轉換為兩種正規化：

• 合取正規化
• 析取正規化

合取正規化

如果一個複合語句是透過對用或連線的變數（包括變數的否定）進行與運算而得到的，則該複合語句處於合取正規化。就集合運算而言，它是透過對用並集連線的變數進行交集而得到的複合語句。

示例

• $(A \lor B) \land (A \lor C) \land (B \lor C \lor D)$

• $(P \cup Q) \cap (Q \cup R)$

析取正規化

如果一個複合語句是透過對用與連線的變數（包括變數的否定）進行或運算而得到的，則該複合語句處於析取正規化。就集合運算而言，它是透過對用交集連線的變數進行並集而得到的複合語句。

示例

• $(A \land B) \lor (A \land C) \lor (B \land C \land D)$

• $(P \cap Q) \cup (Q \cap R)$