離散筆記

邏輯

Propositional Logic

conjunction: ∧
disjunction: ∨
conditional statement（又稱implication）: →
biconditional statement（又稱bi-implications）: ↔
proposition constant: p, q, r, s, f, t

proposition formula的遞迴定義

1. proposition constant 和 proposition variable 為 proposition formula
   
2. 若A、B為 proposition formula，則(¬A), (A∧B),(A∨B),(A→B)，(A↔B)亦為 proposition formula

真值表

p | q | p∧q | p∨q | p⊕q | p→q | p↔q
----- | ----- | ------------- | ------------ | -------------- | ------------------- | ------------
T | T | T | T | F | T | T
T | F | F | T | T | F | F
F | T | F | T | T | T | F
F | F | F | F | F | T | T

優先序由先到後：﹁ > ^ = V > → = ←→

converse: p → q 的converse為 q → p
contrapositive: p → q 的contrapositive為 ﹁ q → ﹁ p
inverse: p → q 的inverse為 ﹁ p → ﹁ q
equivalent: 當二個proposition在各種情形下皆有相同真值時稱之

tautology: 不論propositional variable的真值為何，結果都恆為真的proposition。例： p V ﹁p
contradiction: 不論propositional variable的真值為何，結果都恆為假的proposition。例： p ^ ﹁p
contingency: 不是tautology也不是contradiction的proposition

logically equivalent: 已知二個proposition p 及 q，且 p ←→ q 為tautology時稱之。記為p≡q

some laws

De Morgan's Law

1. ¬(p∧q)≡¬p∨¬q
   
2. ¬(p∨q)≡¬p∧¬q

Identity laws

1. p∨F≡p
   
2. p∧T≡p

Domination laws

1. p∨T≡T
   
2. p∧F≡F

Idempotent laws

1. p∨p≡p
   
2. p∧p≡p

Double negation law
¬(¬p)≡p

Commutative laws 交換率

1. p∨q≡q∨p
   
2. p∧q≡q∧p

Associative laws 結合率

1. (p∨q)∨r≡p∨(q∨r)
   
2. (p∧q)∧r≡p∧(q∧r)

Distributive laws 分配率

1. p∨(q∧r)≡(p∨q)∧(q∨r)
   
2. p∧(q∨r)≡(p∧q)∨(q∧r)

Absorption laws

1. p∨(p∧q)≡p
   
2. p∧(p∨q)≡p

Negation laws

1. p∨¬p≡T
   
2. p∧¬p≡F

集合論

empty set：沒有元素的集合，記為{}或∅
singleton set：只有一個元素的集合
subset：若A的所有元素也都是B的元素，則稱A為B的subset，記為A⊆B
proper subset：若A為B的subset，但A≠B，則稱A為B的proper subset，記為A⊂B

cardinality：集合中的相異元素個數，集合S的cardinality記為|S|
power set：集合S的power set為所有S的子集所構成的集合，記為P(S)

例：

1. 空集合的power set P(∅)=∅
   
2. P({0, 1}) = {∅, {0}, {1}, {0, 1}}

若集合S有n個元素，則P(S)有2n個元素（n個元素，「取」和「不取」二種選擇）

ordered n-tuple \((a_1, a_2, \dots, a_n)\)：為一有序元素集合(collection)，其中a1為第一個元素，…，an為第n個元素
ordered pairs：即2-tuple
集合A1,…,An 的Cartesian product：A1×⋯×An={(a1,…,an)∣ai∈Ai for i=1,…,n}

disjoint、mutually disjoint：若二個集合的交集為空集合，則稱二集合disjoint
index set或set of indices：令I為非空集合，U為宇集，對於每個，則I稱為index set，且I中的每個元素i稱為index

集合的運算

symmertric difference：記做A△B，A△B = (A - B) ∪ (B - A)

relation

(binary) relation from A, B：集合A,B的Cartesian product(即A x B)的任意子集稱之
(binary) relation on A：集合A對自已的Cartesian product(即A x A)的任意子集稱之
related to：當(a,b)∈R，則稱a is related to b by R

注意:

• relation本身亦是集合，其元素皆為2-tuple
  
• 所有集合的運算也適用relation

relation的性質

集合的表示方式

roster method：指一一列出集合的元素以描述集合的方式，例如：S = {1, 2, 3}即是用roster method來描述集合
Venn diagram
membership table：一種類似truth table的表格，若元素屬於某個集合則填上1，否則填上0
例：

A	B	A
0	0	0
0	1	0
1	0	0
1	1	1

Venn diagram即是圖象化的membership table

代數

Group 群

Ring 環

ring (R,+,‧)，其中R為集合，+與‧為運算子，滿足

1. +,‧封閉性
   
2. +,‧結合率
   
3. +交換率
   
4. +單位元(identity)
   
5. +反元素
   
6. • over ‧的分配率

• +單位元通稱為ring的zero（零）

commutative ring：∀a,b∈R,a∗b=b∗a的ring
proper divisors of zero / proper zero divisors / zero divisors：在a≠z且b≠z的情形下，若ab＝Z，則稱a,b為proper divisors of zero
ring with unity：∀a∈R,存在u∈R，使得a u = u * a = a，且u≠0的ring
unity / multiplicative identity：上一句的u即是乘法單位元
units：R中相乘會變成u的元素
如：a,b∈R,a∗b=b∗a=u中的a, b
multiplicative inverse：上例中的a,b互為彼此的乘法反元素

Intefral domain

1. commutative
   
2. has unity a z
   
3. no zero divisors

Field 體

1. commutative
   
2. has unity a z
   
3. has multiplicative inverse of a z for every a

Subring

已知一個ring (R,+,‧)若存在S⊆R且S≠∅，(S,+,‧)為ring，則稱S為R的subring

Ideal

若I為R的ideal，則I滿足在

1. I為R的subring(a−b)∈I
   
2. x∈I&r∈R=>x∗r∈I&r∗x∈I

• 對任意n∈Z+,n>1,Zn中共有ϕ(n)個units及n−1−ϕ(n)個proper divisor

數論

a|b：a整除b(b是a的倍數)，∃c(ac=b)
a∤b：a不整除b

THEOREM
令a,b,c為整數，其中a≠0，則

1. 若 a | b 且 a | c，則 a | (b + c)
   
2. 若 a | b ，則對於所有整數c， a | bc
   
3. 若 a | b 且 b | c，則 a | c

Mod運算

(a+b)modn=[(amodn)+(bmodn)]modn
(a−b)modn=[(amodn)−(bmodn)]modn
(a×b)modn=[(amodn)×(bmodn)]modn

例：
a3modn=[(amodn)2modn×amodn]modn

Mod運算的性質

a≡bmodn=>n|(a−b)
a≡bmodn=>b≡amodn
a≡bmodn,b≡cmodn=>a≡cmodn

封閉性
令a,b∈Zm則a+bmodm及a×bmodm∈Zm

交換律
(w+x)modn=(x+w)modn
(w×x)modn=(x×w)modn

結合律
[(w+x)+y]modn=[w+(x+y)]modn
[(w×x)×y]modn=[w×(x×y)]modn

分配律
[w×(x+y)]modn=[(w×x)+(w×y)]modn
~~ [w+(x×y)]modn=[(w+x)×(w+y)]modn ~~ 筆記有誤
[(w+x)×y]modn=[(w×y)+(x×y)]modn

單位元
(0+w)modn=wmodn
(1×w)modn=wmodn

加法反元素-w
for each w∈,存在z∈Z使得w+z≡0modn

快速運算法

當d很大時，計算hdmodn
例：
$$
d = 23 \\
23 = 2^4 + 2^2 + 2^1 + 2^0 \\
[23]{10} = [10111]2 \\
h^{23} = (((h^2)^2 \times h)^2 \times h)^2 \times h \mod n \\
= h^{2^4} \times h^{2^2} \times h^2 \times h
$$

歐幾里得演算法：就是輾轉相除法
Extended Euclidean Algorithm：
已知a, b,找出s, t使得 s×a+t×b=gcd(a,b)

• 費馬小定理
  If a<P，P是質數且gcd(a,p)=1aP−1≡1modP

  
  或者
  gamodP≡gamodP−1modP

• 歐拉定理（廣義的費馬小定理）
  對於任意a < n，gcd(a, n) = 1，
  則
  aϕ(n)=1(modn)

有名字的數

Euclid numbers

en=e1e2…en+1+1

Euclid numbers彼此互質

Mersenne numbers

2p−1,p是質數

highly composite numbers

因數個數比任何小於它的正整數還要多的正整數

圖論

見這裡