基本上 Database Semantics 講，又做三個假設。 第一個假設叫做 Closed-World，Closed-World 是意思就是說，所有沒有提的就全都是錯的。 我們進入 user，我們打一下，譬如說， 我假設說，我已知的我的是 a 到 b 有連接，然後 b 到 c 有個連線。 這是我們自己想的。 好這邊我們就結束了，好那你 listing 也 ok。 它就是，因為這都是常數，所以基本上你就只能都這個樣，它不會替換因為沒有變數。 好，那如果我問它 譬如說，c 跟 a 之間有沒有，有沒有連接。 那這個其實我們沒有在我們的 database 裡面 它其實應該是不知道的。 但它，但在 database mantics裡面，就是你沒有講的就是沒有 ok，所以它的回答是 no。 它會很明確，你沒有跟我講 c 跟 a 之間有連線，那就是沒有。 ok 這是第一個叫做 Closed- World 的假設。 那第二個假設叫做 Unique-names。 就是在我們講 [iii]的時候我們一開始就講到，就是說，我們講 John 有兩個 brother，是 Mark and David，那我們還要特別，在 FOL 裡面，你必須要，還要特別聲明， John 跟 Mark and David，這三個名字所代表的人都是不一樣的。 它並沒有特別說不一樣的名字就是不一樣。 那 在 Database mantic 裡面只要不一樣的名字就是不同。 譬如說我們會很容易的知道，如果 a 等於 c，那它就會跟你說不。 我還要知道 a 跟 c 這兩個，你用不同的名字，那就是不同的東西。 就這樣。 那最後有一個就是 是叫做 Domain Closure。 也就是說，你只要在 [iii] base 裡面，你沒有，被你選到的任何，不管是常數，或是 function，只要 你沒有提到的它都不存在。 好，這是最後一個，Domain Closure。 好。 那如果我們透漏使用 Database 裡面 Semantics 的話，那有很多，就可以把它講的很簡單。 你比如說它polo，裡面講說，OK 我們有 4 門課，那是，分別是 在美國，基本上課程我們都是這樣定，（CS,101）,那 101 通常是一個最基礎的課程，出國去唸書的同學大家都知道。 那假設我們還有一個課，課號是（CS,102）,那（CS,106）,還有一個（EE,- 101）。 那 這是，用 Prolog 寫的話你就直接這樣寫就可以了，那就是代表這 4 個為 True，哪個在，在事件中 就只有這 4 個。 那如果用 FOL 來寫的話，其實還蠻複雜的。 因為你必須要講說 [iii] 就這 4 門課嘛，對不對，那你要講 at most 4 門， 而且要，最，也就 at least 4 門課。 所以你必須要寫說，類似這樣，如果有 Couse（d，n），那就 imply 了 代表 [iii] 它就是（CS,101），或是（CS,102），或者 （EE,101）。 那接下來這是 at most。 接下來你還要說 就，就是至少有這 4 門課，也就是說，你還要說等於 如果 x = y，那就是代表了，要，要，x 必須是 CS 和 y 是 CS,就是，你要說，他們必須都是一樣的。 然後 102 要和 102 106 和 106 一樣。 這些都是你用 FOL 裡面所要定，因為你沒有所謂 不同的名字代表的，不同的東西。 好那我們，提過了 forward chaining 以及 backward chaining，那我們，最後再來提我們在[iii]上所 [iii]第一個講的 resolution。 那 resolution 一樣在 FOL 是可以使用的。 那 那它基本上一樣要，因為有變數的關係，一樣一樣要走 substitution，那如果你找到UNIFY，使得 某兩個 clause 裡面的 [iii]他們互為一個 complement 的關係的話，那你就可以使用。 譬如說如果我們這句話 說，ok，就是，有錢人都不快樂。 這個這個當然不一定是真實的事情，它只是給你舉個例子，那我們又知道 Ken 是有錢的。 那我們可以利用 UNIFY 的方法去 UNIFY 這兩個 部分。 那你可以 UNIFY 出來 x 其實就是 Ken。 這個 substitution。 那你就可以得到，結果就是 Unhappy（x） x 用 Ken 來替換。 好這就是一樣的東西，是 resolution。 那你要使用 resolution 的時候，那你所使用的就是，額， 你用，你先把整個邏輯式都轉為 CNF，[iii]。 然後，之後你要做的事情就是 KB 而且你不要的那個結論，就是 反證法嘛，矛盾證法，那，你就說，而且，不要那個結論的話呢，你可以導出矛盾的結果。 好那我們 forward chaining 和 backward chaining 呢就只能使用在 FOL裡面[iii]clause。 那它不是整個 FOL 的全部，它只是一個小小的 subject。 那resolution 的話呢可以 apply 在 FOL。 那基本上是 complete 的。 那，不過我們要提一下它 complete 其實rotation of complete。 就是如果是不對的，它是可以說出不對的。 那我們先看一下 我們怎麼把，任何一個式子轉成 CNF。 其實很單純，那我們 [iii]它跟 [iii] 差不多只是有多了一些變數的問題，我們看一下怎麼處理。 譬如說我們這裡舉個例子 這個語義是說，任何人，他只要喜歡，所有的動物它都被某人所喜愛。 好那我們寫下這樣的邏輯式，把它寫成這樣，就是只要 ∀y，y 是個 animal。 然後， 就 imply，我們講 y for all 的話，你要用，你要配合這個 imply，那這個 x 就 喜歡 y，就是喜歡所有動物的這個人。 那對所有這樣的 x，這樣的人呢，都會存在 一個 y，這個 y 跟前面的 animal 當然就不一樣，存在存在一個人，相當於一個y，那個 y love x。 好這是我們上面的這個英文的邏輯式，用 CNF 給大家寫的翻譯。 好。 那第一件事情我們要先把，要變 CNF 的第一件事情就是要把這個 CNF 裡面沒有的這個 implication，或是你如果是雙箭頭。 如果你有雙箭頭的話就是先把它變成兩個單箭頭。 就是 A 和 B 全等就把它改寫成 A imply B，B imply A，好先把它改掉。 改的方法就是 A imply B 就改成 [iii]A or B。 ok。 那你改掉後的這個式子變這一句 那這一句的話接下來就是你要把 ﹃ 引進來，就是把 [iii]引進來，那 如果對，針對於他們的[iii]，就是 for all 的話，你就 ﹃ for all 存在，﹃存在。 你就改成 for all。 那你就可以吧 ﹃ 引進來，這是我們之前就舉過這些例子了。 我們就可以看到，這邊就是你如果把 用這個把 ﹃ 引進來然後就變成一個 double negation，那 double negation 我們再同樣 apply 這個 double negation 的這個 rule。 就是雙重否定就等於肯定。 你們就可以把 ﹃ 都引進 [iii]的裡面，你自己再[iii]外面。 好經過這個第二個步驟以後，那是我就得到 [iii]本身，接下來我們要做的就是 [iii]那個 variable，因為我們 在處理 variable 要小心，我們剛剛有講過我們在原式裡面我們有兩個 y，第一個 y 是指某個 animal。 那第二個 y 指的是 someone，love，who loves x，所以這兩個 y 其實是不一樣的，那我們應該 應該把它分開。 我們又有新的一個，新的一個 variable z 好，那在處理變數的時候，我們接下來要是，就是套 u，uy 我們就是要留著，所以我們接下來 變數，希望處理到最後所有的變數都是 for all，那和我們[iii]需要處理。 那存在這個東西我們需要處理。 那存在我們是需要替換 Ey，但是當 這邊要換的是我們之前提過的 Skolem variable，但是如果你要配合上 另外一個變數的時候，其實我們所需要的是 Skolem function。 為什麼呢因為像這個地方對於 你如果 z 你用只替換一個[iii] 的話，那等於說你是說某一個固定的 人他[iii] 這樣的 x，那這是不對的語義嘛。 那我們在語義 的時候說熱愛動物的這樣人都會被某人所喜歡，那這個 不需要是同一個人就是針對不同的 x，他有一個相對應喜歡的 x 的這個人。 所以我們，我使用這個，我們稱為 Skolem function。 就是我們定的這個 G（x），就是會這樣 喜歡 x 的這一個人。 那同樣，這邊 animal 我們也是類似的做法。 好，就是被 x 所喜歡的 animal，好那我們就定為 F。 那這個 F 和 G 都是我們裡面都是大寫的。 當然指的就是常數。 好那接下來我們 Ei 已經搞定了麼，就 Ei 就是說我的 existence 我們就是全都把它換成 Skolem function 之後，那剩下的 variable 就是全都是 universally quantified for all。 那既然是 for all 我們就可以把所有的 for all 全部都抓捕掉。 好那我們就得到這一個式子。 好那現在就只剩下最後一步，就是我們要，已經要，既然在這個式子已經都所有的 ﹃ 都只，直接跟在 [iii]的前面，而且所有的 for all 和 iii 全部都已經被丟掉了，那隻剩下最後一步就是 end all，只要把它改成 CNF，那你就利用 交換結合這些分配率，你把它換回 CNF 的過程。 好那這個部分就跟 [iii] 提到的一模一樣。 好接下來，那這樣你就得到一個完整的 CNF 的一個邏輯式子。 那我們看一下 resolution 的，resolution 應用在 FOL 其實跟 [iii] 是一樣的。 就是一樣，就是，差別只是你用的是一個比較簡單的 resolution，就是你不是 existed complete，但是你是要找到 UNIFY 的使得這個 clause 裡面的[iii]可以是，互為反述就可以了。 那我們看一下用這個東西怎麼來證明，那個 [iii] 是有罪的怎麼來證明。 那我要證明他有罪首先你就是假設他無罪 那我們希望找到矛盾，那這個矛盾一定要是一個 [iii]。 在這種情況下，我們把它 highlight 出來，這個出題的其實就是可以被 UNIFY 的。 你要 UNIFY [iii]，那你得到的結果 x 就是[iii]。 好那你得到 x 等於[iii]的時候，你就可以把這兩個拿掉，這兩個一起拿掉，那接下來這是你kb，那- 這是你知道的。 東西就是West American，那你這邊一樣，這兩個互為 Compliment就可以拿掉，那這邊的，你說y、 那它Weapon(y)跟Weapon(x)，那你能做到就是x是y， 好是y的話就可以。 然後，接下來我們又可以，這個一樣，Missle(M1)跟 跟Missle(y)，我可以只要y是M1，這兩個就可以拿掉，你依照這個步驟一直做下- 去，那你最後就可以得到， 得到一個Ø，那Ø的意思就是說原句就是整個KB ︿α， α是我們想要得到的結論，它是[iii]viable的，也就是代表了 KB entail α，好，也就等於說你只要得到這個Ø clause就代表了你已經證明了，呃，[iii] 是有罪的。 那他其實 resolution是蠻強力的一個證明法，它在propositional logic的時候，我們有說過它sound and complete， 呃，他的sound 當然還是一樣，就是沒有，沒有什麼變化，那他 在first order logic 裡面一樣是complete，但是這個我們通常會 會加一個名詞叫作refutational，就是refutational complete。 就是如果是拒絕的話， 是complete的。 原因當然很明顯，因為我們講過first order logic 裡面的entailment，它是semi-decidable 也就是說如果是yes，對，那你可以說， 對，但是，如果是no的話，你沒辦法在有限的時間內，知道它是no，這沒辦法。 這是已經被證明做不到的事情。 好，那，refutation complete的意思就是說，反正， 原句 KB ︿ α 它如果是unsatisfiable的話，那它是， 可以在有限的時間內跟你說，導出Ø clause。 那如果不是，也就是說如果，我不知道KB有沒有，如果原本KB其實不entail α的話，你要找到結論，那， resolution可以一直做，做不完，就這樣，而且沒辦法知道， 沒辦法知道結論，那這是沒有辦法的事。 好那它，呃，我們課本如果，對於resolution證明其實有簡單的描述，那它其- 實描述的 也就大致上就是這個樣子。 也就是說，其實它真正證明的重點就是，如果， 我有就這邊S當然就是，這邊S當然一樣，就是KB︿α， 如果我想要導入整個，整個sentence，它如果是 unsatisfiable的話，那，只要你在有限的 resolution的步驟內，你應該可以導得出， Ø clause，它證明的形式就是這樣子。 那這個其實，證明其實，呼應到之前我們提過，就是， 你在 propositionalize，我們在一個first order logic 的 knowledge base，我們可以做propositionalize 嘛，那其實是類似 的，如果，如果你可以entail α 的話，我可以在有限 的步驟內，就是你 propositionalize 可以到無窮大，但是又基本上又不需要，你在有限的一個subset 我就應該可以找到KB entail α，這是可以被證明的。 也就，這是呼應的，也就是說我在用resolution的過程中， 我只要apply有限，有限的步驟，應該就可以證明KB entail α。 那當然如果KB不entail α的話，那這是沒有辦法的事。 好，那，總結我們這一講，我們整個針對的就是在邏輯上我們把它推廣 從 propositional logic 我們推廣到first order logic的時候怎麼做，那first order logic可以 很容易描述現實生活中的所有問題，所以它的應用範圍非常廣。 那針對first order logic的話，首先，第一個， 如果你的懂面不大的話，也就是說你的，整個世界，已知的concern是不大的情況下， 你的確可以直接用UI還有EI把這些concern全部換完，然後你可以把一個first order logic的 knowledge base換成一個，propositional 的logic base，那我們之前在上一講，所提到，說forward-chaining， backward-chaining以及，resolution都可以直接apply。 那如果不行的話，如果你懂的面非常大的話，那這樣做會很沒效率。 那我們就可以用first order logic的做法：那首先有一個概念就是unification，那unifica- tion 做的事就是，找到一個正確的substitution，使得左邊等於右邊。 好，那，如果你，我們只， focus在first order logic的一個比較小的subset，就是definite clause的話，那我們可以直接用，generalized Modus Ponens 那這裡面就是，給前提得到結論嘛，那我們一樣可以使用forward-chaining- ，backward-chaining的技術。 那，generalized Modus Ponens基本上complete的，當然也上那個complete在definite clause上面。 那，那當然entailment本身它是semi-decidable的，那我們有提- 過，那， 在，如果你是一個Datalog，就是如果你沒有function，沒有functio- n的definite clause的話，那， 其實在P-time也是可以搞定的，那我們，因為提過嘛，就是你要無窮的，一直，你會，- 一直沒辦法， 決定下來，是因為你有function的情況下，你function可以無窮地，一直套- 上去，譬如說這樣的，發展的發展的發的 使得你的 object 有無窮多個。 所以你沒辦法在有限的時間內套完。 但是你如果沒有function的時候，就沒有這樣的問題的， object 其實能替換的，有限。 那，呃，所以你在P-time裡面可以做完。 好，那backward chaining呢，在logic program裡面會常被用的，譬如說像 [iii]system裡面它基本上， 呃，是，可以蠻快的。 它為了效率，那它， 沒有去省略accurate check，所以它的導入結論可能unsound，那因為用DFS 是記憶體，所以它的導入結論也可能是incomplete。 但是即使，它可能是unsound又complete的，但是它在大部分我們所需要、 所使用的， 問題上，大部分都可以work得不錯，好這是，那效率非常非常好。 那這是一個[iii]，一些犧牲 一些正確性。 有些時候會給你不正確，但是得到很大部分的效能的提升。 那最後就是，如果， 你如果沒有那麼care效能的話，那你可以使用resolution，那其實上的又是c- omplete，那在 first order logic， 那當然要做一件事情，你要先把你的knowledge base換成整個 [iii] normal form，那之後我們就可以用resolution把它證完。 那以上是這一整講的內容。 以上我們AI的課程到此告一段落，謝謝各位同學的參與。 課程中我們簡單介紹了，有關 search還有logic上的技巧，而人工智慧裡面還有很多其他部分，由其他，與 新倫理有密不可分的關係。 那相關的內容，大家可以參考課本、 網路，或是自行到 coursera上搜尋相關課程，做 進一步的學習。 而大家如果對本課程有任何的想法與建議，歡迎大家在coursera的討論區提出，和我- 們分享，謝謝。 [音樂] [音樂] [音樂]
