1.4 謂詞和限定詞 Predicates and Quantifiers

引入謂詞邏輯

謂詞邏輯使用以下新功能：

• 變數:x,y,z
• 謂詞:P(x),M(x)
• 限定詞

命題功能是命題的概括。
它們包含變數和謂詞，例如，P(x)
變數可以替換為其域

命題函數示例

讓我們"x+y=z"表示 R(x, y, z)和 U(對於所有三個變數)是整數。找到這些真理值：
R(2,-1,5)
Solution: F
R(3,4,7)
Solution: T
R(x, 3, z)
Solution: Not a Proposition

現在讓我們"x - y = z"表示 Q(x, y, z)，以 U 為整數。找到這些真理值：
Q(2,-1,3)
Solution: T
Q(3,4,7)
Solution: F
Q(x, 3, z)
Solution: Not a Proposition

通用量化器 Universal Quantifier

∀ x P(x) 被讀為 “For all x, P(x)” or “For every x, P(x)”

Examples:

• If P(x) denotes “x > 0” and U is the integers, then ∀ x P(x) is false.
• If P(x) denotes “x > 0” and U is the positive integers, then ∀ x P(x) is true.
• If P(x) denotes “x is even” and U is the integers, then ∀ x P(x) is false.

存在量化器 Existential Quantifier

∃ x P(x) 被讀為 “For some x, P(x)”, or as “There is an x such that P(x),” or “For at least one x, P(x).”

Examples:

• If P(x) denotes “x > 0” and U is the integers, then ∃ x P(x) is true. It is also true if U is the positive integers.
• If P(x) denotes “x < 0” and U is the positive integers, then ∃ x P(x) is false.
• If P(x) denotes “x is even” and U is the integers, then ∃ x P(x) is true.

補充:唯一性量化器 Uniqueness Quantifier

∃!x P(x) 表示 P(x) 為真且只有一個 x 在話語的宇宙中
這通常以英語以下列等效方式表示:

• “There is a unique x such that P(x).”
• “There is one and only one x such that P(x)”

Examples:

• If P(x) denotes “x + 1 = 0” and U is the integers, then ∃!x P(x) is true.
• But if P(x) denotes “x > 0,” then ∃!x P(x) is false.

唯一性限定詞並不真正需要，因為限制有一個 x 這樣，P(x)可以表示為:
∃ x (P(x) ∧ ∀ y (P(y) → y =x))

限定詞的優先順序 Precedence of Quantifiers

限定詞 ∀ 和 ∃ 具有高於所有邏輯運算子的優先順序。
例如, ∀ x P(x) ∨ Q(x) 意味 (∀ x P(x))∨ Q(x)
∀ x (P(x) ∨ Q(x)) 意味著不同東西.
不幸的是,當他們想表示 ∀ x (P(x) ∨ Q(x)) 時，人們通常寫 ∀ x P(x) ∨ Q(x)

德摩根的量化法則 De Morgan’s Laws for Quantifiers

• ¬∀xP(x) ≡ ∃x¬P(x)
• ¬∃xP(x) ≡ ∀x¬P(x)

1.5 嵌套限定詞 Nested Quantifiers

Example 1: Let U be the real numbers,
限定 P(x,y): x∙y=0
What is the truth value of the following:

1. ∀x∀yP(x,y)
   Answer: False
2. ∀x∃yP(x,y)
   Answer: True
3. ∃x∀y P(x,y)
   Answer: True
4. ∃x∃y P(x,y)
   Answer: True

Example 2: Let U be the real numbers,
限定 P(x,y): x/y=1
What is the truth value of the following:

1. ∀x∀yP(x,y)
   Answer: False
2. ∀x∃yP(x,y)
   Answer: False
3. ∃x∀yP(x,y)
   Answer: False
4. ∃x∃yP(x,y)
   Answer: True

1.6 推斷規則 Rules of Inference

(速度太快，回去用啦qqqq)

重溫蘇格拉底示例

我們有兩個前提：

• 所有的人都是凡人
• 蘇格拉底是一個人

結論是：

• 蘇格拉底是凡人

我們如何從前提中得出結論？

我們可以將謂詞邏輯中的前提（線以上）和結論（線下）表示為參數：

∀x(Man(x)→Mortal(x))
Man(Socrates)
---------------------
∴ Mortal(Socrates)

我們很快就會看到，這是一個有效的論據。

有效參數 Valid Arguments

我們將展示如何分兩個階段構造有效的參數;首先用於命題邏輯，然後用於謂詞邏輯。推斷規則是構建有效參數的基本組成部分。

1. 命題邏輯 (Propositional Logic)
   推斷規則
2. 謂詞邏輯 (Predicate Logic)
   命題邏輯的推斷規則加上處理變數和限定詞的其他推斷規則

命題邏輯的推斷規則：莫杜斯·波恩斯 Rules of Inference for Propositional Logic: Modus Ponens

例子：
p是"下雪了"
q是"我會學習離散數學"

• 如果下雪，那麼我會學習離散數學。
• 下雪了...

因此，我將學習離散數學。

p → q
p
-----
∴ q

對應的重言式: (p∧(p→q))→q

莫杜斯托倫斯 Modus Tollens

p是"下雪了"
q是"我會學習離散數學"

• 如果下雪，那麼我會學習離散數學。
• 我不會學習離散數學。

因此，沒有下雪。

p → q
¬q
-----
∴ ¬p

對應的重言式: (¬p∧(p →q))→¬q

假設性系統論 Hypothetical Syllogism

p是"它雪"
q是"我會學習離散數學"
r是"我會得到A"

• 如果下雪，那麼我會學習離散數學。
• 如果我學習離散數學，我將獲得A。

因此，如果下雪，我會得到A。

 p → q
 q → r
--------
∴ p → r

對應的重言式: ((p→q)∧(q→r))→(p→r)

分離性詞學 Disjunctive Syllogism

p是"我會學習離散數學"
q是"我會學習英國文學"

• 我會學習離散數學，或者學習英國文學
• 我不會學習離散數學

因此，我將學習英國文學。

 p ∨ q
 ¬p
--------
∴ q

對應的重言式: (¬p∧(p∨q))→q