iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 25
1
自我挑戰組

資工系大一課程/日常筆記系列 第 25

[Day 25] 第三堂離散數學

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
Statement When True? When False
∀x∀yP(x,y)、∀y∀xP(x,y) P(x,y) is true for every pair x,y. There is a pair x, y for which P(x,y) is false.
∀x∃yP(x,y) For every x there is a y for which P(x,y) is true. There is an x such that P(x,y) is false for every y.
∃x∀yP(x,y) There is an x for which P(x,y) is true for every y. For every x there is a y for which P(x,y) is false.
∃x∃yP(x,y)、∃y∃xP(x,y) There is a pair x, y for which P(x,y) is true. P(x,y) is false for every pair x,y

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


上一篇
[Day 24] 第四堂計算機概論
下一篇
[Day 26] 第四堂程式設計
系列文
資工系大一課程/日常筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言