04-面向計(jì)算機(jī)的數(shù)理邏輯(ch3)

1、1,面向計(jì)算機(jī)的數(shù)理邏輯,主講：李偉剛liweigang@nwpu.edu.cn西北工業(yè)大學(xué)軟件與微電子學(xué)院,2,第三章 謂詞邏輯,3,§3.1 我們需要更豐富的語(yǔ)言,命題邏輯通過三個(gè)角度來展開研究證明論（自然演繹演算）句法（公式的樹狀性質(zhì)）語(yǔ)義（公式的實(shí)際含義）這是基于：判斷語(yǔ)句，即關(guān)于現(xiàn)實(shí)世界論述的每個(gè)賦值或模式都能給出真值。,4,我們知道，命題演算的基本研究單位是原子命題，在命題演算中，原子命題是不能再分割的

2、了。這對(duì)研究命題間的關(guān)系是比較合適的。但是，在進(jìn)一步研究時(shí)就會(huì)發(fā)現(xiàn)，僅僅命題演算對(duì)我們是很不夠的并且也不充分，比如：三段論在命題演算系統(tǒng)中是無法完成的。 例如： 所有的科學(xué)是有用的 數(shù)理邏輯是科學(xué) 所以，數(shù)理邏輯是有用的 又例如：凡人必死 張三是人 故張三必死,5,上述兩個(gè)例子用命題邏輯描述不充分的主

3、要原因就是在于這種推理中需要對(duì)原子命題作進(jìn)一步分解，在上述兩個(gè)例子中，每個(gè)例子三個(gè)命題間，具有必然的內(nèi)在邏輯關(guān)系，只有對(duì)這種內(nèi)存邏輯聯(lián)系深入研究后，才能解決形式邏輯中的一些推理問題。謂詞演算正是為了這樣的目的，換言之也就是對(duì)原子命題進(jìn)行進(jìn)一步的分解。,6,在謂詞演算中，將原子命題分解為謂詞與個(gè)體兩部分，在上例中，“數(shù)理邏輯是科學(xué)”即主語(yǔ)“數(shù)理邏輯”與謂語(yǔ)“是科學(xué)”，“張三是人”中的“張三”是主語(yǔ)，“是人” 為謂語(yǔ)。換言之在數(shù)理邏輯中將主

4、語(yǔ)稱為個(gè)體，將謂語(yǔ)稱為謂詞。 所謂個(gè)體是可以獨(dú)立存在的物體。它可以是抽象的，也可以是具體的，如：鮮花，代表團(tuán)，自行車，自然數(shù)，唯物主義等等都是個(gè)體。謂詞是用來刻劃個(gè)體的性質(zhì)或關(guān)系。如“3整除6”這里3與6是個(gè)體，關(guān)系“整除”是謂詞。 一個(gè)謂詞可以與某個(gè)個(gè)體相聯(lián)，此種謂詞稱為一元謂詞。 上例中張三，3，6等也可以是抽象的，比如x，y，稱為變?cè)?變量。由個(gè)體組成的集合稱為

5、個(gè)體域（或論述域），以某個(gè)個(gè)體域I為變域的變?cè)凶鰝€(gè)體變?cè)?7,一個(gè)單獨(dú)的謂詞是沒有含義的，如：“…是大學(xué)生“，這個(gè)謂詞必須跟隨一定數(shù)量的個(gè)體后才有明確的含義，最重要的是能分別其真假。 個(gè)體謂詞中的次序有時(shí)也是很重要的，如“上海位于南京與杭州之間”，此命題為真，其中“上?！?、“南京”、“杭州”三個(gè)個(gè)體間次序不能隨便顛倒，如果寫成“杭州位于南京和上海之間”，則此時(shí)命為假。所以，由謂詞以及跟隨它的若干個(gè)有一定次序的個(gè)

6、體便可構(gòu)成一個(gè)完整的命題。,8,下面我們一般用大寫字母A，B…E表示謂詞，用小寫字母a，b，c…z表示個(gè)體（或個(gè)體變?cè)@樣x，y間具有關(guān)系B可記作B（x，y），x，y，z具有關(guān)系C，記作C（x，y，z），上述是二元謂詞和三元謂詞，當(dāng)然也可以表示為n元謂詞就是有n個(gè)個(gè)體變?cè)闹^詞，并約定0元謂詞是命題。 n元謂詞當(dāng)然需要賦于n個(gè)個(gè)體變?cè)庞幸饬x，我們把謂詞后填以個(gè)體稱為謂詞填式。 有了謂詞的概念后我們可以將

7、一些日常用語(yǔ)及命題更深刻地刻劃出來，下面我們以幾個(gè)例子說明：,9,例1：王強(qiáng)是大學(xué)生李華也是大學(xué)生。 解：F表示是大學(xué)生， F（x）表示x是大學(xué)生。 a表示“王強(qiáng)”，b表示“李華”，則此式可表示為： F（a）∧F （b）,例2：我國(guó)領(lǐng)導(dǎo)人訪問美國(guó) 。 解：F（x，y）表示x訪問y，a表示我國(guó)領(lǐng)導(dǎo)人，b表示美國(guó)，則此式可表示為： F（a，b）,10,例3：大樓建成了。

8、 解：F（x）表示“x建成了”，G（x）表示“x是大的”， H（x）表示“x是樓”， 則此式可表示為： F（a）∧G （a）∧H（a）,例4：這個(gè)人正在看那本紅皮面的書。 解：F（x，y）表示“x正在看y”，G（x）表 示“x是人”，H（y）表示“y是紅皮面的”，U （y）表示“y是書”，a表示“這個(gè)”，b表示“那 本”，則此式可表示為： F（a，b）∧G （a）∧H（b）∧U（b）,11,

9、一般地講，對(duì)日常的語(yǔ)句，我們可給出一個(gè)大體的準(zhǔn)則，根據(jù)這些準(zhǔn)則可寫出其邏輯表達(dá)式來。 名詞：專用名詞（如王強(qiáng)，美國(guó)等）為個(gè)體 通用名詞（如樓房，人等）一般可為個(gè)體 代名詞：人稱代詞（如：你，我，他），指示代詞（如這個(gè)，那個(gè)）為個(gè)體 不定代詞（如任何，每個(gè)，有些，一些等）為量詞 形容詞：一般為謂詞 數(shù)詞： 一般為量詞 動(dòng)詞： 一般為謂詞 副詞：

10、 與所修飾的動(dòng)詞合并為一謂詞，不再分解 前置詞：與其它有關(guān)字合并為一，本身不獨(dú)立表示 連接詞：一般為命題聯(lián)結(jié)詞 以上準(zhǔn)則只供參考，在具體應(yīng)用時(shí)常常也有許多例外,12,§3.2 作為形式語(yǔ)言的謂詞邏輯,在謂詞邏輯中，將句子表達(dá)的復(fù)雜事實(shí)編碼為邏輯公式很重要編碼一旦完成，我們的主要目標(biāo)成為：對(duì)那些公式中表達(dá)的相關(guān)信息進(jìn)行符號(hào)地（├ ）或語(yǔ)義地（╞）推導(dǎo)。,13,§3.2.1 量詞,在

11、數(shù)學(xué)上或日常生活中經(jīng)常碰到“對(duì)一切”、“所有的”、“存在一個(gè)”、“至少有一個(gè)“等的概念，我們學(xué)過的命題邏輯是無法表達(dá)清楚的。一個(gè)謂詞演算中的表達(dá)不一定是確定的，個(gè)體域中不同的個(gè)體代入后可得到不同的真假值。如我們考察下面兩個(gè)式子（它們均以整數(shù)作為其個(gè)體域）： （1）（x+1）2=x2+2 x+1 （2）X+6=5 對(duì)于（1）我們發(fā)現(xiàn)任何整數(shù)代入后等式總是正確，但是對(duì) （2）分析則不然，它只存在一個(gè)

12、整數(shù)即（-1）代入后使得等式 成立。 又如：“q或者大于0，或者等于0，或者小于0”，當(dāng)然 該句可寫成：q＞0∨q=0∨q0∨a=0∨a<0 (a表示“每一數(shù)”)這樣的結(jié)果為,“每一數(shù)大于0或每一數(shù)等于0或每一數(shù)小于0,”顯然這與原意不同。,14,通過上述例子說明：任一謂詞演算與其個(gè)體間存在著一些關(guān)系。 例如：1.對(duì)個(gè)體域中（所有個(gè)體）式子均為真 2.對(duì)個(gè)體域中（一些個(gè)體）

13、式子均為真 那么如何在謂詞演算中刻劃謂詞與個(gè)體間的關(guān)系呢？只有一個(gè)辦法來引進(jìn)一些新的符號(hào)，它們叫做量詞。量詞有兩種，一種叫做全稱量詞，一種叫做存在量詞。 它的定義如下:,15,定義1：凡表示“任意一個(gè)”，“一切”，“每個(gè)”，“任何”等詞時(shí)，均為全稱量詞（全稱變?cè)┯涀?x 。,定義2：“某個(gè)”，“一個(gè)”，“一些” 等詞時(shí)均可用存在性變?cè)g，記為ヨx。凡表示確定的但目前尚未知道的或不必明白指出的個(gè)體變?cè)Q之為存

14、在量詞。,16,對(duì)于個(gè)體域中所有個(gè)體x其謂詞F（x）均為真時(shí)，可用符號(hào)“ x ”表示“對(duì)所有x”,此時(shí)它可以表示成如上例中，當(dāng)個(gè)體域?yàn)閷?shí)數(shù)時(shí)下面的表示為真，即： x（（x+1）2=x2+2 x+1）。符號(hào)“ x”稱為全稱量詞，它后面緊跟著括號(hào)內(nèi)的式子稱作全稱量詞的轄域。 對(duì)于個(gè)體域中個(gè)體x，存在某些個(gè)體謂詞Ｆ（x）為真時(shí)用符號(hào)“ヨx”表示“存在某些x”，此時(shí)表示為：ヨx（F（x）） 如：x+6=5當(dāng)個(gè)體域

15、為實(shí)數(shù)時(shí)，此時(shí)表示式為真：ヨx（x+6=5）符號(hào)“ヨx” 為存在量詞，同理，它后面緊跟著括號(hào)內(nèi)的式子稱作存在量詞的轄域。,17,一個(gè)不確定的公式只要對(duì)其所有變?cè)┘恿吭~后則均為確定的了。如：x+6=5因?yàn)楫?dāng)x=-1時(shí)它為真（T），當(dāng)x=3時(shí)它為假（F）。但是當(dāng)使用量詞后ヨx（x+3=5）則是確定的，因?yàn)樗偸菫檎妫═）。 這個(gè)論點(diǎn)一般而言是正確的，但是它是有前提的，也就是在確定的個(gè)體域條件下，一公式所有個(gè)體變?cè)┘恿吭~后，

16、它就是確定的了。,18,通過例子我們發(fā)現(xiàn)：1.量詞所確定的公式與個(gè)體域有關(guān)。2.對(duì)不同的個(gè)體域表達(dá)式可有不同的值。也就是說，各變?cè)淖冇颍▊€(gè)體域）須做臨時(shí)約定。各變?cè)男再|(zhì)（全稱或存在性）須做臨時(shí)約定。因此在謂詞演算中，每個(gè)個(gè)體變?cè)膫€(gè)體域必需是確定的。因此可見，量詞所確定的公式與個(gè)體域有關(guān)，對(duì)不同的個(gè)體域表達(dá)式的值不同。 例如：ヨx（x+6=5）中，當(dāng)個(gè)體域?yàn)閷?shí)數(shù)時(shí)它為T，但當(dāng)個(gè)體域?yàn)樽匀粩?shù)時(shí)它為F。,19,因此，

17、在謂詞演算中，每個(gè)個(gè)體變?cè)膫€(gè)體域必需是確定的 。但有時(shí)為了討論方便起見，我們干脆將謂詞演算中所有個(gè)體域統(tǒng)一，一律用全總個(gè)體域。用了全總個(gè)體域后，對(duì)每個(gè)個(gè)體變?cè)淖兓秶靡欢ㄌ匦灾^詞去刻劃。對(duì)全稱量詞，此特性謂詞可作為蘊(yùn)含前件而加入。對(duì)存在量詞，此特性謂詞可作為合取式的合取項(xiàng)加入。 例如：上二式中設(shè)R（x）表示x為實(shí)數(shù)，它刻劃了式中個(gè)體變?cè)奶匦怨适翘匦灾^詞，此時(shí)（x+1）2=x2+2 x+1可寫為： x

18、 （R（x）→（（x+1）2=x2+2 x+1）），而x+6=5可寫為： ヨx（R（x）∧（x+6=5））有了量詞的概念后，謂詞演算表達(dá)能力就廣泛的多了，它所能刻劃的語(yǔ)句也普遍，深入。,20,下面我們舉例說明：,例1：沒有不犯錯(cuò)誤的人 解：設(shè)F（x）為“x犯錯(cuò)誤”其特性謂詞為M（x），“表示x為人”此句可譯為： ┐（ヨx（M（x）∧┐F（x））,例2：凡是實(shí)數(shù)不是大于零就是等于零或者小于零。 解

19、：我們將x大于零，x等于零，x小于零分別用>（x，0），=（x，0），（x，0）∨=（x，0）∨< （x，0））,21,§3.2.2 函詞（函數(shù)） 為了說明命題函詞（函數(shù)）的概念，下面先舉例解釋命題與謂詞的關(guān)系。 例：H為謂詞“能夠到達(dá)山頂”。 L表示個(gè)體名稱李四。 T表示個(gè)體名稱老虎。 C表示個(gè)體名稱汽車。 那么H（L），H（

20、T），H（C）等分別表示各種不同的命題，但它們都有一個(gè)共同的形式，即H（X）。當(dāng)X取L，T，C時(shí)就表示了，“李四能夠到達(dá)山頂”，“老虎能夠到達(dá)到山頂”，“汽車能夠到達(dá)山頂”。,22,同理，若L（x，y）表示“x小于y”，那么L（2，3）表示了一個(gè)真命題：“2小于3”。而L（5，1）表示一個(gè)假命題：“5小于1”。 又如A（x，y，z）表示一個(gè)關(guān)系“x+y=z”。則A（3，2，5）表示了真命題“3+2=5”。而A（1，2，4）

21、表示了一個(gè)假命題“1+2=4”。 總之從上述三個(gè)例子可以看到H（x），L（x，y），A（x，y，z）本身不是一個(gè)命題，只有當(dāng)x，y，z等取特定的個(gè)體時(shí)，才確定了一個(gè)命題。即給出如下定義：,23,定義：由一個(gè)謂詞及一些個(gè)體變?cè)M成的表達(dá)式稱為命題函詞（函數(shù)）。 根據(jù)這個(gè)定義可以看到，n元謂詞是有n個(gè)個(gè)體變?cè)~（函數(shù)），當(dāng)n=0時(shí)稱為0元函詞，它本身就是一個(gè)命題，記為a，b，c。通常稱它為常量。故命題是n元謂詞的

22、一個(gè)特殊情況。 由一個(gè)或n個(gè)簡(jiǎn)單函詞（函數(shù)）以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式稱為復(fù)合命題函詞（函數(shù)）。邏輯聯(lián)結(jié)詞┐，∧，∨，→，?。 例如：R（x）表示“x是大學(xué)生”，如果x的討論范圍為某大學(xué)班級(jí)里的學(xué)生，則R（x）是永真式。如果x的討論范圍為某中學(xué)班級(jí)里的學(xué)生，則R（x）是永假式。,24,§3.2.3 自由變?cè)c約束變?cè)?在闡述自由變?cè)c約束變?cè)笆紫纫o出謂詞演算公式的概念。

23、 定義：由命題變?cè)椭^詞填式利用真值聯(lián)結(jié)詞和量詞如下構(gòu)成的式子稱為謂詞演算公式（簡(jiǎn)稱公式）。 （1）命題變?cè)枪剑?（2）填以個(gè)體變?cè)闹^詞變?cè)钍绞枪剑?（3） 如果A是公式，則┐A也是公式； （4）如果A和B是公式，則（A∨B），（A∧B）， （A→B），（A ? B）也是公式； （5）如果A是公式，x是個(gè)體變?cè)獎(jiǎng)t x (A),ヨx(A）也都是公式； （6）公式

24、僅限于此。,25,定義：一個(gè)公式中如果其中有一部分公式形式如: x (A)或ヨx(A)，則凡在這部分中的變?cè)獂的一切出現(xiàn)都叫做在此公式中的約束出現(xiàn)，而變?cè)獂叫做此公式中的約束變?cè)?例如： x（P（x）→F（x））中的變?cè)獂的二次出現(xiàn)均是約束出現(xiàn)。,26,定義：一公式中如果其中有一部分公式內(nèi)變?cè)獂 不呈約束出現(xiàn)，則稱x在此公式中自由出現(xiàn)， 而此變?cè)獂稱此公式的自由變?cè)?例如： x（P（x）→F（x））→Q(y)中的變?cè)獃

25、是自由出現(xiàn)，所以y是自由變?cè)?每個(gè)量詞都有個(gè)轄域，除原子公式外，量詞的轄域既是出現(xiàn)在它后面的括號(hào)內(nèi)的公式。,通過語(yǔ)法分析樹也可以判定自由出現(xiàn)和約束出現(xiàn)（詳見教材）。請(qǐng)分析：（ x(P(x)∧Q(x))) →(┐P(x)∨Q(y)),27,關(guān)于約束變?cè)c自由變?cè)覀冊(cè)倥e一些例子： 例1： x （P（x）→ヨyR（x，y））此公式變?cè)獂，y均為約束出現(xiàn)，無自由出現(xiàn)。 例2：ヨuP（x，

26、z）此公式中變?cè)獂,z為自由出現(xiàn)。 例3： x P（x）∧Q（x）此公式中變?cè)獂即約束出現(xiàn)，又自由出現(xiàn)。 例子中，我們要作一些說明，我們認(rèn)為在一個(gè)公式中允許一個(gè)變?cè)醋杂沙霈F(xiàn)又為約束出現(xiàn)。但為了避免概念上的混肴起見，我們有時(shí)通過改名規(guī)則，使得一個(gè)變?cè)谝粋€(gè)公式中只有一種形式出現(xiàn)，（即或者自由出現(xiàn)或者約束出現(xiàn)）。這樣就避免了二義性。,28,一個(gè)公式的約束變?cè)姆?hào)是無關(guān)緊要的，如公式 x P（x）中如將約束變?cè)?/p>

27、x改為y，則公式 yP（y）與公式 x P（x）具有相同的意義。所以一公式中約束變?cè)强梢愿牡模窃诟臅r(shí)必須要遵守一定的規(guī)則，即約束變?cè)母拿?guī)則。 第一.改名是對(duì)約束變?cè)?，不是?duì)自由變?cè)裕簿褪钦f可以對(duì)約束變?cè)┬懈拿?，不能?duì)自由變?cè)┬懈拿?為什么呢？,29,我們舉例說明： 例如： x（x=y∨x≠y）該式中的約束變?cè)獂可以改名為u，v，w等結(jié)果為： u（u=y∨u≠y

28、）， v （v=y∨v≠y）， w（w = y∨w≠y）等。顯然經(jīng)過改名后的這些式子與原式意義相同，都表示“任何個(gè)體都或者等于y或者不等于y”。 若將原式的自由變?cè)拿麨閦這時(shí)所得到的式子就與原式的意義不同了。,30,第二．改名必須“處處”進(jìn)行。“處處”進(jìn)行的含義是當(dāng)對(duì)公式中受某個(gè)量詞約束出現(xiàn)均改名時(shí)，必須對(duì)原式中該變?cè)囊磺惺茉摿吭~約束的出現(xiàn)均改名，否則改名后將改變?cè)降募s束關(guān)系，即：改變了原式的意義。

29、 例如：將 x （x=y∨x≠y）中x的第一出現(xiàn)改為u第二出現(xiàn)不改則有： u（u=y∨x≠y）。 其意思是“任何個(gè)體u都或者等于y或者x不等于y”結(jié)果與原意不同，其錯(cuò)誤的根源在于改名后結(jié)果式的約束關(guān)系不同了。,31,第三．對(duì)受某個(gè)量詞約束的變?cè)拿麜r(shí)新名決不能與該量詞的作用域中的其它自由變?cè)７駝t改名后將改變?cè)降募s束關(guān)系，改變了原式的意義。 例如：將 x （x=y∨x≠y）中x改名為y則有：

30、 y（y=y∨y≠y）。 其意思是“任何個(gè)體都或者與自己相等或者與自己不等”，這與原意不同。,32,第四．對(duì)受某個(gè)量詞約束的變?cè)拿麜r(shí)新名能否與該量詞的作用域中的約束變?cè)?？回答是有時(shí)行有時(shí)不行。這是為什么呢？我們舉例說明： 例如： x（x2≥0∧ y（x=y∧ヨz（z>y）））。 該式中的約束變?cè)獂不能改名y（y是作用域中的約束變?cè)?，但可改名為z（z也是

31、作用域中的約束變?cè)驗(yàn)樵摴?x（x2 ≥0∧ y （x= y∧ヨz（z>y）））的意思是“對(duì)于任何個(gè)體，其平方必≥0，并且對(duì)于任何新個(gè)體，原個(gè)體都與新個(gè)體相等，并且存在一個(gè)個(gè)體，它大于該新個(gè)體”。而改名為y后的結(jié)果式為： y（y2 ≥0∧ y（y=y∧ヨ z（z>y))),33,其意思是“對(duì)于任何個(gè)體，其平方必≥0，并且對(duì)于任何新個(gè)體，新個(gè)體必與自己相等并且存在一個(gè)個(gè)體，它大

32、于該新個(gè)體”，顯然它們的意思不相同，從約束關(guān)系看，結(jié)果式的約束關(guān)系顯然與原來的約束關(guān)系不相同。但是： z（z2 ≥0∧ y （z=y ∧ヨz（z>y））） 意思與原式相同，從約束關(guān)系看，結(jié)果式的約束關(guān)系與原式一樣。 例如：上面這個(gè)例子中，如果將原式的約束變?cè)獃改名為其它變?cè)?，如改名為t，再將約束變?cè)獂改名為y結(jié)果式為： y（y2 ≥0∧ t（y=t∧ヨ z（z > t））） 顯然與原

33、來的約束關(guān)系完全相同，所以說這是正確的改名。,是否不改變?cè)s束關(guān)系的改名都是正確的改名呢？,確實(shí)如此。,34,總之改名規(guī)則用更加簡(jiǎn)單的途述為： （1）改名時(shí)需要更改的變?cè)?hào)范圍是量詞中的變?cè)约霸摿吭~轄域中此變?cè)屑s束出現(xiàn)處，而在公式之其余部分不變。 （2）對(duì)受某量詞約束的變?cè)拿麜r(shí)，新名決不能與該量詞的轄域中的其它自由變?cè)?（3）改名前與改名后的約束關(guān)系保持不變。,35,接下來我們?cè)谟懻?/p>

34、代入問題。 第一. 代入是對(duì)自由變?cè)?，也就是說對(duì)自由變?cè)墒┬写搿?第二. 特別注意代入是有條件的，不能盲目代入，不則將發(fā)生錯(cuò)誤。,36,例如： x（x=y?z） 該公式中的自由變?cè)獃可以代以2,z,y+z, sin(t)等因?yàn)榇牒蟮慕Y(jié)果式 x （x=2?z）, x（x= z ?z）, x （x=( y+ z )?z）, x （x=

35、(sin(t))?z）均是原式的特例,也就是說約束變?cè)獩]有變化,所以是正確的。 又例如: x (x=y.z) 由自由變?cè)獃代以x或者代以含x的式子就錯(cuò)了，如，自由變?cè)獃決不能代以x，x+t，sin(x)等等，代入后的結(jié)果式為： x (x=x·z)， x (x=（x+t）·z)， x (x=（sin(x)）

36、3;z)均不是原式的特例，也就是說這時(shí)的約束關(guān)系與原式不同。,37,再例如：如果一定要代以x或代以含x的項(xiàng)，則必須先把原式中的約束變?cè)拿?，使得與代入項(xiàng)無關(guān)，比如將上式改為u，而后施行代入，這時(shí)結(jié)果式為： u（u= x·z）， u （u= （x+t）· z）， u（u=（sin(x)）·z）顯然這是原式的特例，約束關(guān)系與原式一致。 第三.代入必須“處處”進(jìn)行。所

37、謂“處處”進(jìn)行是指當(dāng)對(duì)某自由變?cè)┬写霑r(shí)，必須對(duì)該公式中該變?cè)囊磺凶杂沙霈F(xiàn)均施行代入，否則將是錯(cuò)誤的。,38,第四.為了確保對(duì)自由個(gè)體變?cè)恼_代入，我們規(guī)定，代入前先對(duì)原式施行改名，使得原式中所有約束變?cè)c代入式中所有變?cè)ゲ幌嗤缓笤偈┬写搿?第五.對(duì)于命題變?cè)椭^詞變?cè)部墒┬写?，而且代入也是有條件的，其條件仍就是代入前后約束關(guān)系必須保持不變。下面我們舉例說明對(duì)命題變?cè)椭^詞變?cè)拇搿?39,例一. 試

38、在 y（p→A（y））→（p→ xA（x））中把p代入以ヨy B（x，y），和把p代以ヨx B（x，y） 注意：ヨy B（x，y），ヨx B（x，y）也可以寫為 ヨy B xy，ヨx Bxy。 解：因?yàn)閷?duì)p用ヨy B（x，y）代入以后約束關(guān)系不發(fā)生變化，所以可立即施行代入得 y（ヨy B（x，y）→A（y））→（ヨy B（x，y）→ x A（x））。

39、 對(duì)于 ヨx B（x，y）代p的情形，如盲目代入的話，約束關(guān)系就將發(fā)生變化，從而出現(xiàn)錯(cuò)誤，所以必須先將原式中的約束變?cè)獃改名，使之與代入式中的變?cè)獰o關(guān)，如將y改為t得 t（ ヨx B（x，y））→A（t))→(ヨx B（x，y）→ x A（x）） 這個(gè)結(jié)果顯然是原式的特例，故代入正確。,40,經(jīng)過分析為了確保對(duì)命題變?cè)拇胝_我們規(guī)定，代入前先對(duì)原式施行改名，然

40、后施行代入，顯然，按此規(guī)定施行代入，結(jié)果一定正確。而且一切正確的關(guān)于命題變?cè)拇刖砂创艘?guī)定得到。 謂詞變?cè)拇氡容^復(fù)雜，因?yàn)樵诠街袨榇俗冊(cè)且灾^詞填式的形式出現(xiàn)，因此在代入前應(yīng)先將代入的謂詞變成相應(yīng)的填式，然后再把代入好的填式代到原式中去，因此要使每個(gè)代入正確，必須保證二次代入均正確，即二次代入過程中的約束關(guān)系均不應(yīng)發(fā)生變化，我們舉例說明這一過程。,41,例2.試在 x（X（x，y）→y（x））→ヨyX

41、（t，y）中，把X（e1，e2）代以 tA（e1，e2，x，t )。 解：因?yàn)榇胧?tA（e1，e2，x，t）中x是自由變?cè)?，t是約束變?cè)?，而原式中謂詞填式X（x，y）中x是約束變?cè)匀裘つ看氲脑?，必須發(fā)生變?cè)靵y，產(chǎn)生錯(cuò)誤。為此必須先對(duì)原式及代入式進(jìn)行改名，使之相互間的變?cè)煌?，然后施行代入?1)先把代入式改名為 uA（e1，e2 ，x，u） 2)再把原式改名為

42、 z(X(z,y) →Y(z)) →ヨyX（t，y） 3)再作關(guān)于X(z,y)的代入式的填式 uA (z,y, x, u) 4) 再作關(guān)于X(t,y)的代入式的填式 uA(t,y, x, y) 5) 最后將這兩個(gè)填式3),4)代入到原式即可 z (u A(z,y,x,u) →Y(z)) →ヨyu A(t,y, x, y)

43、 同理,為了確保對(duì)謂詞變?cè)拇胝_,我們?nèi)匀粎⒄彰}變?cè)拇胍?guī)定執(zhí)行。,42,定義. 項(xiàng)的定義： （1）任何變量都是項(xiàng)。 （2）若c∈F是零元函數(shù)，則c是項(xiàng)。 （3）若t1, t2, . . . , tn是項(xiàng)，且f∈F的元n>0，則f(t1, t2, . . . , tn)是項(xiàng)。 （4）沒有其他形式的項(xiàng)。BNF寫法：t ::= x | c | f(t, . . . , t)，其中x在變量集合var中選??；c

44、在F中的零元函數(shù)符號(hào)中選?。籪在F中的多元函數(shù)符號(hào)中選取。Note:項(xiàng)的第一批構(gòu)建塊內(nèi)容是常量（零元函數(shù)）和變量；更復(fù)雜的項(xiàng)是由以前構(gòu)造好的項(xiàng)與其元數(shù)相匹配數(shù)目的函數(shù)符號(hào)得到的；項(xiàng)的概念依賴于集合F，如果改變了F ，就改變了項(xiàng)的集合。,43,定義. 給定變量x,項(xiàng)t和公式φ，定義φ[t/x]為用t代替φ中變量x的每個(gè)自由出現(xiàn)而得到的公式。 Note:φ[t/x]實(shí)際意味著對(duì)φ實(shí)施運(yùn)算[t/x]所得到的公式；如果φ是公式，則

45、φ[t/x] 也是一個(gè)公式；替代過程應(yīng)滿足前面討論的改名和代入規(guī)則。,44,定義. 給定變量x,項(xiàng)t和公式φ，說t關(guān)于φ中的x是自由的，如果對(duì)出現(xiàn)在t中的任何變量y，φ中沒有自由的葉子結(jié)點(diǎn)x處于?y或?y的作用范圍之內(nèi)。 Note:實(shí)質(zhì)上是不能由替換引入多余的約束。例子：,用項(xiàng)f(x,y)替代x,45,例子：,用項(xiàng)f(y,y)替代x,,46,§3.3 謂詞邏輯的證明論§3.3.1 自然演繹規(guī)則

46、謂詞邏輯中自然演繹演算的證明和命題邏輯一致，但是需要增加新的規(guī)則，用于處理量詞和相等符號(hào)。 對(duì)量詞和相等的附加規(guī)則以兩種形式出現(xiàn)：引入規(guī)則和消去規(guī)則。,47,1. 相等的證明規(guī)則 相等的含義：不是語(yǔ)義或內(nèi)在的相等，而是計(jì)算結(jié)果的相等。由于任何項(xiàng)t必然與它本身相等，所以有“相等引入規(guī)則”： （3-5）Note：僅當(dāng)t為項(xiàng)時(shí)，這個(gè)規(guī)則才被引用 更一般地，我

47、們需要一個(gè)可以反復(fù)做相等代換的規(guī)則?？梢詫⒋鷵Q表示為規(guī)則=e： Note:無論何時(shí)引用規(guī)則=e，都要求t1和t2對(duì)φ中的x是自由的。,48,約定. 寫形如φ[t/x]的代換時(shí)，假定t對(duì)φ中變量x是自由的。Note:由上一節(jié)，沒有此約定條件，代換是沒有意義的。例子：證明矢列

48、 （3-6）證明：,49,例子：證明矢列 （3-7）證明：Note：對(duì)規(guī)則=i和=e的討論說明相等具有自反性 (3-5) 對(duì)稱性 (3-6) 傳遞性 (3-7),50,2. 全稱量詞的證明規(guī)則

49、 ?的消去規(guī)則如下：它的含義是： 若?xφ是真的，可以將φ中的x用任何項(xiàng)t去代替（要求t關(guān)于φ中的x是自由的），并且可以得出φ[t/x]也是真的。證明:φ[t/x]是通過把φ中所有自由出現(xiàn)的x用t代換得到的?？梢詫視為x的一個(gè)更為具體的實(shí)例。因?yàn)槲覀兗俣甩諏?duì)所有x的取值都是真的，則φ對(duì)于任何項(xiàng)t的情形也應(yīng)該是真。,51,討論:φ=?y(x<y)，用項(xiàng)y代換x。假設(shè)用“小于”關(guān)系研究關(guān)于數(shù)的推理。?xφ的含義是：

50、對(duì)所有的數(shù)n，必然存在某個(gè)比n大的數(shù)m，這對(duì)自然數(shù)和實(shí)數(shù)都正確。然而，φ [y/x]是公式?y(y<y) ，顯然不正確。原因？,52,?的引入規(guī)則如下：它的含義是： 如果從一個(gè)“新”變量x0開始，能證明帶有x0的公式φ[x0/x]，則可以推導(dǎo)出?xφ。證明: x0是新變量，不能出現(xiàn)在框外的任何地方，稱為任意項(xiàng)。因?yàn)閷?duì)x0沒有任何約束，在它的位置上可以是任何內(nèi)容，因此結(jié)論為?xφ。 如果可以

51、證明對(duì)沒有任何特殊性的x0，φ是真的，那么就是證明了對(duì)任意的x， φ是真的。,53,例子:證明矢列?x (P(x) → Q(x)), ?xP(x) ├ ?xQ(x)。,54,例子:證明矢列P(t), ?x (P(x) → ┐Q(x)) ├ ┐Q(t)。,55,討論:參照∧ 規(guī)則去理解? 規(guī)則關(guān)于? 的規(guī)則可以看成是關(guān)于∧的規(guī)則的推廣： ∧只有兩個(gè)合取項(xiàng)，而? 是多個(gè)公式的合?。總€(gè)公式都是它的變量的代換實(shí)例）。因此， ∧i有兩個(gè)前提，

52、而?xi的前提是φ[x0/x]，x0是變量x的每一個(gè)可能取值。類似地， ∧e可以從φ∧ψ推導(dǎo)需要的φ和ψ，而?e可以從?xφ推導(dǎo)φ[t/x]，只要t是需要的任何項(xiàng)（t需要滿足： t關(guān)于φ中的x是自由的）。也就是：為了證明?xφ，必須對(duì)每個(gè)可能取之x0，證明φ[x0/x]；而∧i表示為了證明φ1∧φ2，必須證明φi, i=1,2。,56,3. 存在量詞的證明規(guī)則 關(guān)于?和∧的規(guī)則可以推廣到?和∨ 從對(duì)∨規(guī)則的分析聯(lián)想到關(guān)于?的規(guī)則

53、考察： k=1，2聯(lián)想到：從全稱消去規(guī)則推出存在引入規(guī)則？因?yàn)楣溅誟t/x]包含了比?xφ更多的的信息： ?xφ只是說φ對(duì)x的某個(gè)非特指值成立，而φ[t/x]則表示t是任意一個(gè)證據(jù)。其中應(yīng)保證φ本身是正確的,,57,推廣: 由?和∨

54、之間的關(guān)系，推廣∨e，可得：Note： ?xφ為真，所以φ至少對(duì)一個(gè)x的取值是真的，x0就是所有可能取的一個(gè)一般的值 若通過φ[x0/x]能證明某個(gè)不涉及x0的命題χ，則不管x0是否使φ[x0/x]為真，都有χ是真的 x0不能出現(xiàn)在框外，特別地，不能出現(xiàn)在χ中,,58,例子:證明矢列?xφ├ ?xφ 例子:證明矢列?x(P(x)?Q(x)), ?xP(x)├ ?xQ(x

55、)的有效性,,新參數(shù)x0越出了作用范圍框,,59,,,60,例子:證明矢列?x (Q(x) → R(x)), ?x (P(x) ∧ Q(x)) ├ ?x (P(x) ∧ R(x))事實(shí)：如果所有的學(xué)生會(huì)成員都是黨員，且存在科協(xié)成員是學(xué)生會(huì)成員，則必有科協(xié)成員是黨員,,61,例子:證明矢列?xP(x), ?x ?y (P(x) → Q(y)) ├ ?yQ(y),,,62,注意：?jiǎn)∽兞坎荒艹霈F(xiàn)在它們控制的范圍框以外例子：?xP(x),

56、?x (P(x) → Q(x)) ├ ?yQ(y).,63,§3.3.2 量詞的等價(jià) 考察：“不是所有的鳥都會(huì)飛”¬?x (B(x) →F(x)) or ?x (B(x)∧ ¬F(x)). 定理：設(shè)φ和ψ是謂詞邏輯公式，具有下面的等價(jià)性：,64,1. (a) ¬?xφ┤├?x¬φ (b) ¬?xφ┤├?x¬φ.2. 假設(shè)x

57、在ψ中不是自由的，那么， (a) ?xφ ∧ ψ┤├?x (φ ∧ ψ) (b) ?xφ ∨ ψ┤├?x (φ ∨ ψ) (c) ?xφ ∧ ψ┤├?x (φ ∧ ψ) (d) ?xφ ∨ ψ┤├?x (φ ∨ ψ) (e) ?x (ψ → φ) ┤├ψ → ?xφ (f) ?x (φ → ψ) ┤├?xφ → ψ (g) ?x (φ →

58、ψ) ┤├?xφ → ψ (h) ?x (ψ → φ) ┤├ψ → ?xφ.3. (a) ?xφ ∧ ?xψ ┤├?x (φ ∧ ψ) (b) ?xφ ∨ ?xψ ┤├?x (φ ∨ ψ).4. (a) ?x ?y φ ┤├?y ?xφ (b) ?x ?y φ ┤├?y ?xφ.,65,挑選1.(a)、2(a) 來證明證明1.(a) ：¬?xφ┤├?x¬φ先考慮證明&

59、#172;(p1 ∧ p2) ├¬p1 ∨¬p2,66,再考慮證明¬?xP(x) ├ ?x¬P(x),67,進(jìn)入正題： ¬?xφ├?x¬φ,68,再證： ?x¬φ├ ¬?xφ,69,證明2(a)： ?xφ ∧ ψ┤├?x (φ ∧ ψ)先證?xφ ∧ ψ├?x (φ ∧ ψ),與6相同，因?yàn)閤在ψ中不是自由的,70,再證?x (φ ∧ ψ) ├ ?xφ ∧

60、 ψ,與3相同，因?yàn)閤在ψ中不是自由的,71,§3.4 謂詞邏輯的語(yǔ)義語(yǔ)義與證明論的真正區(qū)別：證明論的目標(biāo)是“構(gòu)建一個(gè)證明”假設(shè)一組公式φ1，φ2，…，φn簡(jiǎn)寫為Γ，為證明Γ├ ψ是有效的，需要構(gòu)建一個(gè)從Γ到ψ的證明。如何證明ψ不是Γ的推導(dǎo)結(jié)果呢？——不容易證明論只給出了邏輯的一個(gè)“正面”刻畫；它為諸如“Γ├ ψ是有效的”這樣的矢列提供了確鑿的證據(jù)，但是對(duì)建立形如“Γ├ ψ是無效的”的論斷卻能力不足。,72,語(yǔ)義

61、的作用方式正好相反證明ψ不是Γ的語(yǔ)義推導(dǎo)結(jié)果顯得容易：找一個(gè)模型，使得φi是真的，但ψ卻非真。 相反，證明ψ是Γ的語(yǔ)義推導(dǎo)結(jié)果，則比較困難。這需要證明每個(gè)使得φi是真的賦值，均使ψ為真，這涉及φi的所有原子命題的真值計(jì)算。語(yǔ)義學(xué)里，有邏輯的“否定”特征。發(fā)現(xiàn)確立Γ╞ψ的論斷比確立形如Γ╞ψ的論斷容易得多，前者只需涉及一個(gè)模型 ，后者可能需要涉及到無窮多個(gè)模型。,,73,這表明：同時(shí)研究證明論和語(yǔ)義的重要性。對(duì)于謂詞邏輯

62、，證明論和語(yǔ)義是等價(jià)的,74,§3.4.1 模型命題邏輯中的賦值本質(zhì)上是公式的真值表的一行的構(gòu)建，謂詞邏輯中如何對(duì)公式賦值？如何處理量詞？?yψ：試著尋找y的某個(gè)實(shí)例，使得ψ對(duì)y的具體實(shí)例成立。如果成功了，則?yψ為T，否則返回值是F。?xψ：要說明ψ對(duì)x的所有可能取值都賦值為T。若成功，則?xψ賦值為T，否則返回F。這樣的賦值需要一個(gè)固定的論域。在知道項(xiàng)ti的含義之前，不能直接對(duì)P（ t1，t2，…，tn ）賦真值

63、，需要一個(gè)涉及所有函數(shù)和謂詞符號(hào)的模型。,75,定義：假設(shè)F是函數(shù)符號(hào)的集合，P是謂詞符號(hào)的集合，每個(gè)符號(hào)所需的參數(shù)的個(gè)數(shù)是固定的。符號(hào)對(duì)兒(F,P)的一個(gè)模型M包含如下的數(shù)據(jù)集合：1.一個(gè)包含具體值的全集的非空集合A2.對(duì)于每個(gè)零元函數(shù)符號(hào)f∈F，對(duì)應(yīng)A中的一個(gè)具體元素fM3.對(duì)每個(gè)元數(shù)為n>0的f∈F，從集合A上n元組An到A的具體函數(shù)fM：An → A4.對(duì)每個(gè)元數(shù)n>0的謂詞P∈P，A上的n元組An的子集PM

64、：PM?An Note：f和P是符號(hào)， fM和PM分別表示模型M中的一個(gè)具體函數(shù)（或元素）和關(guān)系,76,例子：令 ， ；其中i是常量，F(xiàn)是一個(gè)一元謂詞符號(hào)，R是一個(gè)二元謂詞符號(hào)。模型M包含一組具體元素的集合A，它可能是計(jì)算機(jī)程序的狀態(tài)集合。則iM、RM、FM可以分別解釋為設(shè)計(jì)的初始狀態(tài)、狀態(tài)遷移關(guān)系和最終狀態(tài)的集合。例如，令 ， a,

65、 , 對(duì)這個(gè)模型非形式化地檢驗(yàn)一些謂詞邏輯公式：1. 公式,存在從初始狀態(tài)到某個(gè)狀態(tài)的遷移。,77,2. 公式表示：初始狀態(tài)不是可接受的最終狀態(tài)。3. 公式表示：狀態(tài)之間的遷移關(guān)系具有確定性，即始于任何一個(gè)狀態(tài)的所有遷移都至多到一個(gè)狀態(tài)。4. 公式表示：這個(gè)模型不存在死鎖，即任何狀態(tài)都可以遷移到某

66、個(gè)狀態(tài)。,78,定義：對(duì)具體值的論域A，一個(gè)查詢表或環(huán)境指的是從變量集合var到A的函數(shù)l：var?A。對(duì)這樣的l，用 表示將x映射到a并將其他變量y映射到l(y)的查詢表。定義：給定關(guān)于(F,P)的模型M和環(huán)境l，對(duì)于(F,P)上的每個(gè)邏輯公式φ和查詢表l，通過對(duì)φ的結(jié)構(gòu)歸納定義一個(gè)滿足關(guān)系 。若 成立，則稱在模型M中，相對(duì)于環(huán)境l，φ的賦值為T。

67、 P: 如果φ的形式為P(t1, t2,…, tn)，則在集合A中將t1, t2,…, tn解釋為：根據(jù)l把所有變量用它們的值代替。用這種方式，對(duì)這些項(xiàng)的每項(xiàng)來計(jì)算A的具體值a1, a2,…, an，其中任何函數(shù)符號(hào)f∈F可通過fM來描述。 成立當(dāng)且僅當(dāng)(a1, a2,…, an)在PM集合中。,79,?x: 關(guān)系 成立，當(dāng)且僅當(dāng)

68、 對(duì)所有a∈A都成立。?x：對(duì)偶地，關(guān)系 成立，當(dāng)且僅當(dāng) 對(duì)某個(gè)a∈A成立。﹁：關(guān)系 成立，當(dāng)且僅當(dāng) 不成立?！牛宏P(guān)系 成立，當(dāng)且僅當(dāng) 或 成立?！模宏P(guān)系

69、成立，當(dāng)且僅當(dāng) 和 都成立?！宏P(guān)系 成立，當(dāng)且僅當(dāng)只要 成立，則 成立。有時(shí)，用 表示 不成立。,80,歸納論斷： 成立，當(dāng)且僅當(dāng) 成立，只要l與l’是φ的自由變量上的兩個(gè)相同環(huán)境。特別地，如果