那接下來我們提到logic,那logic就是我們剛剛講的 formal language其中的一種,我們要定義一個language的話,我們首先要定義它的- 就是語法和語義, 它的syntax我們等下會簡單提一下,它的semantics我們不會講的太 細,但是一般來說大家都知道是什麼意思 譬如說我們是 A and B為真,那意思就是說 A為真,B為真這樣。那semantics我們假設大家大致上是瞭解的。 那我們在講,其實semantic這個語義呢,在邏輯裡面 是用來定義什麼是truth 這個truth其實也是,一個語法裡面它為真的時候同時它定義了所有可能 的世界,那這個所謂的所有可能的世界這件事,如果你們現在不太熟的話, 等下我們可以講到,就是 如果只講,我們focus在邏輯上的話, 所謂possible world指的就是就是 truth assignment, 就是一組truth assignment,也就是說,譬如說 這個世界裡面A為真而且B為假,C為假,D為真等等,也就是說我們 也就是相對應一組,我剛剛講的,就是A true,B false,然後C是false,然後D是true 這樣一組可能一個其中的世界,我們之後在possible world 和truth assignment 這之間,我們可能會用, 有時候我們講possible world,有時候我們講 truth assignment,到時候以哪種方便來講用哪一種 那 在,我們一天到晚講possible world也蠻辛苦的,所以我們首先 先定義一個term叫model model這個東西呢,定義如下。如果一個sentence,現在α是個 sentence 是true,在一個model m 底下為true的時候,那基本上我們以下三種講法 它的 還是完全equivalent的,identical的,譬如說, 我們可以講 m satisfies α, 這就是語句的問題,那我們也可以講說,m是α的一個model 就是使得α為真,就是記得,是使得α為真的一種 truth assignment。那還有一種講法,用集合論的講法,就是 把 M(α)當作是一個set,就是所有α為真的這些model的集合,那m屬於它之一。 那之後,這三種寫法都是identical的,所以我們用任何一種都可以。 我們定義了model之後,我們要定義一個很重要的概念, 就是叫entailment,entailment這個概念不僅僅是在 proposition logic,基本上在所有的logic上面都是可以通用的。ㄣ 那我們定義上就是這樣 我們這邊寫,因為我們針對AI這門課,我們會講,會寫knowledge base。 但是in general 我們可以就是某一個sentence。 就是某一句話entails另一句話。那entail α , 那if and only if對所有,這邊很重要是,all world,就是只要在KB為真的世界裡面,α全都要為真。 這樣應該可以聽得懂,那如果這件事成立的時候,那我們就把它寫成 這個樣,用這個符號,entail,就前面這個sentence entail 後面 就是只要是KB是真的時候,後面就全都是真。 好這個概念其實咋聽之下會跟imply有點像,就是A implies B,似乎有這樣的概念。 那我們等一下會show,說它們倆不同的地方在哪裡。 好,我們先舉幾個例子,譬如說 如果照我們一般的algebra來講的話 那只要是X+Y=4為真的世界裡面,好這個世界可以有哪些呢,例如, 這個世界其實,如果XY沒有限定的話,可以是無窮多個,譬如說這個世界裡面 可以是X=1,Y=3,你可以是 X=-1.5,那Y=5.5, 你可以像這個世界都是X+Y=4 是真實的世界,那同樣在這個世界裡面,後面這個都會成立 4=X+Y,當然一般來說左右兩個是equivalent的話,因為這個例子是equivalent的,那 當然就equivalent的時候,A跟B equivalence的,那當然A entails B, 這當然蠻明顯的,那另外一個是不同的世界了,就是 如果,只要是X=0的這個世界,那裡面可能有一些不同的Y值 那都entail X*Y都是0,在我們目前定義的algebra裡面 都是這個樣,好,那這邊有個theory嘛 αentails βif and only if α的model是βmodel的子集 真子集,那可以相等,那這個概念還是蠻重要的,那在之前 教課的時候常常會有感覺到同學蠻常弄反的 概念其實不難理解,下面是證明,證明是兩方面,only if and if 那其實根據entail定義就知道 αentails β的意思是說 α為真的世界裡面β都要為真,所以假設這些是 α為真的世界,我這樣寫,其實也就是 M(α),對不對,就是α為真的那些世界裡面 因為β都要為真,那其實很明顯的就是β一定要更大 當然可以一樣啦,可以一樣,可是不能包不到,就是這麼回事,那下面有寫一些 證明,可是這個證明,其實我不管是only if 還是if 這邊其實我用的證明過程其實都是雙箭頭,雙向箭頭, 其實單一個都可以,但是寫起來很單純 其實這就是entailment的定義 如果你在做習題或是考題,如果對entailment有任何懷疑的時候 請記得你一定要回到最原始的定義來證明,那這裡面一直要強調就是 in all world,這是最重要的一件事件,在entailment裡面的定義,好我們舉一個- 例子好了 這個例子是這個樣子 在課本後面的習題裡面就有,我們問的是這個樣 αand β entails γ則 αentails γ 或是βentailsγ這個問的是 true or false 如果這是是非命題的話,這個答案是false,但是 這邊可以看出entailment跟implication的差異,如果我們先用 implication來做一次,implication的話這一題答案是true,好- ,我們先寫一下 如果是imply的話,我們用imply的話符號是單向箭頭 就是αandβimpliesγ,那我們可以把它寫成 就是A implies B,那我們可以寫成﹁A or B,這樣展開 大家應該知道,那我們可以寫成 ﹁αand β or γ 這個等下會看到 我簡單講一下它的概念,就是如果A implies B 為真,那它其實 完全同等於非A或是B,簡單講,譬如說我說 A今天你考試考100分我請你去吃大餐,那這件事為真,其實 依的是我請你吃大餐,如果我請你吃大餐的話,不管你考試考沒考100分 我剛剛講的那句話都是為真嘛,如果你考100分我就請你吃大餐,或是另外的可能是,你沒- 有考到100分 你沒有考到100分的結果其實,我請不請你吃大餐,我那句話都是為真 因為你沒辦法證明我的那句話是否是謊話了,在語義上你可以這樣想 你可以相信,雖然你沒有考100分,但是你可以相信,我們基本上可以相信,如果你考- 100, 我會請你吃大餐的 所以,如果你考100分我請你吃大餐這句話全等於 我請你吃大餐或是你沒有考100分 這是這兩個,這是一樣的事情 那我們把它寫成說,就可以把它寫成 ﹁αand β或是γ 那這個東西我們可以用De Morgan把它拆進來,就是﹁可以把它往里擺,所以你可以寫成 ﹁α,De Morgan進來的話,and要變成or or ﹁βor γ 那我們寫成這樣之後我們就可以做拆項,那它基本上等於 ﹁ α or γ然後再 or ﹁γ我多寫一個γ 剛剛這個式子讓它同等我可以多一個or γ 這個式子是一樣的,我多一個or之後我去 交換一下,結合一下,就形成這兩句話,那這兩句話當然我們就 很習慣,前面這個就是α impliesγ,或是,我們用 把它換成語句,sentence,那就是β implies γ,好,這個地方就是說 如果上面這個命題我們不是用entailment,而是用 implication的話,那這個命題為真,那我們回到 如果原來的命題 αand βentailsγ,則αentailsγ 或是 βentailsγ,這個命題如果簡單講是說 到entailment的時候你最好,就不要做任何的運算,entailment其實- 是一種在 所有的,跟implication其實很像,它就是在所有的世界事件裡面都要 都要imply,我們如果懷疑的話,最簡單的一種方式 就是你可以把truth table全部列出來解釋,當然如果可能變數多可能不能這樣,但是因為第一次遇到我們就- 做一下這件事情 那你全部可能列出來世界就是,在這裡面全部有八種世界 就用0,1表示,那大家應該很熟悉,0 就是指false,那1就指true,好,那這種情況下,那我們再寫一下 αandβ,αandβ的話就是兩個都為真才會為真 所以基本上就只有最後這兩項為true,那其他都是false 那我們回看一下原題目 左邊這邊,αandβentailsγ,意思就是說 αandβ為真的世界情況下,γ都要為真,那在這裡面描述的其實就是 這兩個為真的時候,γ必須為真,所以指的是這一個 以及說,前面如果你是,前面如果是false的話,那後面什麼都可以 前面是false的話,那這邊都可以,也就是說前面這個命題呢 已經指定了在全部的八種世界裡面rule out了 一種世界,也就是這個世界是不存在的 好其他的七種世界都可以,就我這邊畫的,剩下的七種都可以 在這七種世界裡面 我們看一下,α有沒有entailγ,或是 β有沒有entailsγ,那你可以看到,αentailsγ的話,指的是 其中六種事件,我先把這個再划掉一次,指的是 α為假的時候,不為真的時候其實都可以,以及α為真的時候 γ同時為真,那指的是這一個世界 以及這一個世界,我打星的這邊有六種世界 那我們講過entailment就必須在所有的世界裡面都必須要成立 所以我們在全面命題的七種世界已經限定完了 原本全部可能是八種嘛,那根據這個命題我們只剩下七種世界,那這七種世界裡面 α並沒有entailγ,因為如果αentailγ,必須在這七種世界裡面,全部都要成立 可是它其中有一種不成立,就是這一個不成立 在這個世界中,就是前面命題可以成立的世界 可是α沒有entailγ,那後面一樣,βentailγ其實也是另外六種 我們可以看,打一下,βentailγ的話呢,你可以看到要對的就是 β對的全都要對,這個OK,這個 這個錯的就沒關係,那β對的時候後面也要跟著對 這個可以,這個可以,那你會發現這一個世界沒辦法做到 也就是說前面有七種世界情況下,它至少有一種做不到 就是它也只有六種 那我們回到entailment的定義的情況就是,你必須要在所有的事件裡面 我為真的時候你就一定要為真,那其實並沒有,所以,這個命題,如果照我們這樣看來,就是- false 那當然你們會注意到,就是這六個世界 和這六個世界的連集,其實會是 前面七個世界,就全部,這是為什麼,implication的時候 它是真,這個命題為真,可是在entailment這個不符合定義 entailment必須帶對所有的model 所有的model,那我們這邊所有的model就是這七種,也就是這七種model裡面- 你全部要成立,你才能成立 你不能去做這樣的運算,不能去做這六種or這六種這種運算,我們這邊做的是說,這七種- 全部成立 或是另外那七種全部成立,either way,那其實這兩個都不成立就是了,所以這邊,答案其實是false 我們這邊其實是第一次遇到,所以我們就是把 可能的世界全部列出來,然後回想一下entailment的定義,其實entail- ment 一種不是很正式的講法是說,在所有的世界,就是for all model,imply 你如果一定要跟implication去鏈接的話,你可以比較不正式的這樣講,但是如果- 有任何疑慮的時候 我們還是回到最原始的定義來看。我們回到Wumpus的世界,來看一下entailme- nt怎麼應用 大家還記得嗎,我們一開始在1這個點,然後我們agent移到了21這個位置 那感覺到有BREEZE,那在這個時間點,那其實我們是說,合理的 一個agent會認為,應該可以到處1,2不是pit的結論,應該可以做到這一點 因為你在1,1沒有感覺到風,所以你應該知道1不會是pit,anyway我們來看一下, 我們現在所有的資訊是這個樣,你在1,1的時候沒有感受到任何東西,你在2,1的時候感- 覺到BREEZE 然後我們想要知道的事情是我們還沒去過的 臨近的這三個格子,就1,2, 2,2,和3,1這三個位置,它是有pit或是沒有 好,那 這全部來說,因為我們要知道這三個格子有沒有pit,所以你全部你依的是有或沒有 三個格子,所有全部,我們現在在探討這個sentence 可能性裡面,全部的世界,全部possible world,也就是possible model,全部就是八個 那我們接著用entailment的話,我們就直接 把這八個model全部畫出來,下面這兩張圖都是一樣,左邊和右邊 這八個世界都一樣,就是說有可能有pit和沒pit,像這個例子 就是三個都有pit,這個可以是三個都沒有pit的世界,然後其中說可能全部列出來 好,那我們接下來再考慮兩個sentence,一個是α1,α1就是說 1,2沒有pit,α2就是說2,2沒有pit 那我們來看一下這兩個sentence跟原來的entailment的關聯是什麼,那我- 們現在的KB呢 KB是這個樣,我們可以來看一下,KB怎麼畫出來呢,KB是這三個世界 這是我們的KB,應該是model of KB,嚴格講,我現在畫的紅圈 應該是model of KB,其實你就全部都試試看,好不好,譬如說 不可能是這個例子,這個世界不是 KB的model,因為如果在這個世界的時候,你在這裡要感覺到BREEZE 那跟我們的KB不符,所以他不是KB的一個model,那其他的意思一樣,譬如你在這- 里的時候 應該要感覺到BREEZE,可是你在這邊perceive的是NONE 所以這是你的KB的model,就是全部你可以算出來,model of KB 然後之後我們對於α1,你再畫它所有的model,α1的model是這個樣 這四個,就是,這是model of α1,我們可以看到它多了一個world,就是這裡 這個也符合我們的α1的描述,α1描述是1,2沒有pit 那其實這邊是,α1這邊所有的就是這一個沒有 pit的世界,α1這四個點的,就是這個世界就是pit,那其他的這四個 那其他的這四個就是1,2有,有pit的 1,2有pit的世界,這就不屬於α1,那我們如果這樣畫出來, KB在這邊,KB的世界是這樣,α1的世界是這個樣子 那我們從這個圖上看到了什麼呢,就是 KB的model是α1的 我這邊應該,對不起,不好意思,大寫才對 要大寫,就所有的世界來說,只要KB為真的這些世界 是α1所為真的世界的子集 那根據entailment的定義,我們就知道,這就符合entailment的定義嘛- ,所以就是KB entail α1 好,這是它的定義,那同樣我們看一下α2,α2是說沒有pit 在2,2沒有pit,那我們就把剛剛八個世界裡面,2,2這一格 沒有pit的四個世界,就是屬於 and α2,好那KB的世界是這個樣 KB為真的世界是這個樣,那很明顯,KB為真的世界並 不是α為真的世界的子集,所以這個不成立 就是KB沒有entailα2,簡單講就是given 我們講的白話就是說,given我們現在的knowledge base,我們可以合理的inference應該可以導出來 α1是真,那它無法導出α2是真 這件事情很重要,就是我剛剛講的那句話的那個沒有很重要 我們這邊只能說KB沒有entail α2,可是你並不是說 KB entails ﹁α2,這兩件事是完全不同的,大家一定要注意 好,我們並沒有 就是這兩件事是不一樣的,我們這一件事是不知道的 我們還沒有去做,你可以去試試看,其實應該也沒有辦法entail這件事 以我們現在的knowledge base,大家可以玩玩看,應該也是做不到 當我們說KB不entailα2的意思只是說,given我們現在的knowledge- ,我們沒辦法 沒辦法確定 我想用證明這個字眼,可是證明牽扯到我們等下要講的inference 我們先用確定這個字眼好了,就是given我們現在的knowledge,我們沒辦法確定 α2是真的,但是這件事,你沒辦法確定α2是真的,但是不代表說你知道 α2是假的,可以嗎,應該可以理解嗎,就是我沒辦法證明你是對的,那當然不代表你是錯的 OK 這兩個有很明顯的分別,我們一定要分清楚 COURSERA.ORG/TAIWAN 台灣大學