1、引言引言 命題邏輯命題邏輯好像功能強(qiáng)大，但還是有些問題難以解決。好像功能強(qiáng)大，但還是有些問題難以解決。 如楊圣洪要喝水、劉翔要喝水、姚明要喝水、姚晨要如楊圣洪要喝水、劉翔要喝水、姚明要喝水、姚晨要喝水、劉德華要喝水、喝水、劉德華要喝水、，可歸納為，可歸納為“某某要喝水某某要喝水”，無法表示。無法表示。 所有的人都要呼吸、喝水、吃飯所有的人都要呼吸、喝水、吃飯，“所有所有”如何如何表示呢？表示呢？ 有些人要升官、有些人要失戀有些人要升官、有些人要失戀，“有些有些”又如何又如何表示？表示？ 所有所有男人都會多男人都會多看看幾眼漂亮幾眼漂亮女人女人 所有所有女人都會多女人都會多喜歡喜歡漂亮的漂亮的衣

2、服衣服 又如有名又如有名三段論三段論：所有人都是要變老的，楊圣洪是人，：所有人都是要變老的，楊圣洪是人，所以楊圣洪也會變老的，無法表示所以楊圣洪也會變老的，無法表示。 為此為此需要我們學(xué)習(xí)新的邏輯工具需要我們學(xué)習(xí)新的邏輯工具-謂詞邏輯謂詞邏輯或一階邏輯或一階邏輯2.1基本概念基本概念 1、謂詞、謂詞 “某某要喝水某某要喝水”、“喜歡漂亮衣服喜歡漂亮衣服”、“喜歡喜歡帥哥帥哥”、“結(jié)婚生崽結(jié)婚生崽”都是所在句子的都是所在句子的謂語部分謂語部分。 命題邏輯命題邏輯中用大寫字母表示命題。中用大寫字母表示命題。 謂詞邏輯謂詞邏輯中用大寫字母表示中用大寫字母表示謂語部分謂語部分，如，如 用用W表示表示“

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

4、靠前的字母表示常量。常量。2.1基本概念基本概念 3、個(gè)體變元、個(gè)體變元 如如“某某某某”、“男人男人”、“女人女人”， 常用常用x,y,z,r,s,t等字母表中靠后的字母表示，等字母表中靠后的字母表示， 其他學(xué)科中，也是這樣表示，其他學(xué)科中，也是這樣表示， 因此因此“某某要喝水某某要喝水”表示為表示為W(x), ,x泛指所有的人，泛指所有的人， “ “女人喜歡漂亮衣服女人喜歡漂亮衣服”表示為表示為L(x,y)，x泛指泛指“女人女人”、y泛指泛指“衣服衣服”， “ “女人喜歡帥哥女人喜歡帥哥”表示為表示為H(y,z)，其中其中y泛指女人、泛指女人、z泛指帥哥。泛指帥哥。 “ “男人結(jié)婚生崽男人

5、結(jié)婚生崽”表示為表示為M(z)，z泛指男人。泛指男人。 2.1基本概念基本概念 4、全稱量詞、全稱量詞 為了表示為了表示“所有女人都喜歡漂亮的衣服所有女人都喜歡漂亮的衣服”、 “ “所有女人都喜歡帥哥所有女人都喜歡帥哥”等中等中 可能是可能是“ALL”的字母的字母A倒寫，表示倒寫，表示所有、全部所有、全部。 當(dāng)用當(dāng)用x泛指泛指“人人”，“所有人所有人”表示為表示為“ x”， “ “所有活人都要喝水所有活人都要喝水”表示為表示為 xW(x)。 當(dāng)用當(dāng)用x表示表示“女人女人”, ,y表示表示漂亮的衣服漂亮的衣服時(shí)，時(shí)， “ “所有女人所有女人”則表示為則表示為 x x、 “ “所有漂亮的衣服所有漂

6、亮的衣服”則表示為則表示為“ y”，因此，因此 “ “所有女人都喜歡漂亮的衣服所有女人都喜歡漂亮的衣服”表示為表示為 x yL(x,y)。 當(dāng)用當(dāng)用x表示表示“女人女人”, ,y表示帥哥時(shí)，表示帥哥時(shí)， “ “所有女人都喜歡帥哥所有女人都喜歡帥哥”表示為表示為 x yH(x,y)。 2.1基本概念基本概念 5、存在量詞、存在量詞 為了表示為了表示“有些男人結(jié)婚生崽有些男人結(jié)婚生崽”中中“有些有些”， 引入符號引入符號“ ”， 。 稱為稱為存在量詞存在量詞。 它是它是Exist的首字母，左旋的首字母，左旋180180度，度， 如用如用z表示表示“男人男人”，那么，那么 “ “有些男人有些男人”表

7、示為表示為“ z”， “ “有些男人結(jié)婚生崽有些男人結(jié)婚生崽”表示為表示為“ zM(z)”。2.1基本概念基本概念 6、謂詞公式、謂詞公式 將表示將表示全部全部的符號的符號“ ”，表示為，表示為部分部分的的“ ”稱為稱為量量詞詞， 將將單個(gè)謂詞單個(gè)謂詞公式如公式如W(x)，帶，帶量詞量詞的謂詞如的謂詞如 zM(z)， 謂詞謂詞W(x),M(z)中只有中只有1 1個(gè)個(gè)體變元個(gè)個(gè)體變元, , 常用來刻劃對象的常用來刻劃對象的。 謂詞謂詞L(x,y)、H(y,z)中有中有2 2個(gè)個(gè)體變元，稱為個(gè)個(gè)體變元，稱為2 2元元謂詞。謂詞。， 如喜歡，如喜歡， 類似如果有類似如果有n n個(gè)個(gè)體變個(gè)個(gè)體變元則稱

8、為元則稱為n n元元謂詞公式。謂詞公式。 個(gè)體變元的個(gè)體變元的取值取值范圍稱為范圍稱為“討論域討論域”， 如果如果沒有交待沒有交待討論域，表示對個(gè)體變元的討論域，表示對個(gè)體變元的取值范圍取值范圍，不做不做任何任何限制，泛指限制，泛指宇宙界宇宙界的萬物，稱為的萬物，稱為“全總個(gè)體全總個(gè)體域域”，常用大寫，常用大寫字母字母U表示。表示。 利用量詞、謂詞將自然語言轉(zhuǎn)換為謂詞公式利用量詞、謂詞將自然語言轉(zhuǎn)換為謂詞公式 例例1：(1)凡人都要呼吸凡人都要呼吸 (2)有的人用左手寫字。有的人用左手寫字。 解解：當(dāng)個(gè)體域?yàn)椋寒?dāng)個(gè)體域?yàn)椤叭祟惾祟悺睍r(shí)時(shí) xB(x),其中其中B(x)表示表示x人呼吸人呼吸bre

9、ath. xWL(x)，其中，其中WL(x)表示表示x用左邊寫字。用左邊寫字。 當(dāng)當(dāng)個(gè)體域個(gè)體域?yàn)槿倿槿倐€(gè)體域個(gè)體域(宇宙萬物組成宇宙萬物組成) x(H(x)B(x) H(x)表示個(gè)體表示個(gè)體x是人類是人類 x(H(x) WL(x)，WL(x)表示表示x用左邊寫字。用左邊寫字。 個(gè)體域不同，謂詞公式不同。個(gè)體域不同，謂詞公式不同。例例2 (1)任意任意x,x2-2x+1=(x-1)2. 有有x,使得使得x*5=3解：當(dāng)解：當(dāng)x的取值范圍即個(gè)體域?yàn)樽匀粩?shù)的取值范圍即個(gè)體域?yàn)樽匀粩?shù)N時(shí)時(shí) xE(x) E(x)表示表示x2-2x+1=(x-1)2 xF(x) F(x)表示表示x*5=3 當(dāng)當(dāng)x的

10、個(gè)體域?yàn)閷?shí)數(shù)的個(gè)體域?yàn)閷?shí)數(shù)R時(shí)，時(shí)，謂詞公式相同但真值不同謂詞公式相同但真值不同！例例3 (1)兔子比烏龜跑得快兔子比烏龜跑得快 (2)有的兔子比所有的烏龜跑得快有的兔子比所有的烏龜跑得快 (3)并不是所有的兔子都比烏龜跑得快并不是所有的兔子都比烏龜跑得快 (4)不存在跑得同樣快的兩只兔子不存在跑得同樣快的兩只兔子. 解解：H(x,y)表示表示x比比y跑得快跑得快. L(x,y)表示表示x與與y一樣快一樣快 R(x)表示表示x是兔子是兔子 T(x)表示表示x是烏龜是烏龜 (1) x y(R(x) T(y)H(x,y) (2) x y(R(x) T(y) H(x,y) (3) x y(R(x)

11、T(y)H(x,y) x y(R(x) T(y)H(x,y) (4) x y(R(x) R(y) L(x,y) x y(R(x) R(y) L(x,y)例例4任意兩個(gè)不相等實(shí)數(shù)，其平方和大于積的二倍。任意兩個(gè)不相等實(shí)數(shù)，其平方和大于積的二倍。 解解：個(gè)體域?yàn)椋簜€(gè)體域?yàn)槿倐€(gè)體域全總個(gè)體域即不對個(gè)體變元的取值做任即不對個(gè)體變元的取值做任何限制。何限制。 F(x)表示表示x是實(shí)數(shù)，是實(shí)數(shù)， G(x,y)表示表示x y， H(x,y)表示表示xy，則原話表示為，則原話表示為 x y (F(x) F(y) G(x,y)H(x2+y2,2xy)。 若用若用f(x,y)表示表示x2+y2，g(x,y)表示

12、表示2xy，則原話表示為，則原話表示為 (F(x) F(y) G(x,y)H(f(x,y),g(x,y) 因?yàn)閷τ趯?shí)數(shù)因?yàn)閷τ趯?shí)數(shù)x，y，(x2-2xy+y2)=(x-y)2， 當(dāng)當(dāng)x y時(shí)，有時(shí)，有(x-y)20， 故故(x2-2xy+y2)0， 故故x2+y22xy， 故故H(x2+y2,2xy) 為真為真 故原話正確，故以上公式的真值為故原話正確，故以上公式的真值為1 1。 故謂詞公式可出現(xiàn)個(gè)體變元故謂詞公式可出現(xiàn)個(gè)體變元,平方平方,乘、倍數(shù)、函數(shù)等乘、倍數(shù)、函數(shù)等。例例5表示表示“所有人都要變老的，楊圣洪是人，所所有人都要變老的，楊圣洪是人，所以楊圣洪也會變老的以楊圣洪也會變老的”。

13、解解：個(gè)體域?yàn)槿倐€(gè)體域，即對個(gè)體變元的?。簜€(gè)體域?yàn)槿倐€(gè)體域，即對個(gè)體變元的取值不做任何限。值不做任何限。 H(x)表示對象表示對象x是人類，是人類， O(x)表示對象表示對象x變老，變老， c表示個(gè)體常元表示個(gè)體常元“楊圣洪楊圣洪”，則，則 H(c)表示個(gè)體常元楊圣洪是人類，表示個(gè)體常元楊圣洪是人類， O(c)表示個(gè)體常元楊圣洪要變老，原句表示表示個(gè)體常元楊圣洪要變老，原句表示 ( x(H(x)O(x) H(c)O(c)。 該公式不僅有個(gè)體變元，還有個(gè)體常元該公式不僅有個(gè)體變元，還有個(gè)體常元 例例6表示表示“所有人都要死的，蘇格拉底是人，所所有人都要死的，蘇格拉底是人，所以蘇格拉底也會死以

14、蘇格拉底也會死”。 解解：個(gè)體域?yàn)槿倐€(gè)體域，即對個(gè)體變元的取：個(gè)體域?yàn)槿倐€(gè)體域，即對個(gè)體變元的取值不做任何限制。值不做任何限制。 H(x)表示對象表示對象x是人類，是人類， O(x)表示對象表示對象x要死的，要死的， c表示個(gè)體常元表示個(gè)體常元“蘇格拉底蘇格拉底”，則，則 H(c)表示個(gè)體常元蘇格拉底是人類，表示個(gè)體常元蘇格拉底是人類， O(c)表示個(gè)體常元蘇格拉底要死，原句表示表示個(gè)體常元蘇格拉底要死，原句表示 ( x(H(x)O(x) H(c)O(c)。 這兩個(gè)例題，語句不同，但是最后的謂詞公式這兩個(gè)例題，語句不同，但是最后的謂詞公式相同。相同。2.2、謂詞公式及解釋、謂詞公式及解釋

15、上節(jié)上節(jié)得到一些謂詞公式，得到一些謂詞公式，獲得一些結(jié)論，也有獲得一些結(jié)論，也有存在一些存在一些疑惑疑惑？ (1)謂詞公式有個(gè)體謂詞公式有個(gè)體常元常元、個(gè)體、個(gè)體變元變元，還可以有，還可以有個(gè)體變元的個(gè)體變元的表達(dá)式表達(dá)式，那么謂詞公式究竟，那么謂詞公式究竟還有還有哪些哪些形式，究竟什么的字符串是形式，究竟什么的字符串是合法的合法的謂詞公式？謂詞公式？ (2)同一句話有同一句話有二個(gè)不同二個(gè)不同的公式，那么這二個(gè)公的公式，那么這二個(gè)公式式等值等值嗎？嗎？ (3)不同的話擁有不同的話擁有同樣同樣的的謂詞公式謂詞公式，到底這二句，到底這二句話話有何共性有何共性？ (4)同一樣公式在同一樣公式在不同

16、的論域不同的論域下真值不同，究竟下真值不同，究竟如何確定一個(gè)公式的真值呢？如何確定一個(gè)公式的真值呢？ 2.2、謂詞公式及解釋、謂詞公式及解釋非邏輯符號非邏輯符號:個(gè)體常元、函數(shù)符號、謂詞符號個(gè)體常元、函數(shù)符號、謂詞符號邏輯符號邏輯符號:個(gè)體變元、量詞符號、聯(lián)結(jié)詞、逗號、個(gè)體變元、量詞符號、聯(lián)結(jié)詞、逗號、括號。括號。項(xiàng)的定義項(xiàng)的定義：個(gè)體常元與變元及其函數(shù)式為項(xiàng)。：個(gè)體常元與變元及其函數(shù)式為項(xiàng)。(1)個(gè)體常元和個(gè)體變元是項(xiàng)。個(gè)體常元和個(gè)體變元是項(xiàng)。(2)若若 (x1,x2, xn)是是n元函數(shù)元函數(shù),t1,t2,tn是是n個(gè)項(xiàng)，個(gè)項(xiàng)，則則 (t1,t2, tn)是項(xiàng)。是項(xiàng)。(3)有限次使用有限次

17、使用(2)得到的表達(dá)式是項(xiàng)。得到的表達(dá)式是項(xiàng)。原子公式原子公式： 設(shè)設(shè)R(x1,x2,xn)是是n元謂詞，元謂詞，t1,t2,tn是項(xiàng)，則是項(xiàng)，則R(t1,t2, tn)是原子公式。是原子公式。2.2、謂詞公式及解釋、謂詞公式及解釋項(xiàng)的定義項(xiàng)的定義：個(gè)體常元與變元及其函數(shù)式為項(xiàng)。：個(gè)體常元與變元及其函數(shù)式為項(xiàng)。原子公式原子公式： 設(shè)設(shè)R(x1,x2,xn)是是n元謂詞元謂詞，t1,t2,tn是項(xiàng)，則是項(xiàng)，則R(t1,t2, tn)是原子公式。是原子公式。合式謂詞公式合式謂詞公式： (1)原子公式是合式公式；原子公式是合式公式； (2)若若A是合式公式，則是合式公式，則( A)也是合式公式；也是

18、合式公式； (3)若若A,B合式，則合式，則A B, A B, AB , AB 合式合式 (4)若若A合式，則合式，則 xA、 xA合式合式 (5)有限次使用有限次使用(2)(4)得到的式子是合式。得到的式子是合式。2.2、謂詞公式及解釋、謂詞公式及解釋 (F(x) F(y) G(x,y)H(f(x,y),g(x,y)、 x y(R(x) T(y)H(x,y)、 x y(R(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)

19、不是合法不是合法的的公式。公式。 凡按照以上凡按照以上5 5條規(guī)則寫出的表達(dá)式，就是合法條規(guī)則寫出的表達(dá)式，就是合法謂詞公式謂詞公式( (也稱為也稱為合式公式合式公式) )。 不再拘泥不再拘泥于某個(gè)具體的于某個(gè)具體的自然自然語句。語句。 直接研究含義直接研究含義不確定不確定或或泛指泛指的的謂詞謂詞公式。公式。 從從形式上形式上研究研究合式公式合式公式的性質(zhì)。的性質(zhì)。2.2、謂詞公式及解釋、謂詞公式及解釋-個(gè)體變元的身份個(gè)體變元的身份量詞指導(dǎo)變元量詞指導(dǎo)變元： xA和和 xA中的中的x量詞轄域量詞轄域： xA和和 xA中的中的A為量詞為量詞 / 轄域轄域變元的約束出現(xiàn)變元的約束出現(xiàn)：指導(dǎo)變元的每

20、次出現(xiàn)：指導(dǎo)變元的每次出現(xiàn)(稱約束變元稱約束變元)。變元的自由出現(xiàn)變元的自由出現(xiàn)：不是約束出現(xiàn)的變元：不是約束出現(xiàn)的變元(稱自由變元稱自由變元) 。例題例題 x(F(x,y)G(x,z)解解： x是量詞是量詞 的指導(dǎo)變元。的指導(dǎo)變元。 (F(x,y)G(x,z)是量詞是量詞 的轄域的轄域 在在 (F(x,y)G(x,z)中中x是約束出現(xiàn)，出現(xiàn)是約束出現(xiàn)，出現(xiàn)2次。次。 在在(F(x,y)G(x,z)自由出現(xiàn)的變元自由出現(xiàn)的變元y/z，各一次。，各一次。 2.2、謂詞公式及解釋、謂詞公式及解釋-個(gè)體變元的身份個(gè)體變元的身份量詞指導(dǎo)變元量詞指導(dǎo)變元： xA和和 xA中的中的x量詞轄域量詞轄域： x

21、A和和 xA中的中的A為量詞為量詞 / 轄域轄域變元的約束出現(xiàn)變元的約束出現(xiàn)：指導(dǎo)變元的每次出現(xiàn)：指導(dǎo)變元的每次出現(xiàn)(稱約束變元稱約束變元)。變元的自由出現(xiàn)變元的自由出現(xiàn)：不是約束出現(xiàn)的變元：不是約束出現(xiàn)的變元(稱自由變元稱自由變元) 。 例題例題 x(F(x,y)G(x,z)例題例題 x(F(x)G(y)y(H(x) L(x,y,z)解：解： 量詞量詞 的指導(dǎo)變元的指導(dǎo)變元x, (F(x)G(y)是量詞是量詞 的轄域，其中的轄域，其中x是約束出現(xiàn)，是約束出現(xiàn)，y是是自由出現(xiàn)。自由出現(xiàn)。 量詞量詞 的指導(dǎo)變元的指導(dǎo)變元y, H(x) L(x,y,z)是量詞是量詞 的轄域，其中的轄域，其中x是自

22、由是自由2次，次，y是是約束出現(xiàn)。整個(gè)公式中是約束約束出現(xiàn)。整個(gè)公式中是約束1自由自由2次。次。2.2、謂詞公式及解釋、謂詞公式及解釋-個(gè)體變元的身份個(gè)體變元的身份 例題例題 分析分析 x(F(x)G(y)y(H(x) L(x,y,z)變元身份變元身份解解： x的轄域是：的轄域是：(F(x)G(y)，約束變元是，約束變元是x，x有有1次約次約束出現(xiàn)，束出現(xiàn)，y是自由變元，有是自由變元，有1次自由出現(xiàn)。次自由出現(xiàn)。 y的轄域是：的轄域是：H(x) L(x,y,z)，約束變元是，約束變元是y，y有有1次約次約束出現(xiàn)，束出現(xiàn)，x與與z是自由變元，各有是自由變元，各有1次自由出現(xiàn)。次自由出現(xiàn)。 盡管盡

23、管x在公式在公式 x(F(x)G(y)出現(xiàn)，又在出現(xiàn)，又在 y(H(x) L(x,y,z)出現(xiàn)，但兩個(gè)出現(xiàn)，但兩個(gè)x不是一回事，不是一回事， 只是恰巧二個(gè)名字相同而矣，只是恰巧二個(gè)名字相同而矣， 好比有好比有2 2個(gè)個(gè)李勇，一個(gè)是正坐在家里看電視的李勇，一個(gè)是正坐在家里看電視的“李勇李勇”，一個(gè)是在馬路上散步的一個(gè)是在馬路上散步的“李勇李勇”， 為了避免這種為了避免這種“誤會誤會”出現(xiàn)，要對出現(xiàn)，要對“約束變元約束變元”改名。改名。2.2、謂詞公式及解釋、謂詞公式及解釋-個(gè)體變元的身份個(gè)體變元的身份 例題例題 分析分析 x(F(x)G(y)y(H(x) L(x,y,z)變變元身份元身份解解：盡

24、管：盡管x在公式在公式 x(F(x)G(y)出現(xiàn)，又在出現(xiàn)，又在 y(H(x) L(x,y,z)出現(xiàn)，但兩個(gè)出現(xiàn)，但兩個(gè)x不是一回事，不是一回事， 只是恰巧二個(gè)名字相同而矣，只是恰巧二個(gè)名字相同而矣， 為避免這種為避免這種“誤會誤會”出現(xiàn)要對出現(xiàn)要對“約束變元約束變元”改改名。名。 將量詞將量詞 x的指導(dǎo)變元的指導(dǎo)變元x，x的每次約束出現(xiàn)換成的每次約束出現(xiàn)換成公式中未出現(xiàn)的公式中未出現(xiàn)的r。 將量詞將量詞 y指導(dǎo)變元指導(dǎo)變元y、約束變元、約束變元y的每次出現(xiàn)換的每次出現(xiàn)換成公式中未出現(xiàn)的成公式中未出現(xiàn)的s，則原式為，則原式為 r(F(r)G(y)s(H(x) L(x,s,z)， 所有約束變元與

25、自由變元均不重名，無誤會。所有約束變元與自由變元均不重名，無誤會。 2.2、謂詞公式及解釋、謂詞公式及解釋-個(gè)體變元的身份個(gè)體變元的身份 例題例題 分析分析 x y(P(x,y) Q(y,z)xP(x,y)作用域作用域與變元約束情況與變元約束情況 解解： x、 y的的作用域作用域是是(P(x,y) Q(y,z)， x的的作用域作用域是是P(x,y)。 將與將與自由變元自由變元同名同名約束變元約束變元yr， 將與將與前一個(gè)前一個(gè)同名同名約束變元約束變元x xs，則原公式，則原公式 x r(P(x,r) Q(r,z)sP(s,y) 2.2、謂詞公式及解釋、謂詞公式及解釋-個(gè)體變元的身份個(gè)體變元的身

26、份 例題例題 x(P(x)xQ(x,z)yR(x,y) Q(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ī)則：改名規(guī)則：一般僅對約束變元改名一般僅對約束變元改名 后出現(xiàn)者約束變元也要改名。后出現(xiàn)者約束變元也要改名。 方法方法：將量詞的指導(dǎo)變元，及轄域中約束變元：將量詞的指導(dǎo)變元，及轄域中約束變元每次約束出現(xiàn)，全部換成公式中未出現(xiàn)的字母。每次約束出現(xiàn)，全部換成公式中未出現(xiàn)的字母。2.2、謂詞公式及解釋、謂詞公式及解釋-個(gè)體變元的身份個(gè)體

27、變元的身份 閉公式閉公式：不含自由變元的謂詞公式不含自由變元的謂詞公式 。 x(F(x,y)G(x,z)因y,z是自由變元，故不是。 r(F(r)G(y)s(H(x) L(x,s,z) 因?yàn)閥,x,z自由故不是 x r(P(x,r) Q(r,z)sP(s,y) 因z與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自由故不是以下公式均沒有自由變元，均為閉公式： x y(R(x) T(y)H(x,y)、 x y(R(x) T(y)H(x,y)、x y(R(x) T(y)H(x,y)、 x y

28、(R(x) T(y) H(x,y)、x y(R(x) R(y) L(x,y)、 x y(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.22.2、謂詞公式及解釋、謂詞公式及解釋- -謂詞公式的真值謂詞公式的真值 前面我們學(xué)習(xí)前面我們學(xué)習(xí)“合式公式合式公式”時(shí)，說過不再拘泥于某個(gè)時(shí)，說過不再拘泥于某個(gè)具體的自然語句，從形式上研究合式公式的性質(zhì)。具體的自然語句，從形式上研究合式公式的性質(zhì)。 但謂詞公式是邏輯公式，它總得有一個(gè)真假呀？但謂詞公式是邏輯公式，它總得有一個(gè)真假呀？ 如何確定其真假呢？如何確定其真假呢？ 神

29、馬不能總是浮云？神馬不能總是浮云？ 總得落地?？偟寐涞亍?確定真值的方法：確定真值的方法： (1)(1)確定個(gè)體域，即個(gè)體的取值范圍，確定個(gè)體域，即個(gè)體的取值范圍，哪個(gè)范圍哪個(gè)范圍？ (2)(2)將個(gè)體常元指定為個(gè)體域的具體值。將個(gè)體常元指定為個(gè)體域的具體值。哪個(gè)對象哪個(gè)對象？ (3)(3)函數(shù)常元表示指定個(gè)體域中個(gè)體變元的項(xiàng)。函數(shù)常元表示指定個(gè)體域中個(gè)體變元的項(xiàng)。 (4)(4)用指定個(gè)體域中的對象來解釋各個(gè)原子公式。用指定個(gè)體域中的對象來解釋各個(gè)原子公式。 (5)(5)用原子公式的解釋來描述整個(gè)公式的含義。用原子公式的解釋來描述整個(gè)公式的含義。原義？原義？ 根據(jù)個(gè)體域中知識，判斷整個(gè)公式的含

30、義是否正確，根據(jù)個(gè)體域中知識，判斷整個(gè)公式的含義是否正確，若對則公式的真值為若對則公式的真值為1 1，否則為，否則為0 02.2、謂詞公式的解釋、謂詞公式的解釋-謂詞公式的真值謂詞公式的真值例題例題： x(F(x)G(x) 其中其中x的的取值范圍取值范圍是什么？是什么？ F(x)的的含義含義是什么？是什么？G(x)的的含義含義是什么？是什么？ 將這些問題確定后，表達(dá)式將這些問題確定后，表達(dá)式 x(F(x)G(x)的真值就確的真值就確定了，這就是公式的定了，這就是公式的解釋解釋。 dom(x)=D1=全總個(gè)體域全總個(gè)體域 F(x)表示表示x是人，是人，G(x)表示表示x是是黃種黃種人。人。 x(

31、F(x)G(x)：所有的人都是：所有的人都是黃種黃種人，人，值為值為F. dom(x)=D2=實(shí)數(shù)集實(shí)數(shù)集R F(x)表示表示x是自然數(shù)，是自然數(shù)，G(x)表示表示x是是整數(shù)整數(shù)。 x(F(x)G(x)：所有的自然數(shù)都是：所有的自然數(shù)都是整數(shù)整數(shù)，值為值為T.例例： x y (F(x) F(y) G(x,y)H(f(x,y),g(x,y) f(x,y),g(x,y)是函數(shù)變元，一元謂詞公式是函數(shù)變元，一元謂詞公式F(x),二二元謂詞元謂詞G與與H。 x與與y的的個(gè)體域個(gè)體域：全總個(gè)體域全總個(gè)體域。 F(x):x是是實(shí)數(shù)實(shí)數(shù) G(x,y):x y H(x,y):xy f(x,y)=x2+y2 g

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

33、的值域、確定函數(shù)確定函數(shù)、謂謂詞公式詞公式的含義。的含義。例例4：個(gè)體變元的值域：個(gè)體變元的值域D=N, 常元的常元的a=0,函數(shù)函數(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，對于自然數(shù)，對于自然數(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,真假

34、難定真假難定,不是命題不是命題. 個(gè)體常元的值個(gè)體常元的值、個(gè)體變元個(gè)體變元的值域、的值域、確定函數(shù)確定函數(shù)、謂詞公式謂詞公式的含義。的含義。例例：個(gè)體變元的值域：個(gè)體變元的值域D=N, 常元的常元的a=0,函數(shù)函數(shù)f(x,y)=x+y ,g(x,y)=x*y 謂詞謂詞F(x,y):x=y解釋下列各公式的含義解釋下列各公式的含義： (3) F(g(x,y),g(y,z)將函數(shù)確定后將函數(shù)確定后: F(x*y,y*z)將謂詞確定后將謂詞確定后: x*y=y*z, 是否成立要看是否成立要看x,y,z的值的值,非命題非命題! (4) xF(g(x,y),z)確定函數(shù)后確定函數(shù)后: xF(x*y,z)

35、 確定謂詞后確定謂詞后: x(x*y=z)為為0, 當(dāng)當(dāng)x=y=z1時(shí)時(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è)體變元的值域D=N, 常元的常元的a=0,函數(shù)函數(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è)體常量確定個(gè)體常量 xF(g(x,0),x)F(x,y)確定函數(shù)后確定函數(shù)后: x

36、F(x*0,x)F(x,y)確定謂詞后確定謂詞后: x(0=x) (x=y) 條件式的前式為假條件式的前式為假,無論后件為何無論后件為何,均為真均為真 因?yàn)橐驗(yàn)槿Q量詞全稱量詞 x是指個(gè)體域中是指個(gè)體域中所有對象所有對象具有某具有某性質(zhì)、或具有某相互關(guān)系性質(zhì)、或具有某相互關(guān)系。 存在量詞存在量詞 x是指個(gè)體域中部分是指個(gè)體域中部分對象具有對象具有某性質(zhì)、某性質(zhì)、或具有某相互關(guān)系或具有某相互關(guān)系 故故當(dāng)個(gè)體域當(dāng)個(gè)體域dom(X)=a1,a2,an有限有限,即即n有限有限, xA(x)即為即為A(a1) A(a2) A(an)。 xA(x)即即為為A(a1) A(a2) A(an)。 利用這兩個(gè)展

37、開式，在解釋公式的含義時(shí)，可利用這兩個(gè)展開式，在解釋公式的含義時(shí)，可能會帶來某種便利能會帶來某種便利！ 例題：例題：個(gè)體域個(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è)體常元個(gè)體常元得得 x(F(x) G(x,2)，展開展開全稱量詞全稱量詞得得(F(2) G(2,2) (F(3) G(3,2)，代入代入謂詞的值謂詞的值得得(0

38、 1) (1 1)，即為，即為0。 例題：例題：個(gè)體域個(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ù)值函數(shù)值 (F(3) G(2,3) (F(2) G(3,2)，代入代入謂詞謂詞的值的值(1 1) (0 1)，即為，即為1

39、。 例題：例題：個(gè)體域個(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， 求下列謂詞公式的值求下列謂詞公式的值:(3) x yL(x,y)解：解：展開展開 y y得得 x(L(x,2) L(x,3)，展開展開 x x得得(L(2,2) L(2,3) (L(3,2) L(3,3)，代入代入謂詞的值謂詞的值得得(1 0) (0 1)，即為，即為1。 例題：例題：個(gè)體域個(gè)體域D=2,3，常元常元a=2，f(2)=3，f(3)=

40、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) x yL(x,y)代入代入謂詞的值謂詞的值得得(1 0) (0 1)，即為，即為1。(4) y x L(x,y)展開展開 x x得得： y(L(2,y) L(3,y)，展展 y y得得：(L(2,2) L(3,2) ( L(2,3) L(3,3)，代入代入謂詞值謂詞值得得(1 0) (0 1)，即為，即為0。說明說明： x與與 y次序次序很重要！很重要！ 2.2 謂詞公式的類型謂詞公

41、式的類型 正如命題公式有永真正如命題公式有永真/永假永假/可滿足一樣，謂詞公式也可滿足一樣，謂詞公式也有這有這3種類型。種類型。 永真式永真式(邏輯有效式邏輯有效式):在任何解釋下均為真。在任何解釋下均為真。 永假式永假式(矛盾式矛盾式):在任何解釋下均為假。在任何解釋下均為假。 可滿足式可滿足式:至少存在一種至少存在一種解釋下為真。解釋下為真。說明說明： (1)命題邏輯命題邏輯,使用真值表可以判斷一個(gè)公式的類型。使用真值表可以判斷一個(gè)公式的類型。 (2)在一階邏輯即謂詞邏輯中，不存在一個(gè)算法，在有在一階邏輯即謂詞邏輯中，不存在一個(gè)算法，在有限步內(nèi)判斷任意一個(gè)公式的類型。限步內(nèi)判斷任意一個(gè)公式

42、的類型。 (3)不可判定的！不可判定的！ (4)“任何解釋任何解釋”如何窮盡？不可能，因此只能根據(jù)如何窮盡？不可能，因此只能根據(jù)某些某些原則如原則如“代換實(shí)例代換實(shí)例”，即，即“類比類比命題邏輯原則命題邏輯原則”。謂詞公式的類型謂詞公式的類型永真式永真式(邏輯有效式邏輯有效式):在任何解釋下均為真。在任何解釋下均為真。永假式永假式(矛盾式矛盾式):在任何解釋下均為假。在任何解釋下均為假。可滿足式可滿足式:至少存在一種至少存在一種解釋下為真。解釋下為真。代換實(shí)例代換實(shí)例： 設(shè)設(shè)A0是含命題變元是含命題變元p1,p2,.,pn的命題公式，的命題公式，A1,A2,.,An是是n個(gè)謂詞公式個(gè)謂詞公式(

43、其中個(gè)體常元其中個(gè)體常元/變元變元/函函數(shù)數(shù)/謂詞公式都未確定含義謂詞公式都未確定含義)，將，將A0中中pi的每次出的每次出現(xiàn)都換成現(xiàn)都換成Ai，所得公式，所得公式A稱為稱為A0的代換實(shí)例。的代換實(shí)例。A(x)A(x), xA(x)xA(x)是是pp代換實(shí)例代換實(shí)例.A(x)A(x), xA(x) x A(x)是是pp的代換實(shí)的代換實(shí)例例 代換實(shí)例代換實(shí)例： 設(shè)設(shè)A0是含命題變元是含命題變元p1,p2,.,pn的命題公式，的命題公式，A1,A2,.,An是是n個(gè)謂詞公式個(gè)謂詞公式(其中個(gè)體常元其中個(gè)體常元/變元變元/函數(shù)函數(shù)/謂詞公式都未謂詞公式都未確定含義確定含義)，將，將A0中中pi的每次

44、出現(xiàn)都換成的每次出現(xiàn)都換成Ai，所得公式，所得公式A稱為稱為A0的代換實(shí)例。的代換實(shí)例。定理定理：命題重言式的代換實(shí)例都是永真式，：命題重言式的代換實(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í)例。的代換實(shí)例。 p(qp)p ( q p)p pq1，即為重言式，即為重言式, , 故其代換實(shí)例故其代換實(shí)例F(x,y)(G(x,y)F(x,y)是永真式。是永

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

46、 xF(x)，是，是 p(q p) 的代換實(shí)例，的代換實(shí)例， 而而p(q p) p ( q p) 1 故故永真式永真式(3) ( xF(x) yG(y) yG(y) 是是 (pq) q的的代換實(shí)例代換實(shí)例， 而而 (pq) q pq q0 永假，永假，故為永假故為永假2.3謂詞公式等值演算謂詞公式等值演算：定義定義1 設(shè)設(shè)A、B是兩個(gè)是兩個(gè)合法的謂詞合法的謂詞公式公式,如果在任何解釋下如果在任何解釋下兩個(gè)公式的兩個(gè)公式的真值真值都相等，則稱都相等，則稱A與與B等值等值記為記為AB。 因因AB時(shí)在任何解釋下，公式時(shí)在任何解釋下，公式A與公式與公式B的真值都相的真值都相同，故同，故AB為永真式，故

47、有定義為永真式，故有定義2。定義定義2 設(shè)設(shè)A、B是兩個(gè)合法謂詞公式，如果在任何解釋下，是兩個(gè)合法謂詞公式，如果在任何解釋下，AB為永真式，則為永真式，則A與與B等值，記為等值，記為AB。 等值等值問題，轉(zhuǎn)換為問題，轉(zhuǎn)換為永真永真問題，問題， 通過通過代換實(shí)例代換實(shí)例原則找原則找原型原型 并不是所有的謂詞公式有對應(yīng)的原型，并不是所有的謂詞公式有對應(yīng)的原型， 因此有些結(jié)論是無法證明，只能當(dāng)作顯然成立的公理。因此有些結(jié)論是無法證明，只能當(dāng)作顯然成立的公理。謂詞邏輯推理的公理：謂詞邏輯推理的公理：1、個(gè)體域?yàn)閭€(gè)體域?yàn)橛邢藜邢藜疍=a1,a2,.,an,則有則有 xA(x) A(a1) A(a2)

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

49、有這個(gè)特性所有的沒有這個(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) x y(F(x) M(x)H(x,y) x x (F(x) M(x)H(x,y)1、個(gè)體域?yàn)閭€(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)x A(x) x A(x)x A(x) 3、量詞分配律量詞分配律 x(A(x) B(x)xA(x)xB(x) x(

50、A(x) B(x)xA(x) xB(x) 無法證明，只能理解！無法證明，只能理解！1、個(gè)體域?yàn)閭€(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)x A(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ò)張律量詞作用域的收縮與擴(kuò)張律 A(x)含含自由自由x，B不含有不含有自由出現(xiàn)的自由出現(xiàn)的x，則有：，則有： (1) / x(A(x) B)

51、/ xA(x) B (2) / x(A(x) B)/ xA(x) B1、 xA(x) A(a1) A(a2) A(an) 個(gè)體域?yàn)閭€(gè)體域?yàn)橛邢抻邢?xA(x) A(a1) A(a2) A(an)2.量詞的德摩律量詞的德摩律 xA(x)x A(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ò)張律量詞作用域的收縮與擴(kuò)張律 (1) / x(A(x) B)/ xA(x) B A(x)含含自由自由x (2) / x(A(x) B)/ xA(x) B B不含有自由不含有自由x5 、約束

52、變元改名規(guī)則約束變元改名規(guī)則將將A中某量詞轄域中變元的中某量詞轄域中變元的每次約束每次約束出現(xiàn)，全部換成公出現(xiàn)，全部換成公式中式中未出現(xiàn)未出現(xiàn)的字母，所得到的公式記為的字母，所得到的公式記為B，則，則AB 6 、置換規(guī)則：公式局部等值變換后置換規(guī)則：公式局部等值變換后,仍與原公式等值。仍與原公式等值。例題、例題、 x(A(x)B)xA(x)B x(A(x)B)x( A(x) B)pqpq的代換實(shí)例x A(x) B量詞作用域的收縮與擴(kuò)張律xA(x) B德摩律xA(x)B pqpq的代換實(shí)例例題例題、 x(B A(x)BxA(x) x(BA(x)x( B A(x)pqpq的代換實(shí)例BxA(x)量詞

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

54、x)德摩律德摩律x(M(x)F(x) pqp q的代換實(shí)例的代換實(shí)例例題例題、 x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x( M(x) F(x) pqp q的的代換實(shí)例代換實(shí)例x ( M(x) F(x) 德摩律德摩律x (M(x)F(x) 德摩律德摩律x (M(x)F(x) pp的的代換實(shí)例代換實(shí)例例題例題、 x y(F(x) G(y)H(x,y) x y(F(x) G(y)H(x,y) x y(F(x) G(y)H(x,y)x y (F(x) G(y)H(x,y) 德摩律德摩律x y ( (F(x) G(y) H(x,y) pqp q x y( (F(x) G(y)H(x

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

56、z)解：解：x在前件中是約束變元，在后件是自由變元在前件中是約束變元，在后件是自由變元, y在前件中是自由變元，在后件是約束變元，在前件中是自由變元，在后件是約束變元，容易產(chǎn)生歧義，故要改名！容易產(chǎn)生歧義，故要改名！ 約束變元約束變元改名：改名： tF(t,y,z)sG(x,s,z)也可以對也可以對自由變元自由變元改名：改名： xF(x,s,z)yG(t,y,z)例例 將下面公式化成將下面公式化成等值等值的公式的公式,使其不含有既是使其不含有既是約束出現(xiàn)又是約束出現(xiàn)又是自由出現(xiàn)自由出現(xiàn)的個(gè)體變項(xiàng)。的個(gè)體變項(xiàng)。 xF(x,y,z)yG(x,y,z)解：解：x在前件中是約束變元，在后件是自由變元在

57、前件中是約束變元，在后件是自由變元, y在前件中是自由變元，在后件是約束變元，在前件中是自由變元，在后件是約束變元， 約束變元約束變元改名：改名： tF(t,y,z)sG(x,s,z)對對自由變元自由變元改名：改名： xF(x,s,z)yG(t,y,z) x(F(x,y)yG(x,y,z)解：解：y在前件是自由，在后件是約束，有歧義！在前件是自由，在后件是約束，有歧義！ x(F(x,y)sG(x,s,z)2.4 謂詞公式范式謂詞公式范式 定義定義：一個(gè)謂詞公式，如果量詞均在全式的開：一個(gè)謂詞公式，如果量詞均在全式的開頭，它們的作用域延伸到整個(gè)公式的末尾，則該頭，它們的作用域延伸到整個(gè)公式的末尾

58、，則該公式稱為公式稱為前束范式前束范式，形如形如Q1x1Q2x2QkxkB，其，其中中Qi為為 或或 ，B中不含有中不含有數(shù)量詞數(shù)量詞。 如如 x y(F(x) G(y)H(x,y) 是前束范式是前束范式 x(F(x)y(G(y) H(x,y)不是！因不是！因B有量詞有量詞 定理定理1：任何邏輯公式可轉(zhuǎn)換為前束范式。：任何邏輯公式可轉(zhuǎn)換為前束范式。 說明說明：利用代換實(shí)例，將：利用代換實(shí)例，將、轉(zhuǎn)換為轉(zhuǎn)換為 2.4 謂詞公式范式謂詞公式范式定理定理1：任何邏輯公式可轉(zhuǎn)換為前束范式。：任何邏輯公式可轉(zhuǎn)換為前束范式。 步驟步驟： 2.4 謂詞公式范式謂詞公式范式例例 公式公式 xP(x)xQ(x)

59、轉(zhuǎn)換為前束范式轉(zhuǎn)換為前束范式 后方約束變元改名條件式的代換實(shí)例否定到底量詞轄域的擴(kuò)張條件式的代換實(shí)例德摩律量詞的分配律2.4 謂詞公式范式謂詞公式范式例例 2.5 謂詞推理謂詞推理 引言引言：推理推理是永恒的是永恒的話題話題，謂詞邏輯同樣要進(jìn)，謂詞邏輯同樣要進(jìn)行推理，只是比命題邏輯行推理，只是比命題邏輯更加復(fù)雜更加復(fù)雜。 謂詞邏輯中謂詞邏輯中不能不能使用使用真值表真值表。 謂詞邏輯的謂詞邏輯的等值式等值式，其判斷也只能根據(jù)，其判斷也只能根據(jù)代換實(shí)代換實(shí)例規(guī)則例規(guī)則，沿用沿用命題邏輯中的等值式。命題邏輯中的等值式。 因此只能使用因此只能使用自然推理自然推理的方法，即的方法，即直接直接從從前提前提出發(fā)，利用出發(fā)，利用基本原則基本原則，不斷，不斷推出結(jié)論推出結(jié)論 謂詞邏輯謂詞邏輯自有自有的等值式并不多，即使有的等值式并不多，即使有 也是也是只能只能理解而理解而無法無法證明的規(guī)律，如證明的規(guī)律，如德摩律德摩律、分配律等。分配律等。2.5 謂詞推理謂詞推理 定義定義1 若在若在各種解釋各種解釋下下A1 A2 A3 AnB只只能為真能為真,則稱為前提則稱為前提A1,A2,An可推出結(jié)論可推出結(jié)論B。 定義定義2 當(dāng)當(dāng)A1 A2 A3 An為真時(shí)為真時(shí)B為真，即為真，即 當(dāng)當(dāng)A1,A2,A3,An為真時(shí)為真時(shí)B為真。為真。 方法方法： 當(dāng)前提條件當(dāng)前提條件A1,A2,An為真時(shí)，為真時(shí)，利用利