Home

To be completed!

太基礎，不重要者 以及 普通的名詞解釋 將不會被列出來

# Ch1 Logic

  • c for 'it is cold'; r for 'it is rainy'; w for 'it is windy', choose the correct propositional formula for "It is rainy only if it is windy and cold." (p4)

    • r → (w ∧ c)
    • (w ∧ c) → r

    only if 表 →

  • True or False (p5)

    • If 2+2=5, then 1+1=3
    • (1=1 → 2=2) ↔ (2≠2 → 1≠1)
    • 3+2=6 iff 1+1=3
    • If π is a rational number, then the set of integers is uncountable.
    • 前提 false, 所以整句 true
    • iff 為 true ↔ true or false ↔ false, 又第二個 () 前提 false, 所以整句 true
    • 同 A
    • 同 A

  • "x for y" 形式的 condition, find necessary but not sufficient (p7 中央資工)
    => 即找滿足 x→y, 但不滿足 y→x 者

  • 判別是否為 tautology or contradiction 的方法:

    1. truth table
    2. 利用 satisfiable (指能夠代入某組值使整個命題為真) 找反例
    3. 推導出 true or false

  • 命題 (proposition/statement):"If p then q else r" 的 propositional formula 為？(p11)
    Ans: (p → q) ∧ (!p → r) or (p ∧ q) ∨ (!p ∧ r) ，推導如下

(p→q)∧(!p→r)
≡ (!p∨q) ∧ (p∨r) ≡ ((!p∨q)∧p) ∨ ((!p∨q) ∧ r)，分配律
≡ (p∧!p) ∨ (p∧q) ∨ (r∧!p) ∨ (r∧q)，q,r 不可能同時成立
≡ (q∧p) ∨ (!p∧r)
若把 "else r" 去掉，則由 (p ∧ q) ∨ (!p ∧ r) 可以推導成 ~q ∨ p

  • consistent : 指條件們可同時成立，類似 "方程式有解" (p13)

  • p → q ≡ ~q → ~p ≡ ~p ∨ q (p24)

  • 反命題 (inverse): ~p → ~q ≡ 逆命題 (converse): q → p

  • 等價證明常用的性質表: (p27)

對偶∨∧
1. 分配律 (distributive)p ∨ (q∧r) ≡ (p∨q) ∧ (p∨r)p ∧ (q∨r) ≡ (p∧q) ∨ (p∧r)
2. 結合律 (associative)(p∨q) ∨ r ≡ p ∨ (q∨r)(p∧q) ∧ r ≡ p ∧ (q∧r)
3. 交換律 (commutative)p ∨ q ≡ q ∨ pp ∧ q ≡ q ∧ p
4. 吸收律 (absorption)p ∨ (p∧q) ≡ pp ∧ (p∨q) ≡ p
5. 冪等律 (idempotent)p ∨ p ≡ pp ∧ p ≡ p
6. 同一律 (identity)p ∨ F ≡ pp ∧ T ≡ p
7. 控制律 (domination)p ∨ T ≡ Tp ∧ F ≡ F
8. 否定律 (negation)p ∨ ~p ≡ Tp ∧ ~p ≡ F
9. 雙否定律 (double negation)(p) ≡ p
10.De Morgan's law~(p∨q) ≡ ~p ∧ ~q~(p∧q) ≡ ~p ∨ ~q
其它p ↔ q ≡ (p→q) ∧ (q→p)

其中分配律可以擴展如: (p∨a∨b) ∧ (p∨c∨d) ∧ (p∨e∨f) ≡ p ∨ [(a∨b) ∧ (c∨d) ∧ (e∨f)] (p34)

  • ~(p ↔ q) ≡ p ↔ ~q (p29)

  • resolution0 : 以 (p∨q) ∧ (~p∨r) → (q∨r) 為基礎的推論規則。(因為若 p=0, 看 q; 若 p=1, 看 r) (p320)

  • 常用的論證 (argument) 方法 (P38)

名稱true 的前提導出為 true 的結論
1. 肯定律 (modus ponens)(p→q) ∧ (p)∴q
2. 反證法 (modus tollens)(p→q) ∧ (~q)∴~p
3. 矛盾法(~p → F)∴p
4. 三段論證(p→q) ∧ (q→r)∴p→r
5.conjunction(p) ∧ (q)∴p∧q
6.disjunctionp∴p∨q
7.simplication(p ∧ q)∴p
8.(p∨q) ∧ (~q)∴p

  • Let L (x,y) be proposition function "x loves y"，求下面 proposition 的 symbolically. (p51)

    • "There is someone who loves no one besides himself." ∃x∀y\exist{x} \forall{y} (x≠y → ~L(x,y)

    "有個人不愛自己以外的任何人"

    • "Nobody loves everyone." ∀x∃y\forall{x} \exist{y} ~L(x,y)

    "每人都有不愛之人"
    相當於～[∃x∀y\exist{x} \forall{y} L(x,y)]

  • "There is no maximum integer." ∀x∃y\forall{x} \exist{y} x<y (p53)

    不論 x 多大，都有比 x 大的數。

進度: p58

# Ch2 Set

注意: ∅∉∅\emptyset \not\in \emptyset, ∅⊆∅\emptyset \subseteq \emptyset

數系實數ℝ複數ℂ有理數ℚ無理數整數ℤ分數正整數0負整數自然數ℕ

  • N = {1,2,...} 會特別說明，否則都是從 0 起算。

  • 空集合是任意集合的子集合，即 ∀A,∅⊆A\forall A, \emptyset \subseteq A (p85)

  • Power set P (A) 是收集 A 的所有子集合的一個集合，也記做 2A2^A (p89)
    eg: A = {1,2}, 則 P (A)={∅(因為空集合是任意集合 A 之子集合), {1}, {2}, {1,2}(即自己)}

考慮 U 中的子集合 A、B (p96)

  • A-B (或 A\B): 即 A 與 B 的差集，意思同於 A∩B‾A \cap \overline{B} 。
  • A⊕B: 即互斥或 (XOR)，也 = (A∪B)−(A∩B)=(A−B)∪(B−A)(A \cup B) - (A \cap B) = (A-B) \cup (B-A) 。

集合的運算性質 (p106)

名稱
分配律 (distributive)A ∪ (B∩C) = (A∪B) ∩ (A∪C)A ∩ (B∪C) = (A∩B) ∪ (A∩C)
吸收率 (absorption)A ∪ (A∩B) = AA ∩ (A∪B) = A
De Morgan's lawA∪B‾=A‾∩B‾\overline{A \cup B} = \overline{A} \cap \overline{B}A∩B‾=A‾∪B‾\overline{A \cap B} = \overline{A} \cup \overline{B}
單位元性質 (identity)A∪∅=AA \cup \emptyset = A

例: ∅⊕{a,∅,{∅}}={a,∅,{∅}}\emptyset \oplus \{a, \emptyset, \{\emptyset\} \} = \{a, \emptyset, \{\emptyset\} \} 。

  • 如果想要省時間，請直接參考: 考研的筆記 or 台大共筆
  • 工具: Mermaid Live Editor, KaTeX editor