一階邏輯基本概念-課件

第4章一階邏輯基本概念離散數(shù)學(xué)第4章一階邏輯基本概念離散數(shù)學(xué)本章說(shuō)明本章的主要內(nèi)容一階邏輯基本概念、命題符號(hào)化一階邏輯公式、解釋及分類(lèi)本章與后續(xù)各章的關(guān)系克服命題邏輯的局限性是第五章的先行準(zhǔn)備

2020/12/272本章說(shuō)明本章的主要內(nèi)容2020/12/272精品資料精品資料你怎么稱(chēng)呼老師？如果老師最后沒(méi)有總結(jié)一節(jié)課的重點(diǎn)的難點(diǎn)，你是否會(huì)認(rèn)為老師的教學(xué)方法需要改進(jìn)？你所經(jīng)歷的課堂，是講座式還是討論式？教師的教鞭“不怕太陽(yáng)曬，也不怕那風(fēng)雨狂，只怕先生罵我笨，沒(méi)有學(xué)問(wèn)無(wú)顏見(jiàn)爹娘……”“太陽(yáng)當(dāng)空照，花兒對(duì)我笑，小鳥(niǎo)說(shuō)早早早……”一階邏輯基本概念-ppt課件精品資料2020/12/275精品資料2020/12/275你怎么稱(chēng)呼老師？如果老師最后沒(méi)有總結(jié)一節(jié)課的重點(diǎn)的難點(diǎn)，你是否會(huì)認(rèn)為老師的教學(xué)方法需要改進(jìn)？你所經(jīng)歷的課堂，是講座式還是討論式？教師的教鞭“不怕太陽(yáng)曬，也不怕那風(fēng)雨狂，只怕先生罵我笨，沒(méi)有學(xué)問(wèn)無(wú)顏見(jiàn)爹娘……”“太陽(yáng)當(dāng)空照，花兒對(duì)我笑，小鳥(niǎo)說(shuō)早早早……”2020/12/2762020/12/276命題邏輯的缺陷

把命題看成是一個(gè)個(gè)孤立的命題，忽略了命題之間的聯(lián)系，不能反映某些重要的常見(jiàn)的邏輯思維過(guò)程。1.繁瑣例.

表述集合個(gè)體性質(zhì)及相互關(guān)系

S={1,2,…,50}表述S中所有元素都大于3這樣一個(gè)性質(zhì)，需要1>3,2>3,…,50>3等50個(gè)命題。2020/12/277命題邏輯的缺陷把命題看成是一個(gè)個(gè)孤立的命題，忽略了命題之2.不能描述命題間的邏輯聯(lián)系例如，邏輯學(xué)中著名的蘇格拉底三段論：

P：所有人必死

Q：蘇格拉底是人

R：蘇格拉底必死

表示為命題邏輯：應(yīng)該有(P

Q)

R，也就是公式(P

Q)

R應(yīng)該是恒真的。顯然該公式不是恒真的，解釋{P，Q，

R}就能弄假該公式。2020/12/2782.不能描述命題間的邏輯聯(lián)系2020/12/278原因：命題R和命題P,Q是有內(nèi)在關(guān)系的，只是這種關(guān)系在命題邏輯中無(wú)法表示。因此，需要對(duì)命題的成分、結(jié)構(gòu)和命題間的共同特性等作進(jìn)一步的分析，分析出個(gè)體詞、謂詞和量詞，以期達(dá)到表達(dá)出個(gè)體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系，這正是謂詞邏輯所要研究的問(wèn)題。2020/12/279原因：命題R和命題P,Q是有內(nèi)在關(guān)系的，只是這種關(guān)系在命題本章內(nèi)容4.1一階邏輯命題符號(hào)化4.2一階邏輯公式及解釋

本章小結(jié)

習(xí)題

作業(yè)2020/12/2710本章內(nèi)容4.1一階邏輯命題符號(hào)化2020/12/27104.1一階邏輯命題符號(hào)化一階邏輯命題符號(hào)化的三個(gè)基本要素個(gè)體詞謂詞量詞

2020/12/27114.1一階邏輯命題符號(hào)化一階邏輯命題符號(hào)化的三個(gè)基本要素2個(gè)體詞及相關(guān)概念個(gè)體詞一般是充當(dāng)陳述句主語(yǔ)的名詞或代詞說(shuō)明個(gè)體詞：指所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體。舉例命題：電子計(jì)算機(jī)是科學(xué)技術(shù)的工具。

個(gè)體詞：電子計(jì)算機(jī)。命題：他是三好學(xué)生。

個(gè)體詞：他。心物一元or心物二元？量子力學(xué)中的測(cè)不準(zhǔn)原理2020/12/2712個(gè)體詞及相關(guān)概念個(gè)體詞一般是充當(dāng)陳述句主語(yǔ)的名詞或代詞說(shuō)明個(gè)個(gè)體常項(xiàng)：表示具體或特定的客體的個(gè)體詞，用小寫(xiě)字母a,b,c，…表示。個(gè)體變項(xiàng)：表示抽象或泛指的客體的個(gè)體詞，用x,y,z,…表示。個(gè)體域（或稱(chēng)論域）：指?jìng)€(gè)體變項(xiàng)的取值范圍?？梢允怯懈F集合，如{a,b,c},{1,2}?？梢允菬o(wú)窮集合，如N,Z,R,…。全總個(gè)體域（universe）——由宇宙間一切事物組成。個(gè)體詞及相關(guān)概念本教材在論述或推理中，如果沒(méi)有指明所采用的個(gè)體域，都是使用的全總個(gè)體域。說(shuō)明2020/12/2713個(gè)體常項(xiàng)：表示具體或特定的客體的個(gè)體詞，用小寫(xiě)字母a,b,謂詞及相關(guān)概念謂詞（predicate）是用來(lái)刻畫(huà)個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞。(1)

是無(wú)理數(shù)。

是個(gè)體常項(xiàng)，“

是無(wú)理數(shù)”是謂詞，記為F，命題符號(hào)化為F(

)。(2)x是有理數(shù)。

x是個(gè)體變項(xiàng)，“

是有理數(shù)”是謂詞，記為G，命題符號(hào)化為G(x)。(3)小王與小李同歲。

小王、小李都是個(gè)體常項(xiàng)，“

與

同歲”是謂詞，記為H，命題符號(hào)化為H(a,b)，其中a：小王，b：小李。(4)x與y具有關(guān)系L。

x，y都是個(gè)體變項(xiàng)，謂詞為L(zhǎng)，命題符號(hào)化為L(zhǎng)(x,y)。2020/12/2714謂詞及相關(guān)概念謂詞（predicate）是用來(lái)刻畫(huà)個(gè)體詞性質(zhì)謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞。用大寫(xiě)字母表示。如(1)、

(2)、(3)中謂詞F、G、H。謂詞變項(xiàng)：表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞。用大寫(xiě)字母表示。如(4)中謂詞L。n(n1)元謂詞：P(x1,x2,…,xn)表示含n個(gè)個(gè)體變項(xiàng)的n元謂詞。n=1時(shí)，一元謂詞——表示x1具有性質(zhì)P。n≥2時(shí)，多元謂詞——表示x1,x2,…,xn具有關(guān)系P。0元謂詞：不含個(gè)體變項(xiàng)的謂詞。如F(a)、G(a,b)、P(a1,a2,…,an)。若F、G、P為謂詞常項(xiàng)，則上述0元謂詞為命題常項(xiàng)；若F、G、P為謂詞變項(xiàng)，則為命題變項(xiàng)。n元謂詞是命題嗎？不是，只有用謂詞常項(xiàng)取代P，用個(gè)體常項(xiàng)取代x1,x2,…,xn時(shí)，才能使n元謂詞變?yōu)槊}。思考謂詞及相關(guān)概念2020/12/2715謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞。用大寫(xiě)字母表示。如(1)謂詞的形式化定義設(shè)D是非空個(gè)體名稱(chēng)集合，定義在Dn上取值于{0，1}上的n元函數(shù)，稱(chēng)為n元命題函數(shù)或n元謂詞。其中Dn表示集合D的n次笛卡爾乘積。例：令G(x，y)：“x高于y”，G(x，y)是一個(gè)二元謂詞。將x代以個(gè)體“張三”，y代以個(gè)體“李四”，則G(張三，李四)就是命題：“張三高于李四”。G(x，y)不是命題，而是一個(gè)命題函數(shù)即謂詞。將x，y代以任意確定的個(gè)體，由G(x，y)都能得到一個(gè)命題。2020/12/2716謂詞的形式化定義設(shè)D是非空個(gè)體名稱(chēng)集合，定義在Dn上取值于{D={2,3,4}設(shè)P(x)：x大于3，則P(x)為一元謂詞。指定元素--命題：P(2)=0,P(3)=0,P(4)=1設(shè)P(x,y)：x大于y,則P(x,y)為二元謂詞。指定元素--命題：P(2,3)=0,P(4,2)=1設(shè)P(x,y,z)：若x+y-1=z，則P(x,y,z)為1，否則為0。則P(x,y,z)為三元謂詞。指定元素--命題：P(2,3,4)=1,P(4,2,2)=0例題2020/12/2717D={2,3,4}例題2020/12/2717例題將命題“這只大紅書(shū)柜擺滿(mǎn)了那些古書(shū)?！狈?hào)化.(1)設(shè) F(x,y)：x擺滿(mǎn)了y，R(x)：x是大紅書(shū)柜 Q(y)：y是古書(shū)， a：這個(gè)書(shū)柜 b：那些書(shū) 符號(hào)化為：R(a)∧Q(b)∧F(a,b)

(2)設(shè) A(x)：x是書(shū)柜， B(x)：x是大的

C(x)：x是紅的， D(y)：y是古老的

E(y)：y是圖書(shū)， F(x,y)：x擺滿(mǎn)了y a：這個(gè)東西 b：那些東西 符號(hào)化為：A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)2020/12/2718例題將命題“這只大紅書(shū)柜擺滿(mǎn)了那些古書(shū)?！狈?hào)化.2020/用謂詞的概念可將蘇格拉底三段論做如下的符號(hào)化：令

H(x)表示“x是人”，

M(x)表示“x必死”。則三段論的三個(gè)命題表示如下：

P：H(x)

M(x)

Q：H(蘇格拉底)

R：M(蘇格拉底)現(xiàn)在可以將蘇格拉底三段論符號(hào)化為…2020/12/2719用謂詞的概念可將蘇格拉底三段論做如下的符號(hào)化：令

H(x)令命題P為：所有人都會(huì)死，其否定命題為

P=

(H(x)

M(x))

=

(

H(x)

M(x))

=H(x)

M(x)亦即，命題P“所有人都會(huì)死”

的否定命題是“所有人都不會(huì)死”。這和人們對(duì)命題“所有人都必死”的否定的理解並不一致。但問(wèn)題是…2020/12/2720令命題P為：所有人都會(huì)死，其否定命題為但問(wèn)題是…2020原因——命題P的確切意思應(yīng)該是：“對(duì)任意x，如果x是人，則x必死”。但是

H(x)

M(x)

中并沒(méi)有確切的表示出“對(duì)任意x”這個(gè)意思，因此，在謂詞邏輯中除引進(jìn)謂詞外，還需要引進(jìn)“對(duì)任意x”這個(gè)語(yǔ)句，及其對(duì)偶的語(yǔ)句“存在一個(gè)x”。

2020/12/2721原因——命題P的確切意思應(yīng)該是：“對(duì)任意x，如果x是人，則量詞（quantifier）是表示個(gè)體常項(xiàng)或個(gè)體變項(xiàng)數(shù)量屬性的詞。1.全稱(chēng)量詞：符號(hào)化為“

”（All）日常生活和數(shù)學(xué)中所用的“一切的”、“所有的”、“每一個(gè)”、“任意的”、“凡”、“都”等詞可統(tǒng)稱(chēng)為全稱(chēng)量詞。x表示個(gè)體域里的某個(gè)個(gè)體，

xF(x)表示個(gè)體域里所有個(gè)體都有性質(zhì)F。2.存在量詞：符號(hào)化為“

”（Exist）日常生活和數(shù)學(xué)中所用的“存在”、“有一個(gè)”、“有的”、“至少有一個(gè)”等詞統(tǒng)稱(chēng)為存在量詞。y表示個(gè)體域里某個(gè)個(gè)體，

yG(y)表示個(gè)體域里存在個(gè)體y具有性質(zhì)G。量詞及相關(guān)概念2020/12/2722量詞（quantifier）是表示個(gè)體常項(xiàng)或個(gè)體變項(xiàng)數(shù)量屬性引入謂詞后，命題P就可確切地符號(hào)化如下：

x(H(x)

M(x))

命題P的否定命題為：

P=

(

x(H(x)

M(x)))

=

x(H(x)

M(x))

亦即“至少有一個(gè)人是不死的”。這個(gè)命題才是“所有人都要死”的否定。三段論的三個(gè)命題，在謂詞邏輯中可以如下表示：

P：

x(H(x)

M(x))

Q：H(蘇格拉底)

R：M(蘇格拉底)以后可以證明，在謂詞邏輯中，R是P和Q的邏輯結(jié)果。

2020/12/2723引入謂詞后，命題P就可確切地符號(hào)化如下： x(H(x)M例

符號(hào)化下述命題：（1）所有的老虎都要吃人；（2）每一個(gè)大學(xué)生都會(huì)說(shuō)英語(yǔ)；（3）所有的人都長(zhǎng)著黑頭發(fā)；（4）有一些人登上過(guò)月球；（5）有一些自然數(shù)是素?cái)?shù)。解

設(shè)有如下謂詞：P(x)：x會(huì)吃人；Q(x)：x會(huì)說(shuō)英語(yǔ)；R(x)：x長(zhǎng)著黑頭發(fā)；S(x)：x登上過(guò)月球；T(x)：x是素?cái)?shù)。（1）(

x)P(x) x∈{老虎}

；（2）(

x)Q(x) x∈{大學(xué)生}；（3）(

x)R(x) x∈{人}；（4）(

x)S(x) x∈{人}；（5）(

x)T(x) x∈{自然數(shù)}。2020/12/2724例符號(hào)化下述命題：解（1）(x)P(x) x∈{不便之處（1）從書(shū)寫(xiě)上十分不便，總要特別注明個(gè)體域；（2）在同一個(gè)比較復(fù)雜的句子中，不同命題函數(shù)中的個(gè)體可能屬于不同的個(gè)體域，此時(shí)無(wú)法清晰表達(dá)；如例(1)和(4)的合取

(

x)P(x)∧(

x)R(x)x∈{人}x∈{老虎}2020/12/2725不便之處（1）從書(shū)寫(xiě)上十分不便，總要特別注明個(gè)體域；x∈{人不便之處(續(xù))（3）若個(gè)體域的注明不清楚，將造成無(wú)法確定命題真值。即對(duì)于同一個(gè)n元謂詞，不同的個(gè)體域有可能帶來(lái)不同的真值。例如對(duì)于語(yǔ)句“(

x)(x+6=5)”可表示為：“有一些x，使得x+6=5”。該語(yǔ)句在下面兩種個(gè)體域下有不同的真值：

（a）在實(shí)數(shù)范圍內(nèi)時(shí)，確有x=-1使得x+6=5，因此，(

x)(x+6=5)為“真”；

（b）在正整數(shù)范圍內(nèi)時(shí)，則找不到任何x，使得x+6=5為“真”，所以，(

x)(x+6=5)為“假”。2020/12/2726不便之處(續(xù))（3）若個(gè)體域的注明不清楚，將造成無(wú)法確定命題不便之處的根源因?yàn)樾枰貏e標(biāo)注每個(gè)謂詞的個(gè)體域！全總個(gè)體域2020/12/2727不便之處的根源因?yàn)樾枰貏e標(biāo)注每個(gè)謂詞的個(gè)體域！全總個(gè)體域2特性謂詞新的問(wèn)題出現(xiàn)了，U(x)如何與(

x)P(x)，(

x)S(x)結(jié)合才符合邏輯呢？U(x)：x是老虎x∈｛老虎｝U(x)：x是人x∈｛人｝2020/12/2728特性謂詞新的問(wèn)題出現(xiàn)了，U(x)如何與(x)P(x)，(例將下面兩個(gè)命題符號(hào)化:(1)所有的老虎都會(huì)吃人。(2)有些人登上過(guò)月球。

特性謂詞的使用（1）令P(x)：x會(huì)吃人U(x)：x是老虎則符號(hào)化的正確形式應(yīng)該是 (

x)(U(x)→P(x))它的含義是：“對(duì)于任意的x,如果x是老虎，則x會(huì)吃人”，符合原命題的邏輯含義。

若符號(hào)化為

(

x)(U(x)∧P(x))

它的含義是：“對(duì)于任意的x,x是老虎，并且x會(huì)吃人”，與原命題“所有的老虎都要吃人”的邏輯含義不符。2020/12/2729例將下面兩個(gè)命題符號(hào)化:特性謂詞的使用（1）令P(x)（2）令S(x)：x登上過(guò)月球

U(x)：x是人則符號(hào)化的正確形式應(yīng)該是 (

x)(U(x)

∧

S(x))它的含義是：“存在x,x是人并且x登上過(guò)月球”，符合原命題的邏輯含義。

若符號(hào)化為

(

x)(U(x)→S(x))

它的含義是：“存在x,如果x是人，則x登上過(guò)月球”，與原命題“有人登上過(guò)月球”的邏輯含義似乎差不多……U(x)S(x)Universe2020/12/2730（2）令S(x)：x登上過(guò)月球 U(x)：x是人若謂詞邏輯符號(hào)化的規(guī)則若統(tǒng)一個(gè)體域?yàn)槿倐€(gè)體域，對(duì)每一個(gè)句子中個(gè)體變量的變化范圍用一元特性謂詞刻劃，這種特性謂詞在加入到命題函數(shù)中時(shí)必須遵循如下原則：（1）對(duì)于全稱(chēng)量詞(

x)，刻劃其對(duì)應(yīng)個(gè)體域的特性謂詞作為蘊(yùn)涵式之前件加入。（2）對(duì)于存在量詞(

x)，刻劃其對(duì)應(yīng)個(gè)體域的特性謂詞作為合取式之合取項(xiàng)加入。2020/12/2731謂詞邏輯符號(hào)化的規(guī)則若統(tǒng)一個(gè)體域?yàn)槿倐€(gè)體域，對(duì)每一個(gè)句子中例題用謂詞邏輯符號(hào)化下述語(yǔ)句：(1)天下烏鴉一般黑；(2)沒(méi)有人登上過(guò)木星；(3)在美國(guó)留學(xué)的學(xué)生未必都是亞洲人；(4)每個(gè)實(shí)數(shù)都存在比它大的另外的實(shí)數(shù)；(5)盡管有人很聰明，但未必一切人都聰明；(6)對(duì)于任意給定的

>0，必存在著

>0，使得對(duì)任意的x，只要|x-a|<

，就有|f(x)-f(a)|<

成立。2020/12/2732例題用謂詞邏輯符號(hào)化下述語(yǔ)句：2020/12/2732例題(續(xù))（1）天下烏鴉一般黑設(shè)F(x)：x是烏鴉；G(x,y)：x與y一般黑，則：

(

x)(

y)(F(x)∧F(y)→G(x,y))或者┐(

x)(

y)(F(x)∧F(y)∧┐G(x,y))；（2）沒(méi)有人登上過(guò)木星設(shè)H(x)：x是人；M(x)：x登上過(guò)木星，則：

┐(

x)(H(x)∧M(x))或者(

x)(H(x)→┐M(x))；2020/12/2733例題(續(xù))（1）天下烏鴉一般黑2020/12/2733例題(續(xù))（3）在美國(guó)留學(xué)的學(xué)生未必都是亞洲人設(shè)A(x)：x是亞洲人；H(x)：x是在美國(guó)留學(xué)的學(xué)生，則：

┐(

x)(H(x)→A(x))或者(

x)(H(x)∧┐A(x))；（4）每個(gè)實(shí)數(shù)都存在比它大的另外的實(shí)數(shù)設(shè)R(x)：x是實(shí)數(shù)；L(x,y)：x小于y，則：(

x)(R(x)→(

y)(R(y)∧L(x,y))；2020/12/2734例題(續(xù))（3）在美國(guó)留學(xué)的學(xué)生未必都是亞洲人2020/12例題(續(xù))（5）盡管有人很聰明，但未必一切人都聰明設(shè)M(x)：x是人；C(x)：x很聰明，則：

(

x)(M(x)∧C(x))∧┐(

x)(M(x)→C(x))；（6）對(duì)于任意給定的

>0，必存在著

>0，使得對(duì)任意的x，只要|x-a|<

，就有|f(x)-f(a)|<

成立。設(shè)個(gè)體域?yàn)閷?shí)數(shù)集合，則原命題可符號(hào)化為：(

)((

>0)→(

)((

>0)∧(

x)((|x-a|<

)→(|f(x)-f(a)|<

))))。2020/12/2735例題(續(xù))（5）盡管有人很聰明，但未必一切人都聰明2020/例題n元謂詞的符號(hào)化例4.5將下列命題符號(hào)化

（1）兔子比烏龜跑得快。

（2）有的兔子比所有的烏龜跑得快。

（3）并不是所有的兔子都比烏龜跑得快。

（4）不存在跑得同樣快的兩只兔子。解：令F(x):x是兔子，G(y):y是烏龜，

H(x,y):x比y跑得快，L(x,y):x與y跑得同樣快。（1）xy(F(x)∧G(y)

H(x,y))（2）x(F(x)∧y(G(y)

H(x,y)))（3）┐

xy(F(x)∧G(y)

H(x,y))（4）┐xy(F(x)∧F(y)∧L(x,y))2020/12/2736例題n元謂詞的符號(hào)化例4.5將下列命題符號(hào)化

（1）兔子一階邏輯命題符號(hào)化時(shí)需要注意的事項(xiàng)分析命題中表示性質(zhì)和關(guān)系的謂詞，分別符號(hào)化為一元和n（n2）元謂詞。根據(jù)命題的實(shí)際意義選用全稱(chēng)量詞或存在量詞。一般說(shuō)來(lái)，多個(gè)量詞出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換。例如，考慮個(gè)體域?yàn)閷?shí)數(shù)集，H(x，y)表示x+y=10，則命題“對(duì)于任意的x，都存在y，使得x+y=10”的符號(hào)化形式為

xyH(x,y)，為真命題。如果改變兩個(gè)量詞的順序，得y

xH(x,y)，為假命題。有些命題的符號(hào)化形式可不止一種。（例4.5之(3)）

xy(F(x)∧G(y)

H(x,y))xy(F(x)∧G(y)∧┐H(x,y))2020/12/2737一階邏輯命題符號(hào)化時(shí)需要注意的事項(xiàng)分析命題中表示性質(zhì)和關(guān)系的量詞的語(yǔ)義規(guī)定設(shè)G(x)是一元謂詞，任取x0

D，則G(x0)是一個(gè)命題。于是

xG(x)是這樣一個(gè)命題“對(duì)任意x

D，都有G(x)”。故對(duì)命題

xG(x)的真值做如下規(guī)定：

xG(x)取1值

對(duì)任意x

D，G(x)都取1值；

xG(x)取0值至少有一個(gè)x0

D，使G(x0)取0值。2020/12/2738量詞的語(yǔ)義規(guī)定設(shè)G(x)是一元謂詞，任取x0D，則G(x0

xG(x)是命題“存在一個(gè)x0

D，使得G(x0)成立”。對(duì)命題

xG(x)的真值規(guī)定如下：

xG(x)取1值至少有一個(gè)x0

D，使G(x0)取1值；

xG(x)取0值

對(duì)所有x

D，G(x)都取0值。語(yǔ)義上，當(dāng)D={x0,x1,…}是可數(shù)集合時(shí)，

xG(x)等價(jià)于G(x0)

G(x1)

…

xG(x)等價(jià)于G(x0)

G(x1)

…2020/12/2739xG(x)是命題“存在一個(gè)x0D，使得G(x0)成立”例.D={2，3，4}，P(x)：x>3

則

xP(x)等價(jià)于

P(2)

P(3)

P(4)所以其真值為0

0１＝0

xP(x)等價(jià)于P(2)

P(3)

P(4)所以其真值為0

0１＝１2020/12/2740例.D={2，3，4}，P(x)：x>32020/12/2課堂練習(xí)設(shè)個(gè)體域D={1，2，3}，P(x)：x>2。試判斷下列公式的真值：(1)

xP(x)

P(2)；(2)P(3)

xP(x).

xP(x)

P(2)等價(jià)于(P(1)

P(2)

P(3))

P(2)所以其真值為

(0

0

1)

0=1

0=0P(3)

xP(x)等價(jià)于1

(P(1)

P(2)

P(3))所以其真值為1

(0

0

1)=1

0=02020/12/2741課堂練習(xí)設(shè)個(gè)體域D={1，2，3}，P(x)：x>2。x課堂練習(xí)（續(xù)）設(shè)P(x)：x是素?cái)?shù)；I(x)：x是整數(shù)；Q(x,y)：x+y=0。用語(yǔ)句描述下述句子，并判斷其真假值。

（1）(

x)(I(x)→P(x))；（2）(

x)(I(x)∧P(x))；（3）(

x)(

y)(I(x)∧I(y)→Q(x,y))；（4）(

x)(I(x)→(

y)(I(y)∧Q(x,y)))；（5）(

x)(

y)(I(x)∧(I(y)→Q(x,y)))。2020/12/2742課堂練習(xí)（續(xù)）設(shè)P(x)：x是素?cái)?shù)；I(x)：x是整數(shù)；Q解句子(1)可描述為：“對(duì)任意的整數(shù)x，x一定是素?cái)?shù)”，真值為“假”；句子(2)可描述為：“存在一些整數(shù)x，x是素?cái)?shù)”，真值為“真”；句子(3)可描述為：“對(duì)任意的整數(shù)x，y，都有x+y=0”，真值為“假”；句子(4)可描述為：“對(duì)任意的整數(shù)x，都存在著整數(shù)y，使得x+y=0”，真值為“真”；句子(5)可描述為：“存在著整數(shù)x，使得對(duì)任意的整數(shù)y，都有x+y=0”，真值為“假”。2020/12/2743解句子(1)可描述為：“對(duì)任意的整數(shù)x，x一定是素?cái)?shù)”例符號(hào)化下述一組語(yǔ)句：只要是需要室外活動(dòng)的課，郝帥都喜歡；所有的公共體育課都是需要室外活動(dòng)的課；籃球是一門(mén)公共體育課；郝帥喜歡籃球這門(mén)課。解設(shè)O(x)：表示x是需要室外活動(dòng)的課；L(x,y)：表示x喜歡y；S(x)：表示x是一門(mén)公共體育課；Hao：表示郝帥；Ball：表示籃球。上述句子可符號(hào)化為：(

x)(O(x)→L(Hao,x))；(

x)(S(x)→O(x))；S(ball)；L(Hao,Ball)。2020/12/2744例符號(hào)化下述一組語(yǔ)句：上述句子可符號(hào)化為：2020/12/2例符號(hào)化下述一組語(yǔ)句：海關(guān)人員檢查每一個(gè)進(jìn)入本國(guó)的不重要人物；某些走私者進(jìn)入該國(guó)時(shí)僅僅被走私者所檢查；沒(méi)有一個(gè)走私者是重要人物；海關(guān)人員中的某些人是走私者。解設(shè)E(x)：表示x進(jìn)入國(guó)境；V(x)：表示x是重要人物；C(x)：表示x是海關(guān)人員；P(x)：表示x是走私者；B(x,y)：表示y檢查x。2020/12/2745例符號(hào)化下述一組語(yǔ)句：2020/12/2745解上述句子可符號(hào)化為：(

x)((E(x)∧┐V(x))→(

y)(C(y)∧B(x,y)))；(

x)(P(x)∧E(x)∧(

y)(B(x,y)→P(y)))；(

x)((P(x)→┐V(x))；(

x)(P(x)∧C(x))。2020/12/2746解上述句子可符號(hào)化為：2020/12/27464.2一階邏輯公式及解釋同在命題邏輯中一樣，為在一階邏輯中進(jìn)行演算和推理，必須給出一階邏輯中公式的抽象定義，以及它們的分類(lèi)及解釋。一階語(yǔ)言是用于一階邏輯的形式語(yǔ)言，而一階邏輯就是建立在一階語(yǔ)言基礎(chǔ)上的邏輯體系，一階語(yǔ)言本身不具備任何意義，但可以根據(jù)需要被解釋成具有某種含義。一階語(yǔ)言的形式是多種多樣的，本書(shū)給出的一階語(yǔ)言是便于將自然語(yǔ)言中的命題符號(hào)化的一階語(yǔ)言，記為F。2020/12/27474.2一階邏輯公式及解釋同在命題邏輯中一樣，為在一階邏輯中一階語(yǔ)言中的字母表定義4.1一階語(yǔ)言F的字母表定義如下:(1)個(gè)體常項(xiàng)：a,b,c,…,ai

,bi

,ci

,…,i

1(2)個(gè)體變項(xiàng)：x,y,z,…,xi

,yi

,zi

,…,i

1(3)函數(shù)符號(hào)：f,g,h,…,fi

,gi

,hi

,…,i

1；當(dāng)個(gè)體名稱(chēng)集合D給出時(shí)，n元函數(shù)符號(hào)f(x1，…，xn)可以是Dn到D的任意一個(gè)映射。(4)謂詞符號(hào)：F,G,H,…,Fi

,Gi

,Hi

,…,i

1；當(dāng)個(gè)體名稱(chēng)集合D給出時(shí)，n元謂詞符號(hào)P(x1，…，xn)可以是Dn上的任意一個(gè)謂詞，換言之，是Dn到｛0,1｝的任意一個(gè)映射。(5)量詞符號(hào):，

(6)聯(lián)結(jié)詞符號(hào):┐,∧,∨,→,

(7)括號(hào)與逗號(hào):(,),，2020/12/2748一階語(yǔ)言中的字母表定義4.1一階語(yǔ)言F的字母表定義如下:2為何需要函數(shù)符號(hào)？例如符號(hào)化“周紅的父親是教授”：設(shè)f(x)：x的父親；P(x)：x是教授；c：周紅此時(shí)P(f(c))表示“周紅的父親是教授”這一命題。函數(shù)的使用給謂詞邏輯中的個(gè)體詞表示帶來(lái)了很大的方便否則就需要引入二元謂詞g(x,y):x是y的父親，符號(hào)化為：P(x)∧g(x,c)，不如函數(shù)簡(jiǎn)單明了。2020/12/2749為何需要函數(shù)符號(hào)？例如符號(hào)化“周紅的父親是教授”：函數(shù)的一階語(yǔ)言中的項(xiàng)定義4.2一階語(yǔ)言F的項(xiàng)的定義如下:(1)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng)。(2)若

(x1,x2,…,xn)是任意的n元函數(shù)，t1,t2,…,tn是任意的n個(gè)項(xiàng)，則

(t1,t2,…,tn)是項(xiàng)。(3)所有的項(xiàng)都是有限次使用(1)，(2)得到的。2020/12/2750一階語(yǔ)言中的項(xiàng)定義4.2一階語(yǔ)言F的項(xiàng)的定義如下:202一階語(yǔ)言中的原子公式定義4.3設(shè)R(x1,x2,…,xn)是一階語(yǔ)言F的任意n元謂詞，t1,t2,…,tn是一階語(yǔ)言F的任意的n個(gè)項(xiàng)，則稱(chēng)R(t1,t2,…,tn)是一階語(yǔ)言F的原子公式。例如：1元謂詞F(x)，G(x)，2元謂詞H(x,y)，L(x,y)等都是原子公式。2020/12/2751一階語(yǔ)言中的原子公式定義4.3設(shè)R(x1,x2,…,一階語(yǔ)言F的合式公式定義4.4一階語(yǔ)言F的合式公式(well-formedformula)定義如下:(1)原子公式是合式公式。(2)若A是合式公式，則(┐A)也是合式公式。(3)若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(A

B)

也是合式公式。(4)若A是合式公式，則

xA，

xA也是合式公式。(5)只有有限次的應(yīng)用(1)～(4)構(gòu)成的符號(hào)串才是合式公式。

一階語(yǔ)言F的合式公式也稱(chēng)為謂詞公式，簡(jiǎn)稱(chēng)公式。A，B代表任意公式，是元語(yǔ)言符號(hào)。下文的討論都是在一階語(yǔ)言F中，因而不再提及。說(shuō)明2020/12/2752一階語(yǔ)言F的合式公式定義4.4一階語(yǔ)言F的合式公式(w自由出現(xiàn)與約束出現(xiàn)定義4.5指導(dǎo)變?cè)?、轄域、約束出現(xiàn)、自由出現(xiàn)在公式

xA和

xA中，稱(chēng)x為指導(dǎo)變?cè)?。在公?/p>

xA和

xA中，A為相應(yīng)量詞的轄域。在

x和

x的轄域中，x的所有出現(xiàn)都稱(chēng)為約束出現(xiàn)。A中不是約束出現(xiàn)的其他個(gè)體變項(xiàng)均稱(chēng)為是自由出現(xiàn)的。量詞轄域的確定方法：（1）若量詞后有括號(hào)，則括號(hào)內(nèi)的子公式就是該量詞的轄域；（2）若量詞后無(wú)括號(hào)，則與量詞鄰接的子公式為該量詞的轄域。2020/12/2753自由出現(xiàn)與約束出現(xiàn)定義4.5指導(dǎo)變?cè)?、轄域、約束出現(xiàn)、自例確定以下公式各量詞的轄域以及各個(gè)體變量為自由變?cè)€是約束變?cè)＃?）(

x)(P(x)→(

y)R(x,y))；（2）(

x)P(x)∧Q(x,y)；（3）(

x)(

y)(P(y,z)∨Q(x,y))∧(

x)R(x,y)；（4）(

x)(P(x)→R(x))∧(

y)Q(x,y)。2020/12/2754例確定以下公式各量詞的轄域以及各個(gè)體變量為自由變?cè)€是約束變解在(1)中，P(x)中的x，R(x,y)的x，y都為約束變?cè)?。?2)中，P(x)中的x為約束變?cè)?，Q(x,y)中的x，y是自由變?cè)?。?3)中，P(y,z)、Q(x,y)中的x,y都為約束變?cè)?，z為自由變?cè)?；R(x,y)中的x為約束變?cè)?，y為自由變?cè)?。?4)中，P(x)，R(x)中的x為約束變?cè)琎(x,y)中的x為自由變?cè)?、y為約束變?cè)?020/12/2755解在(1)中，P(x)中的x，R(x,y)的x，y都為變?cè)煜?）(

x)(P(x)→R(x))∧(

y)Q(x,y)約束變?cè)杂勺冊(cè)谝粋€(gè)公式中，某一個(gè)變?cè)某霈F(xiàn)既可以是自由的，又可以是約束的，如(4)中的x。為了使得我們的研究更方便，而不致引起混淆，同時(shí)為了使公式給人以一目了然的結(jié)果，對(duì)于表示不同意思的個(gè)體變?cè)?，我們總是以不同的變量符?hào)來(lái)表示。2020/12/2756變?cè)煜?）(x)(P(x)→R(x))∧(y)Q(x改名規(guī)則約束變?cè)母拿?guī)則（1）將量詞中出現(xiàn)的變?cè)约霸摿吭~轄域中此變量的所有約束出現(xiàn)都用新的個(gè)體變?cè)鎿Q；（2）新的變?cè)獞?yīng)有別于公式中的所有其它變量。2020/12/2757改名規(guī)則約束變?cè)母拿?guī)則2020/12/2757代入規(guī)則自由變?cè)拇胍?guī)則（1）將公式中出現(xiàn)該自由變?cè)拿恳惶幎加眯碌膫€(gè)體變?cè)鎿Q；（2）新變?cè)辉试S在原公式中以任何約束形式出現(xiàn)。2020/12/2758代入規(guī)則自由變?cè)拇胍?guī)則2020/12/2758例（1）將公式(

x)(P(x)→Q(x,y))∧R(x,y)中的約束變?cè)獂進(jìn)行改名；（2）將公式(

x)(P(x)→Q(x,y))∧R(x,y)中的約束變?cè)獃進(jìn)行代入。解利用改名規(guī)則對(duì)x進(jìn)行改名，則：

(

z)(P(z)→Q(z,y))∧R(x,y)

(

z)(P(z)→R(x,y))∧R(x,y)(

y)(P(y)→R(y,y))∧R(x,y)

-------對(duì)

-------錯(cuò)

-------錯(cuò)利用代入規(guī)則對(duì)y進(jìn)行代入，則：

(

x)(P(x)→Q(x,z))∧R(x,z)

(

x)(P(x)→Q(x,z))∧R(x,y)

(

x)(P(x)→Q(x,x))∧R(x,x)

------對(duì)

------錯(cuò)

------錯(cuò)2020/12/2759例（1）將公式(x)(P(x)→Q(x,y))∧R(x,改名規(guī)則和代入規(guī)則的關(guān)系改名規(guī)則和代入規(guī)則之間的共同點(diǎn)都是不能改變?cè)械募s束關(guān)系，而不同點(diǎn)是：（1）施行的對(duì)象不同：改名規(guī)則是對(duì)約束變?cè)┬?，代入?guī)則是對(duì)自由變?cè)┬?；?）施行的范圍不同：改名規(guī)則可以只對(duì)公式中的一個(gè)量詞及其轄域內(nèi)施行，即只對(duì)公式的一個(gè)子公式施行；而代入規(guī)則必須對(duì)整個(gè)公式同一個(gè)自由變?cè)乃凶杂沙霈F(xiàn)同時(shí)施行，即必須對(duì)整個(gè)公式施行；2020/12/2760改名規(guī)則和代入規(guī)則的關(guān)系改名規(guī)則和代入規(guī)則之間的共同點(diǎn)都是不改名規(guī)則和代入規(guī)則的關(guān)系（續(xù)）（3）施行后的結(jié)果不同：改名后，公式含義不變，因?yàn)榧s束變?cè)桓拿麨榱硪粋€(gè)個(gè)體變?cè)?，約束關(guān)系不改變，約束變?cè)荒芨拿麨閭€(gè)體常量；代入后，不僅可用另一個(gè)個(gè)體變?cè)M(jìn)行代入，并且也可用個(gè)體常量去代入，從而使公式由具有普遍意義變?yōu)閮H對(duì)該個(gè)體常量有意義，即公式的含義改變了。2020/12/2761改名規(guī)則和代入規(guī)則的關(guān)系（續(xù)）（3）施行后的結(jié)果不同：改名后封閉的公式定義4.6設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個(gè)體變項(xiàng)，則稱(chēng)A為封閉的公式，簡(jiǎn)稱(chēng)閉式。例如：

x

y(F(x)

G(y)

H(x,y))為閉式，

x(F(x)

G(x,y))不是閉式。一階公式的解釋一階公式?jīng)]有確定的意義，一旦將其中的變項(xiàng)（項(xiàng)的變項(xiàng)<亦即個(gè)體變項(xiàng)、函數(shù)變項(xiàng)>、謂詞變項(xiàng)）用指定的常項(xiàng)代替后，所得公式就具備一定的意義，有時(shí)就變成命題了。2020/12/2762封閉的公式定義4.6設(shè)A是任意的公式，若A中不含有自由出現(xiàn)一階公式的解釋定義4.7一階公式的解釋I由下面4部分組成:(a)非空個(gè)體域DI。(b)DI中一些特定元素的集合。(c)DI上特定函數(shù)集合{|i,n≥1}。(d)DI上特定謂詞的集合{|i,n≥1}。2020/12/2763一階公式的解釋定義4.7一階公式的解釋I由下面4部分組成A中的第i個(gè)n元函數(shù)變項(xiàng)被解釋為某個(gè)函數(shù)常項(xiàng)A中的第i個(gè)n元謂詞變項(xiàng)被解釋成某個(gè)謂詞常項(xiàng)對(duì)解釋I的幾點(diǎn)說(shuō)明被解釋的公式不一定全部包含解釋中的四個(gè)部分。被解釋的公式A中的個(gè)體變項(xiàng)均取值于DI。A中的個(gè)體常項(xiàng)ai被解釋成。在解釋的定義中引進(jìn)了幾個(gè)元語(yǔ)言符號(hào)，如2020/12/2764A中的第i個(gè)n元函數(shù)變項(xiàng)被解釋為某個(gè)函數(shù)常項(xiàng)A中的第i給定解釋I如下：

(a)個(gè)體域D=R(b)(c)(d)寫(xiě)出下列公式在I下的解釋,并指出它的真值.(1)

xF(f(x,a),g(x,a))例

x(x+0=x0)真(2)

x

y(F(f(x,y),g(x,y))F(x,y))

x

y(x+y=x

y

x=y)假(3)

xF(g(x,y),a)

x(x

y=0)真值不定,不是命題定理4.1封閉的公式在任何解釋下都變成命題。

2020/12/2765給定解釋I如下：例x(x+0=x0)一階公式的分類(lèi)定義4.8永真式、永假式、可滿(mǎn)足式設(shè)A為一個(gè)公式，若A在任何解釋下均為真，則稱(chēng)A為永真式(或稱(chēng)邏輯有效式)。設(shè)A為一個(gè)公式，若A在任何解釋下均為假，則稱(chēng)A為矛盾式(或永假式)。設(shè)A為一個(gè)公式，若至少存在一個(gè)解釋使A為真，則稱(chēng)A為可滿(mǎn)足式。永真式一定是可滿(mǎn)足式，但可滿(mǎn)足式不一定是永真式。在一階邏輯中，到目前為止，還沒(méi)有找到一種可行的算法，用來(lái)判斷任意一個(gè)公式是否是可滿(mǎn)足的，這與命題邏輯的情況完全不同。但對(duì)某些特殊的公式還是可以判斷的。說(shuō)明2020/12/2766一階公式的分類(lèi)定義4.8永真式、永假式、可滿(mǎn)足式永真式一謂詞公式的可判定性（1）謂詞邏輯公式是不可判定的；（2）只含有一元謂詞變項(xiàng)的公式是可判定的；（3）如下形式的公式：

(

x1)(

x2)…(

xn)P(x1,x2,…,xn)，(

x1)(

x2)…(

xn)P(x1,x2,…,xn)。若P中無(wú)量詞和其它自由變?cè)獣r(shí)，也是可判定的；（4）個(gè)體域有窮時(shí)的謂詞公式是可判定的。2020/12/2767謂詞公式的可判定性（1）謂詞邏輯公式是不可判定的；2020/謂詞邏輯中公式恒真、恒假性的判斷異常困難。原因：謂詞邏輯中的恒真(恒假)公式，要求所有解釋I都滿(mǎn)足(弄假)該公式。而解釋I依賴(lài)于一個(gè)非空集合D。由于集合D可以是無(wú)窮集合，而集合D的“數(shù)目”也可能是無(wú)窮多個(gè)。因此，所謂公式的“所有”解釋?zhuān)瑢?shí)際上是無(wú)法考慮的。1936年Church和Turing分別獨(dú)立地證明了：對(duì)于謂詞邏輯，判定問(wèn)題是不可解的。謂詞邏輯是半可判定的：如果謂詞邏輯中的公式是恒真的，則有算法在有限步之內(nèi)檢驗(yàn)出這個(gè)公式的恒真性。如果該公式不是恒真的(當(dāng)然也不是恒假的)，則無(wú)法在有限步內(nèi)判定這個(gè)事實(shí)。謂詞邏輯公式的判定問(wèn)題

2020/12/2768謂詞邏輯中公式恒真、恒假性的判斷異常困難。謂詞邏輯公式的判定英國(guó)天才數(shù)學(xué)家、計(jì)算機(jī)科學(xué)家圖靈(AlanMathisonTuring,1912-1954)在孩提時(shí)代就對(duì)化學(xué)和機(jī)械著迷,做過(guò)大量化學(xué)實(shí)驗(yàn)。1931年,獲得了劍橋大學(xué)皇家學(xué)院的獎(jiǎng)學(xué)金。在完成畢業(yè)論文后，被選為該學(xué)院的成員。在畢業(yè)論文中，發(fā)現(xiàn)了統(tǒng)計(jì)學(xué)中的一個(gè)著名定理—中心極限定理。1935年，對(duì)判定問(wèn)題著了迷，這是偉大的德國(guó)數(shù)學(xué)家希爾伯特提出的一個(gè)問(wèn)題：是否有一個(gè)能用于判斷任何命題是否為真的一般方法。2020/12/2769英國(guó)天才數(shù)學(xué)家、計(jì)算機(jī)科學(xué)家圖靈(AlanMathison圖靈喜歡跑步，一天，在跑步之后的休息中，發(fā)現(xiàn)了解決判定問(wèn)題的關(guān)鍵思想。在他的解決方案中，他發(fā)明了今天稱(chēng)為圖靈機(jī)的計(jì)算模型，并用它作為計(jì)算機(jī)器的最一般模型。利用這個(gè)機(jī)器，發(fā)現(xiàn)了一個(gè)不能用一般方法判定的問(wèn)題，也就是停機(jī)問(wèn)題。通俗的說(shuō)，停機(jī)問(wèn)題就是判斷任意一個(gè)程序是否會(huì)在有限的時(shí)間之內(nèi)結(jié)束運(yùn)行的問(wèn)題。從1936年到1938年，圖靈在普林斯頓大學(xué)訪(fǎng)問(wèn)，與丘奇(AlonzeChurch)一起工作，丘奇也獨(dú)立解決了希爾伯特提出的判定問(wèn)題。2020/12/2770圖靈喜歡跑步，一天，在跑步之后的休息中，發(fā)現(xiàn)了解決判定問(wèn)題的停機(jī)問(wèn)題不存在這樣一個(gè)程序（算法），它能夠計(jì)算任何程序（算法）在給定輸入上是否會(huì)結(jié)束（停機(jī)）。證明：反證法。假設(shè)我們真做出了這么一個(gè)極度聰明的萬(wàn)能算法（就叫God_algo吧），只要給它一段程序（二進(jìn)制描述），再給它這段程序的輸入，它就能告訴你這段程序在這個(gè)輸入上會(huì)不會(huì)結(jié)束（停機(jī)）boolGod_algo(char*program,char*input){ if(<program>haltson<input>) returntrue; returnfalse;}2020/12/2771停機(jī)問(wèn)題不存在這樣一個(gè)程序（算法），它能夠計(jì)算任何程序（算法boolSatan_algo(char*program){ if(God_algo(program,program)) { while(1);//loopforever! returnfalse;//cannevergethere! } else returntrue;}2020/12/2772boolSatan_algo(char*program)Satan_algo(Satan_algo);顯然，這個(gè)函數(shù)調(diào)用要么能夠結(jié)束，要么不能結(jié)束。如果它能夠結(jié)束，那么Santa_algo算法里面的那個(gè)if判斷就會(huì)成立（因?yàn)镚od_algo(Santa_algo,Santa_algo)將會(huì)返回true），從而進(jìn)入一個(gè)無(wú)窮循環(huán)（while(1);），從而函數(shù)調(diào)用Satan_algo(Satan_algo)就永遠(yuǎn)不會(huì)結(jié)束。而如果它不能結(jié)束，則if判斷就會(huì)失敗，從而跳過(guò)那個(gè)while(1)返回true，即我們調(diào)用Satan_algo(Satan_algo)又能夠結(jié)束?？傊?，Satan_algo(Satan_algo)能夠停機(jī)=>它不能停機(jī)。Satan_algo(Satan_algo)不能停機(jī)=>它能夠停機(jī)。所以它停也不是，不停也不是。得出矛盾。于是，我們的假設(shè)，God_algo算法的存在性不成立。2020/12/2773Satan_algo(Satan_algo);2020/12為現(xiàn)代人工智能做出巨大貢獻(xiàn)的圖靈在理論上奠定了計(jì)算機(jī)產(chǎn)生的基礎(chǔ)。對(duì)于計(jì)算機(jī)人士而言，獲得圖靈獎(jiǎng)就等于物理學(xué)家獲得諾貝爾獎(jiǎng)一樣。圖靈測(cè)試：圖靈認(rèn)為如果機(jī)器能成功的偽裝成人欺騙觀察者，那么就認(rèn)為它具有了智能。

由計(jì)算機(jī)、被測(cè)試的人和主持試驗(yàn)人組成。計(jì)算機(jī)和被測(cè)試的人分別在兩個(gè)不同的房間里。測(cè)試過(guò)程由主持人提問(wèn)，由計(jì)算機(jī)和被測(cè)試的人分別做出回答。觀測(cè)者能通過(guò)電傳打字機(jī)與機(jī)器和人聯(lián)系。被測(cè)人在回答問(wèn)題時(shí)盡可能表明他是一個(gè)“真正的”人，而計(jì)算機(jī)也將盡可能逼真的模仿人的思維方式和思維過(guò)程。如果試驗(yàn)主持人聽(tīng)取他們各自的答案后，分辨不清哪個(gè)是人回答的，哪個(gè)是機(jī)器回答的，則可以認(rèn)為該計(jì)算機(jī)具有了智能。這是一種行為主義的思想，如今看來(lái)并不正確。圖靈測(cè)試的重要意義：使實(shí)驗(yàn)研究智能行為成為可能。2020/12/2774為現(xiàn)代人工智能做出巨大貢獻(xiàn)的圖靈在理論上奠定了計(jì)算機(jī)產(chǎn)生的基在1939年，圖靈回到皇家學(xué)院。在第二次世界大戰(zhàn)爆發(fā)期間，他進(jìn)入了英國(guó)外交部，從事對(duì)德國(guó)密碼的分析工作。他對(duì)破譯機(jī)械的德國(guó)密碼機(jī)Enigma的密碼作出了重要貢獻(xiàn)，在贏得這次戰(zhàn)爭(zhēng)中起到了重要作用。1954年，圖靈服氰化物自殺，沒(méi)有留下遺言作明確解釋。（事實(shí)上可能與圖靈是同性戀有關(guān)，圖靈因此被化學(xué)去勢(shì)。）此外，圖靈具有典型的荒島心態(tài)——來(lái)源于《魯濱遜漂流記》——亦即盡可能的自行制造所需的一切，譬如肥皂等，甚至連圖靈自殺的氰化鉀都是自己提煉的。）2020/12/2775在1939年，圖靈回到皇家學(xué)院。在第二次世界大戰(zhàn)爆發(fā)期間，他丘奇丘奇(AlonzeChurch，1903-1995)出生于華盛頓特區(qū)。曾在哥廷根跟隨希爾伯特學(xué)習(xí)，后來(lái)轉(zhuǎn)到阿姆斯特丹。從1927年到1967，執(zhí)教于普林斯頓大學(xué)1967年調(diào)到加州大學(xué)洛衫磯分校(UCLA)。是符號(hào)邏輯學(xué)會(huì)(AssociationofSymbolicLogic)的創(chuàng)始人。對(duì)可計(jì)算性理論作出了實(shí)質(zhì)性的貢獻(xiàn)，其中包括對(duì)判定問(wèn)題的解、演算的發(fā)明，以及對(duì)現(xiàn)今稱(chēng)為丘奇—圖靈論題的陳述。在90歲生日后還發(fā)表文章。2020/12/2776丘奇丘奇(AlonzeChurch，1903-19代換實(shí)例定義4.9設(shè)A0是含有命題變項(xiàng)p1,p2,…,pn的命題公式，A1,A2