第二章 謂詞邏輯1

1、2/44 離散數(shù)學(xué) 第二章 謂詞邏輯 3/44 謂詞邏輯的引入 在命題邏輯中，試進(jìn)行下列推理: “蘇格拉底三段論”： 凡人都是要死的， P 蘇格拉底是人， Q 所以蘇格拉底是要死的。R (PQ)R 命題邏輯中，命題被當(dāng)作一個(gè)基 本的，不可分割的單位，只研究 由原子命題和聯(lián)接詞所組成的復(fù) 合命題，沒(méi)有研究命題內(nèi)部的內(nèi) 部結(jié)構(gòu)以及 命題之間的內(nèi)在關(guān)系 。 4/44 類(lèi)似的還有很多，例如： 所有軟件學(xué)院的學(xué)生在畢業(yè)之前都要通過(guò)離散數(shù)學(xué)考試，王思奇是 軟件學(xué)院的學(xué)生，所以王思奇在畢業(yè)之前需要通過(guò)離散數(shù)學(xué)考試 。 所有的正整數(shù)都大于0，3是正整數(shù)，所以3大于0。 本章介紹的謂詞邏輯，對(duì)原子命題的成份、結(jié)

2、構(gòu)和原子命題間的共 同特性等作了進(jìn)一步分析。引入了個(gè)體詞、謂詞、量詞、謂詞公 式等概念，在此基礎(chǔ)上研究謂詞公式間的等值關(guān)系和蘊(yùn)含關(guān)系， 并且對(duì)命題邏輯中的推理規(guī)則進(jìn)行擴(kuò)充和進(jìn)行謂詞演繹。 4/9 本章內(nèi)容 謂詞、個(gè)體、量詞 合式謂詞公式 自由變?cè)图s束變?cè)?含有量詞的等價(jià)式和永真蘊(yùn)含式 謂詞邏輯中的推理理論 前束范式、斯柯林范式 5/44 2.1謂詞演算 原子命題被分解為謂詞和個(gè)體兩部分。 個(gè)體：可以獨(dú)立存在的事物 。 老師，計(jì)算機(jī)，證書(shū)，道德，智商等。 謂詞：用來(lái)刻劃個(gè)體的性質(zhì)或個(gè)體之間關(guān)系的詞稱(chēng)為謂詞，刻劃 一個(gè)個(gè)體性質(zhì)的詞稱(chēng)為一元謂詞；刻劃n個(gè)個(gè)體之間關(guān)系的詞 稱(chēng)為n元謂詞。 本質(zhì)上是把

3、數(shù)學(xué)中的邏輯論證 加以符號(hào)化。 6/44 謂詞和個(gè)體 例： （1）李明是學(xué)生； （2）張亮比陳華高； （3）陳華坐在張亮與李明之間。 個(gè)體：李明，張亮，陳華 謂詞：是學(xué)生； 比高； 坐在 和之間 一元謂詞： 是學(xué)生 二元謂詞： 比高 三元謂詞： 坐在 和之間 7/44 謂詞和個(gè)體 （1）李明是學(xué)生； （2）張亮比陳華高； （3）陳華坐在張亮與李明之間。 一般用大寫(xiě)的英文字母表示謂詞，而用小 寫(xiě)的英文字母表示個(gè)體。 上述命題可分別表示為 Q(a),P(b,c),R(c,b,a) 一般地，由n個(gè)個(gè)體和n元謂詞所組成的命 題可表示為F（a1,a2, ,an）,其中F表 示n元謂詞, a1,a2, ,

4、an 分別表示n個(gè) 個(gè)體。 注意：a1,a2, ,an的排列次序是重要 的。 8/44 謂詞和個(gè)體 對(duì)于F（a1,a2, ,an），如果括號(hào)內(nèi)的 個(gè)體是抽象的可變化的，那么F（a1,a2, ,an）稱(chēng)為n元原子謂詞公式或n元命題 函數(shù)。 注意：命題的n元謂詞表示形式和n元命題 函數(shù)不同? a:張明。 命題函數(shù)：P(x) x是學(xué)生。 謂詞表示形式:P(a) 張明是學(xué)生。 9/44 個(gè)體域 個(gè)體域可以是有限的，也可以是無(wú)限的。所有個(gè)體域的總和叫作 全總個(gè)體域。以某個(gè)個(gè)體域?yàn)樽兓秶淖冊(cè)袀€(gè)體變?cè)?個(gè)體域的變換范圍影響到謂詞公式的真假 R(x)：x是大連理工大學(xué)軟件學(xué)院的學(xué)生 如果x的討論范圍是

5、大工軟件學(xué)院某個(gè)班級(jí)的學(xué)生 如果x的討論范圍是某個(gè)幼兒園里的小朋友 如果x的討論范圍是大連的所有市民 任何個(gè)體的變化都有一個(gè) 范圍，這個(gè)變化范圍稱(chēng)為 個(gè)體域(或論域)。 永真 永假 可滿(mǎn)足 10/44 謂詞的階 在謂詞 中，如果個(gè)體變 元是一些簡(jiǎn)單的事物，那么P為一階謂詞 ； 若個(gè)體變?cè)杏幸恍┦且浑A謂詞，那么P 為二階謂詞；二階以上遞推。 12 ( ,) n P x xx 本門(mén)課程僅研究一 階謂詞 11/44 量詞 使用前面介紹的謂詞和個(gè)體變?cè)€不足 以描述自然界的所有命題。 例： 描述命題“所有的正整數(shù)都大于0”以及命 題“有些正整數(shù)是素?cái)?shù)”。 量詞的引入：量詞指在命題里表示數(shù)量的 詞。

6、 12/44 全稱(chēng)量詞 符號(hào)“ ”表示命題：“對(duì)于個(gè) 體域中所有個(gè)體x，謂詞P(x)均為T(mén)”。其 中“ ”叫作全稱(chēng)量詞，讀作“對(duì)于 所有的x”。謂詞P(x)稱(chēng)為全稱(chēng)量詞的轄域 或作用范圍。 例如： 所有的人都是要死的 令D(x)：x 是要死的。 則命題可表示為 x D(x) 取個(gè)體域?yàn)槿w人的集合，是真命題 。 所有的正整數(shù)都是素?cái)?shù)； 令 P(x)：x 是素?cái)?shù) 則命題可表示成 x P(x) 取個(gè)體域?yàn)檎麛?shù)集，是假命題。 () ( )x P x ()x 13/44 存在量詞 符號(hào)“ ”表示命題：“在個(gè)體 域中存在某些個(gè)體使謂詞P(x)為T(mén)”其中“ ”叫作存在量詞，讀作“存在x”。謂詞 P(x)

7、稱(chēng)為存在量詞的轄域或作用范圍。 例如： 有些正整數(shù)是素?cái)?shù)； 令 P(x)：x 是素?cái)?shù) 則命題可表示成 x P(x) 取個(gè)體域?yàn)檎麛?shù)集，是真命題 。 () ( )x P x ()x 13/44 存在唯一量詞! 符號(hào)“ ”表示命題：“在個(gè)體 域中存在一個(gè)且只存在一個(gè)個(gè)體使謂詞 P(x)為T(mén)”其中“ ”叫作存在唯一量 詞，讀作“恰有一個(gè)x”。謂詞P(x)稱(chēng)為存 在量詞的轄域或作用范圍。 例如： 恰有一個(gè)正整數(shù)是素偶數(shù)； 令 P(x)：x 是素偶數(shù) 則命題可表示成 !x P(x) 取個(gè)體域?yàn)檎麛?shù)集，是真命題 。 ( ! ) ( )x P x ( ! )x 14/44 量詞 量詞本身不是一個(gè)獨(dú)立的邏

8、輯概念，可以 用 聯(lián)結(jié)詞取代。 設(shè)個(gè)體域 ， 謂詞可以表示成以下形式： 由量詞確定的命題真值與個(gè)體域有關(guān)。 令 P(x)：x 是素?cái)?shù) 則 x P(x)，如果取個(gè)體域?yàn)樗財(cái)?shù)集， 為真；如果個(gè)體域?yàn)檎麛?shù)集，為假。 , 12 : , n S Sa aa 12 () ( )()()() n x A xA aA aA a 12 () ( )()()() n x A xA aA aA a ( ! ) ( )()()( ( )()x A xcx A xxc 15/44 量詞 為了方便起見(jiàn)，個(gè)體域一律用全總個(gè)體域 ，每個(gè)個(gè)體變?cè)恼嬲兓秶鷦t用一個(gè) 特性謂詞來(lái)刻劃。 注意：對(duì)于全稱(chēng)量詞應(yīng)使用單條件邏輯聯(lián) 結(jié)

9、詞；對(duì)于存在量詞應(yīng)使用邏輯聯(lián)結(jié)詞合 取。 R(x): x是自然數(shù)；P(x): x大于0. ()( ( )( )x R xP x ()( ( )( )x R xP x 以后不加強(qiáng)調(diào)個(gè)體域均指 全總個(gè)體域 16/44 量詞 全稱(chēng)量詞和存在量詞不僅可以單獨(dú)出現(xiàn)， 還可以組合形式出現(xiàn)。 對(duì)于二元謂詞P(x,y)，可能有以下幾種量 化的可能： ()() ( , ),()() ( , ) ()() ( , ),()() ( , ) ()() ( , ),()() ( , ) ()() ( , ),()() ( , ) xy P x yxy P x y xy P x yxy P x y yx P x yyx

10、 P x y yx P x yyx P x y 17/44 組合量詞的含義 設(shè)A(x,y)表示x,y同姓， x的個(gè)體域是1班同學(xué)，y的個(gè)體域是2班同學(xué) 。 ：1班任何一個(gè)同學(xué)與2班的所有同學(xué)同姓； ：2班任何一個(gè)同學(xué)與1班的所有同學(xué)同姓； ：對(duì)1班的任意一個(gè)同學(xué)，2班都有人跟他同姓； ：存在一個(gè)2班同學(xué)和1班的所有同學(xué)同姓。 ()() ( , )xy A x y ()() ( , )yx A x y ()() ( , )xy A x y ()() ( , )yx A x y ()() ( , )()() ( , )xy A x yyx A x y 翻譯時(shí)從左向右 18/44 合式謂詞公式 若P

11、為不能再分解的n元謂詞變?cè)?，x1, x2,xn是個(gè)體變?cè)?，則稱(chēng)P(x1, x2,xn)為原子公式或原子謂詞公式。當(dāng) n=0時(shí)， P表示命題變?cè)丛用}公式 。所以，命題邏輯實(shí)際上是謂詞邏輯的特 例。 由原子謂詞公式出發(fā)，通過(guò)命題聯(lián)結(jié)詞， 可以組成復(fù)合謂詞公式，叫分子謂詞公式 。 19/44 合式謂詞公式 定義： （1）原子謂詞公式是合式公式； （2）若A是合式的公式，則 A也是合式公 式； （3）若A和B都是合式公式，則A B, A B, A B,A B 也都是合式公式； （4） 如果A是合式的公式，x是任意變?cè)?且A中有 或 出現(xiàn)，則 和 都是合式公式； （5）當(dāng)且僅當(dāng)有限次使用規(guī)則（1

12、）（4） 由邏輯聯(lián)結(jié)詞、圓括號(hào)構(gòu)成的有意義的字符串 是合式公式。 () x() x() ( )x A x() ( )x A x 20/44 自由變?cè)图s束變?cè)?在謂詞公式中，如果有形如 或者 ，則稱(chēng)它們是x的約束部 分。 每個(gè)量詞后面的最短公式，稱(chēng)為量詞的轄 域。 約束變?cè)阂粋€(gè)變?cè)舫霈F(xiàn)在包含這個(gè)變 元的量詞(全稱(chēng)量詞或存在量詞)的轄域之 內(nèi)，則該變?cè)Q(chēng)為約束變?cè)?，其出現(xiàn)稱(chēng)為 約束出現(xiàn)。 自由變?cè)鹤冊(cè)姆羌s束出現(xiàn)叫作自由出 現(xiàn)，該變?cè)凶髯杂勺冊(cè)?() ( )x A x () ( )x A x 21/44 自由變?cè)图s束變?cè)?(1) () ( , ) (2) ()( ( )() ( ,

13、) (3) ()()( ( , )( , )()( ( , ) (4) ()( ( )() ( , )() ( , )( , ) x P x y x P xy Q x y xy P x yQ y zx P x y x P xx Q x zy R x yQ x y () ( )() ( , )() ( , )( , )x P xx Q x zy R x yS x y 22/44 自由變?cè)图s束變?cè)?從約束變?cè)母拍羁芍?，謂詞P(x)的量化 ，就是從變?cè)獂的整個(gè)個(gè)體域著眼，對(duì)性 質(zhì)P(x)所作的一個(gè)全稱(chēng)判斷或特稱(chēng)判斷。 其結(jié)果是將謂詞變成一個(gè)命題。因此， 和 可以看成消元運(yùn)算。 對(duì)n元謂詞P(x1

14、, x2,xn)量化后，假設(shè) 有k個(gè)自由變?cè)瑒t降為k元謂詞。 ()x ()x () ( , , )x P x y z ()()( ( , , )yx P x y z 二元謂詞 一元謂詞 23/44 自由變?cè)图s束變?cè)?一般情況下給定一個(gè)謂詞公式A(x)，僅表 明在該公式中只有一個(gè)自由變?cè)?，但并?限制在該公式中還存在若干約束變?cè)?以下各式都可以寫(xiě)成A(x)： (1) ()( ( )( , ) (2) () ( )( ) (3) () ( )( ) (4) () ( , )( ) y P yQ x y x R xS x y S yS x y P x yQ x 23/44 自由變?cè)图s束變?cè)?

15、定義 若公式A中不含自由出現(xiàn)的個(gè)體變?cè)瑒t稱(chēng)A為封閉的公 式，簡(jiǎn)稱(chēng)閉式. 例如，xy(F(x)G(y)H(x,y) 為閉式， 而 x(F(x)G(x,y) 不是閉式 24/44 謂詞公式的解釋 在命題邏輯中對(duì)一個(gè)公式的解釋?zhuān)菍?duì)每 個(gè)命題變?cè)M(jìn)行取值指派，如果公式有n 個(gè)變?cè)?，則有2n種解釋。 謂詞公式的解釋?zhuān)婕暗矫}變?cè)?、謂詞 變?cè)?、個(gè)體變?cè)?、符?hào)函數(shù) 真值表法不可行 25/44 謂詞公式的解釋 定義：設(shè)A的個(gè)體域是D，如果用一組謂 詞常量、命題常量和A中的個(gè)體及函數(shù)符 號(hào)（將它們簡(jiǎn)記為I）代換公式A中相應(yīng)的 變?cè)?，則該公式A轉(zhuǎn)化成一個(gè)命題，可以 確定其真值（記作P）。稱(chēng)I為公式A在D 中

16、的解釋?zhuān)ɑ蛑概桑?，稱(chēng)P為公式A關(guān)于 解釋I的真值。 25/44 謂詞公式的解釋 yxyxF :),( 0 a yxyxgyxyxf ),(,),( 例例6 給定解釋給定解釋 I 如下：如下： (a) 個(gè)體域個(gè)體域 D=R (b) (c) (d) 寫(xiě)出下列公式在寫(xiě)出下列公式在I下的解釋下的解釋, 并指出它的真值并指出它的真值. (1) xF(f(x,a),g(x,a) x(x+0=x0) 真 (2) xy(F(f(x,y),g(x,y)F(x,y) xy(x+y=xyx=y) 假 (3) xF(g(x,y),a) x(xy=0) 真值不定, 不是命題 25/44 謂詞公式的類(lèi)型 定理 閉式在任何

17、解釋下都是命題 注意: 不是閉式的公式在解釋下可能是命題, 也可能不是命題. 定義 若公式A在任何解釋下均為真, 則稱(chēng)A為永真式(邏輯有效式 ). 若A在任何解釋下均為假, 則稱(chēng)A為矛盾式(永假式). 若至少有 一個(gè)解釋使A為真, 則稱(chēng)A為可滿(mǎn)足式. 幾點(diǎn)說(shuō)明： 永真式為可滿(mǎn)足式，但反之不真 25/44 謂詞公式的類(lèi)型 例7 判斷下列公式中，哪些是永真式，哪些是矛盾式？ (1) xF(x)(xyG(x,y)xF(x) 重言式 p(qp) 的代換實(shí)例，故為永真式. (2) (xF(x)yG(y)yG(y) 矛盾式 (pq)q 的代換實(shí)例，故為永假式. (3) x(F(x)G(x) 解釋I1: 個(gè)

18、體域N, F(x):x5, G(x): x4, 公式為真 解釋I2: 個(gè)體域N, F(x):x5, G(x):x10； Q(x)：x是偶數(shù)。 符號(hào)化為： 每個(gè)學(xué)生都要鍛煉身體。 P(x)：x是學(xué)生； Q(x)：x鍛煉身體。 符號(hào)化為： 不能符號(hào)化為： ()( ( )( )x P xQ x ()( ( )( )x P xQ x ()( ( )( )x P xQ x 40/44 有的獅子不愛(ài)喝咖啡。 P(x)：x是獅子； Q(x)：x愛(ài)喝咖啡。 符號(hào)化為： 不能符號(hào)化為： ()( ( )( )x P xQ x ()( ( )( )x P xQ x 41/44 謂詞公式的翻譯 不管黑貓白貓，抓住老鼠就是好貓。 P(x)：x是黑貓。 Q(x)：x是白貓。 R(x)：x是抓住老鼠的貓。 G(x)：x是好貓。 符號(hào)化為： 有些人對(duì)某些食物過(guò)敏。 A(x)：x是人。 B(x)：x是食物。 C(x,y)