謂詞

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

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

3、4.1 一階邏輯命題符號化,個體詞：研究對象中獨立存在的具體或抽象的個體個體常項：具體或特定的個體詞南京，東南大學(xué)，1，2個體變項：抽象或泛指的個體詞x,y,z 取值域稱為個體域或論域個體變元的取值范圍叫做論域或個體域空集不能作為論域,4.1 一階邏輯命題符號化,謂詞：刻畫個體詞性質(zhì)及個體詞之間的關(guān)系的詞謂詞常項：具體性質(zhì)或關(guān)系的謂詞F(a,b)：小王和小李是同學(xué)G(x)：x是有理數(shù)謂詞變項：抽象或泛指的性質(zhì)或關(guān)系

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

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

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

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

8、凡是人都呼吸F(x): x呼吸, M(x): x是人?x（M(x)?F(x))有的人用左手寫字G(x): x用左手寫字, M(x): x是人?x(M(x)?G(x)),4.1 一階邏輯命題符號化,例：將下列命題符號化并判斷真假值所有有理數(shù)都是整數(shù) （個體域為有理數(shù)集合）F(x): x是整數(shù)?xF(x)所有有理數(shù)都是整數(shù) （個體域為實數(shù)集合）F(x): x是整數(shù), Q(x): x有理數(shù)?x（Q(x)?F(x)),4.

9、1 一階邏輯命題符號化,例：將下列命題符號化并判斷真假值任意x，x2-3x+2=(x-1)(x-2) （個體域為自然數(shù)集合）F(x): x2-3x+2=(x-1)(x-2) ?xF(x)存在x, x+5=3 （個體域為自然數(shù)集合）G(x): x+5=3? xG(x)任意x，x2-3x+2=(x-1)(x-2) （個體域為實數(shù)集合）存在x, x+5=3 （個體域為實數(shù)集合）,4.1 一階邏輯命題符號化,謂詞邏輯符號化幾點說

10、明不同的個體域，符號化形式可能不一樣，命題真值也可能不同一般默認是全總個體域，即包含一切個體特性謂詞：描述個體變元取值范圍的謂詞全稱量化中，特性謂詞常作為蘊涵式的前件?x（M(x)?F(x))存在量化中，特性謂詞常作為合取項之一?x (M(x)?G(x)),4.1 一階邏輯命題符號化,例：將下列命題符號化并判斷真假值凡是學(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 一階邏輯命題符號化,例：將下列命題符號化不存在跑得同樣快的兩只兔子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 一階邏輯命題符號化,注意事項根據(jù)命題的實際意義選取全稱量詞或存在量詞多個量詞同時出現(xiàn)時，不能隨意顛倒順序符號化：對任意的x，存在著y，使得x+y=5給定實數(shù)域F(x,y)：x+y=5?x?yF(x,y)不同于?y?xF(x,y),T,F,第四章:一階謂詞邏輯,第一節(jié)：一階邏輯命題符號化 第二節(jié)：一階邏輯公式及其解釋,

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

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

15、,一階謂詞語言?的合式公式（謂詞公式）：原子公式是合式公式 A為合式公式，則?A是合式公式 A，B為合式公式,則(A?B), (A?B), (A?B), (A?B) 為合式公式如A是合式公式，則?xA, ?xA也是合式公式只有有限次應(yīng)用1-4構(gòu)成的符號串才是合式公式,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一階邏輯公式及其解釋,轄域：緊接在量詞后面括號內(nèi)的合式公式?x P(x)，?x (P(x) ?Q(x))?x M(x) ? D(x) 自由變元與指導(dǎo)變元指導(dǎo)變元：出現(xiàn)在量詞?x, ?x轄域內(nèi)的變元x?x M(x) ? D(x)自由變元：非約束出現(xiàn)的變元?x M(x) ? D(x)閉式（封閉公式）：不含自由出現(xiàn)的個體變項的公式,4.2一階邏輯公式及其解釋,例：指出下列公式中的指導(dǎo)變元，各量詞的轄域，自由

17、出現(xiàn)已經(jīng)約束出現(xiàn)的個體變項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ù)變項需要指定具體函數(shù)謂詞變項需要指定具體謂詞,4.2一階邏輯公式及其解釋,例：?x?y(F(x) ? F(y) ? G(f(x,y), g(x,y)))定義域：全總個體域函數(shù)變項需要指

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

19、到DI上的n元關(guān)系RF,4.2一階邏輯公式及其解釋,公式A在I下的解釋AI：取個體域DIA中個體常項符號a?L替換為DI上的個體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下為真，符號為 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 對任意a?DI, I(B(a))=TI(?xB(x))=T iff 存在a?DI, I(B(a))=T,4.2一階邏輯公式及其解釋,給定解釋I個體域為自然數(shù)集Na* = 2f* =x+y, g* =xyF*：x=y給出下列公式在

21、I下的解釋，討論真假值?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個體域為自然數(shù)集Na* = 2f* =x+y, g* =xyF*：x=y給出下列公式在I下的解釋，討論真假值?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一階邏輯公式及其解釋,合式公式分類：公式A重言式(永真式)：A在任意的解釋下為真矛盾式(永假式)：A在任意的解釋下為假可滿足式： A在某個解釋下為真,4.2一階邏輯公式及其解釋,代換實例給定命題公式A0，含命題變項p1,…,pnA1,…,An是n個謂詞公式A稱為A0的

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

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

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

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

27、 單公式的類型,練習(xí)1,1. 在分別取個體域為 (a) D1=N (b) D2=R (c) D3為全總個體域的條件下, 將下面命題符號化，并討論真值 (1) 對于任意的數(shù)x，均有,解 設(shè)G(x): (a) ?xG(x),(b) ?xG(x),(c) 又設(shè)F(x):x是實數(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ù) ?x(F(x)?H(x)),本例說明：不同個體域內(nèi)，命題符號化形式可能不同（也可能相同），真值可能不同（也可能相同）.,真,真,假,練習(xí)2,2. 在一階邏輯中將下列命題符號化 (1) 大熊貓都可愛,(2) 有人愛發(fā)脾氣,(3) 說所有人都愛吃面包是不對的,設(shè)F(x):

29、x為大熊貓，G(x): x可愛 ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛發(fā)脾氣 ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛吃面包 ??x(F(x)?G(x)) 或 ?x(F(x)??G(x)),練習(xí)2,(4) 沒有不愛吃糖的人,(5) 任何兩個不同的人都不一樣高,(6) 不是所有的汽車都比所有的火車快,設(shè)F(x): x是人，G(x): x愛吃糖??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是汽車, G(y):y是火車, 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) 個體域D=N (b) =2 (c) (d) 說明下列公式在 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)說明?與?不能隨意交換,練習(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是素數(shù), 真,解釋2: D2=N, F(x):x是偶數(shù), G(x): x是奇數(shù), 假,解釋1: D1=Z, F(x):x是正數(shù), G(x): x是負數(shù), H(x,y):x>y 真,解釋2: D2=Z, F(x):x是偶數(shù),