謂詞

1、第四章:一階謂詞邏輯,第一節(jié)：一階邏輯命題符號(hào)化 第二節(jié)：一階邏輯公式及其解釋,第四章:一階謂詞邏輯,主要內(nèi)容一階邏輯命題符號(hào)化 個(gè)體詞、謂詞、量詞 一階邏輯命題符號(hào)化一階邏輯公式及其解釋 一階語(yǔ)言 合式公式 合式公式的解釋 永真式、矛盾式、可滿足式,第四章:一階謂詞邏輯,第一節(jié)：一階邏輯命題符號(hào)化 第二節(jié)：一階邏輯公式及其解釋,4.1 一階邏輯命題符號(hào)化,命

2、題邏輯的表示能力缺陷命題演算的基本單元為簡(jiǎn)單命題不能研究命題的結(jié)構(gòu)、成分和內(nèi)部邏輯的特征不能表達(dá)二個(gè)原子命題所具有的共同特征，無(wú)法處理一些簡(jiǎn)單又常見(jiàn)的推理例子凡是人都要死 p?q蘇格拉底是人 r推出：蘇格拉底要死？,,,命題之間的聯(lián)系無(wú)法刻畫(huà),4.1 一階邏輯命題符號(hào)化,謂詞邏輯對(duì)命題做進(jìn)一步分解揭示命題的內(nèi)部結(jié)構(gòu)以及命題間的內(nèi)在聯(lián)系命題分解個(gè)體詞（名詞、代詞）謂詞例：南京是城市個(gè)體詞：南京謂詞：是城市,

3、4.1 一階邏輯命題符號(hào)化,個(gè)體詞：研究對(duì)象中獨(dú)立存在的具體或抽象的個(gè)體個(gè)體常項(xiàng)：具體或特定的個(gè)體詞南京，東南大學(xué)，1，2個(gè)體變項(xiàng)：抽象或泛指的個(gè)體詞x,y,z 取值域稱為個(gè)體域或論域個(gè)體變?cè)娜≈捣秶凶稣撚蚧騻€(gè)體域空集不能作為論域,4.1 一階邏輯命題符號(hào)化,謂詞：刻畫(huà)個(gè)體詞性質(zhì)及個(gè)體詞之間的關(guān)系的詞謂詞常項(xiàng)：具體性質(zhì)或關(guān)系的謂詞F(a,b)：小王和小李是同學(xué)G(x)：x是有理數(shù)謂詞變項(xiàng)：抽象或泛指的性質(zhì)或關(guān)系

4、的謂詞L(x,y)：x,y具有關(guān)系Ln元謂詞P(x1,…,xn)P(x1,…,xn): Dn?{F,T}，D為個(gè)體域不帶個(gè)體變項(xiàng)的謂詞為0元謂詞即命題,4.1 一階邏輯命題符號(hào)化,例:將下列命題用0元謂詞符號(hào)化2既是素?cái)?shù)又是偶數(shù)F(x)：x是素?cái)?shù)G(x)：x是偶數(shù)a:2F(a) ? G(a)例:將下列命題用0元謂詞符號(hào)化如果3>5，則2>3F(x,y):x>ya:3, b:5, c:2F(a

5、,b)?F(c,a),4.1 一階邏輯命題符號(hào)化,量詞：表示個(gè)體變?cè)趥€(gè)體域中取值方式的詞全稱量詞?： ?x表示個(gè)體域里的所有個(gè)體x對(duì)應(yīng)日常語(yǔ)言中的“一切的”、“所有的”等一元謂詞F(x)個(gè)體域?yàn)镈， ?xF(x)真值?xF(x)為真：F(a)為真，對(duì)所有a?D?xF(x)為假：F(a)為假，對(duì)某個(gè)a?D?x?yG(x,y)：個(gè)體域里所有個(gè)體x,y有關(guān)系G?x?yF(x)為真：F(a,b)為真，對(duì)所有a,b?D?x?yF

6、(x)為假：F(a,b)為假，對(duì)某對(duì)a,b?D,4.1 一階邏輯命題符號(hào)化,存在量詞?： ?x表示個(gè)體域里有一個(gè)個(gè)體x對(duì)應(yīng)日常語(yǔ)言中的“存在”、“有一個(gè)”等一元謂詞F(x)個(gè)體域?yàn)镈， ?xF(x)真值?xF(x)為真：F(a)為真，存在某個(gè)a?D?xF(x)為假：F(a)為假，對(duì)任意a?D?x?yG(x,y)：個(gè)體域里存在個(gè)體x,y有關(guān)系G全稱量詞與存在量詞聯(lián)合?x?yG(x,y)：個(gè)體域里任意x,存在個(gè)體y, x, y

7、有關(guān)系G?x?yG(x,y)：個(gè)體域里存在x和所有個(gè)體y都有關(guān)系G,4.1 一階邏輯命題符號(hào)化,討論：?xF(x), ?xF(x), F(x)的聯(lián)系、區(qū)別F(x)是不能確定真值的謂詞?xF(x), ?xF(x)都是命題x稱為約束變?cè)?4.1 一階邏輯命題符號(hào)化,例：將下列命題符號(hào)化凡是人都呼吸 （個(gè)體域?yàn)槿祟?lèi)集合）F(x): x呼吸?xF(x)有的人用左手寫(xiě)字（個(gè)體域?yàn)槿祟?lèi)集合）G(x): x用左手寫(xiě)字?xG(x)

8、凡是人都呼吸F(x): x呼吸, M(x): x是人?x（M(x)?F(x))有的人用左手寫(xiě)字G(x): x用左手寫(xiě)字, M(x): x是人?x(M(x)?G(x)),4.1 一階邏輯命題符號(hào)化,例：將下列命題符號(hào)化并判斷真假值所有有理數(shù)都是整數(shù) （個(gè)體域?yàn)橛欣頂?shù)集合）F(x): x是整數(shù)?xF(x)所有有理數(shù)都是整數(shù) （個(gè)體域?yàn)閷?shí)數(shù)集合）F(x): x是整數(shù), Q(x): x有理數(shù)?x（Q(x)?F(x)),4.

9、1 一階邏輯命題符號(hào)化,例：將下列命題符號(hào)化并判斷真假值任意x，x2-3x+2=(x-1)(x-2) （個(gè)體域?yàn)樽匀粩?shù)集合）F(x): x2-3x+2=(x-1)(x-2) ?xF(x)存在x, x+5=3 （個(gè)體域?yàn)樽匀粩?shù)集合）G(x): x+5=3? xG(x)任意x，x2-3x+2=(x-1)(x-2) （個(gè)體域?yàn)閷?shí)數(shù)集合）存在x, x+5=3 （個(gè)體域?yàn)閷?shí)數(shù)集合）,4.1 一階邏輯命題符號(hào)化,謂詞邏輯符號(hào)化幾點(diǎn)說(shuō)

10、明不同的個(gè)體域，符號(hào)化形式可能不一樣，命題真值也可能不同一般默認(rèn)是全總個(gè)體域，即包含一切個(gè)體特性謂詞：描述個(gè)體變?cè)≈捣秶闹^詞全稱量化中，特性謂詞常作為蘊(yùn)涵式的前件?x（M(x)?F(x))存在量化中，特性謂詞常作為合取項(xiàng)之一?x (M(x)?G(x)),4.1 一階邏輯命題符號(hào)化,例：將下列命題符號(hào)化并判斷真假值凡是學(xué)生都需要學(xué)習(xí)和考試F(x): x是學(xué)生；G(x)：x學(xué)習(xí)；H(x)：x考試?x(F(x) ? G

11、(x) ? H(x))在北京工作的人未必是北京人F(x): x在北京工作；G(x)：x是北京人? (?xF(x) ? G(x)),4.1 一階邏輯命題符號(hào)化,例：將下列命題符號(hào)化不存在跑得同樣快的兩只兔子F(x)：x是兔子，L(x,y):x和y跑得同樣快? ?x?y(F(x) ? F(y) ? L(x,y))盡管有些人聰明，未必所有人都聰明F(x): x是人；G(x)：x聰明?x(F(x) ? G(x)) ? ? ?x

12、(F(x)?G(x))?x(F(x) ? G(x)) ? ?x(F(x) ? ?G(x)),4.1 一階邏輯命題符號(hào)化,注意事項(xiàng)根據(jù)命題的實(shí)際意義選取全稱量詞或存在量詞多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒順序符號(hào)化：對(duì)任意的x，存在著y，使得x+y=5給定實(shí)數(shù)域F(x,y)：x+y=5?x?yF(x,y)不同于?y?xF(x,y),T,F,第四章:一階謂詞邏輯,第一節(jié)：一階邏輯命題符號(hào)化 第二節(jié)：一階邏輯公式及其解釋,

13、4.2一階邏輯公式及其解釋,一階謂詞語(yǔ)言?的字母表非邏輯符號(hào)個(gè)體常項(xiàng)符號(hào)：a, b, c, …函數(shù)符號(hào)：f, g, h, …謂詞符號(hào)：F, G, H, …邏輯符號(hào)個(gè)體變項(xiàng)符號(hào)：x, y, z, …量詞符號(hào)：?，?聯(lián)接詞符號(hào)：?，?，?，?，?括號(hào)與逗號(hào)：( ，)，，函數(shù)符號(hào)不同于謂詞符號(hào),一階謂詞語(yǔ)言?的項(xiàng)：個(gè)體常項(xiàng)符號(hào)和個(gè)體變項(xiàng)符號(hào)是項(xiàng)若f(x1,…,xn)是n元函數(shù)符號(hào)，t1,…,tn是n個(gè)項(xiàng)，則f(t1,…

14、,tn)是項(xiàng)有限次使用①，②生成的符號(hào)串才是項(xiàng)例：下列符號(hào)串為項(xiàng)a, bx, yf(x,y)：x+y; f(a,y): a-yf(f(a,b),b)：f(a,b)+b,4.2一階邏輯公式及其解釋,一階謂詞語(yǔ)言?的原子公式：F(x1,…,xn)為n元謂詞符號(hào)t1,…,tn為n個(gè)項(xiàng)F(t1,…,tn)為?的原子公式例：下列符號(hào)串為原子公式F(a, b)F(x, y)F(f(x,y),a),4.2一階邏輯公式及其解釋

15、,一階謂詞語(yǔ)言?的合式公式（謂詞公式）：原子公式是合式公式 A為合式公式，則?A是合式公式 A，B為合式公式,則(A?B), (A?B), (A?B), (A?B) 為合式公式如A是合式公式，則?xA, ?xA也是合式公式只有有限次應(yīng)用1-4構(gòu)成的符號(hào)串才是合式公式,4.2一階邏輯公式及其解釋,合式公式例子F(a, b)F(x, y)F(a, b)?G(x,y)F(a, b)??xG(x,y)?x(F(a, b)?G

16、(x,y)),4.2一階邏輯公式及其解釋,轄域：緊接在量詞后面括號(hào)內(nèi)的合式公式?x P(x)，?x (P(x) ?Q(x))?x M(x) ? D(x) 自由變?cè)c指導(dǎo)變?cè)笇?dǎo)變?cè)撼霈F(xiàn)在量詞?x, ?x轄域內(nèi)的變?cè)獂?x M(x) ? D(x)自由變?cè)悍羌s束出現(xiàn)的變?cè)?x M(x) ? D(x)閉式（封閉公式）：不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式,4.2一階邏輯公式及其解釋,例：指出下列公式中的指導(dǎo)變?cè)?，各量詞的轄域，自由

17、出現(xiàn)已經(jīng)約束出現(xiàn)的個(gè)體變項(xiàng)F(a, b)?G(x,y)F(a, b)??xG(x,y)?x(F(a, b)?G(x,y))?x(F(a, x))??y(G(x,y)?H(z)),4.2一階邏輯公式及其解釋,如何賦予合式公式含義？定義域函數(shù)變項(xiàng)需要指定具體函數(shù)謂詞變項(xiàng)需要指定具體謂詞,4.2一階邏輯公式及其解釋,例：?x?y(F(x) ? F(y) ? G(f(x,y), g(x,y)))定義域：全總個(gè)體域函數(shù)變項(xiàng)需要指

18、定具體函數(shù)f(x,y)：x+yg(x,y)：xy謂詞變項(xiàng)需要指定具體謂詞F(x)：x是實(shí)數(shù)G(x,y)：x=y,任意x, y，如果x, y是實(shí)數(shù)，則x+y=xy,4.2一階邏輯公式及其解釋,解釋?zhuān)悍沁壿嫹?hào)集L生成的一階語(yǔ)言?，?的解釋I由4部分組成非空個(gè)體域DII將任意一個(gè)個(gè)體常項(xiàng)符號(hào)a?L映射到DI上的個(gè)體a*I將任意一個(gè)n元函數(shù)f?L映射到DI上的n元函數(shù)f*: (DI)n ? DII將任意一個(gè)n元謂詞F?L映射

19、到DI上的n元關(guān)系RF,4.2一階邏輯公式及其解釋,公式A在I下的解釋AI：取個(gè)體域DIA中個(gè)體常項(xiàng)符號(hào)a?L替換為DI上的個(gè)體a*A中的n元函數(shù)f?L替換為DI上的n元函數(shù)f*: (DI)n ? DIA中n元謂詞F?L替換為DI上的n元關(guān)系RF,4.2一階邏輯公式及其解釋,公式A在I下的真值如果AI是閉式，則為命題，可以有真假值,4.2一階邏輯公式及其解釋,模型：AI是閉式，公式A在I下為真，符號(hào)為 I ? A，如果下面條件

20、滿足I(F(t1,…,tn))=T，如果(t*1,…,t*n)?RFI(?B)=T iff I(B)=FI(B?C)=T iff I(B)= I(C)=TI(?xB(x))=T iff 對(duì)任意a?DI, I(B(a))=TI(?xB(x))=T iff 存在a?DI, I(B(a))=T,4.2一階邏輯公式及其解釋,給定解釋I個(gè)體域?yàn)樽匀粩?shù)集Na* = 2f* =x+y, g* =xyF*：x=y給出下列公式在

21、I下的解釋?zhuān)懻撜婕僦?x F(g(x, y), z)?x F(g(x, a), x)?F(x, f(x,a))?x ?y F(f(g(x, a)),y), g(x,y)),4.2一階邏輯公式及其解釋,給定解釋I個(gè)體域?yàn)樽匀粩?shù)集Na* = 2f* =x+y, g* =xyF*：x=y給出下列公式在I下的解釋?zhuān)懻撜婕僦?x F(g(x, y), z)??x (xy=z)?x (F(g(x, a), x)?F(x,

22、f(x,a)))??x ((2x=x)?(x=x+2))?x ?y F(f(g(x, a),y), g(x,y))??x ?y (2x+y=xy),4.2一階邏輯公式及其解釋,合式公式分類(lèi)：公式A重言式(永真式)：A在任意的解釋下為真矛盾式(永假式)：A在任意的解釋下為假可滿足式： A在某個(gè)解釋下為真,4.2一階邏輯公式及其解釋,代換實(shí)例給定命題公式A0，含命題變項(xiàng)p1,…,pnA1,…,An是n個(gè)謂詞公式A稱為A0的

23、代換實(shí)例如果A通過(guò)用Ai代替A0中的pi得到,4.2一階邏輯公式及其解釋,定理：重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式 證明思路：給定重言式A0 ，對(duì)于命題變項(xiàng)p1,…,pn的任意賦值，A0都為真討論：假設(shè)A通過(guò)用Ai代替A0中的pi得到，如果Ai不是封閉公式， A是否還是永真？例：已知p?(q?p)為重言式，那么 F(x)?(G(x)?F(x))是否是重言式？,4.2一階邏輯公式及其

24、解釋,例：判斷下列公式類(lèi)型?x F(x) ??y F(y)?x (F(x) ? G(x))?xF(x) ? (?x?yG(x,y)? ?xF(x)),4.2一階邏輯公式及其解釋,例：判斷下列公式類(lèi)型?x F(x) ??y F(y)對(duì)任意解釋I，如果I使得?x F(x)為真，對(duì)任意x?DI，F(xiàn)(x)為真，I必使得?x F(x)為真?x (F(x) ? G(x))解釋I： DI 為實(shí)數(shù)集RF(x): x是整數(shù)；G(x): x

25、是有理數(shù)?xF(x) ? (?x?yG(x,y)? ?x(F(x))是p ? (q ?p)的代換實(shí)例,永真式,永真式,可滿足式,4.2一階邏輯公式及其解釋,練習(xí)將下列命題符號(hào)化有的火車(chē)比有的汽車(chē)快指出下列公式的指導(dǎo)變?cè)?，量詞的轄域，各個(gè)變項(xiàng)的自由出現(xiàn)和約束出現(xiàn)?xF(x,y) ? ?yG(x,y),4.2一階邏輯公式及其解釋,練習(xí)課本67頁(yè)，14題（1）課本67頁(yè)，15題（2）,4.2一階邏輯公式及其解釋,第四章 習(xí)題課

26、,主要內(nèi)容個(gè)體詞、謂詞、量詞一階邏輯命題符號(hào)化一階語(yǔ)言L 項(xiàng)、原子公式、合式公式公式的解釋 量詞的轄域、指導(dǎo)變?cè)?、個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋公式的類(lèi)型 永真式(邏輯有效式)、矛盾式(永假式)、可滿足式,基本要求,準(zhǔn)確地將給定命題符號(hào)化 理解一階語(yǔ)言的概念 深刻理解一階語(yǔ)言的解釋 熟練地給出公式的解釋 記住閉式的性質(zhì)并能應(yīng)用它 深刻理解永真式、矛盾式、可滿足式的概念, 會(huì)判斷簡(jiǎn)

27、 單公式的類(lèi)型,練習(xí)1,1. 在分別取個(gè)體域?yàn)?(a) D1=N (b) D2=R (c) D3為全總個(gè)體域的條件下, 將下面命題符號(hào)化，并討論真值 (1) 對(duì)于任意的數(shù)x，均有,解 設(shè)G(x): (a) ?xG(x),(b) ?xG(x),(c) 又設(shè)F(x):x是實(shí)數(shù) ?x(F(x)?G(x)),真,真,假,練習(xí)1(續(xù)),解 設(shè)H(x)：

28、x+7=5 (a) ?xH(x),,(2) 存在數(shù)x，使得 x+7=5,(b) ?xH(x),(c) 又設(shè)F(x)：x為實(shí)數(shù) ?x(F(x)?H(x)),本例說(shuō)明：不同個(gè)體域內(nèi)，命題符號(hào)化形式可能不同（也可能相同），真值可能不同（也可能相同）.,真,真,假,練習(xí)2,2. 在一階邏輯中將下列命題符號(hào)化 (1) 大熊貓都可愛(ài),(2) 有人愛(ài)發(fā)脾氣,(3) 說(shuō)所有人都愛(ài)吃面包是不對(duì)的,設(shè)F(x):

29、x為大熊貓，G(x): x可愛(ài) ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛(ài)發(fā)脾氣 ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛(ài)吃面包 ??x(F(x)?G(x)) 或 ?x(F(x)??G(x)),練習(xí)2,(4) 沒(méi)有不愛(ài)吃糖的人,(5) 任何兩個(gè)不同的人都不一樣高,(6) 不是所有的汽車(chē)都比所有的火車(chē)快,設(shè)F(x): x是人，G(x): x愛(ài)吃糖??x(F

30、(x)??G(x)) 或 ?x(F(x)?G(x)),設(shè)F(x):x是人, H(x,y), x與y相同, L(x,y): x與y一樣高 ?x(F(x)??y(F(y)??H(x,y)??L(x,y))) 或 ?x?y(F(x)?F(y)??H(x,y)??L(x,y)),設(shè)F(x):x是汽車(chē), G(y):y是火車(chē), H(x,y):x比y快 ??x?y(F(x)?G(y)?H(x,y)) 或 ?x?y

31、(F(x)?G(y)??H(x,y)),練習(xí)3,?x(2x=x) 假,,3. 給定解釋 I 如下: (a) 個(gè)體域D=N (b) =2 (c) (d) 說(shuō)明下列公式在 I 下的涵義,并討論真值 (1) ?xF(g(x,a),x),(2) ?x?y(F(f(x,a),y)?F(f(y,a),x)),?x?y(x+2=y?y+2=x)

32、 假,練習(xí)3,(3) ?x?y?zF(f(x,y),z),,(5) ?xF(f(x,x),g(x,x)),(4) ?x?y?zF(f(y,z),x),?x?y?z(y+z=x) 假,?x?y?z(x+y=z) 真,?x(x+x=x?x) 真,(3),(4)說(shuō)明?與?不能隨意交換,練習(xí)4,4. 證明下面公式既不是永真式，也不是矛盾式:,(1) ?x(F(x)?G(x)),(2) ?x?

33、y(F(x)?G(y)?H(x,y)),解釋1: D1=N, F(x):x是偶數(shù), G(x): x是素?cái)?shù), 真,解釋2: D2=N, F(x):x是偶數(shù), G(x): x是奇數(shù), 假,解釋1: D1=Z, F(x):x是正數(shù), G(x): x是負(fù)數(shù), H(x,y):x>y 真,解釋2: D2=Z, F(x):x是偶數(shù),