##EasyReadMore##

4.14.2013

述詞邏輯的語法

我們學英文這門語言時,首先會學這個英文有哪些符號(a, b, c, ...),然後學單字(apple, water, ...),再學怎麼組成合文法的句子。

述詞邏輯也是一門語言,所以我們先學這個語言有哪些符號,然後學term,再學well-formed formula(合文法的句式,有人翻成完構式,簡稱wff)長什麼樣。

符號
邏輯符號(所有述詞邏輯的語言都會有這些符號,而且這些符號的詮釋是規定好的,不開放任意詮釋)
  • 變元(variable):$v_1, v_2, ⋯$ (有時會用$x, y, z, u, v$之類的)
  • 連接詞(connective):$¬, ∧, ∨, →, ↔$
    $¬$的其他寫法:$~$
    $∧$的其他寫法:$·$
    $→$的其他寫法:$⊃$
    $↔$的其他寫法:$≣$
  • 量限詞(quantifier):$∃, ∀$(有些人認為量限詞是非邏輯符號才對)
  • 等號:$=$(有些人認為等號是非邏輯符號才對)
  • 括號,或叫分段符號:(, ), [, ], {, } 
非邏輯符號(不是所有述詞邏輯的語言都會有這些符號)
  • 常元(constant):$a, b, c, ⋯, c_1, c_2, ⋯$ (長相不固定,如果有某個述詞邏輯的語言就是要拿「這個是放在,荷花的左邊」當常元,我們也沒辦法)
  • 述詞(predicate):$A, B, C, ⋯, P_1, P_2, ⋯, ∈, <, ⋯$(長相不固定)
  • 函數(function):$f, g, h, ⋯, f_1, f_2, ⋯, +, -, ×, ÷, ⋯$(長相不固定)
在以上這些符號之外的東西,就不是述詞邏輯這門語言的符號了。

Term
  1. 所有變元和常元都是term。
  2. 如果$f$是一個$n$元函數,那麼把$f$的參數位置都用term填滿後得到的東西,也是term。
  3. 以上兩點之外的東西都不是term。
所以,如果語言$L$有$c$這個常元和$g$這個二元函數,那麼下列都是這個語言的term:
  • $g(x, c)$
  • $g(g(x,c), c)$
  • $g(g(x,c), g(y, c))$
  • $g(g(g(x, y), c ), g(c, z))$
下列這些都不是這個語言的term:
  • $g(c, x, c)$($L$裡沒有三元的函數$g$)
  • $g(a, c)$($L$裡沒有符號$a$)
  • $g(c)$($L$裡沒有一元的函數$g$)
  • $cc$
Well-formed formula
  1. 如果$P$是一個$n$元述詞,那麼把$P$的參數位置都用term填滿後得到的東西,就是wff。這種wff有個特定的名字叫atomic formula(原子句式),是最簡單的wff。
  2. 如果$α,β$都是wff,$v$是隨便哪個變元,那麼下列這些也都是wff:$(¬α)$, $(α∧β)$, $(α∨β)$, $(α→β)$, $(α↔β)$, $(∃vα)$, $(∀vα)$。(有時會適度省略一些括號)
  3. 以上兩點以外的東西都不是wff。
所以,如果語言$L$有$c$這個常數,和$g$這個二元函數,和$Q$這個二元述詞,那麼下列都是這個語言的wff:
  1. $Q(c, c)$
  2. $Q(x, y)$
  3. $Q(c, z)$
  4. $Q(x, y)∧Q(x, y)$
  5. $∃zQ(x, y)$
  6. $∃x∀y[∃zQ(x, y)→¬Q(x, y)]$
我們會把裡面沒有出現自由(free)變元的formula稱為sentence。上列六個formula中,只有第一個和第六個是sentence。

下列都不是這個語言的wff:

  • $Q(c, c)= Q(c, c)$(等號是述詞,述詞的參數位置要放term,不是放formula)
  • $Q(Q(x,y), c)$($Q$是述詞,述詞的參數位置要放term,不是放formula)
  • $Q(c)$($L$裡沒有一元的述詞$Q$)
  • $∧Q(x, y)$
  • $Q(x, y)∃z$

述詞邏輯的語意

有了L這個語言的structure,先把這個structure叫$M$好了,我們就可以判斷這個語言中沒有自由變元(free variable)的語句(sentence),在$M$裡是真的還是假的。

以$L'$這個有$a, b, P, Q, f, g$這些非邏輯符號的語言為例,其中$a, b$是常數,$P$是一元述詞,$Q$是二元述詞,$f$是一元函數,$g$是二元函數。我們設計一個$L'$的structure $A$如下:
$U=\{0, 1, 2\}$
$a^A=0$
$b^A=1$
$P^A=\{0, 2\}$
$Q^A=\{(0,1), (1,2), (2,1)\}$
$f^A=\{(0,2), (1,2), (2,0)\}$
——意思是,$f^A(0)=2, f^A(1)=2, f^A(2)=0$
$g^A=\{(0,0,0), (0,1,1),(0,2,2), (1,0,1), (1,1,1), (1,2,1),$ $(2,0,1), (2,1,0), (2,2,1)\}$
—— 意思是,$g^A(0,0)=0, g^A(0,1)=1, g^A(0,2)=2, ⋯$
原子語句(atomic sentence)的真假值
在$A$這個structure裡,$P(a)$是真的還是假的?我們先看$a^A$指到什麼東西,再看看$a^A$指到的東西是不是在$P$的詮釋裡。在裡面,那麼$P(a)$是真的;不在裡面,那麼$P(a)$就是假的。$a^A$指到$0$,而且$0∈P^A$,所以$P(a)$在$A$裡是真的。$P(a)$在$A$裡是真的,通常會記為$A⊨P(a)$或$⊨_AP(a)$。

而$P(b)$因為$1∉P^A$,便是假的。$P(b)$在$A$中為假,則記為$A⊭P(b)$或$⊭_AP(b)$。$Q(a,b)$是真的,記為$A⊨Q(a,b)$,因為$(0,1)∈Q^A$。$A⊭Q(a,a)$,因為$(0,0)∉Q^A$。

至於P(f(a))在$A$裡的真假值,就把$a^A$指到的東西輸進$f^A$裡,看輸出的東西是不是在$P^A$裡。$a^A$指到$0$,$0$輸入$f^A$會輸出$2$(因為$(0,2)∈f^A$,其中$0$是輸入,$2$是輸出),而$2∈P^A$,所以$A⊨P(f(a))$。而$A⊭P(g(b,a))$,因為往$g^A$的第一個參數位置輸入$1$,第二個位置輸入$0$後,輸出的$1$不在$P^A$裡。

有連接詞的語句的真假值
和語句邏輯的計算方式差不多。例如
  • $A⊭P(g(b,a))$,所以$A⊨¬P(g(b,a))$。$A⊨P(a)$,故$A⊭¬P(a)$。
  • $P(a)∧P(g(b,a))$只會在$P(a)$和$P(g(b,a))$都為真的情況下為真,所以$A⊭P(a)∧P(g(b,a))$。
有量限詞(quantifier)的句子的真假值
$∀xP(x)$的意思是,所有domain裡的東西都有$P$這個性質。目前$U=\{0,1,2\}$,也就是說,$∀xP(x)$的意思是$0∈P^A$而且$1∈P^A$而且$2∈P^A$。因為$1∉P^A$,所以$A⊭∀xP(x)$。

$∃xP(x)$的意思是,至少有一個domain裡的東西有$P$這個性質。也就是說,$∃xP(x)$的意思是$0∈P^A$或者$1∈P^A$或者$2∈P^A$。所以$A⊨∃xP(x)$。

$∀x∃yQ(x,y)$的意思是,所有domain裡的東西,都和domain裡至少一個東西有$Q$這個關係。要講得具體一點以幫助理解的話,我們可以先把$Q$視為某個二元關係,例如$x$喜歡$y$(這不代表$Q$這個述詞就是$x$喜歡$y$的意思,$Q$就只是某個述詞符號,$Q^A$僅僅是某個由二元序列構成的集合。就像國小或幼稚園老師教$1+1=2$的時候,把「$1$這個自然數,填進+這個函數的兩個參數位置後,就會輸出$2$」生動地講成,一個蘋果和另一個蘋果放在一起就是兩個蘋果那樣。雖然$1+1=2$和蘋果半毛關係也沒有,但這樣舉例子比較容易理解),那麼$∀x∃yQ(x,y)$的意思便是,每個東西都至少喜歡一個東西。

不過句子太複雜或太長的話,我們可能沒辦法用舉實例的方式,理解句子的意思。不過還有別的辦法。也可以這樣理解$∀x∃yQ(x,y)$:$∀x∃yQ(x,y)$是指所有domain裡的東西都滿足$∃yQ(x,y)$,也就是
$∃yQ(x,y)[^x_0]$而且$∃yQ(x,y)[^x_1]$而且$∃yQ(x,y)[^x_2]$
$∃yQ(x,y)[^x_0]$的意思是$∃yQ(x,y)$中的$x$會指到domain裡的$0$。我們不能直接寫$∃yQ(0,y)$是由於,$0$不是term,所以$∃yQ(0,y)$不是合文法的字串。(私底下想把$∃yQ(x,y)[^x_0]$腦補成$∃yQ(0,y)$是沒問題,但別在正式場合這麼做)

而$∃yQ(x,y)[^x_0]$可以理解成,至少有一個domain裡的東西會滿足$Q(x,y)[^x_0]$,也就是,
$Q(x,y)[^x_0,^y_0]$或者$Q(x,y)[^x_0,^y_1]$或者$Q(x,y)[^x_0,^y_2]$。
所以,$∃yQ(x,y)[^x_0]$而且$∃yQ(x,y)[^x_1]$而且$∃yQ(x,y)[^x_2]$的意思就會是:
【$Q(x,y)[^x_0,^y_0]$或者$Q(x,y)[^x_0,^y_1]$或者$Q(x,y)[^x_0,^y_2]$】而且
【$Q(x,y)[^x_1,^y_0]$或者$Q(x,y)[^x_1,^y_1]$或者$Q(x,y)[^x_1,^y_2]$】而且
【$Q(x,y)[^x_2,^y_0]$或者$Q(x,y)[^x_2,^y_1]$或者$Q(x,y)[^x_2,^y_2]$】。
也就是
【$0$喜歡$0$,或者$0$喜歡$1$,或者$0$喜歡$2$】而且
【$1$喜歡$0$,或者$1$喜歡$1$,或者$1$喜歡$2$】而且
【$2$喜歡$0$,或者$2$喜歡$1$,或者$2$喜歡$2$】
因為domain裡的每個東西的確都喜歡至少一個東西,所以$A⊨∀x∃yQ(x,y)$。

有自由變元的句式(formula)的真假值
有自由變元的句式,基本上沒辦法判斷真假值。試想以下幾個句式:
  • $1=1$
  • $2=1$
  • $x=1$
第一個句式顯然是真的,第二個顯然是假的,但第三個就難辦了,因為我們不知道$x$到底是指哪個數,所以無從判斷$x$是不是等於$1$。

既然問題的根源在於,不知道$x$到底是指什麼,那麼就發派一個東西給$x$去指不就得了。負責這項指派業務的玩意兒,就是一元的assignment function(我不知道這個東西有沒有固定的中文譯名,如果硬要翻的話,就叫指派函數好了)。這個函數和邏輯語言裡那個非邏輯符號的函數的詮釋不一樣。Assignment function的定義域是所有變數的集合(而不是structure的domain,和對非邏輯符號的函數的詮釋不一樣),值域是structure的domain裡的某一個東西。也就是,只要我們輸入某個變數給assignment function,問它這個變數是指啥,它就會輸出一個structure的domain裡的東西,回答我們此變數是指structure的domain裡的這個東西。

問不同的assignment function同一個問題,可能會得到不同的答案。例如$h_1(x)=1$但$h_2(x)=2$之類的。這時在$h_1$這個assignment function的指派之下,$P(x)$在$A$中為假,因為$1∉P^A$,記為$A⊭P(x)[h_1]$,而在$h_2$的的指派之下,$P(x)$在$A$中為真,因為$2∈P^A$,記為$A⊨P(x)[h_2]$。

有時我們會看到一些長相比較奇特的assignment function,例如$h^x_1$。$h^x_1$是指,我們已經有一個assignment function $h$,而$h^x_1$是個這樣的函數:輸入$x$會輸出$1$,輸入$x$以外的變數會輸出和$h$一樣的東西;也就是
$h^x_1(v)=1$    , if $v=x,$($v$是variable的意思)
$h^x_1(v)=h(v)$, if $v≠x$
依此類推,
$h^x_1^y_2(v)=1$    , if $v=x, $
$h^x_1^y_2(v)=2$    , if $v=y, $
$h^x_1^y_2(v)=h(v)$, if $v≠x$ and $v≠y$

重要概念
  1. 某個structure $M$讓某個句子$φ$為真的話,我們就會就說$M$這個structure是$φ$的模型(model)。(不過structure和mode這兩個字常混用就是了)
  2. 某個語言$L$中的句子$φ$是可滿足的(satisfiable),若且唯若,至少有一個$L$的structure,和一個該structure的assignment function(如果$φ$裡有自由變元的話會用上,沒有的話,assignment function就只是來插花的)會讓$φ$為真。
  3. 某個語言$L$中的句子$φ$是邏輯真理(logical truth),記為$⊨φ$,若且唯若,所有$L$的structure,和所有該structure的assignment function都會讓$φ$為真。
    也就是,任選一個$L$的structur和它的隨便那個assignment function,$φ$在裡面都會是真的。
  4. 某個語言$L$中的語句集合$Γ$,蘊含(imply)該語言的某個句子$φ$,記為$Γ⊨φ$,若且唯若,所有會讓$Γ$裡全部句子都為真的$L$的structure,和所有該structure的assignment function,也都會讓$φ$為真。
    也就是,$Γ$裡全部句子都為真的時候,$φ$也會為真。
第3點,是第4點中的$Γ$取為空集合而產生的特例。

4.13.2013

述詞邏輯的structure

語句邏輯的句子是用真值表來判斷真假值,述詞邏輯的句子則是用structure來判斷。Structure是由domain和對非邏輯符號的詮釋(interpretation)構成的;至於要詮譯哪些非邏輯符號,就看語言中的非邏輯符號有哪些,詮釋那些就可以了。

以某個有$c_1, c_2, P_1, P_2, f_1, f_2$這些非邏輯符號的語言為例,其中$c_1, c_2$是常數,$P_1$是一元述詞,$P_2$是二元述詞,$f_1$是一元函數,$f_2$是二元函數此處符號的下標和述詞及函數是幾元一模一樣只是偶然),這個語言的structure大致會長成這樣:$M=(U, c_1^M, c_2^M, P_1^M, P_2^M, f_1^M, f_2^M)$。以下一一介紹這些符號的意思。

Structure的名字
$M=(U, c_1^M, c_2^M, P_1^M, P_2^M, f_1^M, f_2^M)$中的$M$和上標的$^M$顯示了這個structure的名字是$M$,意思是model。取名時通常會用大寫英文字母,有時會用特殊字形呈現,以示區隔,例如$M$的花體字是$\fr M$。

Domain
$U$指structure的domain,$U$是universe的意思。有些人不會寫$U$來表示domain,而是寫$D$,或dom($M$),或$|M|$(最後兩個寫法和structure的名字有關。不過$|M|$這個寫法可能會讓人誤以為你想談的是$M$的domain的基數(cardinality),也就是domain裡有幾個東西)。或者structure的名字用特殊字形,然後domain就用一般字形呈現,例如$\fr A$這個structure的domain就用$A$表示

當我們在說structure的大小、structure有多大時,我們指的是它的domain的基數。

Domain是一個集合,而且不能是空集合。我們可以把structure理解成是某個世界,domain則決定了這個世界上有哪些東西。你可以依自己喜好往domain這個集合裡加進任何東西,例如數字、英文字、中文字、人、幾何圖案;加無限個東西進去也行,例如讓domain是所有實數的集合。以下是一些domain這個集合可能的長相:
  • $\{0, 1, 2\}$ 
  • {$0, △, @, a$, Doctor House, 嗨!, 飛天麵條神}
不過為了書寫方便起見,通常只會放數字或英文字。我們暫定$M$的domain是$\{0, 1, 2\}$。

常數的詮釋
$c_1^M$是指,$c_1$這個常數在$M$裡的詮釋。$c_1^M∈U$,也就是,$c_1^M$會等於domain裡的某一個成員。我們可以把常數理解成domain裡某個東西的名字;一個東西可以有很多個常數當作名字,就像一個人可以有很多個綽號類似;但一個常數不能指到一個以上的東西,因為重名的話,我們就不知道那到底是在叫誰了。以下是一些$c_1, c_2$這兩個常數在$M$中可能的詮釋:
  • $c_1^M = 0, c_2^M = 1$
  • $c_1^M = 0, c_2^M = 0$
述詞的詮釋
$P_1^M$是指,$P_1$這個述詞在$M$裡的詮釋。我們對述詞的詮釋是外延(extension)式的。如果$P$是一個$n$元述詞,那麼$P^M⊆U^n$。$P^M$也是一個集合,而和domain不同的是,述詞的詮釋可以是空集合。

$U^n$是$U×⋯×U$乘$n$次的意思。$A×B$是一個由二元序列(tuple)構成的集合,序列中的第一個東西來自$A$,第二個來自$B$,把所有符合此條件的序列蒐集起來形成的集合,就是$A$×$B$。例如,
若$A=\{1,2\}, B=\{3,4\}$,則$A×B=$ $\{(1,3), (1,4), (2,3), (2,4)\}$。
$A×B×C$則是由許多三元序列構成的集合,序列中的第一個東西來自$A$,第二個來自$B$,第三個來自$C$,把所有符合此條件的序列蒐集起來形成的集合,就是$A×B×C$。例如,
若$A=\{1,2\}, B=\{3,4\}$,$C=\{5,6\}$,則$A×B×C=$ $\{(1,3,5), (1,4,5), (2,3,5), (2,4,5), (1,3,6), (1,4,6), (2,3,6), (2,4,6)\}$
在序列裡,東西的順序很重要,$(1,2)$和$(2,1)$是不同的序列,這點和集合很不一樣,$\{1,2\}$和$\{2,1\}$都是同一個集合。(也有人用角括號表示序列,但是我還沒弄清楚怎麼在blogger上打出角括號)

完全沒弄懂前面$P^M$ ⊆ $U^n$是什麼鬼玩意的人別擔心,先來看幾個例子。我們可以把一元述詞$P_1$的詮釋想成,我們想讓domain裡的哪些東西有$P_1$這個性質,我們就把那些東西放到$P_1^M$這個集合裡。$P_1$在$M$裡幾個可能的詮釋:
  • $\{1\}$ 
  • $\{0, 2\}$ 
  • $\{0, 1, 2\}$ 
我們可以把二元述詞$P_2$的詮釋想成,我們想讓domain裡哪兩個東西有$P_2$這個關係,就把那兩個東西放到$P_2^M$這個集合裡。或者更生動一點地說(就像國小或幼稚園老師教$1+1=2$的時候,把「$1$這個自然數,填進+這個函數的兩個參數位置後,就會輸出$2$」生動地講成,一個蘋果和另一個蘋果放在一起就是兩個蘋果那樣。雖然$1+1=2$和蘋果半毛關係也沒有,但這樣舉例子比較容易理解),把$P_2$想成某個二元關係,例如$x$喜歡$y$,我們想讓domain裡的$0$喜歡自己的話,就把$(0,0)$放進$P_2^M$這個集合裡,想讓domain裡的$1$喜歡domain裡的$2$的話,就把$(1,2)$放進去。

$P_2$在$M$裡幾個可能的詮釋:
  • $\{(0,0), (0,1), (0,2)\}$ ($0$喜歡domain裡的所有東西,$1$和$2$則什麼東西都不喜歡)
  • $\{(0,1), (1,0), (2,0)\}$ ($0$和$1$互相喜歡,$2$單戀$0$)
  • ∅(每個東西都不喜歡每個東西)
如果我們遇到的是三元述詞,而且這個述詞的詮釋不是空集合的話,集合裡的東西會長得像$(□,□, □)$,其中空格的部分各填進一個domain裡的東西。總的來說,如果遇到的是$n$元述詞,而且述詞的詮釋不是空集合的話,集合裡的東西會長得像$(□, ...,□)$,共$n$個空格,其中每個格子都填進一個domain裡的東西。

等號這個述詞非常特別,它是邏輯符號(不過有些邏輯學家不這麼認為,但目前先當作等號是邏輯符號),所以一般而言等號的詮釋已經規定好了,不是我們想要讓哪兩個domain裡的東西相等,就可以把那兩個東西組成的序列丟進等號的詮釋裡。等號的詮釋這個集合裡,放的東西一律是,每個domain裡的東西,自己和自己構成的序列,也就是,$\{(x,x)|x∈domain\}$。現在domain$=\{0,1,2\}$,所以$=^M=\{(0,0), (1,1), (2,2)\}$。

函數的詮釋
$f_1^M$是指,$f_1$這個函數在$M$裡的詮釋。如果函數$f$是$n$元的,則它的定義域是$U^n$,值域是$U$。

我們有個把函數轉成集合的辦法:函數是$n$元,我們就弄出$n+1$元的序列,序列的前面$n$格放輸入值,最後一格放輸出值。例如$g(x)=x+1$這個定義在自然數上的一元函數,轉成集合後會長這樣:$\{(0,1), (1,2), (2,3), ...\}$。

函數的定義是,如果輸入值在定義域裡的話,就一定要有輸出值,而且輸出值只能有一個。所以在詮釋函數時也要符合這條規定。

所以,$f_1^M$的定義域是$\{0, 1, 2\}$,因為$f_1$是一元函數。而$f_1^M$會長這樣:$\{(0,□), (1,□), (2,□)\}$,其中每個空格都填進一個domain裡的東西,就能得到一個可能的詮釋。所有空格都填同一個東西也沒關係。

$f_2^M$的定義域是$\{(0,0), (0,1),(0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)\}$,因為$f_2$是二元函數。而$f_2^M$會長這樣:$\{(0,0,□), (0,1,□),(0,2,□), (1,0,□),$ $(1,1,□), (1,2,□), (2,0,□), (2,1,□), (2,2,□)\}$,其中每個空格都填進一個domain裡的東西。

如何用structure判斷句子是真的還是假的?請見述詞邏輯的語意

11.16.2012

公理,定理,引理和系理

對象語言(object language)和後設語言(metalanguage)
當有人用英文研究拉丁文時,對象語言是拉丁文,後設語言是英文。對象語言和後設語言可以是同一套語言,例如用中文研究中文的時候。基本上,後設語言中要具備對象語言裡的所有符號,不然討論對象語言時可能會遇上困難。例如,若只用中文研究英文,便無法寫出「water的意思是水」這種句子,因為後設語言裡沒有英文字母;若後設語言是一套由英文字母和中文構成的語言,就可以。我們在用中文、英文和某邏輯語言的符號,討論該邏輯語言時,對象語言是該邏輯語言,後設語言是一套由中文、英文和該邏輯語言的符號構成的語言。
公理(axiom)
在邏輯系統中,不需要證明就可以拿來用的句式(formula)便是公理。你可以問選這些句式當公理有什麼好處,但沒辦法要求證明這些句式。如果你覺得某邏輯系統的其中一些公理不能滿足你的需求(例如,不能完美模仿人類的推論方式),可以另闢一套邏輯系統,放自己喜歡的公理。但那套系統有沒有研究價值、是否有人想用則是另一回事。
定理(theorem)
僅利用某邏輯系統的公理,或利用公理及系統允許的推論規則就能證明的句式,便是該邏輯系統的定理。根據定義,任一邏輯系統的公理均是其定理。
定理還有另一個意思。對象語言是某套邏輯系統的邏輯文章裡,定理通常指作者主要想證明的句子,這個句子使用後設語言有,但對象語言沒有的符號描述該邏輯系統的性質。因為這種定理中出現了那套邏輯語言沒有的符號,所以無法被該邏輯系統的公理或推論規則證明。語句邏輯的演譯定理(deduction theorem)便是這樣的句子。第二種意思的定理被稱為後設定理(metatheorem)。
引理(lemma)
引理也是用後設語言描述邏輯系統的性質的句子。引理通常指,用來幫助證明後設定理的重要踏腳石。是後設定理還是引理,端賴它在文章中是否為作者的主要目標,因此可能發生,同一個句子在這篇文章中是引理,在另一篇文章中是後設定理的情況。
系理(corollary)
系理也是用後設語言描述邏輯系統的性質的句子。後設定理蘊含的一些重要結果便是系理,至於哪些被蘊含的結果才是重要的,則由作者決定;作者大多會選和他等一下要討論的事有關的結果當系理。一但證明後設定理,要證明該後設定理的系理通常很容易。

10.08.2011

九十九年中正哲學碩班甄試邏輯試答

I. True or False
  1. [(A∨B)→C]→[(D∧¬C)→(A→E)] is a tautology.
    T
  2. ∃x(∀yPy→Rx) is logically equivalent to ∀yPy→∃xRx.
    T
    1.∃x(∀yPy→Rx)    前提
    2.∀yPy                   ACP for ∃xRx
    3.∀yPy→Rx           1, EI
    4.Rx                        2,3, MP
    5.∃xRx                    4, EG
    6.∀yPy→∃xRx      2-5, CP
    .
    1.∀yPy→∃xRx      前提
    2.¬∃x(∀yPy→Rx)  AIP
    3.∀x¬(∀yPy→Rx) 2, EQ
    4.∀x(∀yPy∧¬Rx)  3, Impl, Dem, DN
    5.∀yPy∧¬Rx          4, UI
    6.∀yPy                    5, Simp
    7.∃xRx                    1,6, MP
    8. ¬Rx                     5, Simp
    9.∀x¬Rx                 8, UG
    10.¬∃xRx                9, EQ
    11.∃xRx∧¬∃xRx    7,10, Conj
    12.∃x(∀yPy→Rx)   2-11, IP
    .
  3. Suppose A is contingent. If A and B are inconsistent and A and C are inconsistent, then B and C must be inconsistent.
    F
    A和B不一致,而且A和C不一致,表示A和B不可能同時為真,而且A和C不可能同時為真。所以當A為真時,B和C都不會為真;但A為假時,B和C的真值不管怎麼設定都不會和「A和B不一致,而且A和C不一致」的前提有衝突。所以A和B不一致,而且A和C不一致,而且B和C一致的情況是有可能的。
    .
    或者,畫出A、B、C的真值表,然後把A和B同時為真的那列劃掉,再把A和C同時為真的那列劃掉,最後檢查剩下的列裡有沒有B和C同時為真的情況。
    .
  4. P∧R logically implies Q if and only if P logically implies P→Q and R logically implies R→Q.
    F
    P∧R⊧Q iff  P⊧P→Q and R⊧R→Q
    A蘊含(imply,⊧)B的意思是,當A為真時,B也會為真(不會有A為真B為假的情況)。檢查A if and only if B為不為真的方式有三種:
    一、當A為真時,B也為真。而且當B為真時,A也為真。
    二、當A為假時,B也為假。而且當B為假時,A也為假。
    三、當A為真時,B也為真。而且當A為假時,B也為假。
    我用第二種方式檢查。
    P∧R⊧Q只會在P和R為真,Q為假的時候為假。在P和R為真,Q為假的時候,P⊧P→Q and R⊧R→Q也為假。
    P⊧P→Q and R⊧R→Q會在P或R為真,Q為假的時候為假。在P和R只有其中一個為真,Q為假的時候,P∧R⊧Q會為真。
    .
    因為有P∧R⊧Q為真,但P⊧P→Q and R⊧R→Q為假的情況(P和R只有其中一個為真,Q為假),故P∧R⊧Q iff  P⊧P→Q and R⊧R→Q為假。
    .
  5. A is true unless B is false. So A and B cannot be both true.
    F
    P: A is true.
    Q: B is true.
    「A is true unless B is false」可以被改寫成P∨¬Q。當P和Q皆為真時,P∨¬Q也為真。所以A和B可以同時為真。
II. A politician made the following statement during a TV interview: 
“If I am not attending a congressional meeting, I am planning for a better future of our country. And if I am not planning for a better future of our country, I am listening to our people for their opinions.” What’s wrong with his statement?
A: I am attending a congressional meeting.
P: I am planning for a better future of our country.
L: I am listening to our people for their opinions.

這位政治家說的話可以被改寫成¬A→P, ¬P→L。

1.¬A→P          前提
2.¬P→L          前提
3.¬P                ACP
4.A                  1,3, MT
5.L                   2,3, MP
6.A∧L             4,5, Conj
7.¬P→(A∧L)  3-6, CP
8.¬(A∧L)        根據常識,大概沒有人可以一邊開國會會議一邊聴取人民的意見。
9.P                  7,8, MT

這位政治家一直在為國家的美好未來做打算。不過大概沒有人能無時無刻都掛念著同一件事。
III. Let “Lxy” stand for “x loves y”,
     “Hxy” stand for “x hates y” and
     “Px” stand for “x is a philosopher”.
Please symbolize the following sentence.
Someone who is not a philosopher loves exactly two different philosophers who hate each other.
∃x(¬Px∧∃y∃z(Lxy∧Lxz∧∀u(Lxu→(u=y∨u=z))∧¬y=z∧Py∧Pz∧Hyz∧Hzy))
IV. Please prove the following valid argument.
∀x(Rx↔Qx), ∃x(¬(Px↔Qx)↔Rx) /∴ ∀x((∃yRy∧∃yQy)→Px)→∀x¬Rx
  1. ∀x(Rx↔Qx)
  2. ∃x(¬(Px↔Qx)↔Rx)
  3. ∀x((∃yRy∧∃yQy)→Px)                          ACP for ∀x¬Rx
  4. ¬(Px↔Qx)↔Rx                                        2, EI
  5. (¬Px↔Qx)↔Rx                                        4, 等價
  6. ¬Px↔(Qx↔Rx)                                        5, 等價
  7. [¬Px∧(Qx↔Rx)]∨[Px∧¬(Qx↔Rx)]         6, Equiv
  8. Rx↔Qx                                                    1, UI
  9. ¬Px∨(Rx↔Qx)                                         8, Add, Comm
  10. ¬[Px∧¬(Qx↔Rx)]                                    9, Dem, DN, 等價
  11. ¬Px∧(Qx↔Rx)                                         7,10, DS
  12. ¬Px                                                           11, Simp
  13. (∃yRy∧∃yQy)→Px                                   3, UI
  14. ¬(∃yRy∧∃yQy)                                        12,13, MT
  15. ∀y¬Ry∨∀y¬Qy                                       14, QN
  16. ¬∀y(¬Ry∨¬Qy)                                        AIP
  17. ∃y(Ry∧Qy)                                               16, QN, DeM, DN
  18. Ry∧Qy                                                      17,EI
  19. ∃yRy∧∃yQy                                             18, Simp, EG, Conj
  20. ¬∀y¬Ry∧¬∀y¬Qy                                   19,QN
  21. ¬(∀y¬Ry∨∀y¬Qy)                                   20, Dem, DN
  22. (∀y¬Ry∨∀y¬Qy)∧¬(∀y¬Ry∨∀y¬Qy)   15,21, Conj
  23. ∀y(¬Ry∨¬Qy)                                           16-22, IP
  24. ¬Rx∨¬Qx                                                  23, UI
  25. ¬(Rx∧Qx)                                                 24, Dem, DN
  26. (Rx∧Qx)∨(¬Rx∧¬Qx)                              8, Equiv
  27. ¬Rx∧¬Qx                                                  25, 26, DS
  28. ¬∀yQy                                                       27, Simp, EG, QN
  29. ∀y¬Ry                                                       15,28, DS
  30. ¬Rz                                                            29, UI
  31. ∀x¬Rx                                                       30, UG
  32. ∀x((∃yRy∧∃yQy)→Px)→∀x¬Rx             3-31, CP
另一個方法:
  1. ∀x(Rx↔Qx)
  2. ∃x(¬(Px↔Qx)↔Rx)
  3. ¬[∀x((∃yRy∧∃yQy)→Px)→∀x¬Rx]             AIP 
  4. ∀x((∃yRy∧∃yQy)→Px)∧¬∀x¬Rx                3, DeM, DN
  5. ∃xRx                                                               4, Simp, QN
  6. Rx                                                                   5, EI
  7. Rx↔Qx                                                           1, UI
  8. Qx                                                                   6,7, Equiv, Simp, MP
  9. ∃yRy∧∃yQy                                                   6,8, EG, Conj
  10. ¬(Py↔Qy)↔Ry                                               2, EI
  11. ∃yRy∧∃yQy→Py                                           4, Simp, UI
  12. Py                                                                    9,11, MP
  13. ¬Py↔(Qy↔Ry)                                               10, 等價
  14. Qy↔Ry                                                            1, UI, 等價
  15. ¬Py                                                                  13,14, Equiv, Simp, MP
  16. Py∧¬Py                                                           12,15, Conj
  17. ∀x((∃yRy∧∃yQy)→Px)→∀x¬Rx                  3-16, IP
相關文章:

10.07.2011

中正的研究所開始招生(101學年度)

重要日程表
  • 簡章發售日期:10月6日起。
  • 報名期間:10月6日至10月25日。
  • 「系所指定繳交資料」郵寄截止日:10 月26 日。
  • 複試:11月18日至11月20日(確切日期以各系所正式通知為準)。
相關連結: