iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 11
3
自我挑戰組

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

[Day 11] 第二堂離散數學

1.1 命題邏輯 (Propositional Logic)

命題 (Propositions)

==命題是正確或虛假的聲明性句子==

  • 命題示例:
    • 月亮是由綠色乳酪製成的。
    • 特倫頓是新澤西州的首府。
    • 多倫多是加拿大的首都。
    • 1 + 0 = 1
    • 0 + 0 = 2
  • 不是命題的示例。
    • 坐下!
    • 現在幾點鐘?
    • X + 1 = 2
    • X + Y = Z

命題邏輯 (Propositional Logic)

  • 構建命題 (Constructing Propositions)
    • 命題變數:p, q, r, s, …
    • 總是正確的命題用T表示
    • 總是虛假的命題用F表示
    • 複合提案;由邏輯連接和其他命題構造
      • 否定(Negation) ¬
      • 關聯(Conjunction) ∧
      • 無關(Disjunction) ∨
      • 含意(Implication) →
      • 雙條件(Biconditional) ↔

¬ 複合命題:否定 (Compound Propositions: Negation)

P ¬P
1 0
0 1

∧ 關聯 (Conjunction)

==AND==

p q p∧q
1 1 1
1 0 0
0 1 0
0 0 0

∨ 無關 (Disjunction)

==OR==

p q p∨q
1 1 1
1 0 1
0 1 1
0 0 0

⊕ "Or"在英文中的涵義 (The Connective Or in English)

p q p⊕q
1 1 0
1 0 1
0 1 1
0 0 0

→ 含意 (Implication)

==p對,q就應該對==

p q p→q
1 1 1
1 0 0
0 1 1
0 0 1

e.g. 如果p表示"我在家,"q表示"下雨了",p→q表示"如果我在家,那麼下雨了。
在p→q,p是假設(先行或前提)和q是結論(或後果).

不同方式表示"p→q"

  • if p, then q
  • if p, q
  • q unless ¬p
  • q if p
  • q whenever p
  • q follows from p
  • p implies q
  • p only if q
  • q when p
  • p is sufficient(充分) for q
  • q is necessary(必須) for p
  • a necessary condition for p is q
  • a sufficient condition for q is p

逆向、對換和反 (Converse, Contrapositive, and Inverse)

  • 從 p→q 產生新的句子
    • q→p ▶ p→q (Converse)
    • ¬q→¬p ▶ p→q (Contrapositive)
    • ¬p→¬q ▶ p→q (Inverse)

e.g.
converse: If I do not go to town, then it is raining.
inverse: If it is not raining, then I will go to town.
contrapositive: If I go to town, then it is not raining.

↔ 雙條件 (Biconditional)

p q p↔q
1 1 1
1 0 0
0 1 0
0 0 1

真值表 (Truth Table)

p q r ¬r p∨q p∨q → ¬r
1 1 1 0 1 0
1 1 0 1 1 1
1 0 1 0 1 0
1 0 0 1 1 1
0 1 1 0 1 0
0 1 0 1 1 1
0 0 1 0 0 1
0 0 0 1 0 1

等效命題 (Equivalent Propositions)

p q ¬p ¬q p→q ¬q → ¬p
1 1 0 0 1 1
1 0 0 1 0 0
0 1 1 0 1 1
0 0 1 1 1 1

使用真值表顯示不等效性 (Using a Truth Table to Show Non-Equivalence)

p q ¬p ¬q p→q ¬p → ¬q q→p
1 1 0 0 1 1 1
1 0 0 1 0 1 1
0 1 1 0 1 0 0
0 0 1 1 1 1 1

邏輯運算子的優先順序 (Precedence of Logical Operators)

  1. ¬

1.2 命題邏輯的應用 (Applications of Propositional Logic)

邏輯拼圖1

一個島上有兩種居民,騎士總是說實話,惡棍總是說謊。
你去島上,遇見A和B。
A說"B是騎士"
B說"我們兩個類型相反"

例子:A 和 B 的類型是什麼?
解決方案:

A B ok?
1 1 0
1 0 0
0 1 0
0 0 1

邏輯拼圖2

一個島上有兩種居民,騎士總是說實話,惡棍總是說謊。
你去島上,遇見A和B。
A說"B是騎士"
B說"A是惡棍"

例子:A 和 B 的類型是什麼?
解決方案:

A B ok?
1 1 0
1 0 0
0 1 0
0 0 0

邏輯電路 (Logic Circuits)

  • 電子電路
    輸入/輸出信號可以視為 0 或 1
    • 0 表示假
    • 1 表示真
  • 複雜的電路由三個基本電路構成,稱為閘門。
    • 逆變器(inverter)(不是gate)獲取輸入位並生成該位的否定
    • 的OR門取兩個輸入位,並生成等效于兩個位的分離的值
    • 的AND門取兩個輸入位,並生成等效于兩個位結合的值
  • 通過組合這些基本電路,通過為輸出運算式的每一部分構建電路,然後組合它們,可以生成給定輸入信號的所需輸出,從而構建更複雜的數位電路

1.3 命題等價 (Propositional Equivalences)

語論、矛盾和意外 (Tautologies, Contradictions, and Contingencies)

p ¬p p∨¬p p∧¬p
1 0 1 0
0 1 1 0

邏輯等效 (Logically Equivalent)

p q ¬p ¬p∨q p→q
1 1 0 1 1
1 0 0 0 0
0 1 1 1 1
0 0 1 1 1

德摩根定律 (De Morgan’s Laws)

==¬(p∧q)≡¬p∨¬q==
==¬(p∨q)≡¬p∧¬q==

p q ¬p ¬q p∨q ¬(p∨q) ¬q∧¬p
1 1 0 0 1 0 0
1 0 0 1 1 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 1

關鍵邏輯等價 (Key Logical Equivalences)

p∧T≡p, p∨F≡p
p∨T≡T, p∧F≡F
p∨p≡p, p∧p≡p
¬(¬p)≡p
p∨¬p≡T, p∧¬p≡F

p∨q≡q∨p, p∧q≡q∧p
(p∧q)∧r≡q∧(p∧r)
(p∨q)∨r≡q∨(p∨r)
(p∨(q∧r))≡(p∨q)∧(p∨r)
(p∧(q∨r))≡(p∧q)∨(p∧r)
p∨(p∧q)≡p
p∧(p∨q)≡p

補充

  • DNF
    • ()內連接詞只能有'且' 和'¬',()外連接時只能有'或'
  • CNF
    • ()內連接詞只能有'或',()外連接時只能有'且'和'¬'

上一篇
[Day 10] 第二堂計算機概論
下一篇
[Day 12] 第二堂程式設計
系列文
資工系大一課程/日常筆記30

尚未有邦友留言

立即登入留言