# 離散數學 上課筆記

[TOC]
- [notion](https://www.notion.so/e317254f9920443397b55c05978fb033?v=c542fa0fd3ca42ffb6b4697a47e303c4)
# 複習大綱
| Unit | 考古程度 | 熟練程度 | 備註 |
|:----------:|:--------:|:--------:|:--------------:|
| 基本數學 | ★☆☆☆☆ | ✓✓✓✓✓ | |
| 關係與函數 | ★★☆☆☆ | ✓✓✓✓✓ | |
| 排組、排容 | ★★★★☆ | ✓✓✓✓✓ | |
| 生成函數 | ★★★★★ | ✓✓✓✓✓ | |
| 遞迴關係 | ★★★★★ | ✓✓✓✓✓ | 三校必考 |
| 圖論 | ★★★★★ | ✓✓✓✓✓ | 台大電機丙必考 |
| 樹 | ★★★★★ | ✓✓✓✓✓ | 資料結構再讀 |
| 演算法分析 | ★★★★★ | ✓✓✓✓✓ | 演算法再讀 |
| 代數系統 | ★☆☆☆☆ | ✓ | |
| 偏序、全序 | ★☆☆☆☆ | ✓✓✓ | 電機丙很喜歡考 |
| 坡里亞計數 | ☆☆☆☆☆ | ✓✓ | |
| 編碼與解碼 | ☆☆☆☆☆ | | |
| 有線狀態機 | ★☆☆☆☆ | ✓✓✓✓✓ | |
:::spoiler

:::


# CH1(permutation)
### Negation(¬p)
1¬p (not p):
Discrete mathematics is <font color="#f00">**NOT**</font> a required
course for CS undergraduates.
### Conjunction(p ∧ q)
p ∧ q (p and q):
Discrete mathematics is a required course
for CS undergraduates <font color="#f00">**AND**</font>Professor
Chen teaches discrete mathematics.
### Disjunction(p ∨ q)
p ∨ q (p or q):
Discrete mathematics is a required course
for CS undergraduates <font color="#f00">**OR**</font> Professor Chen
teaches discrete mathematics.
### Implication(p→q)
p→q (p implies q):
<font color="#f00">**IF**</font> discrete mathematics is a required
course for CS undergraduates, <font color="#f00">**THEN**</font>
Professor Chen teaches discrete
mathematics. <font color="#f00">(“**p only if q**”) </font>
⭐<font color="#f00">**¬p∨q**(台大必考)</font>
### <font color="#f00">**Bicon**</font>ditional(IFF/p↔q )

p↔q (p if and only if q):
Discrete mathematics is a required course
for CS undergraduates <font color="#f00">IF AND ONLY IF</font>
Professor Chen teaches discrete
mathematics.
### TRUE TABLE

| p | q | ┐p | ┐q | p^q | ┐q v ┐p | p→q | p ↔ q | p XOR q |
|:-----:| ----- | ----- |:-----:|:-----:|:-------:|:-------:|:-----:|:-------:|
| / | / | not p | not q | and | or | if than | IFF | XOR |
| True | False | Flase | True | Flase | True | F | T | T |
| Flase | False | True | True | Flase | True | T | F | F |

運先優先權
如果需要更改順序用誇號表示

### 邏輯等價(logical Equivalences)

#### 恆真恆假
def : a compound proposition(復合乘數) **always true**(or false)
We call it<font color="#f00"> (**true的情況="tautology"),( false的情況="contradiction"**)</font>
#### 狀況補充
if p ↔ q is tautology (p≡q)
**<==>(two statament)
<-->(one statment)**
p->q≡ ┐pvq
**觀察法**
找出比較難發生的情況
or 看蛇模時候 是 false
and 看甚麼時候 True

---
當我們運用證明時序要靠這下方的資料去做證明
E.g **迪摩根定理**

| ┐(p ∩ q)≡ ┐p ∪ q┐ | ┐(p ∪q )≡┐p ∩ ┐q | Column 3 |
| ------------------ |:----------------:| -------- |
| Text | Text | Text |

# CH2 relation
### Binary Relations
**R = {(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4)}.**
可以寫成
1. Relation matrix
2. Graph representation

- reflextive{aRb > bRa}
- irreflextive{aRb > bRa but a!=b}
- sysmetic {有(a,b)則必有(b,a)}
- antisysmetric{有(a,b)則不能有 (b,a)除非 a=b}
- asysmetic{有(a,b)則不能有(b,a)}
- transive{aRb > bRc 則 aRc}
### Equivalence Relations

# CH3 Permutation
## power set 冪集合()
binnary 去思考會更好懂

# CH4 GF

# CH5 [Recarsion](/2ieDBfUZSYK3rExBQVlXeg)
# CH6
# CH7 tree
## Tree 基本定義
**不含 cycle的連通無向圖<font color ="red">(acyclic)**</font>
## MST(miniunm span tree)
## Kruskal's Algorithm:

## prim tree:

# CH8 Boolean
1. Closure under ⋅ and +
For all a, b ∈ K, a ⋅ b ∈ K and a + b ∈ K.
2. Commutativity of ⋅ and +
For all a, b ∈ K, a ⋅ b = b ⋅ a and a + b = b + a.
3. Distributivity of ⋅ and +
For all a, b, c ∈ K, a ⋅(b + c) = (a ⋅ b) + (a ⋅ c) and
a + (b ⋅ c) = (a + b)⋅(a + c).
4. Identity and zero elements
K contains two elements 1 (identity) and 0 (zero) :
a ⋅ 1 = a and a + 0 = a for all a ∈ K.
5. Complement
For every a ∈ K, there exists a (≠ a) such that
a ⋅a = 0 and a +a = 1.
a is the complement of a.
6. There are at least two distinct elements a and b
(a ≠ b) in K.