第一章 集合 (Set Theory).

Presentation on theme: "第一章 集合 (Set Theory)."— Presentation transcript:

1 第一章 集合 (Set Theory)

2 1-0 簡介 由於數位觀念的開展，在數學與電腦應用上、集合(Set)儼然已成為其中重要的一環。讀者了解集合之含義後，就如同有了一把利刃，可將電腦觀念的外殼撕開，窺得學習的切入點。 本章將集合的觀念、定理、運算、與圖示、依序清晰敘述，搭配精緻習題，讀者可徹底剖析了解何謂 “集合(Sets)”。

3 1-1 集合與元素 (Sets and Elements)
1-2 宇集 (Universal Set) 與 空集合 (Empty Set) 1-3 子集合 (Subsets) 1-4 范氐圖 (Venn Diagrams) 1-5 集合運算 (Set Operations) 1-6 集合代數定律 (Laws of the Algebra of Sets) 1-7 有限集合 (Finite Sets) 1-8 群集合(Classes of Sets) 與 冪次集合 (Power Sets) 1-9 含意 (Arguments) 與 范氐圖 (Venn Digrams) 1-10 數學歸納推演 (Mathematical Induction) 1-11 習題

4 1-1 集合與元素 (Sets and Elements)
所謂集合(Set)是謂 “有一定義完善的範圍(well-defined List/Collection)，在範圍內包涵適當數量之元素(Elements)”。 習慣上、集合(Set) 以大寫字母表示(如A、B、C、…)；元素(Elements) 以小寫字母表示(如a、b、c、…) 。

5 1-2 宇集 (Universal Set) 與 空集合 (Empty Set)
在合乎集合(Sets)之定義下，若所有的集合元素、均是某一大集合的元素，則該某大集合是謂 宇集(Universal Set)。如People可稱為全世界人類的宇集。通常習慣以U為宇集之代表名稱。 如果有一集合，其中無任何元素，則該集合是謂 空集合(Empty Set / Null Set)。通常習慣以Ø為 空集合之代表名稱。

6 1-3 子集合 (Subsets) 設有集合A、與集合B，如果集合A的所有元素、亦是集合B的元素，則集合A是集合B之子集合。其關係式 (Relationship) 為： A B。 如果集合A的元素中、有任何一個不是集合B的元素，則集合A將不是集合B之子集合。其關係式 (Relationship) 為： A B。

7 1-4 范氐圖 (Venn Diagrams) 范氐圖的功能、是將集合(Sets) 的意義借由圖案(Pictorial Representation) 來表示。圖案以矩形為邊緣範圍，矩形內所有之各點均是宇集U的元素，在其範圍內的集合以圓形(Disks)表示。

8 1-5 集合運算 (Set Operations)
集合運算可概分四類運算方法：聯集運算(Union)、交集運算(Intersection)、相對餘補集運算(Relative Complement)、與絕對餘補集運算(Absolute Complement)。

9 1-6 集合代數定律 (Laws of the Algebra of Sets)
1、等冪律(Idempotent Laws) (a) A∪A = A (b) A∩A = A 2、結合律(Associative Laws) (a) (A∪B)∪C = A∪(B∪C) (b) (A∩B)∩C = A∩(B∩C) 3、交換律(Commutative Laws) (a) A∪B = B∪A (b) A∩B = B∩A 4、分配律(Distributive Laws) (a) A∪(B∩C) =(A∪B)∩(A∪C) (b) A∩(B∪C) =(A∩B)∪(A∩C) 5、統一律(Identity Laws) (a) A∪Ø = A (b) A∩U = A (c) A∪U = U (d) A∩Ø = Ø 6、對合律(Involution Law) (a) (Ac )c = A 7、餘補律(Complement Laws) (a) A∪Ac = U (b) A∩Ac = Ø (c) Uc = Ø (d) Øc = U 8、迪摩根律(DeMorgan’s Laws) (a) (A∪B)c = Ac∩Bc (b) (A∩B)c = Ac∪Bc

10 1-7 有限集合 (Finite Sets) 如果集合A有m個元素，其中m為正整數，則集合A謂 “有限集合(Finite Set)”。例如A = {x: x is a letter of English alphabet}、或空集合Ø = { } 均是有限集合(Finite Sets)。

11 1-8 群集合(Classes of Sets) 設有一集合A = {O, P, Q, R}，其元素是由集合O, P, Q, R組成。此時A是謂 “群集合(Class of Sets)”；B = {O, P}是謂 “子群集合 (SubClass或Subcollection)”。

12 1-9 含意 (Arguments) 與 范氐圖 (Venn Digrams)
有些語言詞藻複雜，往往無法清晰地陳述含意，本節介紹如何將一串複雜難懂的陳述，以集合架構的范氐圖清礎點出要點含意。

13 1-10 數學歸納推演 (Mathematical Induction)

14 第二章 關係式 (Relations)

15 2-0 簡介 若有元素a與b，兩者間存在某種關係R，即可以式 “aRb” 表示之，此為關係式(Relations)。我們曾熟悉的如 “等於(=)”、“大於(>)”、“因此(→)” 等均屬之。 關係式中也談集合(Sets)，於第一章 {a, b} = {b, a}，元素的先後次序並不影響集合的含義；但於關係式中的集合 {a, b}≠{b, a}，除非 a = b，因其先後次序代表著不同的含義。

16 2-1 積集合 (Product Sets) 2-2 關係式 (Relations) 2-3 關係式圖示 (Pictorial Representations of Relations) 2-4 反逆關係式 (Inverse Relations) 2-5 合成關係式 (Composition of Relations) 2-6 關係式特性 (Properties of Relations) 2-7 分割關係 (Partitions) 2-8 等價關係 (Equivalence Relations) 2-9 分割與等價關係 (Equivalence Relations and Partitions) 2-10 n元關係元 (n-Ary Relations) 2-11 習題

17 2-1 積集合 (Product Sets) 於關係式、我們定義 “序對(Ordered Pairs)”，如 (a, b)，因內容之先後次序代表著不同的含義。(a, b)≠(b, a)，除非 a = b。 積集合(Porduct Sets) 是定義兩組集合的關係。

18 2-2 關係式 (Relations) 設有集合A與B，另有 二元關係(Binary Relation) R，R之元素均是A × B 的子集合(Subset)，如果 (x, y) R，則謂 “x以R關係於y”，即 xRy。

19 2-3關係式圖示 (Pictorial Representations of Relations)
一般來言，我們可以4種圖示方式來表達關係式：(1) 關係式座標圖示(Coordinate Diagram of Relation)、(2) 關係式矩陣圖示(Matrix of Relation)、(3) 關係式配對圖示(Arrow Diagram of Relation)、(4) 關係式有向圖示(Direct Graph of Relation)。

20 2-5合成關係式 (Composition of Relations)
合成關係式(Composition of Relations) 是由數個關係元R、S、T 連串組合而成者，以 “R。S。T” 表示之。

21 2-6關係式特性 (Properties of Relations)
本節介紹關係元(Relation) 常有的4種特性：(1) 反身性(Reflexive)、(2) 對稱性(Symmetric)、(3) 反對稱性(Anti-Symmetric)、(4) 遞移性(Transitive)。

22 2-7 分割關係 (Partitions) 設有集合A，其子集合為 {Si}、且不得有重覆元素或空元素，則A為分割集合(Partition)。其條件如下： (Ⅰ) A的每一元素a，必須且僅出現於其中一個子集合內； (Ⅱ) Si ≠ Sj 且 Si ∩ Sj = Ø

23 2-8 等價關係 (Equivalence Relations)
設有集合A，如果其關係元R可同時滿足 (1) 反身性(Reflexive)、(2) 對稱性(Symmetric)、(3) 遞移性(Transitive)，則R為等價關係元(Equivalence Relation)。

24 2-9 分割與等價關係 (Equivalence Relations and Partitions)
定理(Theorem) 2-9： 設有集合A，令R為其等價關係元(Equivalence Relation)，則 “等價關係族(Equivalence Classes)” 有下列特性： (Ⅰ) a [a]、其中a為A的元素，即 a A。 (Ⅱ) [a] = [b]、若且唯若(if and only if) (a, b) R。 Ⅲ) 如果 [a]≠[b]、則 [a] 與 [b] 無交集。

25 2-10 n元關係元 (n-Ary Relations)
到目前為止，我們談到的均是二元關係(Binary Relation)，即有二元關係、當然也有多元關係(n-Ary Relations)，可以 An 表示之。如以座標圖案表示，A2是2D平面圖形之關係；A3是3D立體圖形之關係。

26 第三章 函數 (Function)

27 3-0 簡介 在數學應用上、函數(Function) 扮演了很重要的觀念，猶如是一個工作機制(Assingnment)，輸入不同的參數，產生並輸出對應的結果。因而、輸入的參數與輸出的結果就圍繞著函數(Fuction) 產生了許多有用的數學觀念與應用方法。於本章、我們將研討函數的基本特性。

28 3-1 函數定義 (Functions) 3-2 函數圖形(Graph of Function) 3-3 函數圖形特性(Properties of Functions) 3-4 習題

29 3-1 函數定義 (Functions) 設有集合A、與B、及工作機制(Work Assignment) W。將A的某一元素a輸入W，若W因此而產生一個對應結果b、其中b B，如此過程是謂 “A映至B之函數(Function from A into B)”，可表示如： f： A → B

30 3-2函數圖形(Graph of Function)
函數(Function) “f：A → B” 在函數圖形 (Graph of Function) 定義為：每一A的元素a A、必配屬一組 序對(Ordered Pair) 關係元(Relation) 如 (a, b)，且該關係元是唯一的(Unique)。

31 3-3 函數圖形特性 (Properties of Functions)
(1) 一對一配對(One to One)：於函數 f：A→B、如果A的每一元素均映出不同的函數像(Image)；或於函數圖形、每一A的元素均有配對、且每一B的元素僅與一個A的元素作配對。如此函數是謂 “一對一配對(One to One)函數”。 (2) 映成配對(Onto)：於函數 f：A→B、如果B的每一元素均出現於函數像(Image)，即 f(A) = B，則函數f謂 “映成配對(Onto)函數”。 (3) 可反逆配對(Invertible)：於函數 f：A→B、如果其反逆函數 f -1：B→A 亦為真；或者、f 既是一對一配對(One to One) 函數、亦是 映成配對(Onto)函數，此時f 謂 “可反逆配對(Invertible) 函數”。

32 向量 與 行列矩陣 (Vectors and Matrices)
第四章 向量 與 行列矩陣 (Vectors and Matrices)

33 4-0 簡介 我們常將資料(Data) 以矩陣(Arrays) 方式排列或儲存，亦即、將資料(Data) 以索引(Index) 編序其位置。於電腦程式、我們以參數表示 (如 “ A(15) ”)；於數學式、我們以下標註(Subscripts) 表示 (如 “ A15 ”)。 一般來言，一維矩陣(one-Demensional Array) 是謂 “向量(Vector)”；二維矩陣(two-Demensional Array) 是謂 “行列矩陣(Matix)”，一維矩陣(one-Demensional Array)亦可謂 “特殊型行列矩陣(Special Type of Matrix)”。

34 4-1 向量 (Vectors) 4-2 行列矩陣 (Matrices) 4-3 行列矩陣相加 (Matrices Addition) 4-4 行列矩陣系數 (Scalar Multiplication) 4-5 行列矩陣相乘 (Matrix Multiplication) 4-6 行列置換 (Transpose) 4-7 平方行列矩陣 (Square Matrices) 4-8 反逆行列矩陣 (Invertible Matrices) 4-9 決值區 (Determinants) 4-10 習題

35 4-1 向量 (Vectors) 設有向量u，我們通常是以一序列數字表示之，例如u有n個元件(n-Tuple)、則可表示為：
u = (u1, u2,…, un) 其中、ui 是向量u之元件(Components)，如果所有的 ui 均為0、則u為零向量(zero Vector)。

36 4-2 行列矩陣 (Matrices) 前節所述向量(Vector) 是將資料作一維矩陣排列，行列矩陣(Matrix) 則是將資料作二維矩陣排列

37 4-3 行列矩陣相加 (Matrices Addition)
設有行列矩陣A與B，兩者之長寬(Size)相等，即有相同數量的 列(Rows)、與相同數量的 行(Columns)，此時、可作兩行列矩陣相加 A + B，亦即將A、B的對應(Corresponding) 元件相加

38 4-4 行列矩陣系數 (Scalar Multiplication)
設有行列矩陣A，令k為係數(Scalar)，則兩者的乘積為k•A、 kA、或是 Ak，亦即將行列矩陣之每一元件(Component) 均乘以k；A與 kA 有著相同的長寬(Size)。

39 4-5 行列矩陣相乘 (Matrix Multiplication)
設有行列矩陣A，其長寬(Size) 為 m × p，其第i列元件為 (ai1 … aip)；行列矩陣B，其長寬(Size) 為 p × n，其第j行元件為 (b1j … bpj)。兩行列矩陣相乘得行列矩陣C = A × B，其長寬(Size) 將為 m × n。

40 4-6 行列置換 (Transpose) 於行列矩陣A、將其行(Column) 之資料依序置換成列(Row) 之資料，是謂 “行列置換(Transpose)”，以AT表示之。

41 4-7 平方行列矩陣 (Square Matrices)
設有行列矩陣A，行(Column) 的數量、與列(Row) 的數量相等，A是謂 “平方行列矩陣(Square Matrix)”。若其行、列數量均為n，則稱謂 “序列n (Order n)”，是謂 “ n-平方行列矩陣( n-Square Matrix)”。

42 4-8 反逆行列矩陣 (Invertible Matrices)
設有平方行列矩陣A，若令B為A之反逆行列矩陣(Invertible Matrix)，則B必須滿足： AB = BA = 1 如此平方行列矩陣B是謂A的反逆行列矩陣(Inverse of A)，以 B = A-1表示。由觀察得知，如果B是A的反逆行列矩陣；A亦將是B的反逆行列矩陣，即 A = B-1。

43 4-9 決值區 (Determinants) 設有一 n-平方行列矩陣( n-Square Matrix) A = ( aij )，我們取一正整數(Positive Integer) d，令 1≧d≦n，d可被應用為A的決值區(Determinant)，以det(A) 或 |A| 表示之。

44 第五章 圖論 (Graph Theory)

45 5-0 簡介 一般來言、圖(Graph) 是圖形、圖案、圖表、甚或照片的總稱，但在數學上、却有著不同的意義，圖形可作為某特定觀念之表示方法，例如於前述章節、我們曾以圖形表達關係式(Relations)、函數(Functions)、與行列矩陣(Matrices)。於本章、我們更將以節點(Vertices)、連線(Edges) 表達執行程序之觀念，稱之謂 “圖論(Graph Theory)。

46 5-1 圖 (Graph) 與 子圖 (Subgraph)
5-2 分支度 (Degree) 5-3 連通 (Connectivity) 5-4 圖之可行性 (Traversable Multigraph) 5-5 特殊形圖 (Special Graphs) 5-6 行列矩陣圖 (Matrices) 5-7 標註圖 (Labeled Graph) 5-8 同構/同胚 圖 (Isomorphic/Homeomorphic Graph) 5-9 習題

47 5-1 圖 (Graph) 與 次圖 (Subgraph)
圖(Graph) 之組成要件有二：(1) 一組節點(Vertices、Points、or nodes)；(2) 一組節點間之連線(Edges)。 設有簡圖G(V, E)，若令V’為V的子集合(Subset)；E’為E的子集合，則G(V’, E’)是謂G(V, E) 之子圖(SubGraph)。

48 5-2 分支度 (Degree) 設有一節點v、其有一連線e，則e是謂v之 “分支線(Incident on v)”。若節點v有n個分支線，則是謂 “v之分支度(Degree) 為n”，可以 deg(v) = n 表示之。如圖Fig.5-1-1、節點A有分支線e1與e4，A的分支度(Degree)為2，即 deg(A) = 2。 定理(Theorem) 5-2：於任意一簡圖(Graph)，各節點(Vertices) 分支度(Degree) 之和(Sum) 是其所有連線(Edges) 數量之2倍。

49 5-3 連通 (Connectivity) 於多重圖(Multigraph)、其節點(Vertices) Pi 與其連線(Edges) ei 因走過而組成的線串是謂 “連通走跡(Walk)”。 當 連通走跡(Walk) 的所有連線(Edges) 均無重覆通過時、是謂 “連通軌跡(Trail)”。當 連通走跡(Walk) 的所有節點(Vertices) 均無重覆通過時、是謂 “連通路徑(Path)”。

50 5-4 圖之可行性 (Traversable Multigraph)
於多重圖(Multigraph)、當要進入一個節點(Vertex)，該節點必須要有一連線(Edge) 才可執行進入，若要再離開該節點，為了不走過任一條線2次、該節點必須要有另一連線(Edge) 才可執行離開。亦即、若要於任一節點執行進入與離開，且不得於任一連線重覆走過2次，該節點之分支度(Degree) 必須是偶數，即為偶數節點(Even Vertex)。

51 5-5 特殊形圖 (Special Graphs)
不同形態的圖有許多，本節將介紹4種特殊形圖(Special Graph)：(1) 完整圖(Complete Graph)、(2) 正規圖(Regular Graph)、(3) 二分圖(Bipartite Graph)、(4) 樹形圖(Tree Graph)。

52 5-6 行列矩陣圖 (Matrices) 設有圖(Graph) G = (V, E)，V = {V1, V2, …,Vm}，E = {e1, e2, …, en}，為了電腦運算方便，往往以行列矩陣表示圖G。常用的行列矩陣有：(1) 連線矩陣(Edge Matrix)、(2) 相鄰節點矩陣(Adjacency Matrix)、(3) 節點連線矩陣(Incidence Matrix)。

53 5-7 標註圖 (Labeled Graph) 一個圖(Graph) 是謂 “標註圖(Labeled Graph)”、如果其節點(Vertices) 或連線(Edges) 被標註某種型態的資料符號(Label of Data)。

54 5-8 同構 / 同胚 圖 (Isomorphic/Homeomorphic Graph)
設有2圖(Graph) G1(V1, E1) 與 G2(V2, E2)，有一函數 f：V1→V2，其中V1與V2的節點(Vertices) 為一對一對稱，且G1有一連線 {u, v} 若且唯若 G2 亦有一連線 {f(u), f(v)}。此時 f 為G1與G2的同構函數(Isomorphism)，G1與G2是謂 “同構圖(Isomorphic Graph)”。

55 平整圖(Planar Graphs)、 著色法(Colorations)、 樹(Tree)
第六章 平整圖(Planar Graphs)、 著色法(Colorations)、 樹(Tree)

56 6-0 簡介 讀者如果有興趣，可以找一塊線路板來觀察，將會發現其中之佈線是沒有交叉的，一方面是為了美觀，另一方面是為了避免短路。

57 6-1 平整圖組(Maps) 與 區域(Regions)
6-2 尤拉公式(Euler’s Formula) 6-3 非平整圖(Nonplanar Graph) 6-4 著色圖(Colored Graphs) 6-5 四色圖定理(Four Color Theorem) 6-6 樹(Trees) 6-7 根樹(Rooted Trees) 6-8 排序根樹(Ordered Rooted Trees) 6-9 習題

58 6-1 平整圖組(Maps) 與 區域(Regions)
一個平整之特定有限多重圖(Finite Planar Multigraph) 是謂 “平整圖組(Maps)”。如果多重圖是連通的(Connected)、對應的平整圖組亦將是連通的，且可將所涵蓋的範圍分割成數個不同區域(Regions)。

59 6-2 尤拉公式(Euler’s Formula)
於平整圖組(Maps)，尤拉(Euler) 以其各連通節點(Vertices) 的數量V、各連通連線(Edges) 的數量E、與各區域(Regions) 的數量R，提出一非常有意義之公式如定理(Theorem)6-2-1： 定理(Theorem) 6-2-1：尤拉公式(Euler’s Formula) V – E + R = 2。

60 6-3 非平整圖(Nonplanar Graph)
非平整圖(Nonplanar Graph) 之定義一直困擾數學界許多年，直到1930年、才由波蘭數學家庫羅托威斯基(K. Kuratowski) 描述出確切之定義。 定理(Theorem) 6-3：庫羅托威斯基定理(Kuratowski’s Theorem) 一個圖是非平整圖(Nonplanar Graph)，若且唯若(if and only if) 其含有同胚圖(Homeomorphic Graph) K3,3與K5。

61 6-4 著色圖(Colored Graphs) 設有圖(Graph) G，將其各節點(Vertices) 著色，為了明顯區分圖形中節點間之關係，將相鄰的兩個節點著以不同的顏色，如此著色是謂 “節點著色(Vertex Coloring)”。 如果G可著以n種不同的顏色、我們稱G為 “n-著色性(n-colorable)”。一個圖以最少種類的顏色完成著色，該顏色數量是謂 “最小色彩值(Chromatic Number)”，以 x(G) 表示。

62 6-5 四色圖定理 (Four Color Theorem)
四色圖定理(Four Color Theorem)：任一平整圖(Planar Graph) G 是為 “節點之4-著色性(Vertex 4-colorable)”。 1976年、艾培爾(Appel) 與 哈肯(Haken) 模擬2,000 個圖、百萬種不同的狀況，宣稱任一平整圖(Planar Graph) 均滿足 “4-著色性(4-colorable)”，但仍屬模擬推論，不如 “5-著色性(5-colorable)” 証明確定，直至今日數學界仍在努力中。

63 6-6 樹(Trees) 一個圖是謂 “非迴路圖(Cycle-Free Graph / Acyclic)”、如果該圖沒有任何迴路；一個非迴路圖是謂 “樹形圖(Tree Graph)”、亦謂 “樹(Tree)”；由多個樹(Trees) 連通而成的圖是謂 “叢樹(Forest)”；如果 樹形圖(Tree Graph) 僅有一個節點、且無任何連線是謂 “弧點樹(Degenerate Tree)”。

64 6-7 根樹(Rooted Trees) 設有一樹形圖(Tree Graph) G，其最上端有一起始根節點(Root) r，則該圖是謂 “根樹(Rooted Tree)”。

65 6-8 排序根樹 (Ordered Rooted Trees)
設有一根樹(Rooted Tree) R，其各節點(Vertices) 或各連線(Edges) 因某條件需求而作排序標記，該根樹是謂 “排序根樹(Oredered Rooted Tree)”。

66 有向圖(Directed Graphs)、有限狀態器(Finite State Machines)
第七章 有向圖(Directed Graphs)、有限狀態器(Finite State Machines)

67 7-0 簡介 在表達瞬間變化上(如數位運算或流動系統)、有向圖(Directed Graph) 較無向圖(Nondirected Graph) 更為貼切有用。 本章將介紹有向圖(Directed Graph) 之基本觀念與定義，並以 有向標註圖(Labeled Directed Graph) 與 有限狀態器(Finite State Machine) 範例解說之。

68 7-1 有向圖(Directed Graph) 7-2 基礎定義(Basic Definitions) 7-3 有向圖行列矩陣(Matrices of Digraph) 7-4 刪修演算法(Pruning Algorithm for Minimal Path) 7-5 有限狀態器(Finite State Machine) 7-6 有限自動機(Finite Automata) 7-7 習題

69 7-1 有向圖(Directed Graph) 設有一個 有向圖(Directed Graph / Digraph) D，其要件有2，我們以 D(V, A) 表示之： (1) 節點集合V，包涵D之所有節點(Vertices)； (2) 有向連線集合A，包涵D之所有2節點間之有向連線(Arcs)。

70 7-2 基礎定義(Basic Definitions)
設有一有向圖(Directed Graph) D，有向連線(Arc) a = {u, v} 以箭頭 (Arrow) 表示，即 有向連線a 之起始節點(Initial Point) 為u、終止節點(Terminal Point) 為v。對某一節點來言，箭頭向外離開之連線數量是謂 “外分支度(Outdegree)”； 箭頭向內進入之連線數量是謂 “內分支度(Indegree)”。於任一有向圖(Directed Graph) 所有節點外分支度(Outdegrees) 之總和(Sum) 必等於所有節點內分支度(Indegrees) 之總和(Sum)。如果一個節點之內分支度(Indegree)為0、則該節點是謂 “資源節點(Source)”；如果一個節點之外分支度(Outdegree) 為0、則該節點是謂 “收納節點(Sink)”。

71 7-3 有向圖行列矩陣 (Matrices of Digraph)
有關有向圖行列矩陣(Matrices of Digraph)、我們於第二章就曾己討論，唯當時僅作粗略描述，且不涵及並行有向連線(Parallel arcs)。本章將再述有向圖行列矩陣(Matrices of Digraph)，且涵及並行有向連線(Parallel arcs)。

72 7-4 刪修演算法 (Pruning Algorithm for Minimal Path)
設有一有向圖(Digraph) D，無任何迴路，求取從其起始節點u到其終止點w之最短路徑(Minimal Path)。本節將介紹 “刪修演算法(Pruning Algorithm)” 求取之

73 7-5 有限狀態器 (Finite State Machine)
我們可以想像一串數位線路的執行程序，設有一連串之節點，每一節點就像是一個工作狀態點(State)，接受資料(Data) 的輸入(Input)；於狀態點(State) 內執行運算整理後，將結果(Result) 循連線(Edge) 輸出(Output) 至次一狀態點，直至終止點(Final State) 為止。如此一連串的有限狀態點與連線是謂 “有限狀態器(Finite State Machine)”。

74 7-6 有限自動機(Finite Automata)
有限自動機(Finite Automata) 與前節所述之有限狀態器(Finite State Machine) 很類似，不同者是、有限自動機可為某特定條件的執行程序作 “接受(Accepting)” 或 “拒絕(Rejecting)” 之判斷。

75 組合分析 (Combinatorial Analysis)
第八章 組合分析 (Combinatorial Analysis)

76 8-0 簡介 組合分析(Combinatorial Analysis) 的範圍包括 排列(Permulations)、組合(Combinations)、與 群組(Partitions)。本章將就其觀念以精選例題詳細介紹。

77 8-1 基礎觀念(Fundamental Principle of Counting)
8-2 階乘(Factorial Notation) 8-3 二項式系數(Binomial Coefficients) 8-4 排列(Permutation) 8-5 排列與重覆(Permutations and Repetitions) 8-6 組合(Combinations) 8-7 有序分割群(Ordered Partitions) 8-8 樹形圖(Tree Diagrams) 8-9 習題

78 8-1 計數基礎觀念 (Fundamental Principle of Counting)
如果有一事件(Event) E1，有n1種執行方式；另有二輪事件(Second Event) E2，依E1之執行方式再繼續執行，且有n2種執行方式；另再有三輪事件(Second Event) E3，依E2之執行方式再繼續執行，且有n3種執行方式；以此類推 …，此時、事件之執行方式為：n1․n2․n3․…。

79 8-3 二項式系數 (Binomial Coefficients)
nCr的符號為 ，其中r與n均是正整數(Positive Integer)，且 r ≦ n，定義如下： =

80 8-4 排列(Permutation) 設有一集合(Set) S，有n個物件(Objecs)，將此n個物作各種不同次序之安置是謂 “所有物件之排列(Permutation of all)”。如果取其中r個物件(r≦n) 作排列是謂 “r–物件排列(r–Permutation)”。

81 8-6 組合(Combinations) 組合(Combination) 與排列(Permutation) 類似，所不同者排列有位置次序的要求，組合則無。

82 8-7 有序分割群(Ordered Partitions)
設有一集合(Set) S，有n個物件(Objecs)，先取其中n1個物件組成子集合(Subset) S1；再於剩餘物件中、取其中n2個物件組成子集合(Subset) S2；…；再於剩餘物件中、取其中nm個物件組成子集合(Subset) Sm，其中 S = {S1, S2, …, Sm}、n = n1 + n2 + … + nm。如此依先後次序執行選取是謂 “有序分割群(Ordered Partitions)。

83 8-8 樹形圖(Tree Diagrams) 於計算有關機遇率的問題上、根樹圖(Rooted Tree Diagrams) 可助益解題之了解

84 代數觀點(Algebraic Systems) 與 語言(Languages)
第九章 代數觀點(Algebraic Systems) 與 語言(Languages)

85 9-0 簡介 於第七章、本書曾描述 有限狀態器(Finite State Machine)、有限自動機(Finite Automata)，我們可將此兩者比如是電腦系統之硬體，是一種機器，將用於執行一些有意義的軟體。 而本章所介紹的就是那些有意義的軟體，從數學的代數觀點切入，定義機器之執行條件與能力；連接可表達意義的字串，因我們人類可籍由有意義的字串傳遞思維，故而如此有意義的字串亦可視為是語言(Languages)，可由 有限狀態器(Finite State Machine)、有限自動機(Finite Automata) 執行的語言是為電腦語言之母，是謂 “形式語言(Formal Languages)”。

86 9-1 運算屬性(Operations) 與 半群組(Semigroups)
9-2 自由型半群組(Free Semigroups)、語言(Languages) 9-3 文法與語言(Grammars and Languages) 9-4 群組(Groups) 9-5 子群組(Subgroups) 與 標準子群組(Normal Subgroups) 9-6 習題

87 邏輯主張(Proposition Calculus)
第十章 邏輯主張(Proposition Calculus)

88 10-0 簡介 在電腦應用上，無論是處於硬體架構之排列、或是軟體語言之設計，這些都將與邏輯問題息息相關。
電腦是一堆冰冷且無生命的銹鐡，我們人類是有血有肉有智慧的萬物之靈，經過我們人類的思考、作成合乎邏輯之符號、灌注入那冰冷的電腦，此時電腦亦如有了生命，生動活潑地執行我們要求的指令。 因此可看到邏輯思維與邏輯符號有其重大的意義，本章將有系統地幫助我們整理邏輯思維、有效率地作出邏輯符號。

89 10-1 陳述(Statements) 與 複合陳述(Compound
10-2 連接屬性(Conjunction) 10-3 分離屬性(Disjunction) 10-4 否定屬性(Negation) 10-5 邏輯主張(Proposition) 與 真值表(Truth Table) 10-6 恆真邏輯(Tautologies) 與 恆偽邏輯(Contradictions) 10-7 相等邏輯(Logical Equivalence) 10-8 邏輯主張之代數式(Algebra of Proposition) 10-9 單向條件 與 雙向條件陳述(Conditional and Biconditional Statements) 10-10 論証(Arguments) 10-11 邏輯意向(Logical Implication) 10-12 習題

90 10-1 陳述(Statements) 與 複合陳述(Compound Statements)
以文字表達一有意義之事件是謂 “陳述(Statement)”，其基本特性(Fundamental Property) 是在表達 “真(True)”、或是 “偽(False)”。表示 “真(True)” 或 “偽(False)” 的意義是謂一個陳述之 “真值(True Value)”。 有些陳述(Statements) 是由數個 次陳述(Substatements) 聯組而成，每一個次陳述有其自身的 真值(True Value) 意義，如此聯組之陳述是謂 “複合陳述(Compound Statement)”。

91 10-2 連接屬性(Conjunction) 任何兩個陳述(Statements) p與q、可由單字 “和(and)” 連接成一個複合陳述(Compound Statement)，以p and q、或 pΛq 表示

92 10-3 分離屬性(Disjunction) 任何兩個陳述(Statements) p與q、可由單字 “或(or)” 連接成一個複合陳述(Compound Statement)，以p or q、或 pVq 表示

93 10-4 否定屬性(Negation) 設有一陳述(Statement) p，另一與其陳述真值相反的陳述p’ 是謂p之 “否定陳述(Negation of p)”，通常以 not p 或 ~p 表示。

94 10-5 邏輯主張(Proposition) 與 真值表(Truth Table)
在語言(Language) 運用上、各陳述的真值(True Value) 將一再重覆被使用，為了方便、為了明確、我們設計一種圖表來表達各類陳述(Statements) 的真值屬性，如此圖表稱為 “真值表(Truth Table)”，表達複雜的邏輯主張(Proposition)。

95 10-6 恆真邏輯(Tautologies) 與 恆偽邏輯(Contradictions)
設有邏輯主張(Proposition) P(p, q, …)，如果其真值表(Truth Table) 的最後步驟欄全為T，則該 邏輯主張(Proposition) 是謂 “恆真邏輯(Tautology)”；相對地、如果其真值表(Truth Table) 的最後步驟欄全為F，則該 邏輯主張(Proposition) 是謂 “恆偽邏輯(Contradiction)”。

96 10-7 相等邏輯 (Logical Equivalence)
設有邏輯主張(Propositions) P(p, q, …) 與 Q(p, q, …)，如果兩者間有相同含意的真值表(Truth Table)，則P與Q為 “相等邏輯(Logical Equivalence)”，以 P(p, q, …) = Q(p, q, …) 表示。

97 10-8 邏輯主張之代數式 (Algebra of Proposition)
(1) 等冪律(Idempotent Laws)： 1a、 pVp =p b、 pΛp = p (2) 結合律(Associative Laws)： 2a、 (pVq)Vr = pV(qVr) b、 (pΛq)Λr = pΛ(qΛr) (3) 交換律(Commutative Laws)： 3a、 pVq = qVp b、 pΛq = qΛp (4) 分配律(Distributive Laws)： 4a、 pV(qΛr) = (pVq)Λ(pVr) 4b、 pΛ(qVr) = (pΛq)V(pΛr) (5) 統一律(Identity Laws)： 5a、 pVf = p b、 pΛf = p 6a、 pVt = t b、 pΛt = t (6) 餘補律(Complement Laws)： 7a、 pV~p = t b、 pΛ~p = f 8a、 ~t = f b、 ~f = t (7) 對合律(Involution Law)： 9a、 ~~p = p (8) 迪摩根定理(DeMorgan’s Laws)： 10a、 ~(pVq) = ~pΛ~q b、 ~(pΛq) = ~pV~q

98 10-9 單向條件 與 雙向條件陳述(Conditional and Biconditional Statements)
於電腦程式碼、或於數學式，我們常遇到 “單向條件陳述(Conditional Statements)”， “如果 p為真、則q亦為真” (if p then q)，我們通常以 “p → q” 表示。 另一種條件陳述是顧及必要條件與充分條件，稱為 “雙向條件陳述(Biconditional Statements)”， “p為真、若且唯若q為真” (p if and only if q)，我們通常以 “p q” 表示。

99 10-10 論証(Arguments) 在電腦程式設計、“Arguments” 被視為 “參數”；在數學應用上、則被視為 “論証”，是一運算式用於確定一組陳述(Statement) 是否為真(True)。

100 10-11 邏輯意向 (Logical Implication)
當一個邏輯主張(Proposition) P(p, q, …) 邏輯意向於(logically imply) 另一邏輯主張 Q(p, q, …)，則以下列式表示之： P(p, q, …) → Q(p, q, …) 亦即、如果 Q(p, q, …) 為真(True)、則P(p, q, …) 必為真。