---
robots: index, follow
tags: NCTU, CS, 共筆, OOP, 游逸平
description: 交大資工課程學習筆記
lang: zh-tw
dir: ltr
breaks: true
disqus: calee
GA: UA-100433652-1
---
離散數學--楊武
===

# 課程

## 第一章 Logic and Proofs

## 第二章 Sets, Functions, Sequences and Sum
- Sets
- 元素可任意(不一定要數字) e.g: { car, airplane, ... }
- 元素可重複 e.g: {1,1,2,3,5,7}
- 寫法
1. {2,3,5,7,...}
2. {n | n=2k}

- 集合可爲另一集合的元素 e.g: { {1,2,3}, car, {airplane,shoe}, {{{0}}} }
- 空集合 {} = ∅
- 集合關係
1. 聯集 A ∪ B = { x | x ∈ A || x ∈ B }
2. 交集 A ∩ B = { x | x ∈ A && x ∈ B }
3. 差集 A - B = { x | x ∈ A but x ∉ B } ≠ B - A
4. 補集 U - A = ~A { x | x ∈ ∀ ~A }
5. 宇集 U = ∀x = A + ~A
6. symmatrix difference A ⊕ B = (A-B) ∪ (B-A)
7. subset A ⊆ B
8. proper subset A ⊂ B = A ⊆ B && A ≠ B

- Lemma
1. A e= B iff ∀x ∈ A, x ∈ B ( A ⊆ A, ∅ ⊆ A, ∅ ⊆ ∅)
2. 1 ≠ {1} ≠ {{1}}
3. A = B iff A ⊆ B && B ⊆ A
4. ~(A ∪ B ∪ C) == ~A ∩ ~B ∩ ~C
5. (A*B)∩(B*A) == (A∩B)*(B∩A)==(A∩B)*(A∩B)==(A∩B)^2
ex1:
A={ap * bp * cq | p,q ∈ N}
B={ap * bq * cq | p,q ∈ N}
A ∩ B = {ap * bp * cp | p ∈ N}
A ∪ B = {ax * by * cz | x=y or y=z}
A - B = {ap * bp * cq | p ≠ q}
ex2:
A ⊆ B && B = {1,2,3,4} (|B| = 4)
=> A 的可能性有 2^|B| 種
ex3:
A={1,2,3} B={x,y,z}
A x B = {(1,x)(1,y)(1,z)(2,x)...(3,z)} ((1,x) 不可對調)
|A*B|=|A|*|B| 2^|A*B| = 2^|A|*2^|B|
ex4:
∅ * A = ∅ A * ∅ = ∅
ex5:
<pf> (P*Q)∩(R*S)=(PAR)*(QAS)
Hint: X=Y == X⊆Y && Y⊆X
1. (P*Q)∩(R*S) ⊆ (P∩R)*(Q∩S)
choose any (a,b) ∈ (P*Q)∩(R*S)
so (a,b) ∈ P*Q && (a,b) ∈ R*S
=> a ∈ P && b ∈ Q && a ∈ R && b ∈ S
=> a ∈ (P∩R) && b ∈ (Q∩S)
=> (a,b) ∈ (PAR)*(QAS)
2. (P∩R)*(Q∩S) ⊆ (P*Q)∩(R*S)
(P∩R)*(Q∩S) == (P*(Q∩S)∩(R*(Q∩S)) (cause:(x∩y)*z = (x*z)∩(y*z))
== ((P*Q)∩(P*S))∩((R*Q)∩(R*S)) e= (P*Q)∩(R*S) (cause:A∩B∩C∩De=A∩C)

- operation
1. x&y=y&x
2. x|y=y|x
3. (x|y)|z=x|(y|z)
4. (x&y)&z=x&(y&z)
5. x&(y|z)=(x&y)|(x&z)
6. x|(y&z)=(x|y)&(x|z)
7. x&x=x
8. x|x=x
9. ~x=x
- infinite sets
- n(N) = |N| = ∞
- property: if A ⊂ N (A != N) => |A| = |N|
- countable set
- set that can map N { x | x ∈ N}
Lemma X={x | 0 < x < 1 } is not countable
Proof Assume X is countable
we may list all elements of x as:
x1 = 0.12376...
x2=0.2376...
x3=0.376
x4=0.000099...
....
Let y = 0.y1y2y3y4...., where yi = (the i-th digit after the decimal point of xi) + 1 (9 becomes 0)
then 0 < y < 1, i.e. y ∈ X
But we have listed all elements of X, y must be one of those xi's.
This is impossible since the i-th digit after the decimal point of y differ from the i-th digit after the decimal point of xi, which implies that y ≠ xi ∀ i →←

Lemma Assume A and B are countable,
Then A∩ B is countable
Then A ∪ B is countable
Then A x B is countable
Lemma Assume A1, A2, ... are countable
Then A1 ∪ A2 ∪ A3... is countable?
Then A1 x A2 x A3 ... is countable?
- conumerous
Def: A and B are conumerous iff ∃1-1 onto mapping f A → B
ex: N and O, N and E, N and Z, N and Q, N and P, N and R...
- composition
- f。g(x) = f(g(x))
- (f。g)。h (x) = f。(g。f) (x)
- f。f = f2
- f。f。f = f3
- f0 = identity function
ex:
f=[abcdefgh] = [abcdefgh] . [abcdefgh]
dfacgehb dbacefgh afcdgheb
- inverse
- Given f: A -> B
if g satisfies g(y) = x iff f(x) = y
then g = f-1(x)
- not all function have inverse
[abcd] have no inverse
ccba 1. f-1(c) = a or b ? 2. f-1(d) = ?
- Lemma: f has an inverse iff f is 1-1 and onto(映成)
- Lemma: inverse is unique -> f-1 is unique (if f-1 exists)
- Lemma: Assume f-1 and g-1 exist => f-1。g-1 = (g。f)-1
- Lemma: (fk)-1 =(fff...f)-1
- Theorem: Assume A is any finit set, there is no 1-1 onto function from A to 2A
- Theorem: Assume A is infinit set, there is no 1-1 onto function from A to 2A
- sequences summation products
- 1 2 3 ... arithmetic seq
- 1 2 4 8 16... geometric
- 1/1 1/2 1/3 1/4... harmonic (倒數呈等差) (Hn)
- 1 1 2 3 5 8... Feb
- ∑ summation
- ∑c = nc
- ∑k = n(n+1) / 2
- ∑k2 = n(n+1)(2n+1) / 6
- ∑k3 = ( n(n+1) / 2 )2
- ∑xk = x1 + x2 + ... + xn = (x-xn+1) / (1-x)
- ∑Hn = infinit
- π products
- π(ab) = πa * πb
ex:

will be an harmonic seq.
ex:
n筒油，車車每走來回走幾公里？
ex:
πi=1n πj=1m(ij) = (m!)n(n!)m
πi=1n(πj=1m(πk=1p(ijk))) = (n!)mp(m!)np(p!)nm
ex:
Let Hn = 1/1+1/2+1/3+...+1/n
=> H2^k >= 1+k/2
when k = 1 => H2 = 1+1/2 ok
if H2^k> 1+k/2
H2^(k+1) = 1+1/2+1/3+...+1/2k+...+1/2k+1
= H2^k + 1/2k+1 + 1/2k+2 +...+1/2k+1
>= 1+k/2 + 2k*1/2k+1
= 1+ k/2 + 2k / 2k+1
= 1 + k/2 + 1/2
= 1+(k+1)/2
ex:
p1a1p2a2p3a3...pkak
= (p10+p11+...+p1a_1)(p20+...p2a_2)...(pk0+...pka_k)
= (1-p1a_1+1)/(1-p1) * ... * (1-pka_k+1)/(1-pk)
ex:
πp1a1p2a2...pkak
= ππ...π()
= p1a1v(n)/2p2a2v(n)/2...pkakv(n)/2
ex:
Assume 2n-1 are primes
σ(2n-1(2n-1))
所有質因數有：2,2n-1
所有因數：...
= 2n-1 + (2n-1)(2n-1)
= (2n-1)2n
=2 2n-1(2n-1)
perfect number!
ex:
an = 1,2,2,3,3,3,4,4,4,4,...
Define f(k) = the position of last k
f(n) = n + f(n-1) = ∑n = n(n+1)/2
an = [squl(2n) + 1/2]
Assume n(n-1)/2 + 1 < j < n(n+1)/2
then n = [squl(2j)+1/2]

## 第四章 Natural number
1729 = 13+123 = 93+103

- meaning of natural number
- order
1<2<3<4<5<...
- counter
- 整除
- 因數、公因數、最大公因數gcd、公倍數、最小公倍數lcm
- Lemma: gcd(x,y) = gcd(x-y,y) ==> 展轉相除法
<proof>
Let d = gcd(x,y)
Let e = gcd(x-y,y)
so d | x
d | y
so d | x-y
so d <= gcd(x-y,y)
i.e. d <= e

so e | x-y
e | y
so e| (x-y)+y
so e | x
so e <= gcd(x,y)
so e <= d ===> e == d
- 質數prime
- infinite primes 無限個
- unique factorization 質因數分解唯一
Let p1 <= p2 <= ... <= pn
q1 <= q2 <= ... <= qm (be prime)
Assume p1p2...pn = q1q2...qn
=> n=m && pi = qi
<error proof>
cause p1p2...pn = q1q2...qm
so p1 | q1q2...qm ---> this step to the next is error!! (because it use the same lemma as itself(requisive))
so ∃k s.t. p1=qk
cause qk >= q1
so p1 >= q1
as the same result => q1 >= p1
so p1 = q1
<proof>
p1 | q1 *q2 *...
p1 | qr (for some r)
p1 = qr >= q1
同理 q1 >= p1
=> q1 = p1
- Lemma: if gcd(x,y) = 1 => E u,v s.t. ux + vy = 1
- Lemma: gcd(x,y) = gcd(x-y,y) Assume x > y > 0
- Lemma: Assume p is a prime q ∈ N => gcd(p,q) = 1 or p
- Lemma: Assume p is prime, p | a,b => p | a or p | b
- Lemma: Assume p is a prime
p | q1*q2*...
then p | q1 or p | q2 or ...or p | qn
- Unique Factorization (每一個數做分解，只有唯一形式)
- [170141183460469231731687303715884105727](https://en.wikipedia.org/wiki/Wikipedia:Evaluating_how_interesting_an_integer%27s_mathematical_property_is#170141183460469231731687303715884105727)
- Assume the smallest prime fector of n is greater than n1/3 => n is two prime number's product
- 質因數分解 < 從 sqrt(n)往下做
ex: 13837 = 101 * 137
[sqrt(n)] = 118
δ(118) - 1182 - n = 87
δ(119) = 1192 - n = 324 = 182
δ(120) = δ(119) + 2*120 - 1 = ...
ex: 一數若可分兩種兩質因平方數的合，此數必為合數
n = a2 + b2 = c2 + d2
assume n is odd
assume a,c are odd, b,d are even
a2 - c2 = d2 - b2
(a-c)(a+c) = (d-b)(d+b)
Let k = gcd(a-c,d-b)
a-c = kl
d-b = km
gcd(l,m) = 1
kl(a+c) = km(d+b)
l | d+b
m | a+c
a+c = mu ?why can same u? A:'cuz kl(a+c) = km(d+b)
d+b = lu
u | gcd(a+c,d+b)
a = (mu+kl)/2, b = (lu-km)/2, c = (mu-kl)/2, d = (lu+km)/2
n = [(k/2)2 + (u/2)2](m2 + l2)
=> 質數只可拆成一種兩平方數的合(Euler's theorem)
ex: 數列4n-1有無限多個質數
assume there are only finite primes of the form 4n-1
all prime in this form is p1, p2,...pk
define R = 4(p1*p2*...*pk) - 1
R != pi && R > pk
Suppose R is not a prime
=> R's prime factors must be odd (R is odd)
=> must be 4m-1 or 4m+1
=> R = (4m1+1)(4m2+1)...(4mk+1) = 4w+1 != 4n-1 -x-
- there are infinite prime of the form am+b {a,b|gcd(a,b)=1} (Lejeune-Dirichlet Theorem)
- 質數漸稀疏性？
- Prime number Theorem (Ganuss)
Let π(x) = number of prime ≤ x
limx->inf ( π(x)/(x/lnx) ) = 1
- twin prime: n,n+1 are prime
- Theorem: Let p,q are two consecotive primes. Then |p-q| can be as large as you wish
We wish to find p,q so that |p-q| > k
let r = k!
let p be the largest prime less than r+2
let q be the smallest prime greater than r+k
q-p >= k
- Lemma: if 2n-1 is prime, then n is a prime <=> if n is not prime, then 2n-1 is not prime
<proof> 2rs - 1 = (2r)s - 1 = ((2r)s-1 + (2r)s-2 + ... + 2r + 1)(2r - 1)
- mersenne prime 2n-1
- modular
- a ≡ b (mod n) <=> n | a-b
- Lemma: assume p and q are primes
if q | 2p - 1 then p | q-1
if p !| q-1
gcd(p,q-1) = 1
∃n,m mp+n(q-1) = 1
assume n > 0, m < 0
ause q | 2p - 1 => 2p mod q ≡ 1 ≡ (2p)-m
cause q is a prime and 2 is not a muiple of q
2q-1 mod q ≡ 1
2n(q-1) = (2q-1)n mod q ≡ 1
2 ≡ 2mp+n(q-1) mod ≡ 2mp2n(q-1) ≡ 2n(q-1) ≡ 1
- Fermat's Little Theorem
let p be a ***prime***
1. for any a: ap mode p ≡ a
2. if a is not a multiple of p, then ap-1 mod p ≡ 1
- Lemma: Assume p > 2, p is a prime then every divisor of 2p-1 must have the form 2pk+1
<proof> **===============================================> 看不懂 ＝ ＝|||**
we need to prove all prime divisors of 2p-1 have the form 2pk+1
Assume q is a prime divisor of 2p-1 => p | q-1
=> q is odd, 2 | q-1, p | q-1, 2p | q-1 => q = 2pk+1
- Lemma: Assume p and q are prime
if q | 2p - 1 then p | q - 1
- perfect number: sum of all factors = 2n
- Lemma: Assume 2n - 1 is a prime
2n-1(n2-1) is an even perfect number
(2n - 1), 2(2n - 1), 22(2n - 1)... -> Σ[2n(2n - 1)]
- Lemma: Suppose a,b ∈ N, a,b are relative prime => σ(ab) = σ(a)σ(b)
<proof>
Let a1, a2, ..., ak be all factors of a
b1, b2, ..., bp is all factors of b
=> every divisor of ab must be aibj
=> ΣΣ(aibj) = Σ(ai)Σ(bj) = σ(a)σ(b)
- Lemma: All even perfect numbers have the form 2n-1(2n - 1), where 2n - 1 is a prime
<proof> Let n is an even perfect number
σ(n) - 2n
n = 2a * m (where m is odd and a≥1)
=> σ(n) = σ(2a)σ(m) = (2a+1-1)σ(m)
σ(n) = 2n = 2*2am
=> 2a+1-1|σ(m)
σ(m) = 2a+1 * m/(2a+1-1)
let l = m/(2a+1-1)
σ(m) = m+l
l|m -> l is a factor of m
σ(m) = 1 + m + ...
=> m is a prime and l = 1
=> m = 2a_1 - 1, n = 2a(2a+1-1)
- Linear Diophantine equation: c = ax + by (a,b,c ∈ Z)
- Lemma: ax+by = c, has solutions iff gcd(a,b) | c
- 解法：先找到跟a,b到gcd的比例，乘倍數到 c …
- 3x+17y = 6 ≡ 3x ≡ 6(mod 17)

- Theme: if ca == cb (mod m)
- => a == b (mod m/gcd(c,m) )
- Theme: Let d be a multiple of gcd(c,m)
- => cx == d (mod m) has exaetly gcd(c,m) slolutions (0 <= x <= m-1)
- Fermate's Little Theme:
- Let p be a prime,
- => if a is not a multiple of p => ap-1 == 1 (mod p)
- => ap == a (mod p)
ex:
99999923 mod 23 = ?
cause 23 !| 999999 => ? = 999999
<proof>
consider a, 2a, 3a, ..., (p-1)a
a mod p, 2a mod p, 3a mod p, ..., (p-1)a mod p
if ia mod p == 0 => p | ia => p | i or p | a (but p!|a, p!|i, cause i < p)
-><- => from a to (p-1)a are all difference and not 0 when mod p
=> a*2a*3a...(p-1)a == (p-1)! (mod p)
=> (p-1)! * ap-1 == (p-1)! mod p => ap-1 == 1 (mod p) (cause p-1!==1 mod p)
ex:
31000 mod 17 = (316)62 * 38 mod 17 = 38 == (34)2 == (-4)2 ==16
- if bp-1 == 1 mod p but p is not a prime, we say p is a pseudo-prime to the base b
- 中國餘數定理:
- Let m1,m2,...mn be pairwise relatively prime,(互相互質)
- Let m = m1m2...mn
- Then the following equation have a unique solution mod m:
- x == a1 mod m1
- x == a2 mod m2
- .
- .
- .
- x == an mod mn
<proof>
1. have solution
Let pk = m/mk = m1*m2*...*mk-1* mk+1*...*mn
gcd(pk,mk) = 1 => qkpk == 1 mod mk
mk !| pk
mk | pj (j != k)
consider x = (a1p1q1+a2p2q2+...+anpnqn) mod m
=> x mod m1
== (a1p1q1+a2p2q2+...anpnqn) mod m1 == a1p1q1 mod m1 == a1 mod m1 (pkqk == 1 mod mk)
x is a solution
2. unique
assume y1 != y2 are both solution (0 <= y1,y2 < m)
m1 | y1-y2
m2 | y1-y2
...
mn | y1-y2
=>y1-y2 = i*lcm(m1,m2,...,mn) but lcm(m1...mn) = m1*m2*...*mn = m => y1-y2 > m -><-
ex:
x == 2 mod 3
x == 3 mod 5
x == 2 mod 7
=> m1 = 3, a1 = 2, q1 = 2
=> m2 = 5, a2 = 3, q2 = 1
=> m3 = 7, a3 = 2, q3 = 1
=> x == 23 mod 105
- Theme: Let p,q,a e N
- Let m = lcm(p,q)
- the unique solution:
- x == a mod p
- x == a mod q
- is
- x == a mod m
<proof>
x = a+pk = a+ql => m | pk m | ql => x = a+mc
- Theme:
- Let m1,m2,...,mn,a e N
- Let m = lcm(m1,m2,...,mn)
- The unique solution to
- x == a mod m1
- x == a mod m2
- ...
- x == a mod mn
- is
- x == a mod m
- Theme:
- Let m1,m2,...,mn be pairwise relatively prime
- Let m = m1*m2*...*mn
- Then x == a mod m1
- x == a mod m2
- ...
- x == a mod mn
- has a unique solution modulo m
- Encryption
- 對稱式
- 非對稱式: public, private key
- RSA => 挑戰質因數分解速度(弱點一 因數分解n 求 p,q, 弱點案二 e過小
m -> encrypt c = me mod n -> ciphertext -> decrypt p = cb mod n -> p (= m)
method:
choose two large primes p,q
choose e the is relatively prime to (p-1)(q-1)
choose d s.t. d*e == 1 mod (p-1)(q-1)
set n = q*p
encrypt:
me mod n = c
decrypt
cd mod n = m
=> public key: (e,n)
=> private key: (d,p,q)
<proof> (me)d mod n == m
assume p !| m
p is a prime => mp-1 == 1 mod p
(me)d = med = m1+(p-1)(q-1)k = m(mp-1)(q-1)k mod p == m mod p
同理 (me)d == m mod q
lcm(p,q) = qp -------中國餘數定理---------> (me)d == m mod n

**Math Induction**
P(N)
[ P(1) ∧ ∀k (P(k)->P(k+1)] -> ∀kP(k)
- 河內塔
- 費氏數列: fn > an-2 for n >= 3 and a = ( 1 + sqrt(5) ) / 2
- Lame's theorem:
- gcd(a,b) (a > b > 0)
- at most [5 * log10 b] + 1 次輾轉相除法可找到 gcd
assume 做n次
=>
r0 = r1q1 + r2
r1 = r2q2 + r3
.
.
.
rn-2 = rn-1qn-1 + rn
rn-1 = rnqn

=>
rn >= 1 = f2
rn-1 = rnqn >= 2 = f3
rn-2 = rn-1qn-1 + rn >= rn-1 + rn = 3 = f4
.
.
.
r2 >= r3 + r4 = fn
b = r1 >= r2 + r3 = fn+1
- blaanced parentheses (括號成對題目) (s 為成立的set)
- if λ e s (λ是空字串)
- if x e s => (x) e s
- if x, y e s => xy e s
- anthmetic expressions
- i e s
- if x e s => (x) e s
- if x,y e s => (x+y) e s, (x-y) e s, (x * y) e s, (x / y) e
- 逆敘述問題
- Pigeon hole principle (鴿籠原理)
- 任意選五個數字，其中必有二數和或差為7的倍數
- [0], [1 6], [2 5], [3 4]
- choose n+1 numbers from 1 to 2n (n > 1), exist a,b s.t. a | b
- [1 2 4 8 ...], [3 3*2 3*4 3*8...], [5 5*2...], [7...]
- choose n+1 numbers from 1 to 2n (n > 1), exist a,b s.t. a,b 互質
- [1 2], [3 4], [5 6],...
- choose n numbers, exist a,b s.t. either (2n-3 | a+b) or (2n-3 | a-b)
- [0], [1 2n-4], [2 2n-5] ... [n-2 n-1]
- 三角形問題
- 交點問題
- 整數點問題
- 1~9 pi (a-b)
- ˙77天 >= 1 and <= 132
- n2 + 1 (distinct) => n+1 個數都是遞增或遞減 ~~~~~
- 方形九點 三角形area <= 1/8

**Permutations**
有趣題目 [a](http://www.funlearn.tw/viewthread.php?tid=2920) [b](http://math1.ck.tp.edu.tw/%E6%9E%97%E4%BF%A1%E5%AE%89/%E5%AD%B8%E8%A1%93%E7%A0%94%E7%A9%B6/%E8%A4%87%E7%BF%92%E8%AC%9B%E7%BE%A9/%E6%8E%92%E5%88%97%E7%B5%84%E5%90%88(%E5%AD%B8%E7%94%9F%E7%89%88).pdf) [c](http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_07/)
Counting

- no repetition
- no missing items
- correct viewpoint
- parity:
- 2: 2r-1 ( if last r-1 digit is even, the first digit just can have 1, otherwise, 0 )
- 5: g(r) = 4*g(r-1) + 1*(5r-1 - g(r-1))
- rule of sum
- rule of product
| | ordered | unordered |
| ----------------- | ------- | --------- |
| no repetitions | P | C |
| allow repetitions | π | H |

- 重複加密 is better
- Hnr = Hr+1n-1
- Hnr != Hrn
- Hnr = Hn-1r + Hn-1r-1 + Hn-1r-2 + ... + Hn-10
- Hnr = Hn-1r + Hnr-1
- Hnr = n/r Hrn
- => 上面的加左邊的
- 捷徑走法 之 不能超過對角線
- 1. DP
- 2. f(k,k) = c(k) (catalan number)= (2n)! / (n! n!) - (2n)! / ( (n-1)! * (n+1)! ) (只針對目標點在對角線上)
- 3. f(i,j) 每次向右的次數會大於等於向上的次數 (類似括號問題)
- [Catalan numbers](https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0)
- C(0) = 1, C(n) = Σ [ C(k-1) * C(n-k) ]
- C(n) = 2n! / n!n! - 2n! / (n+1)!(n+1)! = 1/(n+1) × (2nn)
- f(i,j) = f(i-1, j) + f(i, j-1), f(i,i) = f(i, i-1), f(i, 0) = 1
- 多邊形的三角形分類
- 捷徑走路對角線問題
- 二元樹
- a permntation pi() of 1,2,3,...,n(n is biggest) is cute iff pi = u n v
- every element of u is less than every element of v
- u and v are also cute
- ex: 13254
- n 個元素中可以有幾個cute
- B(n) = sum( B(k) * B(n-k-1) )
- 括號問題
- property M matrix (2×*n*的矩陣的標準[楊氏矩陣](https://zh.wikipedia.org/wiki/%E6%9D%A8%E6%B0%8F%E7%9F%A9%E9%98%B5)的數量為特例, 可用Catalan算) :
- 陣列中行與列都遞增
- 將第一行換成 a ,第二行換成 b, ...
- f(i,0,0) = 1
- f(i,j,k) = f(i-1,j,k) + f(i,j-1,k) + f(i,j,k-1) ( i > j > k )
- f(i,i,k) = f(i,i-1,k) + f(i,i,k-1)
- f(i,j,j) = f(i-1,j,j) + f(i,j,j-1)
- f(i,i,i) = f(i,i,i-1))
- or
- f(i,0,0) = 1
- f(i,j,0) = f(i-1, j, 0) + f(i,j-1, 0) (i >= j > 0)
- f(i,j,k) = f(i-1,j,k) + f(i,j-1,k) + f(i,j,k-1) (i >= j >= k > 0)
- f(i,j,k) = 0 (others)
- 巴斯卡定理 + 二項式定理
- 內含費波那契數 (斜數字和)
- ...
- Vandermonde identity
- Cn+mr = sumk=0r( Cnk Cmr-k)
- r <= n,m ?
- sumk=0r Cn+kk = Cn+r+1r
- C2n2 = Cn2 + Cn2 +n*n = 2Cn2 + n2
- 擴展 (a + b + c)n = ...
- n2 / 2n = n2 / (1+1)n <= n2 / (n3/24) = 23 / n => 0 when n -> inf
- (1 + 1)n = ... + ( n(n+1)(n+2) ) / (1 * 2 * 3) >= ( n(n+1)(n+2) ) / (1 * 2 * 3) >= n3 / 24
- principle of Inclusion and Exclusion (排容)
- onto mapping: 1 - (not onto)
- [derangements](https://zh.wikipedia.org/wiki/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98)
- define Pi = { f | f(i) = i }
- ans = P1' and p2' and ... Pn'
- p1vp2vp3v...vpn= p1 + p2 + ... + pn - p1Ap2 - p2Ap3 - ... + p1Ap2Ap3 ......
- = (n1) (n-1)! - (n2) (n-2)! + (n3) (n-3)! ... = n! (1 - 1/2! + 1/3! - 1/4! + ...)
- => ans = n! - n! (1 - 1/2! + 1/3! ...) = n!/e
- 一筆劃問題
- A -> B n條路 = n!
- A -> B (-> A -> B) -> C 5條路 與 7條路
- AB -> BAB(2) or BCB(3) -> BC => 先說組合數有 5! / (2!3!)
- 在對選出的線編號 => 5!/(2!3!) * 7! * 5!
- 部分集合 (set and bag)

**Relation**

- A subset of A * B is called a relation
- relation, tuple, attribuate
- table, matrix
- binary relation
- A * A, a binary relation on A
- S is reflexive iff Ax (x,x) e S(對角線為 1)
- S is irreflexive iff Ax (x,x) !e S (對角線為 0)
- S is symmetric iff (if(a,b) e S then (b,a) e S) (非對角線要對稱)
- S is anti-symmetric iff ( if (a,b) e S and (b,a) e S => a = b ) -> x's refection can't be in S if x's refection isn't x (非對角線要互補)
- S is asymmetric iff( if (a,b) e S then (b,a) !e S ) => anti-symmetric without (x,x) = anti-symmetric + irreflexive (非對角線互補+對角線為0)
- S is transtive iff( if(a,b) e S and (b,c) e S => (a,c) e S
- Identity relation ( I ): 只有對角線是 1
- Used
- (R-1)-1 = R
- Lemma: Assume R is symmetric => R-1 = R
- complement: R' = { (a,b) | (a,b) !e R }
- compose: R * S = { (a,c) | if(a,b) e R, (b,c) e S } (bool matrix compose)
- ↑可用於有向圖問題
- (R*S)*T = R*(S*T)
- Rn, R0 = I
- Lemma: Let R e A*A => R is transitive iff R2 e R
proof
=>
Let (a,b) e R*R
E c s.t. (a,c) e R and (c,b) e R
cause R is transtive => (a,b) e R
so R*R e R
<=
Assume R2 e R
Let (a,c) e R, (c,b) e R
(a,b) e R2 e R
so R is transitive
- Lemma: Let R e A * A => R is transtive iff Rn e R for n = 1,2,...
- Lemma: Let R e A * A => if R is reflexive and transitive then R2 = R
- [Transitive closure](https://zh.wikipedia.org/wiki/%E4%BC%A0%E9%80%92%E9%97%AD%E5%8C%85): Let R e A * A
- Let R* be the smallest transitive relation containing R, R* is called the transitive closure of R
- Theorem: R* = R U R2 U R3 U ...
proof
(1) R e R U R2 U R3 U ...
(2) R U R2 U R3 U... is transitive
Let (a,b) e R U R2 U R3 U...
(b,c) e R U R2 U R3 U...
We need to prove
(a,c) e R U R2 U R3 U...
cause (a,b) e SET
=> E k (b,c) e Rk
cause (b,c) e SET
=> E h (a,b) e Rh
(a,c) e Rk*Rh
=> (a,c) e SET
(3) smallest
We want to prove SET e R*
Use math induction:
k = 1 => R e R* (定義裡)
assume Rk e R*
=> when n = k+1:
Suppose Rk+1 !e R*
E (e,f) e Rk+1, (e,f) !e R*
cause (e,f) !e R*
R e R*, R2 e R* ... Rk e R*
so (e,f) !e R, (e,f) !e R2, ..., (e,f) !e Rk
E d (e,d) e Rk, (d,f) e R
(e,d) e Rk e R*, (d,f) e R e R*
so R* is transitive (e,f) e R*
-><-
By induction, ...
- Define R = { (n,n+1) | n e N } (1->2->3->4->5->...)
- R* = { a < b | a,b e N } = R U R2 U R3 U ... (inf because N is inf set)
- Lemma: Assume R e A * A && |A| = n
- R* = R U R2 U R3 ... Rn
- R* algorithm
func tc(R)
T := R
repeat
U = T
T = (U*R) U R
until no change
return T /* T = R* */
OR
Warshall's algorithm
- [Equivilence relation](https://en.wikipedia.org/wiki/Equivalence_relation)
- R is reflexive
- R is symmetnc
- R is transitive
- D[ a ] = { b | (a,b) e R, a == b (mod x) }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

- Lemma: Let R e A * A
- Assume R is an eq rel
- The fellowing there claims are equal...
- (1) (a,b) e R
- (2) [a] = [b]
- (3) [a] = A [b] != 0

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# **作業**

第一次：
Construct a truth table for each of these compound propositions.

1. (p∨q)∧(q∨¬q)∧(r∨¬q)
2. (p∧q∧r)∨(¬p∧¬q∧¬r)
3. ¬ [ (p∨q∨r)∧(¬p∨¬q∨¬r) ]

第二次：
Construct a truth table for each of these compound propositions.

1. (p → q) ↔ (¬q → ¬p)
2. (p → q) → (q → p)
3. (p ↔ q) ⊕ (p ↔ ¬q)

第三次：
Are the following inferences valid?

1. ∃x (P(x) → Q(x)) ⊢∃x P(x) → ∃x Q(x)
2. ∃x P(x) → ∃x Q(x) ⊢∃x (P(x) → Q(x))

第四次：

1. Determine whether each of these arguments is valid. If an argument is correct, what rule of inference is being used? If it is not, what logical error occurs?
1. If n is a real number such that n > 1, then n 2 > 1. Suppose that n 2 > 1. Then n > 1
2. If n is a real number with n > 3, then n 2 > 9. Suppose that n 2 ≤ 9. Then n ≤ 3
3. If n is a real number with n > 2, then n 2 > 4. Suppose that n ≤ 2. Then n 2 ≤ 4
2. Identify the error or errors in this argument that supposedly shows that if ∃xP(x) ∧ ∃xQ(x) is true then ∃x(P(x) ∧ Q(x)) is true.
1. ∃xP(x) ∨ ∃xQ(x) Premise
2. ∃xP(x) Simplification from (1)
3. P(c) Existential instantiation from (2)
4. ∃xQ(x) Simplification from (1)
5. Q(c) Existential instantiation from (4)
6. P(c) ∧ Q(c) Conjunction from (3) and (5)
7. ∃x(P(x) ∧ Q(x)) Existential generalizatio
3. Use rules of inference to show that if ∀x(P(x) ∨ Q(x)) and ∀x((¬P(x) ∧ Q(x)) → R(x)) are true, then ∀x(¬R(x) → P(x)) is also true, where the domains of all quantifiers are the same.
4. Use rules of inference to show that if ∀x(P(x) ∨ Q(x)), ∀x(¬Q(x) ∨ S(x)), ∀x(R(x) → ¬S(x)), and ∃x¬P(x) are true, then ∃x¬R(x) is tru

第五次：

proof the function is define or undefine:
f(n) = { n/2 -------------- if n is even
{ f(f((3n+1)/2)) --- if n is odd

第六次：

# **考試**