本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
7-1 First-Order Logic (i) - Syntax of FOL and Semantics
Loading...
From the course by National Taiwan University
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
154 ratings
From the lesson
First Order Logic
Meet the Instructors
于天立副教授 (Associate Professor)
電機工程學系 (Department of Electrical Engineering)
好大家好，上一講我們講了Logic中最基本的一種Propositional Logic
那它的sound inference是可以又既sound又complete
但是它的表達能力是比較有限的。那今天我們要講的是它的進階版，First-Order Logic，那它基本上
能夠表達大部分我們現實生活中的大部分的事物，好，那今天我們也會順便提到就是
AI界裡面很常用的一種語言，叫Prolog，那它裡面的大部分的一些演繹 是一種First-Order Logic的
一個subset，那我們也會提到它的做法以及這個語言本身的用處。
好，首先我們會提First-Order Logic它的語法還有語義， 然後我們也會先提及它怎麼利用First-Order Logic
來描述我們日常生活想要表達一些 一些語句。那接下來我們要談的就是它的inference，那First-Order Logic
這部分對應的是AIMA課本的大概第八章，8.2,8.3這附近，
那第二部分這個inference就是利用First-Order Logic來推論出我們想要證明的正確的東西，那這個
部分是相對於課本第九章的地方。那我們首先會先提instantiation這個技巧- ，那利用
instantiation讓把First-Order Logic裡面的quantifier就是∃還有∀
這種quantifier，把它拿掉使得First-Order Logic整個knowledge base可以整個
reduce回propositional logic，那這個技術 稱為propositionalization，好，那如果可以這樣做的話那我們所有
上一講所提到在propositional logic所提到的各種inference的技巧包含resolution，forwa-
rd，backward chaining 都一樣大致上可以適用。好那這樣的做法有，等一下也會提到它有些效率上的issue。
所以在First-Order Logic我們另外一種做法是直接用First-Order Logic的一些推導方法，
那裡面我們會，首先會介紹一個First-Order Logic裡面很重要的概念叫unification，那就是試著找出一個
替代法，使得左右兩邊式子的變數替換完以後它們長得一模一樣，
好這個概念叫unification。那利用這個unification技術我們同樣就- 可以做到forward以及backward chaining，
那接下來我們會一樣介紹resolution，就是既sound又complete的技巧- ，那同時我們會提到prolog programming這個部分。
好，First-Order Logic呢在跟propositional logic
不一樣的主要地方在於它introduce進一個概念，就是除了object- 之外，它分成
relation還有function這兩個概念其實在propositional logic是比較沒有的，
那當然了，就是relation和function這兩個東西其實如果有修過離散數- 學的同學
大概可以知道，它們有一些蠻有趣的觀點，就是relation呢基本上描述的範圍
比function大，但是所有relation的背後你可以用一個characteristic
function我們稱為特徵函式 來描述這個relation，那在這個First-Order Logic
的話基本上它都，我們都可以定， 就是它讓使用者有這個能力去定義relation以及function，例如說
我們可以定義譬如說，如果我說father是個relation的話，那 它就是一個true or false的東西，譬如說我說
Mark是David的爸爸, 好，那這個東西就是一個true or
false，這個relation它就take兩個object，然後它的output- 就是一個
true orfalse。 這樣的東西，那這樣我們稱為一個relation。那當然同時我們也可以用-
function的概念，那如果以function來講的話， 那我如果把father定義成一個function的話，那它input就是一個
物件，那它其實它的輸出呢這個東西其實就是Mark。
好這是以function的方式來定義我想要講的東西。
好那其實就是either，我就是relation能定義的東西更廣，就是functi- on它需要一個one to one的一個mapping，那
relation沒有規定一定要這個樣子，那當然我們在 First-Order Logic
寫這些事情的時候一樣，就是只有，這句話意義就是我們人類賦予它的， 那logic本身它不care這些東西。
好，那在First-Order Logic syntax來說，它有定義一些，它新加入了一個概念叫variable，
就是一個變數，那constant這個東西是我們在propositional logic就已經存在了，就是我們
上一講提到任何像P呀，Q呀這一類proposition 它本身都是OK， 那它分成就是constant和variable，那variable是一個變數，就是-
它的像這邊寫的a,b,x,y它都可以 是任意的東西，任意的告訴我們可以定下來是某個constant等等。
好，那我們有function，那又所謂predicate，那predicate相對- 應的就是用來描述relation，
好就是relation它是一個比較數學上的用語，那如果我們用First-Order Logic的時候
我們把這個字眼稱為predicate，好，那接下來我們可以把這些東西去做一些鏈結， 那用的方法就跟propositional logic
是一樣的，就是包含了and or not、imply還有就是if and only if就是
A imply B，B imply A的雙箭頭等等。好，那有一個是 比較不一樣的，我指出來的跟propositional logic比較不一樣的包含
這邊還有，因為你現在有變數了，所以我們希望有一個辦法去測說某兩個東西是相等，好 ，這是有，增加了一個這個symbol，
就是equal，像我剛剛寫的，David的爸爸是Mark，這樣的話。
那就是我就可以利用這種東西，Father......那Mark=David，這樣的話我們需要 equal這個symbol
那我們也可以equal也可以同時說是如果有兩個變數我們也可以這樣講，
然後讓它們兩個bind在一起。那還有一個還蠻不一樣的地方是
quantifier，quantifier其實就兩個，那分別是這個symbol代表- 了for all
那這個symbol代表了存在，exist，
OK，那它的symbol其實也蠻好記的，其實是exist，就是
E的左右相反，然後另外一個for all的話就是A的
上下相反這個樣子，那這些symbol大家應該不陌生，在集合論上我們是使用一樣的sy- mbol。
好，quantifier的用法其實蠻有趣的，就是
基本上它就是一個，它的語義就是我剛剛講的一個，一個是存在，一個是for all，
那只是在實際上用quantifier來描述現實世界的一些
狀況的時候我們常常用的是，就是你對for all常常我們需要配的是imply，
常常，這不能百分之百保證，然後另外一個就是用exist通常我們所用的是and。
好，那這個是一個一般情況。 但是也就是說如果你真的知道自己在幹甚麼的話你當然可以不要這樣用。
但是通常我們要描述的情況是for all上是要配imply的，我們看一下下面的一個句子。
好，例如說上面這一個來講的話，如果我們想要講說ok在台大NTU的每個人
都很聰明，那我們講用for all嘛，就對所有的人，只要這個人在 NTU裡面，像這個in就是一個predicate，predicates，那它描述一
個relation， 就是x在NTU這裡，它就true or false，那然後我們就代表了它是smart。
OK，這是我們通常我們想要講的句子。
那如果你今天不小心用了and的話，它完全是，這個語句本身還是
valid的，它還是一個合法的邏輯式子，但是 通常你要表達語義就不太一樣，如果你用and的話你代表是說
所有的人都在NTU裡面，就是這一塊
for all x嘛，就是所有人都在NTU而且，
你對所有的人呢，所有的人都很聰明，就變成你.....你講兩句話， 就變成說所有人都在台大而且所有人都很聰明。
那跟你原本要講的台大的人都很聰明是不太一樣的。
好，那另外一個例子如果我們要講說，在台大裡面至少有一個人是聰明的。
如果我們要這樣講的話也就someone in NTU is smart,那通常你要用的就是存在一個x嘛，然後你用的通常是and，
好，就是你存在一個，你至少存在一個人他在NTU，而且這個人 它是聰明的。所以你通常用的是and，如果你這邊不小心用了
imply的話那你的語句就變了，你的意思就變成說， 因為這個imply大家應該記得，就是它是
如果A implies B，大家還有印象嗎？它其實就是not A or B,
它其實這兩個是完全全等的，那其實我可以把下面這句話改一下， 就是not，就是前面，也就是not這個東西，
我現在在寫的是這一個， OK，其實，這一句話如果你用imply的話那全等於
上面這一句話，那其實這句話，下面這句要true的時候呢，
就是前面的前提是false，或者後面是true，永遠都是true.也就說
即使都沒有人在台大，只要全世界有一個人他是聰明的，這句話就成立。
這句話就是true，那同樣，就是或是全部都沒有人在...... 沒有任何人在台大，這種情況下就全世界都沒有人是聰明的，你這整句話還是true。
OK，就是這一個為true或是這個為true，就是這句話。
只要有一個人聰明，你整句話就為true，或是所有的人都不在台大，那也是為true， 那說我們根本不用care，有沒有人聰明，好，那跟你原來想要講說，
台大有某人是聰明的，可能這個語義上是完全就不太一樣的事情。好，所以這個是golden rule，
就是一般來說，你用這個會使用imply，那你用存在的時候，會使用and，那這是一般 的情況。
那quantifiers可能大家常用，但它的一些特性，可能大家比較少接觸，
那我這邊簡單講一下，那有幾個它們服務和交換，那交換率如果在
for all和for all的話，它是同樣的，就是你
for all x再for all y，那相當於for all y再for all x，好，這個是一樣的。那同樣的存在是一樣的，就是存在，存在x再存在y，
和存在y再存在x，就這兩句話本身沒有任何的語義上的任何的分別。
那for all再存在呢，這個in general，
在大部分情況下，是不能交換的，就是我們這邊寫的， 如果，就是這兩個，譬如說我們看一下上面這一句，
好，如果說，存在x，然後for all y loves (x，y)，那假設我說love這個
predicate它imply的意思是說x love y， 就是我們人類賦予它的語義，那這樣的話，其實我們上面這一句話講的是說，
有一個人，然後他愛所有的人，就神愛世人，有一個x，那這個x愛所有的y，
ok，所有的y，那這是上面這一句話的意思。那如果下面你把它反過來，你把 你把存在和for all
把它反過來的話，那你就是對所有的y，都存在一個人愛你。
ok，這就是，就是因為是x在前面嘛，就是x loves y，那就是說，每一個人其實
都被某人所喜愛的，而且這個被某人所喜愛的這一個one person不需要是同一個人，
他當然可以是同一個人，但是他不需要，可以對每一個y，他都有不同的一個x 喜歡他，那這兩句話的語義，我想一般來說是完全不一樣的。
好，那quantifier還有一個duality的特性，就是我們其實大概都知道，
就是它的not，就是De Morgan也可以直接用，就是它的not，就是存在 存在和不for all
和又基本上是duality， 它是差不多equivalent的，但是後面句子要反過來，也就是說，我們看一下下面這-
個句子，如果我們說， 這句話大家應該可以猜得出來，意思大概是說，所有的人都喜歡吃冰淇淋，
前面這句話就for all x嘛，然後x喜歡冰淇淋， 那其實我們換白話講，就是下面和一句話是equivalent，意思就是說
不存在不喜歡吃冰淇淋的人，ok，這是後面這句話的意思，那應該可以，大家應該
也判斷這兩句話，原則上是一樣的。那同樣的，對存在也是，如果我說 有人喜歡讀書，就存在至少一個人
喜歡讀書，那意思就是，並不是所有的人都不喜歡讀書，
這種話我們在日常生活也常講啦，就是，雙重否定嘛，就是基本上就等於肯定。
115 好所以這基本上這邊，我們式子這邊已經在講De Morgan，
這其實就是De Morgan apply到quantifier的情況，
由De Morgan，當你把not往裡縮的時候， 我們在propositional logic講的是
and要變or嘛，然後or要變and，那同樣，就是exist要變for all，for all要變exist，大致上是這個樣子。
其實用First-Order logic來描述世界上的事情
有很多小陷阱，就是說你是第一次使用的話，可能要稍微注意一下， 譬如說我們講，這個是我們想表達的英文，
就natural language的語句，說 John has two brothers, Mark and David.
ok，好，那這句話在日常生活很常用，其實在這個例子，我們也可以看出， 我們自然語言有多麼的強烈，自然語言算是一個，因為我們在講自然語言的時候，
包含了很多我們的common knowledge，包含了很多，好，譬如說
我們在講這一句話，那我們看一下，我們可以很容易寫出來，你說ok，那就是Mark是- John的brother，而且John跟David是brother，
好，聽起來好像ok了，但是這句話，我寫的這個邏輯式子到底有沒有完整的表達 我上面這一句英文，好，其實並沒有，對不對，因為
上面這一個，這個邏輯是只說了Mark跟John是brother，然後David跟- John是brother，
可是你不知道還有沒有人跟John是brother，那上面這一個英文呢， 講的很清楚，就是John has two brother.
他沒有三個，他沒有四個，好，這是我們natural language 的一個假設，就是，當我講說他有兩個的時候，我們並不assume他還有，可以有更多個，
好，exactly就是那兩位，我們必須要寫說， 他們John跟David和Mark都是brother，而且只要任何，只要
for all x， 只要John跟他，這個x是brother的情況下，x不是Mark
就是David。也就是說他有兩個brother，也只有兩個brother。
好，這樣搞定了嗎？那really，因為在first-order logic的情況下，
它並沒有假設不同的constant是不同的人，也就是說你並沒有講清楚，
Mark跟David不是同一個人，他可以是同一個人，有兩個名字，而在這個自然語言，我- 們是不會這樣認為
所以說我們可能還要再寫清楚一點，就是ok，而且Mark跟David不同，那當然你說再清- 楚一點，你可能還要再寫
John跟Mark跟David他們也是不同人，但是這個看你要怎麼定義啦， 就是你可以在brother那邊定義，就是說brother如果他們是同一個人，他們本-
身brother這個predicate就可以return false。
好，這個例子是想跟大家講，就是用first-order logic來描述
現實生活中的事情，其實是做得到，它有這個能力去描述，但是還是有很多地方要小心，然後
然後自然語言其實裡面語義，我們再回想一下，我們自然語言常常，因為我們有很多 background knowledge
所以其實我們有時候講很簡短的話，但是它有很多的意思，當然，邏輯- 有好處就是，
你這些意思不會就是定義下來，就定下來了，它只有字面上的意思，我們不用多做解釋， 但是自然語言，我們可能要根據每個人不同的knowledge，
不同的背景知識，有時候對不同的人，對同一句話，有時候會有不同的解釋。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
