數(shù)理邏輯－謂詞邏輯

1、數(shù)理邏輯－謂詞邏輯,教師：孫繼榮電話：87768609Email:sunjr0@scrtvu.net,數(shù)理邏輯－謂詞邏輯,學(xué)習(xí)內(nèi)容謂詞邏輯基本概念 謂詞，個(gè)體詞，命題函數(shù)量詞，自由變?cè)图s束變?cè)^詞的合式公式，謂詞的解釋自然語(yǔ)句的形式化謂詞邏輯的等值和推理演算 謂詞邏輯的等值式范式，基本推理公式推理演算。,數(shù)理邏輯－謂詞邏輯,教學(xué)要求理解謂詞、量詞、變?cè)€(gè)體域等概念掌握用謂詞、量詞、聯(lián)結(jié)詞構(gòu)造謂詞邏輯公式的方

2、法掌握謂詞公式在給定解釋下求真值的方法會(huì)將謂詞邏輯化為前束公式會(huì)將謂詞邏輯作為工具，將命題符號(hào)化，并能用推理規(guī)則進(jìn)行邏輯證明。,2.1謂詞邏輯基本概念,個(gè)體詞與謂詞在謂詞邏輯中，原子命題分解成個(gè)體詞和謂詞定義：個(gè)體詞是可以獨(dú)立存在的客體，它可以是具體事物或抽象的概念 ；個(gè)體域是個(gè)體（客體）的取值范圍；謂詞是用來(lái)刻劃個(gè)體詞的性質(zhì)或事物之間的關(guān)系的詞 大寫字母表示謂詞，小寫字母表示個(gè)體（客體）注意：?jiǎn)为?dú)的個(gè)體詞和謂詞不能構(gòu)成

3、命題，將個(gè)體詞和謂詞分開不是命題.,2.1謂詞邏輯基本概念,個(gè)體詞與謂詞謂詞也稱為命題函數(shù)或簡(jiǎn)單命題函數(shù)相關(guān)概念：零元謂詞，n元謂詞，全總個(gè)體域，復(fù)合命題函數(shù)命題是謂詞的特殊情況,2.1謂詞邏輯基本概念,全稱量詞與存在量詞量詞是在命題中表示數(shù)量的詞量詞有兩類：全稱量詞?，表示“所有的”，“任何的”，或“每一個(gè)”；存在量詞?，表示“存在某個(gè)”或“至少有一個(gè)”. 命題符號(hào)化必須指明個(gè)體域,2.1謂詞邏輯基本概念,全稱量

4、詞與存在量詞對(duì)于一個(gè)謂詞，如果其中每個(gè)變量都有一個(gè)量詞作用之下，則它就不再是命題函數(shù)，而是一個(gè)命題了。在謂詞邏輯，使用量詞應(yīng)注意以下幾點(diǎn)：在不同個(gè)體域中，命題符號(hào)化的形式可能不同，命題的真值也可能會(huì)改變。在考慮命題符號(hào)化時(shí)，如果對(duì)個(gè)體域未作說(shuō)明，一律使用全個(gè)體域。 多個(gè)量詞出現(xiàn)時(shí)，不能隨意顛倒它們的順序，否則可能會(huì)改變命題的涵義。,2.1謂詞邏輯基本概念,課堂練習(xí)：將下列命題符號(hào)化(1)每個(gè)母親都愛(ài)自己的孩子；(

5、2) 所有的人都呼吸；(3) 有某些實(shí)數(shù)是有理數(shù).,2.2謂詞公式,謂詞公式只是一個(gè)符號(hào)串，沒(méi)有什么意義，但我們給這個(gè)符號(hào)串一個(gè)解釋，使它具有真值，就變成一個(gè)命題. 所謂解釋就是使公式中的每一個(gè)變項(xiàng)都有個(gè)體域中的元素相對(duì)應(yīng). 學(xué)習(xí)這一部分內(nèi)容要側(cè)重于能將謂詞邏輯公式表達(dá)式中，消除量詞寫成與之等值的公式，然后將解釋中的數(shù)值代入，求出真值，并著重理解在謂詞和量詞的作用下變?cè)淖杂尚?、約束性和更名規(guī)則、代入規(guī)則等.,2.2謂詞公式,字

6、母表的意義個(gè)體常項(xiàng)：a,b,c,…a0,a1,a2,…個(gè)體變項(xiàng)：x,y,z,…x0,x1,x2 ,…函數(shù)符號(hào)：f,g,h,…f0,f1,f2 ,…謂詞符號(hào)：P,Q,R,…S0 ,S1,S2,…量詞符號(hào)：?，?邏輯符號(hào)： ?，?，?，?，?，?? 括號(hào)與逗號(hào)：(,),2.2謂詞公式,相關(guān)概念：字母表項(xiàng)：遞歸定義 P43原子公式,2.2謂詞公式,合式公式遞歸定義：P43命題常數(shù)0，1，一個(gè)命題和命題變?cè)约耙粋€(gè)命

7、題函數(shù)P(x1,x2,…,xn)，統(tǒng)稱原子公式由原子公式、聯(lián)結(jié)詞和量詞可構(gòu)成謂詞公式(嚴(yán)格定義見(jiàn)教材). 命題的符號(hào)化結(jié)果都是謂詞公式。 例子：?x(F(x)?G(x))，?x(F(x)?G(x))，?x?y(F(x)?F(y)?L(x,y)?H(x,y))等都是謂詞公式.,2.2謂詞公式,變?cè)c轄域在謂詞公式?xA和?xA中，x是指導(dǎo)變?cè)?，A是相應(yīng)量詞的轄域. 在?x和?x的轄域A中，x的所有出現(xiàn)都是約束出現(xiàn)，即x是約束變

8、元，不是約束出現(xiàn)的變?cè)?，就是自由變?cè)? 也就是說(shuō)，量詞后面的式子是轄域. 量詞只對(duì)轄域內(nèi)的同一變?cè)行?,2.2謂詞公式,變?cè)c轄域自由變?cè)袝r(shí)會(huì)在量詞轄域中出現(xiàn)，但是它不受相應(yīng)量詞指導(dǎo)變?cè)募s束。當(dāng)謂詞公式中沒(méi)有自由變?cè)獣r(shí)，它就是一個(gè)命題。出現(xiàn)n個(gè)自由變?cè)褪莕元謂詞。變?cè)梢约仁羌s束出現(xiàn)又是自由出現(xiàn)。例子：P44,2.2謂詞公式,換名規(guī)則：對(duì)約束變?cè)M(jìn)行換名就是把公式中量詞的指導(dǎo)變?cè)捌湓摿吭~轄域中的約束變?cè)獡Q成該

9、公式中沒(méi)有出現(xiàn)的個(gè)體變?cè)?，公式的其余部分不? 代入規(guī)則：對(duì)自由變?cè)M(jìn)行代入就是把公式中的某一自由變?cè)?，用該公式中沒(méi)有出現(xiàn)的個(gè)體變?cè)?hào)替代，且要把該公式中所有的該自由變?cè)紦Q成新引入的該符號(hào).經(jīng)過(guò)換名或代入后，公式的意義不應(yīng)該改變,2.2謂詞公式,課堂練習(xí)對(duì)P44 例1中公式用換名或代入規(guī)則重要公式?xA(x)?A(a1)?A(a2)?A(an)?xA(x) ?A(a1)?A(a2)?A(an),2.3謂詞的等值演

10、算,解釋(賦值)：謂詞公式的個(gè)體域D是非空集合(1) 每一個(gè)常項(xiàng)指定D中一個(gè)元素；(2) 每一個(gè)n元函數(shù)指定Dn到D的一個(gè)函數(shù)；(3) 每一個(gè)n元謂詞指定Dn到{0,1}的一個(gè)謂詞. 解釋就是對(duì)各個(gè)變項(xiàng)指定特殊的常項(xiàng)去代替，有四部分組成：(1) 非空個(gè)體域D；(2) D中有一部分特定元素，用來(lái)解釋個(gè)體常項(xiàng)；(3) D上一些特定函數(shù)，用來(lái)解釋出現(xiàn)的函數(shù)變項(xiàng)；(4) D上一些特定謂詞，用來(lái)解釋謂詞變項(xiàng)。,2.3謂詞的等

11、值演算,例子：P46課堂練習(xí)：給定解釋I：① D＝{2,3};② D中特定元素a=2；③ 函數(shù)為④ 謂詞F(x)為F(2)=0,F(3)=1 G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1 L(x,y)為L(zhǎng)(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0求在解釋I下各公式的真值. (1) ?x( F(x)?G(x,a)) (

12、2) ?x?y L(x,y),2.3謂詞的等值演算,謂詞公式分類在任何解釋下，謂詞公式A取真值1，公式A為邏輯有效式(永真式)；在任何解釋下謂詞公式A取真值0，公式A為永假式；至少有一個(gè)解釋是公式A取真值1，公式A稱為可滿足式。,2.3謂詞的等值演算,謂詞演算的等值式和重言蘊(yùn)含式 (1)命題公式的推廣；(2) 量詞否定式的等值式；(3) 量詞轄域擴(kuò)張和收縮的等值式；(4) 量詞與聯(lián)結(jié)詞?，?，?的等值式；(5) 量

13、詞與聯(lián)結(jié)詞的重言蘊(yùn)含式；(6) 兩個(gè)量詞公式間的等值式與重言蘊(yùn)含式。,2.4前束范式,前束范式 :若一個(gè)謂詞公式F等值地轉(zhuǎn)化成Q1x1Q2x2 …QkxkB,那么就是F的前束范式，其中Qi只能是量詞?或?，而x1,x2,…,xk是個(gè)體變?cè)珺是不含量詞的謂詞公式. 量詞均在全式的開頭，其作用域延伸到整個(gè)公式的末尾,2.4前束范式,前束范式的重要性質(zhì)性質(zhì)1：P49性質(zhì)2：P50證明忽略,2.4前束范式,每個(gè)謂詞公式F都可

14、以變換成與它等值的前束范式. 其步驟如下：① 消去聯(lián)結(jié)詞?，?，??；② 將聯(lián)結(jié)詞?移至原子謂詞公式之前；③ 利用換名或代入規(guī)則使所有約束變?cè)姆?hào)均不同，并且自由變?cè)c約束變?cè)姆?hào)也不同；④將?x,?x移至整個(gè)公式最左邊；⑤ 將公式化為前束范式。 一般地，前束范式不是唯一地。,2.4前束范式,謂詞公式->前束范式例子：P51課堂練習(xí)：練習(xí)2.4（B）3,2.5謂詞邏輯地推理理論,謂詞演算的推理是命題演算推理

15、的推廣和擴(kuò)充命題演算中的一些規(guī)則，如基本等值公式，重言蘊(yùn)含式以及P，T，CP規(guī)則在謂詞演算中仍然使用.,2.5謂詞邏輯地推理理論,在謂詞演算推理中，某些前提和結(jié)論可能受到量詞的限制，為了使用這些推理，引入消去和添加量詞的規(guī)則，以便使謂詞演算公式的推理過(guò)程可類似于命題演算的推理進(jìn)行 US規(guī)則(全稱量詞消去規(guī)則)UG規(guī)則(全稱量詞附加規(guī)則)ES規(guī)則(存在量詞消去規(guī)則)EG規(guī)則(存在量詞附加規(guī)則)等,2.5謂詞邏輯地推理理論,課