在學習數理邏輯(Mathematical Logic)的時候，常常會聽到若 $P$ 則 $Q$，可能會被 "$\Longrightarrow$"(if .... then ...) 的意義搞得似懂非懂，就算懂了它的結果跟生活上的結合也是有種莫名陌生感，像筆者小時候會想成"因為 ... 所以 ..."，但這不是它的正確意義。而日常生活中集合論的交集，聯集或許是大家比較容易理解的。本文是用集合論的觀點去了解邏輯，方程組，數學規劃上的應用，並介紹布林代數(Boolean Algebra)跟邏輯的關係，提供另一個角度可能更容易理解數學 !!
[輔助理解]
因為集合論可以在黑板上畫文氏圖(Venn Diagram)，詢問點是落在哪個圈圈裡面還外面，大家都能輕易理解認同，而產生共鳴的語言!!
[假想實驗]
通常我們會先定義宇集，論域(universal set) $U$，代表我們所感興趣的東西，事物，元素變數符號 $u$。$P$，$Q$在日常生活中可能是某個條件(condition)，性質(property)，限制(constraint)。而我們會依依檢驗 $U$裡面的元素 $u$ 是否滿足條件$P$，如果滿足就把它們收集起來，形成一個集合。
同理 $Q$ 也照做，所以我們會收集到兩個集合!! 白話來說，可以寫成
$S_P := \{ u \in U : u \text{ satisfies condition } P\}$
$S_Q := \{ u \in U : u \text{ satisfies condition } Q\}$
註: 比較正式的寫法是可以分別把 $P$，$Q$對應到布林值(Boolean 或叫 Predicate 或叫 Indicator function) $f_P$ , $f_Q$，$f_P,f_Q: U \longrightarrow \{0 , 1 \}$，$S_P := \{ u \in U : f_P(u) = 1 \}，S_Q :=\{ u \in U : f_Q(u) = 1 \}$
虛擬碼大致上是
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Into Data Into $U$
Write routine $f_P$ , $f_Q$
Let $S_P$ , $S_Q$ be empty container ,
For $u \in U$
$\qquad$ If($f_P(u)==1$) Put $u$ Into $S_P$
$\qquad$ If($f_Q(u)==1$) Put $u$ Into $S_Q$
EndFor
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[輔助理解]
因為集合論可以在黑板上畫文氏圖(Venn Diagram)，詢問點是落在哪個圈圈裡面還外面，大家都能輕易理解認同，而產生共鳴的語言!!
[假想實驗]
通常我們會先定義宇集，論域(universal set) $U$，代表我們所感興趣的東西，事物，元素變數符號 $u$。$P$，$Q$在日常生活中可能是某個條件(condition)，性質(property)，限制(constraint)。而我們會依依檢驗 $U$裡面的元素 $u$ 是否滿足條件$P$，如果滿足就把它們收集起來，形成一個集合。
同理 $Q$ 也照做，所以我們會收集到兩個集合!! 白話來說，可以寫成
$S_P := \{ u \in U : u \text{ satisfies condition } P\}$
$S_Q := \{ u \in U : u \text{ satisfies condition } Q\}$
註: 比較正式的寫法是可以分別把 $P$，$Q$對應到布林值(Boolean 或叫 Predicate 或叫 Indicator function) $f_P$ , $f_Q$，$f_P,f_Q: U \longrightarrow \{0 , 1 \}$，$S_P := \{ u \in U : f_P(u) = 1 \}，S_Q :=\{ u \in U : f_Q(u) = 1 \}$
虛擬碼大致上是
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Into Data Into $U$
Write routine $f_P$ , $f_Q$
Let $S_P$ , $S_Q$ be empty container ,
For $u \in U$
$\qquad$ If($f_P(u)==1$) Put $u$ Into $S_P$
$\qquad$ If($f_Q(u)==1$) Put $u$ Into $S_Q$
EndFor
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
當然我們知道還有補集合，不能遺忘它!!
$\bar{S}_P := \{ u \in U : f_P(u) = 0 \} \quad \bar{S}_Q := \{ u \in U : f_Q(u) = 0 \}$
我們可以再加個新條件 $R$ ，構造出 $S_{R}$，$\bar{S}_R$
有了這些集合以後，就大功告成了:
以下是列表對應:
$\begin{array}{cccc}
(E1) & P \Longrightarrow Q & & S_P \subseteq S_Q \\
(E2)& Q \Longrightarrow R & & S_Q \subseteq S_R \\
(E3)& P \Longrightarrow \neg Q & & S_P \subseteq \bar{S}_{Q} \\
(E4)& P \Longrightarrow R & & S_P \subseteq S_R \\
(E5)& \neg Q \Longrightarrow \neg P & & \bar{S}_Q \subseteq \bar{S}_P \\
(E6) & \neg P \Longrightarrow \neg Q & & \bar{S}_P \subseteq \bar{S}_Q \\
(E7) & Q \Longrightarrow P & & S_Q \subseteq S_P \\
\end{array}$
--------------------------------------------------------------------
練習：畫文氏圖就可以很清楚回答下面的問題 :
1. Either $(E1)$ or $(E3)$ is True ?? Ans : No.
2.$(E1)$, $(E2)$ are True , $(E4)$ is automatically True ?? Ans : Yes.
3.$(E1)$,$(E4)$ are True , $Q$,$R$ are automatically equivalent ?? Ans : No.
4.$(E1)$,$(E5)$ are equivalent ?? Ans : Yes.
5.$(E6)$,$(E7)$ are equivalent ?? Ans : Yes.
--------------------------------------------------------------------
[and $\wedge$ , or $\vee $]
($P\wedge Q$) 會對應到 $S_{P\wedge Q} = S_P \cap S_Q$
($P\vee Q$) 會對應到 $S_{P\vee Q} = S_P \cup S_Q$
[nesscessity & suffciency]
If ( $(E1)$ and $(E2)$ ) are True then $(E4)$ is True
也就是 $P \Longrightarrow Q \Longrightarrow R$
則稱$P$ 為 $Q$ 的 充分條件(sufficient condition)
且稱$R$ 為 $Q$ 的必要條件(nesscessary condition)
以下談很重要的部分
****廣義演算法搜尋概念****
承上也可以寫成 $ S_P \subseteq S_Q \subseteq S_R $
當我們想要從$U$裡找$u\in S_Q$ 時
可以使用窮舉法(Brute & Force), [BF]
++++++++++++++++++++++++++++++++++
For $u \in U$
$\qquad$ if($f_{Q}(u)==1$) then $u$ is solution !!
EndFor
+++++++++++++++++++++++++++++++++++
但是如果無法直接刻劃出$S_Q$具體搜尋方法 or $f_Q$的具體運算性質 or 運算成本太高，我們就要發展理論去找刻劃$f_{R}$,$f_{P}$ !!
發展 [For_U_If_R+P] 演算法!!
++++++++++++++++++++++++++++++++++
For $u \in U$
$\qquad$ if($f_{R}(u)==1$) then $u$ maybe solution (candidate) !!
$\qquad$ if($f_{P}(u)==1$) then $u$ is a solution !!
EndFor
+++++++++++++++++++++++++++++++++++
但是$|U|$通常很大甚至無限，我們要想辦法改善搜尋範圍，如果我們能刻劃出 $S_R$ 的具體搜尋方法，則可以改寫成新演算法 [For_R_If_P]
+++++++++++++++++++++++++++++++++++
For $u \in S_R$
$\qquad$ if($f_{P}(u)==1$) then $u$ is a solution !!
EndFor
則我們只要搜尋$S_R$ 就足夠了
+++++++++++++++++++++++++++++++++++
同理如果我們能刻劃出$S_P$，則[For_P]演算法，每一步都是解！！
但是就算有刻劃出$S_R$，$S_P$的集合搜尋性質，我們也無法找到所有的解!!
注意：除非我們證明$P$或$R$與$Q$等價(證明 $S_Q \subseteq S_P$ or $S_R \subseteq S_Q$) !!
數學上就稱$P$或$R$是$Q$ 的充要條件(sufficient + nesscessary condition)!!
[微積分求極值例子] 在實數軸上找 $y = g(x)$ 的極小值時
$S_Q = \underset{x\in \mathbb{R}}{\text{argmax} }f(x)$ (Local Min Definiton)
$S_P = \{x\in \mathbb{R}: g''(x)>0 , g'(x) = 0 \}$ (Sufficient Second Order Condition)
$S_R = \{x\in \mathbb{R}: g'(x) = 0 \}$ (Nesscessary First Order Condition)
其中 :
$ S_P \subseteq S_Q \subseteq S_R $
$f_P(x)$ 代表 [ 要檢查 $g''(x)$ 是否大於 $0$ , $g'(x)$ 是否等於 0，皆是則回傳 1，否則回傳 0 ]
$f_R(x)$ 代表 [ 要檢查 $g'(x)$ 是否等於 0 ，是則回傳 1，否則回傳 0 ]
[跟方程組的關係]
假設我們要找 $x \in U$滿足這兩條方程式 $E_1(x) \leq 0 , E_2(x) \leq 0$
可以想成集合版本
$S_P:=\{x \in U : E_1(x) \leq 0 \}$
$S_Q:=\{x \in U : E_2(x) \leq 0 \}$
則解聯立方程組相當於找 $S_{P\wedge Q} = S_P \cap S_Q$。
這告訴我們加入限制式跟取交集一樣，限制式越多，集合會越來越小!!，無解代表空集合!!
接下來介紹一個非常重要的應用:
*****在數學規劃(Mathematical Programming)上的領域*****
給定兩個集合 $A\subseteq B$ , g 為 real-valued function 則
$\underset{x\in B}{\text{min } } g(x) \leq \underset{x\in A}{\text{min } } g(x) $
$\underset{x\in A}{\text{max } } g(x) \leq \underset{x\in B}{\text{max } } g(x) $
(註: 嚴格要假設 $A$,$B$ 是緊緻集 (compact set) 或是 max 改成 sup ， min 改成 inf )
這是一個很難察覺但很容易判斷的事實，可以類比於回答下列的問題:
Q1:全台灣最高的山跟全世界最高的山哪一個比較高?
Q2:全台灣最矮的山跟全世界最矮的山哪一個比較矮?
根據方程組結論我們得到限制式越多，集合越來越小則 max 值會越來越小，
min 值會越來越大。
而這事實上就是 cutting plane algorithm (branch and bound) 的原理 !!
以下大致敘述其原理 :
---------------------------------------------------------------
以純整數規劃(Pure Integer Programming)來說，極大化問題來說，假設$n$個 0-1決策變數
可行解域(Feasible Solution) $F^{I} :=\{0,1\}^{n}$，最佳解$x^{*}$ ，最佳值 $y^{*}$，我們可以擴大可行解域即 LP-relaxation ，定義為 $F^{LP}:= [0,1]^{n}$ 很明顯 $ F^{I} \subseteq F^{LP}$，假設$k$為迭代次數，而 cutting plane algorithm 會持續一直加限制式(valid inequality) 會把問題化成一系列的可行解域$\{F^k\}$ ($\forall k \ ,F^{I}\subseteq F^k \subseteq F^{LP}$) 演算法會求出 $x^k$，$y^k := f(x^k) =\underset{x \in F^{k} }{\text{max}} g(x)$ ，很明顯 $y^{*} \leq y^{k}$ ，隨著 $k$ 越大 $F_{k}$ 會越小，則 $y^{k}$ 會越來越接近 $y^{*}$ ，我們稱$y^{k}$ 為上界(Bound)。
(註: 這是主要 bound + cut 的核心概念，下界的概念跟 branch 的部分可在參考整數規劃相關領域)
---------------------------------------------------------------
[布林代數的應用]
回顧可以用集合$S_P, S_Q$ 表示邏輯的條件 $P,Q$，也介紹了 Indicator function $f_P,f_Q$
還可以用 $0,1$ 四則運算來代替交集聯集，也可以使用整數規劃限制式來表達邏輯!!
$\begin{array}{cccc}
\text{Logicial Condition }& \text{Set Thinking} & \text{Boolean Operation } & \text{IP Linear Constraint} \\
P& S_P & f_P & f_P \\
\neg P& \bar{S}_P & 1- f_P & 1-f_P & \\
P\wedge Q & S_P \cap S_Q & f_P \cdot f_Q \text{ or min }(f_P , f_Q) & Z \leq f_P , Z \leq f_Q , f_P + f_Q \leq 1+Z \\
P\vee Q& S_P \cup S_Q & (f_P + f_Q) - f_P \cdot f_Q \text{ or max }(f_P , f_Q) & f_P + f_Q \geq 1 \\
P\Longrightarrow Q & S_P \subseteq S_Q & \text{ max }(1-f_P , f_Q) & f_P \leq f_Q \\
\end{array}$
註: $Z \in \{0,1\}$ 是輔助變數，
註: 整數規劃(IP)的例子，$U = \{a,b,c,d,e\}$ ，$P$代表 元素是 "$a$"，$S_P = \{a\}$則 $f_P(u) ==1$相當於 $u == a$ 的意思
[小結]
我們可以發現，邏輯，集合，布林，線性限制式，有某種對應!!邏輯建立了數學，數學又是科學之母。而可以用集合方便人們去思考邏輯，而在資工電機等科系，軟硬體上，布林扮演在實作上很重要的角色，而整數規劃限制式更是在現實問題數學建模(mathematical modeling)有很大的幫助!! 透過此文希望能讓讀者更全面認識邏輯 !!
$\bar{S}_P := \{ u \in U : f_P(u) = 0 \} \quad \bar{S}_Q := \{ u \in U : f_Q(u) = 0 \}$
我們可以再加個新條件 $R$ ，構造出 $S_{R}$，$\bar{S}_R$
有了這些集合以後，就大功告成了:
以下是列表對應:
$\begin{array}{cccc}
(E1) & P \Longrightarrow Q & & S_P \subseteq S_Q \\
(E2)& Q \Longrightarrow R & & S_Q \subseteq S_R \\
(E3)& P \Longrightarrow \neg Q & & S_P \subseteq \bar{S}_{Q} \\
(E4)& P \Longrightarrow R & & S_P \subseteq S_R \\
(E5)& \neg Q \Longrightarrow \neg P & & \bar{S}_Q \subseteq \bar{S}_P \\
(E6) & \neg P \Longrightarrow \neg Q & & \bar{S}_P \subseteq \bar{S}_Q \\
(E7) & Q \Longrightarrow P & & S_Q \subseteq S_P \\
\end{array}$
--------------------------------------------------------------------
練習：畫文氏圖就可以很清楚回答下面的問題 :
1. Either $(E1)$ or $(E3)$ is True ?? Ans : No.
2.$(E1)$, $(E2)$ are True , $(E4)$ is automatically True ?? Ans : Yes.
3.$(E1)$,$(E4)$ are True , $Q$,$R$ are automatically equivalent ?? Ans : No.
4.$(E1)$,$(E5)$ are equivalent ?? Ans : Yes.
5.$(E6)$,$(E7)$ are equivalent ?? Ans : Yes.
--------------------------------------------------------------------
[and $\wedge$ , or $\vee $]
($P\wedge Q$) 會對應到 $S_{P\wedge Q} = S_P \cap S_Q$
($P\vee Q$) 會對應到 $S_{P\vee Q} = S_P \cup S_Q$
[nesscessity & suffciency]
If ( $(E1)$ and $(E2)$ ) are True then $(E4)$ is True
也就是 $P \Longrightarrow Q \Longrightarrow R$
則稱$P$ 為 $Q$ 的 充分條件(sufficient condition)
且稱$R$ 為 $Q$ 的必要條件(nesscessary condition)
以下談很重要的部分
****廣義演算法搜尋概念****
承上也可以寫成 $ S_P \subseteq S_Q \subseteq S_R $
當我們想要從$U$裡找$u\in S_Q$ 時
可以使用窮舉法(Brute & Force), [BF]
++++++++++++++++++++++++++++++++++
For $u \in U$
$\qquad$ if($f_{Q}(u)==1$) then $u$ is solution !!
EndFor
+++++++++++++++++++++++++++++++++++
但是如果無法直接刻劃出$S_Q$具體搜尋方法 or $f_Q$的具體運算性質 or 運算成本太高，我們就要發展理論去找刻劃$f_{R}$,$f_{P}$ !!
發展 [For_U_If_R+P] 演算法!!
++++++++++++++++++++++++++++++++++
For $u \in U$
$\qquad$ if($f_{R}(u)==1$) then $u$ maybe solution (candidate) !!
$\qquad$ if($f_{P}(u)==1$) then $u$ is a solution !!
EndFor
+++++++++++++++++++++++++++++++++++
但是$|U|$通常很大甚至無限，我們要想辦法改善搜尋範圍，如果我們能刻劃出 $S_R$ 的具體搜尋方法，則可以改寫成新演算法 [For_R_If_P]
+++++++++++++++++++++++++++++++++++
For $u \in S_R$
$\qquad$ if($f_{P}(u)==1$) then $u$ is a solution !!
EndFor
則我們只要搜尋$S_R$ 就足夠了
+++++++++++++++++++++++++++++++++++
同理如果我們能刻劃出$S_P$，則[For_P]演算法，每一步都是解！！
但是就算有刻劃出$S_R$，$S_P$的集合搜尋性質，我們也無法找到所有的解!!
注意：除非我們證明$P$或$R$與$Q$等價(證明 $S_Q \subseteq S_P$ or $S_R \subseteq S_Q$) !!
數學上就稱$P$或$R$是$Q$ 的充要條件(sufficient + nesscessary condition)!!
[微積分求極值例子] 在實數軸上找 $y = g(x)$ 的極小值時
$S_Q = \underset{x\in \mathbb{R}}{\text{argmax} }f(x)$ (Local Min Definiton)
$S_P = \{x\in \mathbb{R}: g''(x)>0 , g'(x) = 0 \}$ (Sufficient Second Order Condition)
$S_R = \{x\in \mathbb{R}: g'(x) = 0 \}$ (Nesscessary First Order Condition)
其中 :
$ S_P \subseteq S_Q \subseteq S_R $
$f_P(x)$ 代表 [ 要檢查 $g''(x)$ 是否大於 $0$ , $g'(x)$ 是否等於 0，皆是則回傳 1，否則回傳 0 ]
$f_R(x)$ 代表 [ 要檢查 $g'(x)$ 是否等於 0 ，是則回傳 1，否則回傳 0 ]
[跟方程組的關係]
假設我們要找 $x \in U$滿足這兩條方程式 $E_1(x) \leq 0 , E_2(x) \leq 0$
可以想成集合版本
$S_P:=\{x \in U : E_1(x) \leq 0 \}$
$S_Q:=\{x \in U : E_2(x) \leq 0 \}$
則解聯立方程組相當於找 $S_{P\wedge Q} = S_P \cap S_Q$。
這告訴我們加入限制式跟取交集一樣，限制式越多，集合會越來越小!!，無解代表空集合!!
接下來介紹一個非常重要的應用:
*****在數學規劃(Mathematical Programming)上的領域*****
給定兩個集合 $A\subseteq B$ , g 為 real-valued function 則
$\underset{x\in B}{\text{min } } g(x) \leq \underset{x\in A}{\text{min } } g(x) $
$\underset{x\in A}{\text{max } } g(x) \leq \underset{x\in B}{\text{max } } g(x) $
(註: 嚴格要假設 $A$,$B$ 是緊緻集 (compact set) 或是 max 改成 sup ， min 改成 inf )
這是一個很難察覺但很容易判斷的事實，可以類比於回答下列的問題:
Q1:全台灣最高的山跟全世界最高的山哪一個比較高?
Q2:全台灣最矮的山跟全世界最矮的山哪一個比較矮?
根據方程組結論我們得到限制式越多，集合越來越小則 max 值會越來越小，
min 值會越來越大。
而這事實上就是 cutting plane algorithm (branch and bound) 的原理 !!
以下大致敘述其原理 :
---------------------------------------------------------------
以純整數規劃(Pure Integer Programming)來說，極大化問題來說，假設$n$個 0-1決策變數
可行解域(Feasible Solution) $F^{I} :=\{0,1\}^{n}$，最佳解$x^{*}$ ，最佳值 $y^{*}$，我們可以擴大可行解域即 LP-relaxation ，定義為 $F^{LP}:= [0,1]^{n}$ 很明顯 $ F^{I} \subseteq F^{LP}$，假設$k$為迭代次數，而 cutting plane algorithm 會持續一直加限制式(valid inequality) 會把問題化成一系列的可行解域$\{F^k\}$ ($\forall k \ ,F^{I}\subseteq F^k \subseteq F^{LP}$) 演算法會求出 $x^k$，$y^k := f(x^k) =\underset{x \in F^{k} }{\text{max}} g(x)$ ，很明顯 $y^{*} \leq y^{k}$ ，隨著 $k$ 越大 $F_{k}$ 會越小，則 $y^{k}$ 會越來越接近 $y^{*}$ ，我們稱$y^{k}$ 為上界(Bound)。
(註: 這是主要 bound + cut 的核心概念，下界的概念跟 branch 的部分可在參考整數規劃相關領域)
---------------------------------------------------------------
[布林代數的應用]
回顧可以用集合$S_P, S_Q$ 表示邏輯的條件 $P,Q$，也介紹了 Indicator function $f_P,f_Q$
還可以用 $0,1$ 四則運算來代替交集聯集，也可以使用整數規劃限制式來表達邏輯!!
$\begin{array}{cccc}
\text{Logicial Condition }& \text{Set Thinking} & \text{Boolean Operation } & \text{IP Linear Constraint} \\
P& S_P & f_P & f_P \\
\neg P& \bar{S}_P & 1- f_P & 1-f_P & \\
P\wedge Q & S_P \cap S_Q & f_P \cdot f_Q \text{ or min }(f_P , f_Q) & Z \leq f_P , Z \leq f_Q , f_P + f_Q \leq 1+Z \\
P\vee Q& S_P \cup S_Q & (f_P + f_Q) - f_P \cdot f_Q \text{ or max }(f_P , f_Q) & f_P + f_Q \geq 1 \\
P\Longrightarrow Q & S_P \subseteq S_Q & \text{ max }(1-f_P , f_Q) & f_P \leq f_Q \\
\end{array}$
註: $Z \in \{0,1\}$ 是輔助變數，
註: 整數規劃(IP)的例子，$U = \{a,b,c,d,e\}$ ，$P$代表 元素是 "$a$"，$S_P = \{a\}$則 $f_P(u) ==1$相當於 $u == a$ 的意思
[小結]
我們可以發現，邏輯，集合，布林，線性限制式，有某種對應!!邏輯建立了數學，數學又是科學之母。而可以用集合方便人們去思考邏輯，而在資工電機等科系，軟硬體上，布林扮演在實作上很重要的角色，而整數規劃限制式更是在現實問題數學建模(mathematical modeling)有很大的幫助!! 透過此文希望能讓讀者更全面認識邏輯 !!
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2017.08
留言
張貼留言