# 三大理論

- Complexity Theory
- 區分「困難的問題」跟「簡單的問題」
- Computability Theory
- 區分「可解決的問題」跟「不可解決的問題」

上面這兩個可以和稱為 「theory of computation」

- Automata Theory
- 處理「數學計算模型 mathematical models of computation」的定義和性質

由於上面兩個 Theory 需要精確的數學定義和性質，所以需要先從 Automata Theory 開始。

# Mathematical Notions and Terminology

下面是常用的概念和術語，要熟記：

## Set

- non-ordered
- elements / members
- Membership
- Subset
- Empty set
- Union
- Intersection

## Sequence

- ordered
- Finite sequences / k-tuple

## Cartesian (Cross) Product

## Functions

[參考維基百科](https://en.wikipedia.org/wiki/Range_of_a_function)。

- 定義域 domain
- 對應域 codomain
- 值域 image

另一個比較常見的名詞「range」，有時候會拿來指「codomain」，有時候會指「image」。

在自動機裡面指「codomain」。

- 滿射「onto/surjection」
- 當 codomain 等於 image 的時候

如果 function 的 argument 只有一個，或者說 1-ary-function，他又可以叫做 uniary function。

如果有兩個，又叫做 binary function。

>ary 是 arity 的...別稱?

## Relations

range 跟 domain 都很特殊的 function。

對於一個 binary relation，暫作 R，則 $R(x,y)=true$ 可以簡寫為 $x R y$，例如常見的 $1<2$。

如果一個 relation 滿足

- 自反性
- $\forall x,xRx$
- 對稱性
- $\forall x,y,xRy\ implies\ yRx$
- 遞移性
- $\forall x,y,z,xRy\ and\ yRz\ implies\ xRz$

叫做 equivalence relation；例如常見的等號。

## Graph

## Strings and Languages

- alphabet
- symbols
- a String = finite sequence of symbols
- Empty string ε
- Shortlex (string) order
- dictionary order but shorter precede longer
- language = a set of strings

## Boolean Logic

- MP 肯定前件就肯定後件規則
- $$A\rightarrow B\\A\\/\therefore B$$
- MT 否定後件就否定前件規則
- $$A\rightarrow B\\\sim B\\/\therefore \sim A$$
- Add 添加規則
- $$P\\/\therefore P \vee Q$$
- DS 選言三段論規則
- $$P \vee Q\\ \sim P \\ /\therefore Q$$
- HS 假言三段論規則
- $$P\rightarrow Q\\Q\rightarrow R\\ /\therefore P \rightarrow R$$
- Simp 簡化規則
- $$P\cdot Q \\ /\therefore P$$
- Conj 連結規則
- $$P\\Q\\\therefore P\cdot Q$$
- CD 建設性兩難規則
- $$P\rightarrow Q\\R\rightarrow S\\ P\vee R \\ /\therefore Q\vee S$$
- DN 雙重否定規則
- $$P\\/\therefore \sim\sim P$$
- Contra 異質換位規則
- $$P\rightarrow Q \equiv \sim Q\rightarrow \sim P$$
- Impl 蘊涵規則
- $$P\rightarrow Q \equiv \sim P\vee Q$$
- Idemp 等冪規則
- $$P\equiv P\cdot P \\ P \equiv P \vee P$$
- Dist 分配規則
- $$P \vee (Q \cdot R)\equiv (P \vee Q) \cdot (P \vee R)$$
- $$P \cdot (Q \vee R)\equiv (P \cdot Q) \vee (P \cdot R)$$
- IE 移出移入規則
- $$P \rightarrow ( Q \rightarrow R)\equiv (P\cdot Q)\rightarrow R$$
- Comm 交換規則
- $$P \vee Q \equiv Q \vee P\\P \cdot Q \equiv Q \cdot P$$
- Assoc 結合規則
- $$P \vee (Q \vee R) \equiv (P \vee Q) \vee R\\P \cdot (Q \cdot R) \equiv (P \cdot Q) \cdot R$$
- Equiv 等值規則
- $$P \leftrightarrow Q \equiv (P \rightarrow Q) \cdot (Q \rightarrow P)$$
- $$P \leftrightarrow Q \equiv (P \cdot Q) \vee (\sim P \cdot \sim Q)$$
- DeM 德摩根規則
- $$\sim (P \cdot Q) \equiv \sim P\vee \sim Q$$
- $$\sim (P \vee Q) \equiv \sim P\cdot \sim Q$$

兩種證法：

- IP 間接證法
- $$A \rightarrow B \\ A \vee B \\ /\therefore B$$
- 藉由假設 $\sim B$ 可以產生 $B \cdot \sim B$ 這樣的矛盾，於是便知道 $/\therefore B$
- CP 條件證法
- $$A \rightarrow (\sim B \rightarrow C)\\ \sim C \\ /\therefore A \rightarrow \sim \sim B$$
- 藉由假設 $A$ 可以推得 $\sim \sim B$，因此可以得到 $/\therefore A \rightarrow \sim \sim B$

# 有關 Definitions 跟 Theory 的名詞

- Definitions
- 描述某個物體的概念
- statement
- 描述某個物體具有某個性質
- statement 可能是對的或錯的
- proof
- 使用可信的邏輯論證，證明某個 statement 是對的。
- theorem
- proved mathematical statement
- Lemma
- 證明一個 statement 的過程中，某些其他有用的 statement
- 這些 statement 可以幫助我們證明原本的 statement
- 所以也是需要把 Lemma 證明成 theorem
- Corollary
- 可以從某些 theorem 或 proof 輕易推導出的有關的 statement

# Finding Proofs

- 小心的閱讀 statement
- 分段討論 statement
- 從某些(簡單的)例子得到直覺性的感受
- 考慮 special cases

# Types of Proof

- Proof by Construction
- Proof by Contradiction
- Proof by Induction