邏輯、集合論，映射與函數（邏輯淺論） 江銘輝 五夢網
一、 邏輯淺論
1.敘述
敘述通常以小寫字母p、q、r等表示之。吾人所謂之敘述，有一基本之性質，即敘述的內容可判斷真或假，但不能既真又假。敘述之真、假稱為該敘述之真值（Truth Value）。
有些敘述一定為是正確者，此種敘述稱為公理(axioms);另外有些敘述經由證明後，方可確定其為正確者，此種敘述稱為定理(Theorems)。
例如 :
"2為一自然數"為一敘述;因我們可判斷其為真也。
"你貴姓?"不是一個敘述，因我們無法判斷它是真或是假。
"若m為一奇數，則m2為一奇數" 為一敘述，因我們可證其為真也。
"4+3=6" 為一敘述，因我們知其為假也。
2.合成敘述
有些敘述是由1個以上的敘述合成者，稱為合成敘述，通常以“且（and）”、“或（or）”、“非（not）”、“若…則（if）”、“若且唯若（if and only if）”、“意指（imply）”……等字連結二個敘述。
一合成敘述之真、假，可由其每一子敘述之真、假值及連接方式決定。
在合成敘述分析中，我們經常使用簡單的符號來表示，下列是我們經常使用的符號。
|
名辭
|
符號
|
|
單一敘述
|
p、q、r、s
|
|
且
|
Λ
|
|
或
|
V
|
|
意指（若p，則q）
|
→
|
|
若且唯若
|
↹
|
|
非
|
～
|
3.聯合敘述
二敘述用"且"字連結而形成的敘述，即pΛq。
pΛq的真、假值滿足下列性質:
"若p、q均為真，則pΛq為真;若其中有一個是假，則pΛq為假"。我們將此歸納為下表:
|
p
|
q
|
pΛq
|
|
真
|
真
|
真
|
|
真
|
假
|
假
|
|
假
|
真
|
假
|
|
假
|
假
|
假
|
註：形式如上表者，稱為真值表（Truth table）
例1：
若p是"4+4=8"； q是"5≧2" 則 pΛq是"4+4=8"且"5≧2"，因為p是真；q也是真，所以pΛq是真。
例2：
若p是"5為實數"； q是"4為奇數" 則 pΛq是"5為實數"且"4為奇數"，因為p是真；q是假，所以pΛq是假。
4.分離敘述(disjunction)
任二敘述可用"或"字連結，稱為分離敘述，通常以pVq表示。
"若p、q均為假，則pVq為假;若其中有一個是真，則pVq皆為真"。我們將此歸納為下列真值表:
|
p
|
q
|
pVq
|
|
真
|
真
|
真
|
|
真
|
假
|
真
|
|
假
|
真
|
真
|
|
假
|
假
|
假
|
例1:
若p是"2為一有理數"；q是"4+3=8"，則
pVq 表示"0為一有埋數或4+3=8"。因為p是真，q是假，故由上表知pVq為真。
例2:
若p是"π為一有理數"；q是"5為一偶數"，則
pVq"為π為一有理數或5為一偶數"。又因p為假q亦為假，故由上表知pVq為假。
5.否定敘述(negation)
我們可於任一敘述之後加上"是假的"三字，以形成否定的敘述。
(可能的話，有時可於敘述內加上"非"字)。敘述p之否定敘述通常以符號 ~p
表示。~p之真、假值滿足下性質:
“若p為真，則~p為假;若p為假，則~p為真”。換言之:否定敘述之真值永遠與原敘述之真值相反。此亦可以下列真值表表之:
例1:
若p是“2為偶數” ，則~p是“2為非偶數”，因此p是真，~p是假。
例2:
p是"3+3=3"，則~p是"3+3≠3"，因為p是假，所以~p是真。
6.函蘊敘述（implication statement）
對於若p則q.的形態，通常以p→q表示之; p稱為假設、q稱為推論。
p→q之真值表滿足以下性質:
"若p為真，q為假，則p→q為假;其餘p→q皆為真"。我們可歸納此性質為下列真值表:
|
p
|
q
|
p→q
|
|
真
|
真
|
真
|
|
真
|
假
|
假
|
|
假
|
真
|
真
|
|
假
|
假
|
真
|
例1 :
若P是"3+2＝5"；q是"3×2＝6"則p→q是“若3+2＝5則3×2＝6” P是真，且q也是真，按上面真值表，p→q也是真。
例2 :
若P是"3+2＝6"；q是"3×3＝9"則p→q是“若3+2＝6則3×3＝9” P是假，且q是真，按上面真值表，p→q也是真。
7.對等敘述(equivalent statement)
敘述如果以P若且僅若q，形式出現，通常以"P↹q"表之;此類敘述稱為對等敘述。對等敘述滿足下列性質:
若P、q有相同之真值，則P↹q為真;若P↹q之真值相反，則P↹q為假。我們可歸納為下列真值表:
|
p
|
q
|
P↹q
|
|
真
|
真
|
真
|
|
真
|
假
|
假
|
|
假
|
真
|
假
|
|
假
|
假
|
真
|
例 1 :
x為一正數若且僅若5x為正數，這裡p是"x為正數"，q是"5x為一正數"二敘述之對等敘述。因為二敘述有相同之真值，故其合成對等敘述為真。
這裡有一點我們要說明的，p和q是有關連性，p是真q也必定真，p是假q也必定假。
例2：
"2+2=4若且僅若2x2=3"為假;蓋因2+1=3為真，而2X2=3為偽也。
8.從真值表看來，p→q與 ~pVq是對等，它們的真值表完全相同。
9.互斥閘（XOR gate）
互斥閘是用來執行XOR的邏輯運算，其真值表如下：
當p、q都是真或都是假的時，XOR的邏輯運算結果是“假”，但p、q有一個是假的，一個是真的，XOR的邏輯運算結果是“真”。
|
p
|
q
|
pXOR q
|
|
真
|
真
|
假
|
|
真
|
假
|
真
|
|
假
|
針
|
真
|
|
假
|
假
|
假
|