1、第二章 謂詞邏輯楊圣洪第二章 謂詞邏輯楊圣洪引言 命題邏輯好像功能強(qiáng)大，但還是有些問題難以解決。 如楊圣洪要喝水、劉翔要喝水、姚明要喝水、姚晨要喝水、劉德華要喝水、，可歸納為“某某要喝水”，無法表示。 所有的人都要呼吸、喝水、吃飯，“所有”如何表示呢？ 有些人要升官、有些人要失戀，“有些”又如何表示？ 所有男人都會(huì)多看幾眼漂亮女人 所有女人都會(huì)多喜歡漂亮的衣服 又如有名三段論：所有人都是要變老的，楊圣洪是人，所以楊圣洪也會(huì)變老的，無法表示。 為此需要我們學(xué)習(xí)新的邏輯工具-謂詞邏輯或一階邏輯引言 2.1基本概念 1、謂詞 “某某要喝水”、“喜歡漂亮衣服”、“喜歡帥哥”、“結(jié)婚生崽”都是所在句子的

2、謂語部分。 命題邏輯中用大寫字母表示命題。 謂詞邏輯中用大寫字母表示謂語部分，如 用W表示“要喝水”， 用L表示“喜歡漂亮衣服”， 用H表示“喜歡帥哥”， 用M表示“結(jié)婚生崽”。 這些表示謂語部分的大寫字母，稱為“謂詞”。 2.1基本概念2.1基本概念 2、個(gè)體常元 表示某種判斷的語句一般都有主語。 主語是表示某個(gè)、某些客體，也稱為個(gè)體。 如“劉翔”、“姚明”。 為了描述方便，常用小寫字母表示這些個(gè)體。 如a表示“劉翔”， c表示“姚明”， 這些表示具體個(gè)體的小寫字母，稱為“個(gè)體常元”或個(gè)體常量。 其他學(xué)科中，也是用字母表中靠前的字母表示常量。2.1基本概念2.1基本概念 3、個(gè)體變?cè)?對(duì)于不

3、針對(duì)特定個(gè)體的泛指， 如“某某”、“男人”、“女人”， 常用x,y,z,r,s,t等字母表中靠后的字母表示， 其他學(xué)科中，也是這樣表示， 這些小字字母稱為“個(gè)體變?cè)薄?因此“某某要喝水”表示為W(x),x泛指所有的人， “女人喜歡漂亮衣服”表示為L(zhǎng)(x,y)，x泛指“女人”、y泛指“衣服”， “女人喜歡帥哥”表示為H(y,z)，其中y泛指女人、z泛指帥哥。 “男人結(jié)婚生崽”表示為M(z)，z泛指男人。 2.1基本概念2.1基本概念 4、全稱量詞 為了表示“所有女人都喜歡漂亮的衣服”、 “所有女人都喜歡帥哥”等中 “所有”，引入符號(hào)“”，稱為全稱量詞。 可能是“ALL”的字母A倒寫，表示所有、

4、全部。 當(dāng)用x泛指“人”，“所有人”表示為“x”， “所有活人都要喝水”表示為xW(x)。 當(dāng)用x表示“女人”,y表示漂亮的衣服時(shí)， “所有女人”則表示為x、 “所有漂亮的衣服”則表示為“y”，因此 “所有女人都喜歡漂亮的衣服”表示為xyL(x,y)。 當(dāng)用x表示“女人”,y表示帥哥時(shí)， “所有女人都喜歡帥哥”表示為xyH(x,y)。 2.1基本概念2.1基本概念 5、存在量詞 為了表示“有些男人結(jié)婚生崽”中“有些”， 引入符號(hào)“”， 表示“存在，有些、有部分”等的含義。 稱為存在量詞。 它是Exist的首字母，左旋180度， 如用z表示“男人”，那么 “有些男人”表示為“z”， “有些男人結(jié)

5、婚生崽”表示為“zM(z)”。2.1基本概念2.1基本概念 6、謂詞公式 將表示全部的符號(hào)“”，表示為部分的“”稱為量詞， 將單個(gè)謂詞公式如W(x)，帶量詞的謂詞如zM(z)， 統(tǒng)稱為“謂詞公式”。 謂詞W(x),M(z)中只有1個(gè)個(gè)體變?cè)? 則稱為1元謂詞公式， 常用來刻劃對(duì)象的性質(zhì)、屬性。 謂詞L(x,y)、H(y,z)中有2個(gè)個(gè)體變?cè)?，稱為2元謂詞。 常用來表示二個(gè)對(duì)象之間的關(guān)系， 如喜歡， 類似如果有n個(gè)個(gè)體變?cè)獎(jiǎng)t稱為n元謂詞公式。 個(gè)體變?cè)娜≈捣秶Q為“討論域”， 如果沒有交待討論域，表示對(duì)個(gè)體變?cè)娜≈捣秶蛔鋈魏蜗拗?，泛指宇宙界的萬物，稱為“全總個(gè)體域”，常用大寫字母U表示。

6、 2.1基本概念利用量詞、謂詞將自然語言轉(zhuǎn)換為謂詞公式 例1：(1)凡人都要呼吸 (2)有的人用左手寫字。 解：當(dāng)個(gè)體域?yàn)椤叭祟悺睍r(shí) xB(x),其中B(x)表示x人呼吸breath. xWL(x)，其中WL(x)表示x用左邊寫字。 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域(宇宙萬物組成) x(H(x)B(x) H(x)表示個(gè)體x是人類 x(H(x) WL(x)，WL(x)表示x用左邊寫字。 個(gè)體域不同，謂詞公式不同。例2 (1)任意x,x2-2x+1=(x-1)2. 有x,使得x*5=3解：當(dāng)x的取值范圍即個(gè)體域?yàn)樽匀粩?shù)N時(shí) xE(x) E(x)表示x2-2x+1=(x-1)2 xF(x) F(x)表示x*5=

7、3 當(dāng)x的個(gè)體域?yàn)閷?shí)數(shù)R時(shí)，謂詞公式相同但真值不同！利用量詞、謂詞將自然語言轉(zhuǎn)換為謂詞公式 例3 (1)兔子比烏龜跑得快 (2)有的兔子比所有的烏龜跑得快 (3)并不是所有的兔子都比烏龜跑得快 (4)不存在跑得同樣快的兩只兔子. 解：H(x,y)表示x比y跑得快. L(x,y)表示x與y一樣快 R(x)表示x是兔子 T(x)表示x是烏龜 (1) xy(R(x)T(y)H(x,y) (2) xy(R(x)T(y) H(x,y) (3) xy(R(x)T(y)H(x,y) xy(R(x)T(y)H(x,y) (4) xy(R(x)R(y)L(x,y) xy(R(x)R(y) L(x,y)例3 (1

8、)兔子比烏龜跑得快例4任意兩個(gè)不相等實(shí)數(shù)，其平方和大于積的二倍。 解：個(gè)體域?yàn)槿倐€(gè)體域即不對(duì)個(gè)體變?cè)娜≈底鋈魏蜗拗啤?F(x)表示x是實(shí)數(shù)， G(x,y)表示xy， H(x,y)表示xy，則原話表示為 xy (F(x)F(y)G(x,y)H(x2+y2,2xy)。 若用f(x,y)表示x2+y2，g(x,y)表示2xy，則原話表示為 (F(x)F(y)G(x,y)H(f(x,y),g(x,y) 因?yàn)閷?duì)于實(shí)數(shù)x，y，(x2-2xy+y2)=(x-y)2， 當(dāng)xy時(shí)，有(x-y)20， 故(x2-2xy+y2)0， 故x2+y22xy， 故H(x2+y2,2xy) 為真 故原話正確，故以上公式

9、的真值為1。 故謂詞公式可出現(xiàn)個(gè)體變?cè)?平方,乘、倍數(shù)、函數(shù)等。例4任意兩個(gè)不相等實(shí)數(shù)，其平方和大于積的二倍。例5表示“所有人都要變老的，楊圣洪是人，所以楊圣洪也會(huì)變老的”。 解：個(gè)體域?yàn)槿倐€(gè)體域，即對(duì)個(gè)體變?cè)娜≈挡蛔鋈魏蜗蕖?H(x)表示對(duì)象x是人類， O(x)表示對(duì)象x變老， c表示個(gè)體常元“楊圣洪”，則 H(c)表示個(gè)體常元楊圣洪是人類， O(c)表示個(gè)體常元楊圣洪要變老，原句表示 (x(H(x)O(x)H(c)O(c)。 該公式不僅有個(gè)體變?cè)?，還有個(gè)體常元 例5表示“所有人都要變老的，楊圣洪是人，所以楊圣洪也會(huì)變老的例6表示“所有人都要死的，蘇格拉底是人，所以蘇格拉底也會(huì)死”。 解

10、：個(gè)體域?yàn)槿倐€(gè)體域，即對(duì)個(gè)體變?cè)娜≈挡蛔鋈魏蜗拗啤?H(x)表示對(duì)象x是人類， O(x)表示對(duì)象x要死的， c表示個(gè)體常元“蘇格拉底”，則 H(c)表示個(gè)體常元蘇格拉底是人類， O(c)表示個(gè)體常元蘇格拉底要死，原句表示 (x(H(x)O(x)H(c)O(c)。 這兩個(gè)例題，語句不同，但是最后的謂詞公式相同。例6表示“所有人都要死的，蘇格拉底是人，所以蘇格拉底也會(huì)死”2.2、謂詞公式及解釋 上節(jié)得到一些謂詞公式，獲得一些結(jié)論，也有存在一些疑惑？ (1)謂詞公式有個(gè)體常元、個(gè)體變?cè)?，還可以有個(gè)體變?cè)谋磉_(dá)式，那么謂詞公式究竟還有哪些形式，究竟什么的字符串是合法的謂詞公式？ (2)同一句話有二

11、個(gè)不同的公式，那么這二個(gè)公式等值嗎？ (3)不同的話擁有同樣的謂詞公式，到底這二句話有何共性？ (4)同一樣公式在不同的論域下真值不同，究竟如何確定一個(gè)公式的真值呢？ 2.2、謂詞公式及解釋2.2、謂詞公式及解釋非邏輯符號(hào):個(gè)體常元、函數(shù)符號(hào)、謂詞符號(hào)邏輯符號(hào):個(gè)體變?cè)?、量詞符號(hào)、聯(lián)結(jié)詞、逗號(hào)、括號(hào)。項(xiàng)的定義：個(gè)體常元與變?cè)捌浜瘮?shù)式為項(xiàng)。(1)個(gè)體常元和個(gè)體變?cè)琼?xiàng)。(2)若(x1,x2, xn)是n元函數(shù),t1,t2,tn是n個(gè)項(xiàng)，則(t1,t2, tn)是項(xiàng)。(3)有限次使用(2)得到的表達(dá)式是項(xiàng)。原子公式： 設(shè)R(x1,x2,xn)是n元謂詞，t1,t2,tn是項(xiàng)，則R(t1,t2,

12、tn)是原子公式。2.2、謂詞公式及解釋2.2、謂詞公式及解釋項(xiàng)的定義：個(gè)體常元與變?cè)捌浜瘮?shù)式為項(xiàng)。原子公式： 設(shè)R(x1,x2,xn)是n元謂詞，t1,t2,tn是項(xiàng)，則R(t1,t2, tn)是原子公式。合式謂詞公式： (1)原子公式是合式公式； (2)若A是合式公式，則(A)也是合式公式； (3)若A,B合式，則AB, AB, AB , AB 合式 (4)若A合式，則xA、 xA合式 (5)有限次使用(2)(4)得到的式子是合式。2.2、謂詞公式及解釋2.2、謂詞公式及解釋 (F(x)F(y)G(x,y)H(f(x,y),g(x,y)、 xy(R(x)T(y)H(x,y)、 xy(R(

13、x)T(y)H(x,y)、x(H(x)WL(x)、(x(H(x)O(x) H(c) )O(c)， 因此以上公式均是合法的公式，而 F(x)F(y)G(x,y)、F(y)G(x,y)不是合法的公式。 凡按照以上5條規(guī)則寫出的表達(dá)式，就是合法謂詞公式(也稱為合式公式)。 不再拘泥于某個(gè)具體的自然語句。 直接研究含義不確定或泛指的謂詞公式。 從形式上研究合式公式的性質(zhì)。2.2、謂詞公式及解釋2.2、謂詞公式及解釋-個(gè)體變?cè)纳矸萘吭~指導(dǎo)變?cè)簒A和xA中的x量詞轄域：xA和xA中的A為量詞/轄域變?cè)募s束出現(xiàn)：指導(dǎo)變?cè)拿看纬霈F(xiàn)(稱約束變?cè)?。變?cè)淖杂沙霈F(xiàn)：不是約束出現(xiàn)的變?cè)?稱自由變?cè)? 。例題

14、 x(F(x,y)G(x,z)解： x是量詞的指導(dǎo)變?cè)?(F(x,y)G(x,z)是量詞的轄域 在 (F(x,y)G(x,z)中x是約束出現(xiàn)，出現(xiàn)2次。 在(F(x,y)G(x,z)自由出現(xiàn)的變?cè)獃/z，各一次。 2.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?.2、謂詞公式及解釋-個(gè)體變?cè)纳矸萘吭~指導(dǎo)變?cè)簒A和xA中的x量詞轄域：xA和xA中的A為量詞/轄域變?cè)募s束出現(xiàn)：指導(dǎo)變?cè)拿看纬霈F(xiàn)(稱約束變?cè)?。變?cè)淖杂沙霈F(xiàn)：不是約束出現(xiàn)的變?cè)?稱自由變?cè)? 。 例題 x(F(x,y)G(x,z)例題 x(F(x)G(y)y(H(x)L(x,y,z)解： 量詞的指導(dǎo)變?cè)獂, (F(x)G(y)是量

15、詞的轄域，其中x是約束出現(xiàn)，y是自由出現(xiàn)。 量詞的指導(dǎo)變?cè)獃, H(x)L(x,y,z)是量詞的轄域，其中x是自由2次，y是約束出現(xiàn)。整個(gè)公式中是約束1自由2次。2.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?例題 分析x(F(x)G(y)y(H(x)L(x,y,z)變?cè)矸萁猓?x的轄域是：(F(x)G(y)，約束變?cè)莤，x有1次約束出現(xiàn)，y是自由變?cè)?，?次自由出現(xiàn)。 y的轄域是：H(x)L(x,y,z)，約束變?cè)莥，y有1次約束出現(xiàn)，x與z是自由變?cè)?，各?次自由出現(xiàn)。 盡管x在公式x(F(x)G(y)出現(xiàn)，又在 y(H(x)L(x,y,z)出現(xiàn)，但兩個(gè)

16、x不是一回事， 只是恰巧二個(gè)名字相同而矣， 好比有2個(gè)李勇，一個(gè)是正坐在家里看電視的“李勇”，一個(gè)是在馬路上散步的“李勇”， 為了避免這種“誤會(huì)”出現(xiàn)，要對(duì)“約束變?cè)备拿?.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?例題 分析x(F(x)G(y)y(H(x)L(x,y,z)變?cè)矸萁猓罕M管x在公式x(F(x)G(y)出現(xiàn)，又在 y(H(x)L(x,y,z)出現(xiàn)，但兩個(gè)x不是一回事， 只是恰巧二個(gè)名字相同而矣， 為避免這種“誤會(huì)”出現(xiàn)要對(duì)“約束變?cè)备拿?將量詞x的指導(dǎo)變?cè)獂，x的每次約束出現(xiàn)換成公式中未出現(xiàn)的r。 將量詞y指導(dǎo)變?cè)獃、約束變?cè)獃的每次出現(xiàn)換

17、成公式中未出現(xiàn)的s，則原式為 r(F(r)G(y)s(H(x)L(x,s,z)， 所有約束變?cè)c自由變?cè)恢孛?，無誤會(huì)。 2.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?例題 分析xy(P(x,y)Q(y,z)xP(x,y)作用域與變?cè)s束情況 解：x、y的作用域是(P(x,y)Q(y,z)， x的作用域是P(x,y)。 將與自由變?cè)s束變?cè)獃r， 將與前一個(gè)同名約束變?cè)獂s，則原公式 xr(P(x,r)Q(r,z)sP(s,y) 2.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?例題 x(P(x)xQ(x,z)yR(x,y)Q(

18、x,y) 解：x的轄域是P(x)xQ(x,z)yR(x,y)，。 x的轄域是Q(x,z) y的轄域是R(x,y) s(P(s)rQ(r,z)tR(s,t)Q(x,y) 改名規(guī)則：一般僅對(duì)約束變?cè)拿?后出現(xiàn)者約束變?cè)惨拿?方法：將量詞的指導(dǎo)變?cè)?，及轄域中約束變?cè)看渭s束出現(xiàn)，全部換成公式中未出現(xiàn)的字母。2.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?閉公式：不含自由變?cè)闹^詞公式 。x(F(x,y)G(x,z)因y,z是自由變?cè)?，故不是。r(F(r)G(y)s(H(x)L(x,s,z)因?yàn)閥,x,z自由故不是xr(P(x,r)Q(r,z)sP(s,y) 因z

19、與y自由，故不是。s(P(s)rQ(r,z)tR(s,t) 因z自由故不是(F(x)F(y)G(x,y)H(f(x,y),g(x,y) 因x/y自由故不是以下公式均沒有自由變?cè)?，均為閉公式：xy(R(x)T(y)H(x,y)、xy(R(x)T(y)H(x,y)、xy(R(x)T(y)H(x,y)、xy(R(x)T(y) H(x,y)、xy(R(x)R(y)L(x,y)、xy(R(x)R(y) L(x,y)、x(H(x)B(x)、x(H(x)WL(x)、(x(H(x)O(x)H(c)O(c)2.2、謂詞公式及解釋-個(gè)體變?cè)纳矸?.2、謂詞公式及解釋-謂詞公式的真值 前面我們學(xué)習(xí)“合式公式”時(shí)，

20、說過不再拘泥于某個(gè)具體的自然語句，從形式上研究合式公式的性質(zhì)。 但謂詞公式是邏輯公式，它總得有一個(gè)真假呀？ 如何確定其真假呢？ 神馬不能總是浮云？ 總得落地。 確定真值的方法： (1)確定個(gè)體域，即個(gè)體的取值范圍，哪個(gè)范圍？ (2)將個(gè)體常元指定為個(gè)體域的具體值。哪個(gè)對(duì)象？ (3)函數(shù)常元表示指定個(gè)體域中個(gè)體變?cè)捻?xiàng)。 (4)用指定個(gè)體域中的對(duì)象來解釋各個(gè)原子公式。 (5)用原子公式的解釋來描述整個(gè)公式的含義。原義？ 根據(jù)個(gè)體域中知識(shí)，判斷整個(gè)公式的含義是否正確，若對(duì)則公式的真值為1，否則為02.2、謂詞公式及解釋-謂詞公式的真值2.2、謂詞公式的解釋-謂詞公式的真值例題：x(F(x)G(x)

21、 其中x的取值范圍是什么？ F(x)的含義是什么？G(x)的含義是什么？ 將這些問題確定后，表達(dá)式x(F(x)G(x)的真值就確定了，這就是公式的解釋。 dom(x)=D1=全總個(gè)體域 F(x)表示x是人，G(x)表示x是黃種人。 x(F(x)G(x)：所有的人都是黃種人，值為F. dom(x)=D2=實(shí)數(shù)集R F(x)表示x是自然數(shù)，G(x)表示x是整數(shù)。 x(F(x)G(x)：所有的自然數(shù)都是整數(shù)，值為T.2.2、謂詞公式的解釋-謂詞公式的真值例：xy (F(x)F(y)G(x,y)H(f(x,y),g(x,y) f(x,y),g(x,y)是函數(shù)變?cè)辉^詞公式F(x),二元謂詞G與H。

22、 x與y的個(gè)體域：全總個(gè)體域。 F(x):x是實(shí)數(shù) G(x,y):xy H(x,y):xy f(x,y)=x2+y2 g(x,y)=2xy 這時(shí)整個(gè)公式的含義： 對(duì)于任意的x和y，若x與y是實(shí)數(shù)且xy，那么x2+y2 2xy ，其真值為1. 如果H(x,y): xy f(x,y)=x2+y2 g(x,y)=2xy 這時(shí)整個(gè)公式的含義： 對(duì)于任意的x和y，若x與y是實(shí)數(shù)且xy，那么x2+y2 2xy ，其真值為1. 總結(jié)： 個(gè)體常元的值、個(gè)體變?cè)闹涤?、確定函數(shù)、謂詞公式的含義。例題：xy (F(x)F(y)G(x,y)H(f( 個(gè)體常元的值、個(gè)體變?cè)闹涤?、確定函數(shù)、謂詞公式的含義。例4：個(gè)體

23、變?cè)闹涤駾=N, 常元的a=0,函數(shù)f(x,y)=x+y ,g(x,y)=x*y 謂詞F(x,y):x=y解釋下列各公式的含義： (1) F(f(x,y),g(x,y)原式=F(x+y,x*y)，x+y=x*y，對(duì)于自然數(shù)x/y，此式真假不確定，故不是命題。 (2) F(f(x,a),y)F(g(x,y),z)代入各式= F(x+0,y)F(x*y,z)=F(x,y)F(x*y,z)確定F后: x=yx*y=z,真假難定,不是命題. 個(gè)體常元的值、個(gè)體變?cè)闹涤?、確定函數(shù)、謂詞公式的含義。 個(gè)體常元的值、個(gè)體變?cè)闹涤?、確定函數(shù)、謂詞公式的含義。例：個(gè)體變?cè)闹涤駾=N, 常元的a=0,函數(shù)

24、f(x,y)=x+y ,g(x,y)=x*y 謂詞F(x,y):x=y解釋下列各公式的含義： (3) F(g(x,y),g(y,z)將函數(shù)確定后:F(x*y,y*z)將謂詞確定后: x*y=y*z, 是否成立要看x,y,z的值,非命題! (4) xF(g(x,y),z)確定函數(shù)后:xF(x*y,z) 確定謂詞后:x(x*y=z)為0, 當(dāng)x=y=z1時(shí)(x*y=z)為0 xF(x)F(x0)F(x1). F(xk).(*) (*)式為0則左=0 xF(x)=1F(x0)=1, F(x1)=1. F(xk)=1.,若F(xi0)=0則 個(gè)體常元的值、個(gè)體變?cè)闹涤?、確定函數(shù)、謂詞公式的含義。例：

25、個(gè)體變?cè)闹涤駾=N, 常元的a=0,函數(shù)f(x,y)=x+y ,g(x,y)=x*y 謂詞F(x,y):x=y解釋下列各公式的含義： (5) xF(g(x,a),x)F(x,y)確定個(gè)體常量xF(g(x,0),x)F(x,y)確定函數(shù)后:xF(x*0,x)F(x,y)確定謂詞后:x(0=x) (x=y) 條件式的前式為假,無論后件為何,均為真 例：個(gè)體變?cè)闹涤駾=N, 常元的a=0, 因?yàn)槿Q量詞x是指?jìng)€(gè)體域中所有對(duì)象具有某性質(zhì)、或具有某相互關(guān)系。 存在量詞x是指?jìng)€(gè)體域中部分對(duì)象具有某性質(zhì)、或具有某相互關(guān)系 故當(dāng)個(gè)體域dom(X)=a1,a2,an有限,即n有限, xA(x)即為A(a1)

26、A(a2)A(an)。 xA(x)即為A(a1)A(a2)A(an)。 利用這兩個(gè)展開式，在解釋公式的含義時(shí)，可能會(huì)帶來某種便利！ 因?yàn)槿Q量詞x是指?jìng)€(gè)體域中所有對(duì)象具有某性質(zhì)、或具有 例題：個(gè)體域D=2,3，常元a=2，f(2)=3，f(3)=2 ，F(xiàn)(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 L(2,2)=L(3,3)=1, L(2,3)=L(3,2)=0， 求下列謂詞公式的值:(1) x(F(x)G(x,a)解：代入個(gè)體常元得x(F(x)G(x,2)，展開全稱量詞得(F(2)G(2,2)(F(3)G(3,2)，代入謂詞的值得(01)(11)

27、，即為0。 例題：個(gè)體域D=2,3，常元a=2， 例題：個(gè)體域D=2,3，常元a=2，f(2)=3，f(3)=2 ，F(xiàn)(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 L(2,2)=L(3,3)=1, L(2,3)=L(3,2)=0， 求下列謂詞公式的值:(2) x(F(f(x)G(x,f(x)解：展開存在量詞得(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)，代入函數(shù)值 (F(3)G(2,3)(F(2)G(3,2)，代入謂詞的值(11)(01)，即為1。 例題：個(gè)體域D=2,3，常元a=2， 例題：個(gè)體域D=2,3，常元a=2，f(2)=

28、3，f(3)=2 ，F(xiàn)(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 L(2,2)=L(3,3)=1, L(2,3)=L(3,2)=0， 求下列謂詞公式的值:(3) xyL(x,y)解：展開y得x(L(x,2)L(x,3)，展開x得(L(2,2)L(2,3)(L(3,2) L(3,3)，代入謂詞的值得(10)(01)，即為1。 例題：個(gè)體域D=2,3，常元a=2， 例題：個(gè)體域D=2,3，常元a=2，f(2)=3，f(3)=2 ，F(xiàn)(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 L(2,2)=L(3,3)=

29、1, L(2,3)=L(3,2)=0， 求下列謂詞公式的值:(3) xyL(x,y)代入謂詞的值得(10)(01)，即為1。(4) yx L(x,y)展開x得：y(L(2,y)L(3,y)，展y得：(L(2,2)L(3,2)( L(2,3)L(3,3)，代入謂詞值得(10)(01)，即為0。說明： x與y次序很重要！ 例題：個(gè)體域D=2,3，常元a=2，2.2 謂詞公式的類型 正如命題公式有永真/永假/可滿足一樣，謂詞公式也有這3種類型。 永真式(邏輯有效式):在任何解釋下均為真。 永假式(矛盾式):在任何解釋下均為假。 可滿足式:至少存在一種解釋下為真。說明： (1)命題邏輯,使用真值表可以

30、判斷一個(gè)公式的類型。 (2)在一階邏輯即謂詞邏輯中，不存在一個(gè)算法，在有限步內(nèi)判斷任意一個(gè)公式的類型。 (3)不可判定的！ (4)“任何解釋”如何窮盡？不可能，因此只能根據(jù)某些原則如“代換實(shí)例”，即“類比命題邏輯原則”。2.2 謂詞公式的類型謂詞公式的類型永真式(邏輯有效式):在任何解釋下均為真。永假式(矛盾式):在任何解釋下均為假?？蓾M足式:至少存在一種解釋下為真。代換實(shí)例： 設(shè)A0是含命題變?cè)猵1,p2,.,pn的命題公式，A1,A2,.,An是n個(gè)謂詞公式(其中個(gè)體常元/變?cè)?函數(shù)/謂詞公式都未確定含義)，將A0中pi的每次出現(xiàn)都換成Ai，所得公式A稱為A0的代換實(shí)例。A(x)A(x),

31、xA(x)xA(x)是pp代換實(shí)例.A(x)A(x),xA(x) x A(x)是pp的代換實(shí)例 謂詞公式的類型代換實(shí)例： 設(shè)A0是含命題變?cè)猵1,p2,.,pn的命題公式，A1,A2,.,An是n個(gè)謂詞公式(其中個(gè)體常元/變?cè)?函數(shù)/謂詞公式都未確定含義)，將A0中pi的每次出現(xiàn)都換成Ai，所得公式A稱為A0的代換實(shí)例。定理：命題重言式的代換實(shí)例都是永真式， 矛盾式的代換實(shí)例都是矛盾式。例題判斷公式F(x,y)(G(x,y)F(x,y)的類型。解：F(x,y)p, G(x,y)q， 得命題公式p(qp)， F(x,y)(G(x,y)F(x,y)是p(qp)的代換實(shí)例。 p(qp)p(qp)pp

32、q1，即為重言式, 故其代換實(shí)例F(x,y)(G(x,y)F(x,y)是永真式。 稱p(qp)為F(x,y)(G(x,y)F(x,y)的原型代換實(shí)例：2.2 謂詞公式： 設(shè)A0是含命題變?cè)猵1,p2,.,pn的命題公式，A1,A2,.,An是n個(gè)謂詞公式，用Ai處處代替A0中pi的每次出現(xiàn)，所得公式A稱為A0的代換實(shí)例。 定理：命題重言式的代換實(shí)例都是永真式， 矛盾式的代換實(shí)例都是矛盾式。(1) x(F(x)G(x) 不是永真/永假/可滿足 實(shí)-整(2) xF(x)(xyG(x,y)xF(x)，是 p(q p) 的代換實(shí)例， 而p(q p)p(q p) 1 故永真式(3)(xF(x)yG(y)

33、yG(y) 是(pq)q的代換實(shí)例， 而(pq)q pqq0 永假，故為永假2.2 謂詞公式：2.3謂詞公式等值演算：定義1 設(shè)A、B是兩個(gè)合法的謂詞公式,如果在任何解釋下兩個(gè)公式的真值都相等，則稱A與B等值記為AB。 因AB時(shí)在任何解釋下，公式A與公式B的真值都相同，故AB為永真式，故有定義2。定義2 設(shè)A、B是兩個(gè)合法謂詞公式，如果在任何解釋下，AB為永真式，則A與B等值，記為AB。 等值問題，轉(zhuǎn)換為永真問題， 通過代換實(shí)例原則找原型 并不是所有的謂詞公式有對(duì)應(yīng)的原型， 因此有些結(jié)論是無法證明，只能當(dāng)作顯然成立的公理。2.3謂詞公式等值演算：謂詞邏輯推理的公理：1、個(gè)體域?yàn)橛邢藜疍=a1,

34、a2,.,an,則有 xA(x) A(a1)A(a2) A(an) xA(x) A(a1)A(a2) A(an) 無法證明，只能理解！2.量詞的德摩律 xA(x)xA(x) x A(x)x A(x) 當(dāng)否定符“”移過時(shí)，變成、變成、變成、變成。謂詞邏輯推理的公理：2、量詞否定等值式-對(duì)于量詞的德摩律 設(shè)公式A(x)含自由出現(xiàn)的個(gè)體變項(xiàng)x,則 (1) xA(x) xA(x) 不是所有的個(gè)體有某性=有些個(gè)體沒有該特性 (2) xA(x) xA(x) 沒有x有某些特性=所有的沒有這個(gè)特性如： x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x)

35、 xy(F(x)M(x)H(x,y) xx(F(x)M(x)H(x,y)2、量詞否定等值式-對(duì)于量詞的德摩律1、個(gè)體域?yàn)橛邢藜疍=a1,a2,.,an,則有 xA(x) A(a1)A(a2) A(an) xA(x) A(a1)A(a2) A(an) 無法證明，只能理解！2.量詞的德摩律 xA(x)xA(x) x A(x)x A(x) 3、量詞分配律x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x) xB(x) 無法證明，只能理解！1、個(gè)體域?yàn)橛邢藜疍=a1,a2,.,an,則有1、個(gè)體域?yàn)橛邢藜疍=a1,a2,.,an,則有 xA(x) A(a1)A(a2) A(an) x

36、A(x) A(a1)A(a2) A(an)2.量詞的德摩律 xA(x)xA(x) x A(x)x A(x) 3、量詞分配律x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x) xB(x)4、量詞作用域的收縮與擴(kuò)張律 A(x)含自由x，B不含有自由出現(xiàn)的x，則有： (1)/x(A(x)B)/xA(x)B (2)/x(A(x)B)/xA(x)B1、個(gè)體域?yàn)橛邢藜疍=a1,a2,.,an,則有1、 xA(x) A(a1)A(a2) A(an) 個(gè)體域?yàn)橛邢?xA(x) A(a1)A(a2) A(an)2.量詞的德摩律 xA(x)xA(x) x A(x)x A(x) 3、量詞分配律

37、x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x) xB(x)4、量詞作用域的收縮與擴(kuò)張律 (1)/x(A(x)B)/xA(x)B A(x)含自由x (2)/x(A(x)B)/xA(x)B B不含有自由x5 、約束變?cè)拿?guī)則將A中某量詞轄域中變?cè)拿看渭s束出現(xiàn)，全部換成公式中未出現(xiàn)的字母，所得到的公式記為B，則AB 6 、置換規(guī)則：公式局部等值變換后,仍與原公式等值。1、 xA(x) A(a1)A(a2) A(an例題、x(A(x)B)xA(x)B x(A(x)B)x(A(x)B)pqpq的代換實(shí)例xA(x)B量詞作用域的收縮與擴(kuò)張律xA(x)B德摩律xA(x)B pq

38、pq的代換實(shí)例例題、x(A(x)B)xA(x)B 例題、 x(B A(x)BxA(x) x(BA(x)x(BA(x)pqpq的代換實(shí)例BxA(x)量詞作用域的收縮與擴(kuò)張律 BxA(x) pqpq的代換實(shí)例例題、 x(A(x)B) xA(x)Bx(A(x)B)x(A(x)B) pqpq的代換實(shí)例xA(x)B 量詞作用域的收縮與擴(kuò)張律xA(x)B 德摩律xA(x)B pqpq的代換實(shí)例例題、 x(B A(x)BxA(x) 例題、 x(B A(x)BxA(x) x(B A(x)x(B A(x)pqpq的代換實(shí)例BxA(x)量詞作用域的收縮與擴(kuò)張律BxA(x) pqpq的代換實(shí)例例題、 x(M(x)F

39、(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)德摩律x (M(x)F(x)德摩律x(M(x)F(x) pqpq的代換實(shí)例例題、 x(B A(x)BxA(x) 例題、 x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x) pqpq的代換實(shí)例x(M(x)F(x) 德摩律x (M(x)F(x) 德摩律x (M(x)F(x) pp的代換實(shí)例例題、 x(M(x)F(x)x(M(x)F例題、 xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x,y) 德摩律xy(F(x)G(y

40、)H(x,y) pqpq xy( (F(x)G(y)H(x,y)德摩律xy(F(x)G(y)H(x,y) ppxy(F(x)G(y)H(x,y) 結(jié)合律 例題、 xy(F(x)G(y)H(x,y)例題、 xy (F(x)G(y) L(x,y) xy (F(x)G(y)L(x,y) xy (F(x)G(y) L(x,y)xy(F(x)G(y) L(x,y)德摩律xy(F(x)G(y)L(x,y)德摩律xy(F(x)G(y)L(x,y) pqpq 例題、 xy (F(x)G(y) L(x,y)例1 將下面公式化成等值的公式,使其不含有既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。 xF(x,y,z)yG(x

41、,y,z)解：x在前件中是約束變?cè)诤蠹亲杂勺冊(cè)? y在前件中是自由變?cè)?，在后件是約束變?cè)菀桩a(chǎn)生歧義，故要改名！ 約束變?cè)拿?tF(t,y,z)sG(x,s,z)也可以對(duì)自由變?cè)拿?xF(x,s,z)yG(t,y,z)例1 將下面公式化成等值的公式,使其不含有既是約束出現(xiàn)又是自例 將下面公式化成等值的公式,使其不含有既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。 xF(x,y,z)yG(x,y,z)解：x在前件中是約束變?cè)?，在后件是自由變?cè)? y在前件中是自由變?cè)?，在后件是約束變?cè)?約束變?cè)拿?tF(t,y,z)sG(x,s,z)對(duì)自由變?cè)拿?xF(x,s,z)yG(t,y,z

42、) x(F(x,y)yG(x,y,z)解：y在前件是自由，在后件是約束，有歧義！ x(F(x,y)sG(x,s,z)例 將下面公式化成等值的公式,使其不含有既是約束出現(xiàn)又是自2.4 謂詞公式范式 定義：一個(gè)謂詞公式，如果量詞均在全式的開頭，它們的作用域延伸到整個(gè)公式的末尾，則該公式稱為前束范式，形如Q1x1Q2x2QkxkB，其中Qi為或，B中不含有數(shù)量詞。 如 xy(F(x)G(y)H(x,y) 是前束范式 x(F(x)y(G(y)H(x,y)不是！因B有量詞 定理1：任何邏輯公式可轉(zhuǎn)換為前束范式。 說明：利用代換實(shí)例，將、轉(zhuǎn)換為 用德摩律將否定深入到原子公式前面 用量詞轄域的擴(kuò)張與收縮律，

43、將量詞的前面，左移到最前面，可能還要對(duì)約束變?cè)獡Q名。2.4 謂詞公式范式2.4 謂詞公式范式定理1：任何邏輯公式可轉(zhuǎn)換為前束范式。 步驟： (1)剔除不起作用的量詞；(2)若約束變?cè)c自由變?cè)麆t約束變?cè)拿?3)如果與前面的約束變?cè)?，則后者改名；(4)利用代換實(shí)例，將、轉(zhuǎn)換表示；(5) 將否定深入到原子公式的前面；(6)利用量詞轄域的擴(kuò)張與收縮規(guī)律或利用量詞的分配律，將量詞移到最左邊 。2.4 謂詞公式范式2.4 謂詞公式范式例 公式xP(x)xQ(x)轉(zhuǎn)換為前束范式 xP(x)xQ(x)xP(x)yQ(y)后方約束變?cè)拿鹸P(x) yQ(y)條件式的代換實(shí)例xP(x)yQ(y)否

44、定到底xy(P(x)yQ(y)量詞轄域的擴(kuò)張或，顯然不唯一xP(x)xQ(x)xP(x)xQ(x)條件式的代換實(shí)例xP(x)xQ(x)德摩律x(P(x)Q(x)量詞的分配律2.4 謂詞公式范式2.4 謂詞公式范式例 xP(x,y) yQ(x,y)轉(zhuǎn)換為前束范式 xP(x,y) yQ(x,y)rP(r,y) sQ(x,s)約束變?cè)拿鹯P(r,y) sQ(x,s)轉(zhuǎn)換條件式rP(r,y) sQ(x,s)德摩律rs(P(r,y)Q(x,s)量詞轄域的擴(kuò)張2.4 謂詞公式范式例x(yA(x,y)xy(B(x,y)y(A(y,x)B(x,y)為前范式x(yA(x,y)xy(B(x,y)y(A(y,x)

45、B(x,y)x(yA(x,y)xy(B(x,y)r(A(r,x)B(x,r) 改名x(yA(x,y)xs(B(x,s)r(A(r,x)B(x,r) 改名x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 改名 書上錯(cuò)了x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 條件式x (yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 德摩律x (yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 同上x (yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) x (yA(x,y)ts (B(t,s)r(A(r,t)B(t,r) x (yA(

46、x,y)ts (B(t,s)r(A(r,t)B(t,r) x (yA(x,y)ts (B(t,s)r (A(r,t)B(t,r) x (yA(x,y)ts (B(t,s)r (A(r,t)B(t,r)xytsr(A(x,y) (B(t,s) (A(r,t)B(t,r)例x(yA(x,y)xy(B(x,y)y(A2.5 謂詞推理 引言：推理是永恒的話題，謂詞邏輯同樣要進(jìn)行推理，只是比命題邏輯更加復(fù)雜。 謂詞邏輯中不能使用真值表。 謂詞邏輯的等值式，其判斷也只能根據(jù)代換實(shí)例規(guī)則，沿用命題邏輯中的等值式。 因此只能使用自然推理的方法，即直接從前提出發(fā)，利用基本原則，不斷推出結(jié)論 謂詞邏輯自有的等值式

47、并不多，即使有 也是只能理解而無法證明的規(guī)律，如德摩律、分配律等。2.5 謂詞推理2.5 謂詞推理 定義1 若在各種解釋下A1A2A3AnB只能為真,則稱為前提A1,A2,An可推出結(jié)論B。 定義2 當(dāng)A1A2A3An為真時(shí)B為真，即 當(dāng)A1,A2,A3,An為真時(shí)B為真。 方法： 當(dāng)前提條件A1,A2,An為真時(shí)，利用等值式推出其他公式也為真，或利用謂詞推理規(guī)律，推出其他公式為真， 最終推出結(jié)論也為真。2.5 謂詞推理 常見的推理方法 一、謂詞邏輯的等值演算原則、規(guī)律： 命邏的代換實(shí)例、量詞德摩律、量詞分配律、量詞轄域的擴(kuò)張與收縮、約束變?cè)拿?。二、命題邏輯的推理規(guī)則的代換實(shí)例。 如假言推理

48、規(guī)則、傳遞律、合取與析取的性質(zhì)律、CP規(guī)則、反證法等。三、謂詞邏輯的推理公理xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x) 別反了 四條推理鐵律 常見的推理方法 三、謂詞邏輯推理公理:僅能理解左真時(shí)右真xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x) 別反了 四條推理鐵律全稱量詞的指定US或-：xA(x)A(x0) x0是論域中的任意個(gè)體 存在量詞的指定ES或-：xA(x)A(c) c為某個(gè)特定的個(gè)體，不是任意的個(gè)體全稱量詞的推廣UG或+：A(x0) xA(x) x0是論域中的任意個(gè)體 存在量詞的推廣EG或+：A(c) xA

49、(x) c為某個(gè)體 三、謂詞邏輯推理公理:僅能理解左真時(shí)右真例題 (x(H(x)O(x)H(c)O(c)， 亞里斯多德的三段論(1) x(H(x)O(x)為真(前提)(2) H(c)O(c) 為真(全稱指定x=c時(shí)為真)(3) H(c) 為真(前提)(4) O(c) 為真(2)(3)與假言推理代換實(shí)例) 通過“指定規(guī)則”將量詞去掉, 通過代換實(shí)例沿用命題邏輯的方法. 例題 (x(H(x)O(x)H(c)O(c)，例題 (x(H(x)O(x)H(c)O(c)， 亞里斯多德的三段論(1) x(H(x)O(x)為真(前提)(2) H(c)O(c) 為真(全稱指定x=c時(shí)為真)(3) H(c) 為真(前提)(4) O(c) 為真(2)(3)與假言推理代換實(shí)例) 通過“指定規(guī)則”將量詞去掉, 通過代換實(shí)例沿用命題邏輯的方法. 例題 (x(H(x)O(x)H(c)O(c)，例題 x(F(x)G(x),xF(x)xG(x)證明:(1)xF(x)為真 (前提)(2) F(c)為真 (存在指定,至少存在c使F(c)為真)(3) x(F(x)G(x)為真 (前提)(4) F(c)G(c)為真 (全稱指定,尤其x=c時(shí)為真)(5) G(c)為真 ( (2)