離散數(shù)學(xué)的謂詞邏輯詳解(課堂PPT)課件(PPT 74頁(yè))

1、謂 詞 邏 輯2022/7/221.第1頁(yè)，共74頁(yè)。命題邏輯的局限性 蘇格拉底三段論： P：所有的人都是要死的。 Q：蘇格拉底是人 。 R：所以蘇格拉底要死 。 憑直覺(jué)知道這個(gè)結(jié)論是真的，推理是有效的。但是，借助命題演算的推理理論，卻不能推導(dǎo)出這個(gè)結(jié)論（無(wú)法證明它的正確性）。Why ?2022/7/222.第2頁(yè)，共74頁(yè)。 此三段論的論斷顯然正確。 但是，在命題邏輯中無(wú)法得到正確性的反應(yīng): PQR 不是重言式！命題邏輯不能正確反映此三段論的推理過(guò)程。這是命題邏輯的局限性!2022/7/223.第3頁(yè)，共74頁(yè)。原 因在命題邏輯中無(wú)法將簡(jiǎn)單命題之間的內(nèi)在聯(lián)系反映出來(lái)。命題邏輯中描述的上述三段

2、論，即PQR，使R與命題P、Q無(wú)關(guān)的獨(dú)立命題。但是，實(shí)際上R與命題P、Q是有關(guān)系的，只是這種關(guān)系在命題邏輯中得不到反映。要反映這種內(nèi)在聯(lián)系，需對(duì)簡(jiǎn)單命題作進(jìn)一步分解，分解出其中的成份，包括：個(gè)體詞，謂詞，量詞，函詞等，研究它們的形式結(jié)構(gòu)及邏輯關(guān)系，總結(jié)出正確的推理形式和規(guī)則，這就是一階邏輯所研究的內(nèi)容.一階邏輯也稱(chēng)謂詞邏輯。謂詞邏輯是一種表達(dá)能力更強(qiáng)的邏輯。2022/7/224.第4頁(yè)，共74頁(yè)。謂詞邏輯我們將介紹謂詞邏輯的基本概念和符號(hào)。關(guān)于命題、命題的真值、命題詞、命題常量和命題變?cè)约斑壿嬑鍌€(gè)聯(lián)結(jié)詞其含意和在命題邏輯中的基本相同，本章中只介紹謂詞邏輯中新出現(xiàn)的基本概念和符號(hào)，其中主要的是

3、個(gè)體詞，謂詞，量詞以及函詞。2022/7/225.第5頁(yè)，共74頁(yè)。1.謂詞與個(gè)體詞 將簡(jiǎn)單命題分解成個(gè)體與謂詞這樣兩個(gè)組成部分。謂詞，通常是用來(lái)描述個(gè)體的性質(zhì)或特征，或者個(gè)體之間的關(guān)系。謂詞邏輯，是命題邏輯的擴(kuò)充與發(fā)展 。例1：下面兩個(gè)命題 1. 張華是學(xué)生 2. 李明是學(xué)生 a: 張華 b:李明 H：是學(xué)生 ，則 H（x）:x是學(xué)生 1，2可分別表示成 H(a) ，H(b). 這樣表示就揭示了兩命題間有相同的謂語(yǔ)這一特征。 2022/7/226.第6頁(yè)，共74頁(yè)。例2：張華比李明高 令 a:張華 b:李明 L(x，y):x高于y 該命題可表示為： L(a，b)例1和例2中的 H、L稱(chēng)為謂詞

4、， 其中H是一元謂詞，表示個(gè)體的性質(zhì)（是什么）， L是二元謂詞，表示個(gè)體之間的關(guān)系。 注： （1）常用大寫(xiě)拉丁字母表示謂詞. （2）謂詞是用來(lái)刻劃個(gè)體的性質(zhì)或者個(gè)體之間的關(guān)系的。2022/7/227.第7頁(yè)，共74頁(yè)。命題函數(shù)與命題例: 令P(x)表示x為質(zhì)數(shù)，則P(x)為一元謂詞。 令 H(x，y)表示“x高于y”,則 H(x，y)為二元謂詞。 則：H(張三，李四) 表示“張三高于李四”，是命題。注意： P(x.y), H(x，y)為命題函數(shù). P(2)與 H(張三，李四)才是命題。謂詞中如果有n個(gè)變?cè)獎(jiǎng)t稱(chēng)為n元謂詞. n元謂詞反映了個(gè)體之間的n元關(guān)系. 2022/7/228.第8頁(yè)，共74

5、頁(yè)。2.個(gè)體詞個(gè)體是可以獨(dú)立存在的實(shí)體，它可以是一個(gè)具體的 事物-個(gè)體常元，常用小寫(xiě)拉丁字母a，b，c等表示。也可以是一個(gè)抽象的概念（即沒(méi)指定哪一個(gè)個(gè)體） -個(gè)體變?cè)?，常用小?xiě)拉丁字母：x，y，z等表示2022/7/229.第9頁(yè)，共74頁(yè)。函詞例：張華的哥哥比李明高 a:張華 b:李明 L(x，y):x高于y f(x):x的哥哥則上述符號(hào)化為： L(f(a)，b) f稱(chēng)為函詞定義：一個(gè)n元函詞即是一個(gè)論域上的一個(gè)n元函數(shù)2022/7/2210.第10頁(yè)，共74頁(yè)。 變?cè)谥^詞中的次序直接影響了謂詞的取值 。如:設(shè)謂詞P(x，y)為“x比y高”， 設(shè)張三為170cm，李四為180cm.則: P

6、(李四，張三)為真命題。 P(張三，李四)為假命題.概念的討論2022/7/2211.第11頁(yè)，共74頁(yè)。命題的符號(hào)化例1:武漢位于重慶與上海之間.解:用個(gè)體詞a，b，c分別表示武漢，重慶和上海， 謂詞P(x，y，z)表示x位于y與z之間， 則該命題表示為:P(a，b，c).例2：如果王英坐在李紅的后面，則王英比李紅高.解：令 a:王英;b:李紅;P(x，y):x坐在y的后面; G(x，y):x比y高.則該命題表示為：P(a，b)G(a，b).2022/7/2212.第12頁(yè)，共74頁(yè)。3. 量詞 使用前面介紹的概念，還不足以表達(dá)日常生活中的各種命題。 例如： “ 所有的正整數(shù)都是素?cái)?shù) ” “

7、 有些正整數(shù)是素?cái)?shù) ” 兩種量詞: 全稱(chēng)量詞和存在量詞.2022/7/2213.第13頁(yè)，共74頁(yè)。全稱(chēng)量詞: 1.全稱(chēng)量詞 ： （任意，所有） x: “對(duì)一切x”，“對(duì)所有的x”， “對(duì)任一x” 如： x P(x) “對(duì)一切x，P(x)是真” x P(x) “并非對(duì)一切x，P(x)是真” x P(x) “對(duì)一切x， P(x) 是真” 如: “ 所有人都是要死的”設(shè)x的個(gè)體域?yàn)槿w人的集合，則可表示為 x D(x) 2022/7/2214.第14頁(yè)，共74頁(yè)。存在量詞: 2. 存在量詞： （存在） x: “存在x“、 ”某些x“、 ”至少有一x”如： x P(x) “存在x， P(x)是真”

8、x P(x) “存在x， P(x)是真，并非這樣” x P(x) “存在x， P(x)是真” 如: “有些有理數(shù)是整數(shù)?！?令(x）：x是整數(shù)，設(shè)x的個(gè)體域?yàn)橛欣頂?shù)集合，則命題可表示為： x I(x） 2022/7/2215.第15頁(yè)，共74頁(yè)。 4. 論 域 含有量詞的命題的表達(dá)式的形式，與論域有關(guān)。用量詞量化后的命題，其值也與論域有關(guān)。 例 1 x（x=0) 若論域?yàn)檎麛?shù)集，則此命題值為真， 若論域?yàn)檎麛?shù)集，則命題的值為假。 為了方便，引入全總個(gè)體域，記為：U，簡(jiǎn)稱(chēng)全域: 定義:宇宙間所有的個(gè)體聚集在一起所構(gòu)成的集合稱(chēng)為全域。 2022/7/2216.第16頁(yè)，共74頁(yè)。特性謂詞后面的討

9、論中，除特殊說(shuō)明外，均使用全域。而對(duì)個(gè)體變化的真正取值范圍，用特性謂詞加以限制。 一般地，對(duì)全稱(chēng)量詞，特性謂詞作蘊(yùn)含的前件引入；而對(duì)存在量詞，特性謂詞常作為合取項(xiàng)引入。2022/7/2217.第17頁(yè)，共74頁(yè)。例 (1) “所有的人都是要死的?！?(2) “有的人不怕死?！?1.當(dāng)x的個(gè)體域?yàn)槿w人組成的集合時(shí)，符號(hào)化上述命題。解: 令D（x）：x是要死的，令G（x）：x怕死。 則（1）可表示為: x D(x)。 （2）可表示為: x G(x)。 2022/7/2218.第18頁(yè)，共74頁(yè)。論域?yàn)槿驎r(shí)2. 當(dāng)取x的個(gè)體域?yàn)槿驎r(shí)，必須引入一個(gè)特性謂詞將“人”從全域中分離出來(lái)。 （1）對(duì)所有

10、個(gè)體而言，如果它是人，則它是要死的。 （2）存在著個(gè)體，它是人并且它不怕死 于是令 M（x）：x是人。 （1） x（M(x)D(x) （2） x (M（x） G（x） 2022/7/2219.第19頁(yè)，共74頁(yè)。命題符號(hào)化(翻譯)：將漢語(yǔ)(或其他自然語(yǔ)言)語(yǔ)句翻譯成邏輯表達(dá)式，這在數(shù)學(xué)、邏輯編程、人工智能、軟件工程以及許多其他學(xué)科中都是一項(xiàng)重要的任務(wù)。翻譯的目的是生成簡(jiǎn)單而有用的邏輯表達(dá)式。20.第20頁(yè)，共74頁(yè)。命題符號(hào)化：例：沒(méi)有不犯錯(cuò)誤的人令H（x）： x是人， M（x）： x犯錯(cuò)誤例：存在著偶質(zhì)數(shù)令E(x)：x是偶數(shù)，P(x)：x是質(zhì)數(shù)則有：x(E(x)P(x)2022/7/2221

11、.第21頁(yè)，共74頁(yè)。例：每個(gè)自然數(shù)都有后繼數(shù)若令：N（x）：x 是自然數(shù)， H（x，y）：y是x的后繼數(shù)例：對(duì)平面上的任意兩點(diǎn)，有且僅有一條直線通過(guò)這兩點(diǎn)。若令P（x）： x是一個(gè)點(diǎn)，L（x）：x是一條直線，T（x，y，z）：z通過(guò)x，y，E（x，y）：x等于y2022/7/2222.第22頁(yè)，共74頁(yè)。 例5 將下列命題符號(hào)化(使用全域)。 (1) 發(fā)光的并非都是金子 令：P（x）：x發(fā)光；G（x）：x是金子。則該命題可表示為 ： （2）所有運(yùn)動(dòng)員都?xì)J佩某些教練。 令：P（x）：x是運(yùn)動(dòng)員；T（x）：x是教練；Q（x，y）：x欽佩y。則該命題可表示為 ：2022/7/2223.第23頁(yè)，共

12、74頁(yè)。 （3）凡是實(shí)數(shù)均能比較大小。 若令R（x）：x是實(shí)數(shù)；G（x，y)：x與y可比較大小. 則該命題可表示為：例6將蘇格拉底三段論進(jìn)行符號(hào)化：令：(x)：x是人(x): x要死則2022/7/2224.第24頁(yè)，共74頁(yè)。 量化斷言與命題的關(guān)系 (1)如果論述域是有限的，不妨設(shè)論述域是1，2，3，則 x P(x)P(1)P(2)P(3) x P(x) P(1)P(2)P(3) (2) 如果論述域是可數(shù)無(wú)限，例如自然數(shù)集合，我們可以這樣理解： (x)P(x) P(1)P(2)P(3) (x)P(x) P(1)P(2)P(3) (3)如果論述域不可數(shù)無(wú)限，則無(wú)法表達(dá)。 2022/7/2225

13、.第25頁(yè)，共74頁(yè)。練習(xí) 任何金屬都可以溶解在某種液體中.令J(x):x是金屬; E(x):x是液體;S(x，y):x可以溶解在y中，2022/7/2226.第26頁(yè)，共74頁(yè)。原子與公式 設(shè)P(x1，xn)是n元謂詞，則稱(chēng)其為為原子公式，或簡(jiǎn)稱(chēng)原子謂詞公式，簡(jiǎn)稱(chēng)為公式，其遞歸定義為：（1）原子是合式公式；（2）若A是合式公式，則(A)也是合式公式；（3）若A，B是合式公式，則(AB)， (AB)， (AB)， (AB)也是合式公式；（4）若A是合式公式，x是A中的變量符號(hào)，（5）只有有限次地使用（1）（4）所生成的符號(hào)串才是合式公式。2022/7/2227.第27頁(yè)，共74頁(yè)。前面各命題符

14、號(hào)化的結(jié)果都是合式公式。對(duì)于一個(gè)謂詞，如果其中每一個(gè)變量都在一個(gè)量詞的作用之下，則它就不再是命題函數(shù)而是一個(gè)命題了。但是，這種命題和命題邏輯中的命題還是有區(qū)別的。因?yàn)檫@種命題中畢竟還有變量，盡管這種變量和命題函數(shù)中的變量有所不同。因此，有必要區(qū)分這些變量。2022/7/2228.第28頁(yè)，共74頁(yè)。例1 ：令 P（x， y）：“ xy.則A(y)是真命題原因是:條件2)不滿足。2022/7/2258.第58頁(yè)，共74頁(yè)。存在推廣規(guī)則EG 使用此規(guī)則時(shí)注意: (1) c是個(gè)體域中某個(gè)確定的個(gè)體。 (2) 代替c的x不能已在A(c)中出現(xiàn)。例如：設(shè)A(x，y):xy，考查下面的推理過(guò)程: (1)

15、A(x，c) (2) 是錯(cuò)誤的！原因在于代替c的x已在A(x)中出現(xiàn)2022/7/2259.第59頁(yè)，共74頁(yè)。存在指定規(guī)則(ES規(guī)則):成立條件：1) c是使A(c)為真的常量符號(hào)3)A(x)中的自由變?cè)挥衳.例如：設(shè)D為自然數(shù)集， F(x)表示“x是奇數(shù)”，G(x)表示“x是偶數(shù)”.注意：以上四條規(guī)則中的A(x)都是公式2022/7/2260.第60頁(yè)，共74頁(yè)。但，若不注意使用條件，則有：前提引入化簡(jiǎn)，根據(jù)（1）ES規(guī)則，根據(jù)（2）化簡(jiǎn)，根據(jù)（1）ES規(guī)則，根據(jù)（4）合取，根據(jù)（3），（5）EG規(guī)則，根據(jù)（6）于是得出：（）違反了條件2）2022/7/2261.第61頁(yè)，共74頁(yè)。例

16、1 證明：證明如下：前提引入U(xiǎn)S規(guī)則，根據(jù)（1）前提引入ES規(guī)則，根據(jù)（3）化簡(jiǎn)，根據(jù)（4）化簡(jiǎn)，根據(jù)（4）假言推理，根據(jù)（2），（6）合取，根據(jù)（5），（7）EG規(guī)則，根據(jù)（8）2022/7/2262.第62頁(yè)，共74頁(yè)。本例也可作如下證明：前提引入ES規(guī)則，根據(jù)（1）化簡(jiǎn)，根據(jù)（2）前提引入U(xiǎn)S規(guī)則，根據(jù)（4）假言推理，根據(jù)(3)，(5)化簡(jiǎn)，根據(jù)（2）合取，根據(jù)（6），（7）EG規(guī)則，根據(jù)（8）2022/7/2263.第63頁(yè)，共74頁(yè)。例 2 證明： 蘇格拉底三段論“凡人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的”。證明:結(jié)論: D(a)首先將命題符號(hào)化：設(shè)M(x):x是人. D(

17、x):x是要死的. a:蘇格拉底.前提:證明:規(guī)則US規(guī)則，（1）規(guī)則假言推理，（2），（3）2022/7/2264.第64頁(yè)，共74頁(yè)。例 3有些病人相信所有的醫(yī)生，但是病人都不相信騙子。證明：醫(yī)生都不是騙子。證明：命題符號(hào)化：設(shè)論域?yàn)槿?P(x):x是病人；D(x):x是醫(yī)生；Q(x):x是騙子；R(x，y):x相信y。前提：x(P(x)y(D(y)R(x，y)， xy(P(x)Q(y)R(x，y)結(jié)論：x(D(x)Q(x)證明：2022/7/2265.第65頁(yè)，共74頁(yè)。x(P(x)y(D(y)R(x，y) 前提引入P(c)y(D(y)R(c，y) ES，(1)xy(P(x)Q(y)R

18、(x，y) 前提引入y(P(c)Q(y)R(c，y) US，(3)P(c)Q(z)R(c，z) US，(4)(P(c)Q(z)R(c，z) 蘊(yùn)涵等值式，(5)P(c)Q(z)R(c，z) De Morgan律，(6)P(c)(Q(z)R(c，z) 蘊(yùn)涵等值式，(7)P(c) 化簡(jiǎn)，(2)Q(z)R(c，z) 析取三段論，(8)，(9)R(c，z)Q(z) 等值演算，(10)y(D(y)R(c，y) 化簡(jiǎn)，(2)D(z)R(c，z) US，(12)D(z)Q(z) 假言三段論，(11)，(13)x(D(x)Q(x) UG，(14) 2022/7/2266.第66頁(yè)，共74頁(yè)。例 4：指出下面推理

19、的錯(cuò)誤x(F(x)G(x) 前提引入F(y)G(y) US，(1)xF(x) 前提引入F(y) ES，(3)G(y) 假言推理，(2)，(4)xG(x) UG，(5)沒(méi)有滿足ES規(guī)則的條件1即： xA(x)A(c)c是使A(c)為真的常量符號(hào)。 F(c) ES，(3) G(c) 假言推理，(2)，(4)xG(x) EG，(5)2022/7/2267.第67頁(yè)，共74頁(yè)。例證明下述論證的正確性人會(huì)說(shuō)話，猴子不會(huì)說(shuō)話，因此猴子不是人。解：設(shè)論域?yàn)槿颉ＴO(shè) M(x):x是人。 S(x): x會(huì)說(shuō)話。B(x):x是猴子。則前提為：x(M(x)S(x)和 x(B(x)S(x) 結(jié)論為： x(B(x)M(

20、x)證明: 1 x(M(x)S(x) P規(guī)則，前提 2 M(x)S(x) T，1，US 3 x(B(x)S(x) P規(guī)則，前提 4 B(x)S(x) T，3，US 5 S(x) B(x) T，4， 逆反律 6 M(x) B(x) T，2，5，I6 7 B(x) M(x) T，6，逆反律 8 x(B(x)M(x) T，7，UG2022/7/2268.第68頁(yè)，共74頁(yè)。練習(xí)：符號(hào)化下列命題，并論證其結(jié)論：任何人如果他喜歡步行，他就不喜歡乘汽車(chē)，每一個(gè)人或 者喜歡乘汽車(chē)，或者喜歡騎自行車(chē)。有的人不愛(ài)騎自行車(chē)，因而有的人不愛(ài)步行。命題符號(hào)化：設(shè)P(x):x喜歡步行。Q(x):x喜歡乘汽車(chē). R(x)

21、:x喜歡騎自行車(chē)。推理的形式結(jié)構(gòu)：2022/7/2269.第69頁(yè)，共74頁(yè)。結(jié)構(gòu)形式：前提引入ES，(1)前提引入U(xiǎn)S ，(3)(5)Q(c) 析取三段論 (2)，(4).前提引入(7) P(c)Q(c)US，(6)(8) Q(c) P(c) 等值演算，(7).EG，(9).證明：推理如下：(9) P(c) 假言推理 (5)，(8).102022/7/2270.第70頁(yè)，共74頁(yè)。謂詞邏輯應(yīng)用實(shí)例-邏輯程序設(shè)計(jì)有一類(lèi)重要的程序設(shè)計(jì)語(yǔ)言使用謂詞邏輯的規(guī)則進(jìn)行推理。例如:Prolog(Programming in Logic),Prolog程序包括一組聲明，有兩類(lèi)語(yǔ)句:Prolog事實(shí)和Prolog規(guī)則。P