一階邏輯基本概念-課件

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

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

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

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

S={1,2,…,50}表述S中所有元素都大于3這樣一個性質(zhì)，需要1>3,2>3,…,50>3等50個命題。2020/12/277命題邏輯的缺陷把命題看成是一個個孤立的命題，忽略了命題之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)系在命題邏輯中無法表示。因此，需要對命題的成分、結(jié)構(gòu)和命題間的共同特性等作進一步的分析，分析出個體詞、謂詞和量詞，以期達到表達出個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系，這正是謂詞邏輯所要研究的問題。2020/12/279原因：命題R和命題P,Q是有內(nèi)在關(guān)系的，只是這種關(guān)系在命題本章內(nèi)容4.1一階邏輯命題符號化4.2一階邏輯公式及解釋

本章小結(jié)

習(xí)題

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

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

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

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

是無理數(shù)。

是個體常項，“

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

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

x是個體變項，“

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

小王、小李都是個體常項，“

與

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

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

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

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

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

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

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

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

P：H(x)

M(x)

Q：H(蘇格拉底)

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

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

P=

(H(x)

M(x))

=

(

H(x)

M(x))

=H(x)

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

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

H(x)

M(x)

中并沒有確切的表示出“對任意x”這個意思，因此，在謂詞邏輯中除引進謂詞外，還需要引進“對任意x”這個語句，及其對偶的語句“存在一個x”。

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

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

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

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

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

x(H(x)

M(x))

命題P的否定命題為：

P=

(

x(H(x)

M(x)))

=

x(H(x)

M(x))

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

P：

x(H(x)

M(x))

Q：H(蘇格拉底)

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

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

符號化下述命題：（1）所有的老虎都要吃人；（2）每一個大學(xué)生都會說英語；（3）所有的人都長著黑頭發(fā)；（4）有一些人登上過月球；（5）有一些自然數(shù)是素數(shù)。解

設(shè)有如下謂詞：P(x)：x會吃人；Q(x)：x會說英語；R(x)：x長著黑頭發(fā)；S(x)：x登上過月球；T(x)：x是素數(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例符號化下述命題：解（1）(x)P(x) x∈{不便之處（1）從書寫上十分不便，總要特別注明個體域；（2）在同一個比較復(fù)雜的句子中，不同命題函數(shù)中的個體可能屬于不同的個體域，此時無法清晰表達；如例(1)和(4)的合取

(

x)P(x)∧(

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

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

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

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

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

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

x)P(x)，(

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

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

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

若符號化為

(

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

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

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

x)(U(x)

∧

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

若符號化為

(

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

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

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

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

>0，必存在著

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

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

成立。2020/12/2732例題用謂詞邏輯符號化下述語句：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）沒有人登上過木星設(shè)H(x)：x是人；M(x)：x登上過木星，則：

┐(

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

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

┐(

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

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

x)(R(x)→(

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

(

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

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

>0，必存在著

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

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

成立。設(shè)個體域為實數(shù)集合，則原命題可符號化為：(

)((

>0)→(

)((

>0)∧(

x)((|x-a|<

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

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

（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元謂詞的符號化例4.5將下列命題符號化

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

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

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

xy(F(x)∧G(y)

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

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

xG(x)是這樣一個命題“對任意x

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

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

xG(x)取1值

對任意x

D，G(x)都取1值；

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

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

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

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

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

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

D，使G(x0)取1值；

xG(x)取0值

對所有x

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

xG(x)等價于G(x0)

G(x1)

…

xG(x)等價于G(x0)

G(x1)

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

則

xP(x)等價于

P(2)

P(3)

P(4)所以其真值為0

0１＝0

xP(x)等價于P(2)

P(3)

P(4)所以其真值為0

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

xP(x)

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

xP(x).

xP(x)

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

P(2)

P(3))

P(2)所以其真值為

(0

0

1)

0=1

0=0P(3)

xP(x)等價于1

(P(1)

P(2)

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

(0

0

1)=1

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

（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是素數(shù)；I(x)：x是整數(shù)；Q解句子(1)可描述為：“對任意的整數(shù)x，x一定是素數(shù)”，真值為“假”；句子(2)可描述為：“存在一些整數(shù)x，x是素數(shù)”，真值為“真”；句子(3)可描述為：“對任意的整數(shù)x，y，都有x+y=0”，真值為“假”；句子(4)可描述為：“對任意的整數(shù)x，都存在著整數(shù)y，使得x+y=0”，真值為“真”；句子(5)可描述為：“存在著整數(shù)x，使得對任意的整數(shù)y，都有x+y=0”，真值為“假”。2020/12/2743解句子(1)可描述為：“對任意的整數(shù)x，x一定是素數(shù)”例符號化下述一組語句：只要是需要室外活動的課，郝帥都喜歡；所有的公共體育課都是需要室外活動的課；籃球是一門公共體育課；郝帥喜歡籃球這門課。解設(shè)O(x)：表示x是需要室外活動的課；L(x,y)：表示x喜歡y；S(x)：表示x是一門公共體育課；Hao：表示郝帥；Ball：表示籃球。上述句子可符號化為：(

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

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

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

,bi

,ci

,…,i

1(2)個體變項：x,y,z,…,xi

,yi

,zi

,…,i

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

,gi

,hi

,…,i

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

,Gi

,Hi

,…,i

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

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

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

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

(t1,t2,…,tn)是項。(3)所有的項都是有限次使用(1)，(2)得到的。2020/12/2750一階語言中的項定義4.2一階語言F的項的定義如下:202一階語言中的原子公式定義4.3設(shè)R(x1,x2,…,xn)是一階語言F的任意n元謂詞，t1,t2,…,tn是一階語言F的任意的n個項，則稱R(t1,t2,…,tn)是一階語言F的原子公式。例如：1元謂詞F(x)，G(x)，2元謂詞H(x,y)，L(x,y)等都是原子公式。2020/12/2751一階語言中的原子公式定義4.3設(shè)R(x1,x2,…,一階語言F的合式公式定義4.4一階語言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)成的符號串才是合式公式。

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

xA和

xA中，稱x為指導(dǎo)變元。在公式

xA和

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

x和

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

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例確定以下公式各量詞的轄域以及各個體變量為自由變元還是約束變解在(1)中，P(x)中的x，R(x,y)的x，y都為約束變元。在(2)中，P(x)中的x為約束變元，Q(x,y)中的x，y是自由變元。在(3)中，P(y,z)、Q(x,y)中的x,y都為約束變元，z為自由變元；R(x,y)中的x為約束變元，y為自由變元。在(4)中，P(x)，R(x)中的x為約束變元，Q(x,y)中的x為自由變元、y為約束變元。2020/12/2755解在(1)中，P(x)中的x，R(x,y)的x，y都為變元混淆（4）(

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

y)Q(x,y)約束變元自由變元在一個公式中，某一個變元的出現(xiàn)既可以是自由的，又可以是約束的，如(4)中的x。為了使得我們的研究更方便，而不致引起混淆，同時為了使公式給人以一目了然的結(jié)果，對于表示不同意思的個體變元，我們總是以不同的變量符號來表示。2020/12/2756變元混淆（4）(x)(P(x)→R(x))∧(y)Q(x改名規(guī)則約束變元的改名規(guī)則（1）將量詞中出現(xiàn)的變元以及該量詞轄域中此變量的所有約束出現(xiàn)都用新的個體變元替換；（2）新的變元應(yīng)有別于公式中的所有其它變量。2020/12/2757改名規(guī)則約束變元的改名規(guī)則2020/12/2757代入規(guī)則自由變元的代入規(guī)則（1）將公式中出現(xiàn)該自由變元的每一處都用新的個體變元替換；（2）新變元不允許在原公式中以任何約束形式出現(xiàn)。2020/12/2758代入規(guī)則自由變元的代入規(guī)則2020/12/2758例（1）將公式(

x)(P(x)→Q(x,y))∧R(x,y)中的約束變元x進行改名；（2）將公式(

x)(P(x)→Q(x,y))∧R(x,y)中的約束變元y進行代入。解利用改名規(guī)則對x進行改名，則：

(

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)

-------對

-------錯

-------錯利用代入規(guī)則對y進行代入，則：

(

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)

------對

------錯

------錯2020/12/2759例（1）將公式(x)(P(x)→Q(x,y))∧R(x,改名規(guī)則和代入規(guī)則的關(guān)系改名規(guī)則和代入規(guī)則之間的共同點都是不能改變原有的約束關(guān)系，而不同點是：（1）施行的對象不同：改名規(guī)則是對約束變元施行，代入規(guī)則是對自由變元施行；（2）施行的范圍不同：改名規(guī)則可以只對公式中的一個量詞及其轄域內(nèi)施行，即只對公式的一個子公式施行；而代入規(guī)則必須對整個公式同一個自由變元的所有自由出現(xiàn)同時施行，即必須對整個公式施行；2020/12/2760改名規(guī)則和代入規(guī)則的關(guān)系改名規(guī)則和代入規(guī)則之間的共同點都是不改名規(guī)則和代入規(guī)則的關(guān)系（續(xù)）（3）施行后的結(jié)果不同：改名后，公式含義不變，因為約束變元只改名為另一個個體變元，約束關(guān)系不改變，約束變元不能改名為個體常量；代入后，不僅可用另一個個體變元進行代入，并且也可用個體常量去代入，從而使公式由具有普遍意義變?yōu)閮H對該個體常量有意義，即公式的含義改變了。2020/12/2761改名規(guī)則和代入規(guī)則的關(guān)系（續(xù)）（3）施行后的結(jié)果不同：改名后封閉的公式定義4.6設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個體變項，則稱A為封閉的公式，簡稱閉式。例如：

x

y(F(x)

G(y)

H(x,y))為閉式，

x(F(x)

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

(a)個體域D=R(b)(c)(d)寫出下列公式在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)一階公式的分類定義4.8永真式、永假式、可滿足式設(shè)A為一個公式，若A在任何解釋下均為真，則稱A為永真式(或稱邏輯有效式)。設(shè)A為一個公式，若A在任何解釋下均為假，則稱A為矛盾式(或永假式)。設(shè)A為一個公式，若至少存在一個解釋使A為真，則稱A為可滿足式。永真式一定是可滿足式，但可滿足式不一定是永真式。在一階邏輯中，到目前為止，還沒有找到一種可行的算法，用來判斷任意一個公式是否是可滿足的，這與命題邏輯的情況完全不同。但對某些特殊的公式還是可以判斷的。說明2020/12/2766一階公式的分類定義4.8永真式、永假式、可滿足式永真式一謂詞公式的可判定性（1）謂詞邏輯公式是不可判定的；（2）只含有一元謂詞變項的公式是可判定的；（3）如下形式的公式：

(

x1)(

x2)…(

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

x1)(

x2)…(

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

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

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