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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、為實數(shù)時，此時表示式為真：ヨx（x+6=5）符號“ヨx” 為存在量詞，同理，它后面緊跟著括號內(nèi)的式子稱作存在量詞的轄域。,17,一個不確定的公式只要對其所有變元均施加量詞后則均為確定的了。如：x+6=5因為當x=-1時它為真（T），當x=3時它為假（F）。但是當使用量詞后ヨx（x+3=5）則是確定的，因為它總是為真（T）。 這個論點一般而言是正確的，但是它是有前提的，也就是在確定的個體域條件下，一公式所有個體變元均施加量詞后，

16、它就是確定的了。,18,通過例子我們發(fā)現(xiàn)：1.量詞所確定的公式與個體域有關(guān)。2.對不同的個體域表達式可有不同的值。也就是說，各變元的變域（個體域）須做臨時約定。各變元的性質(zhì)（全稱或存在性）須做臨時約定。因此在謂詞演算中，每個個體變元的個體域必需是確定的。因此可見，量詞所確定的公式與個體域有關(guān)，對不同的個體域表達式的值不同。 例如：ヨx（x+6=5）中，當個體域為實數(shù)時它為T，但當個體域為自然數(shù)時它為F。,19,因此，

17、在謂詞演算中，每個個體變元的個體域必需是確定的 。但有時為了討論方便起見，我們干脆將謂詞演算中所有個體域統(tǒng)一，一律用全總個體域。用了全總個體域后，對每個個體變元的變化范圍用一定特性謂詞去刻劃。對全稱量詞，此特性謂詞可作為蘊含前件而加入。對存在量詞，此特性謂詞可作為合取式的合取項加入。 例如：上二式中設R（x）表示x為實數(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））有了量詞的概念后，謂詞演算表達能力就廣泛的多了，它所能刻劃的語句也普遍，深入。,20,下面我們舉例說明：,例1：沒有不犯錯誤的人 解：設F（x）為“x犯錯誤”其特性謂詞為M（x），“表示x為人”此句可譯為： ┐（ヨx（M（x）∧┐F（x））,例2：凡是實數(shù)不是大于零就是等于零或者小于零。 解

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

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

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

22、一個特殊情況。 由一個或n個簡單函詞（函數(shù)）以及邏輯聯(lián)結(jié)詞組合而成的表達式稱為復合命題函詞（函數(shù)）。邏輯聯(lián)結(jié)詞┐，∧，∨，→，?。 例如：R（x）表示“x是大學生”，如果x的討論范圍為某大學班級里的學生，則R（x）是永真式。如果x的討論范圍為某中學班級里的學生，則R（x）是永假式。,24,§3.2.3 自由變元與約束變元 在闡述自由變元與約束變元之前首先要給出謂詞演算公式的概念。

23、 定義：由命題變元和謂詞填式利用真值聯(lián)結(jié)詞和量詞如下構(gòu)成的式子稱為謂詞演算公式（簡稱公式）。 （1）命題變元是公式； （2）填以個體變元的謂詞變元填式是公式； （3） 如果A是公式，則┐A也是公式； （4）如果A和B是公式，則（A∨B），（A∧B）， （A→B），（A ? B）也是公式； （5）如果A是公式，x是個體變元則 x (A),ヨx(A）也都是公式； （6）公式

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

25、是自由出現(xiàn)，所以y是自由變元。 每個量詞都有個轄域，除原子公式外，量詞的轄域既是出現(xiàn)在它后面的括號內(nèi)的公式。,通過語法分析樹也可以判定自由出現(xiàn)和約束出現(xiàn)（詳見教材）。請分析：（ x(P(x)∧Q(x))) →(┐P(x)∨Q(y)),27,關(guān)于約束變元與自由變元我們再舉一些例子： 例1： x （P（x）→ヨyR（x，y））此公式變元x，y均為約束出現(xiàn)，無自由出現(xiàn)。 例2：ヨuP（x，

26、z）此公式中變元x,z為自由出現(xiàn)。 例3： x P（x）∧Q（x）此公式中變元x即約束出現(xiàn)，又自由出現(xiàn)。 例子中，我們要作一些說明，我們認為在一個公式中允許一個變元即自由出現(xiàn)又為約束出現(xiàn)。但為了避免概念上的混肴起見，我們有時通過改名規(guī)則，使得一個變元在一個公式中只有一種形式出現(xiàn)，（即或者自由出現(xiàn)或者約束出現(xiàn)）。這樣就避免了二義性。,28,一個公式的約束變元的符號是無關(guān)緊要的，如公式 x P（x）中如將約束變元

27、x改為y，則公式 yP（y）與公式 x P（x）具有相同的意義。所以一公式中約束變元是可以更改的，但是在更改時必須要遵守一定的規(guī)則，即約束變元的改名規(guī)則。 第一.改名是對約束變元而言，不是對自由變元而言，也就是說可以對約束變元施行改名，不能對自由變元施行改名。,為什么呢？,29,我們舉例說明： 例如： x（x=y∨x≠y）該式中的約束變元x可以改名為u，v，w等結(jié)果為： u（u=y∨u≠y

28、）， v （v=y∨v≠y）， w（w = y∨w≠y）等。顯然經(jīng)過改名后的這些式子與原式意義相同，都表示“任何個體都或者等于y或者不等于y”。 若將原式的自由變元改名為z這時所得到的式子就與原式的意義不同了。,30,第二．改名必須“處處”進行?！疤幪帯边M行的含義是當對公式中受某個量詞約束出現(xiàn)均改名時，必須對原式中該變元的一切受該量詞約束的出現(xiàn)均改名，否則改名后將改變原式的約束關(guān)系，即：改變了原式的意義。

29、 例如：將 x （x=y∨x≠y）中x的第一出現(xiàn)改為u第二出現(xiàn)不改則有： u（u=y∨x≠y）。 其意思是“任何個體u都或者等于y或者x不等于y”結(jié)果與原意不同，其錯誤的根源在于改名后結(jié)果式的約束關(guān)系不同了。,31,第三．對受某個量詞約束的變元改名時新名決不能與該量詞的作用域中的其它自由變元同名。否則改名后將改變元式的約束關(guān)系，改變了原式的意義。 例如：將 x （x=y∨x≠y）中x改名為y則有：

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

31、作用域中的約束變元），因為該公式 x（x2 ≥0∧ y （x= y∧ヨz（z>y）））的意思是“對于任何個體，其平方必≥0，并且對于任何新個體，原個體都與新個體相等，并且存在一個個體，它大于該新個體”。而改名為y后的結(jié)果式為： y（y2 ≥0∧ y（y=y∧ヨ z（z>y))),33,其意思是“對于任何個體，其平方必≥0，并且對于任何新個體，新個體必與自己相等并且存在一個個體，它大

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

33、來的約束關(guān)系完全相同，所以說這是正確的改名。,是否不改變原約束關(guān)系的改名都是正確的改名呢？,確實如此。,34,總之改名規(guī)則用更加簡單的途述為： （1）改名時需要更改的變元符號范圍是量詞中的變元以及該量詞轄域中此變元所有約束出現(xiàn)處，而在公式之其余部分不變。 （2）對受某量詞約束的變元改名時，新名決不能與該量詞的轄域中的其它自由變元同名。 （3）改名前與改名后的約束關(guān)系保持不變。,35,接下來我們在討論

34、代入問題。 第一. 代入是對自由變元而言，也就是說對自由變元可施行代入。 第二. 特別注意代入是有條件的，不能盲目代入，不則將發(fā)生錯誤。,36,例如： x（x=y?z） 該公式中的自由變元y可以代以2,z,y+z, sin(t)等因為代入后的結(jié)果式 x （x=2?z）, x（x= z ?z）, x （x=( y+ z )?z）, x （x=

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

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

37、謂“處處”進行是指當對某自由變元施行代入時，必須對該公式中該變元的一切自由出現(xiàn)均施行代入，否則將是錯誤的。,38,第四.為了確保對自由個體變元的正確代入，我們規(guī)定，代入前先對原式施行改名，使得原式中所有約束變元名與代入式中所有變元名互不相同，然后再施行代入。 第五.對于命題變元和謂詞變元也可施行代入，而且代入也是有條件的，其條件仍就是代入前后約束關(guān)系必須保持不變。下面我們舉例說明對命題變元和謂詞變元的代入。,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。 解：因為對p用ヨy B（x，y）代入以后約束關(guān)系不發(fā)生變化，所以可立即施行代入得 y（ヨy B（x，y）→A（y））→（ヨy B（x，y）→ x A（x））。

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

40、后施行代入，顯然，按此規(guī)定施行代入，結(jié)果一定正確。而且一切正確的關(guān)于命題變元的代入均可按此規(guī)定得到。 謂詞變元的代入比較復雜，因為在公式中為此變元均是以謂詞填式的形式出現(xiàn)，因此在代入前應先將代入的謂詞變成相應的填式，然后再把代入好的填式代到原式中去，因此要使每個代入正確，必須保證二次代入均正確，即二次代入過程中的約束關(guān)系均不應發(fā)生變化，我們舉例說明這一過程。,41,例2.試在 x（X（x，y）→y（x））→ヨyX

41、（t，y）中，把X（e1，e2）代以 tA（e1，e2，x，t )。 解：因為代入式 tA（e1，e2，x，t）中x是自由變元，t是約束變元，而原式中謂詞填式X（x，y）中x是約束變元，所以若盲目代入的話，必須發(fā)生變元混亂，產(chǎn)生錯誤。為此必須先對原式及代入式進行改名，使之相互間的變元均不同名，然后施行代入。 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) 最后將這兩個填式3),4)代入到原式即可 z (u A(z,y,x,u) →Y(z)) →ヨyu A(t,y, x, y)

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

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

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

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

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

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

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

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

51、證明對沒有任何特殊性的x0，φ是真的，那么就是證明了對任意的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ī)則的推廣： ∧只有兩個合取項，而? 是多個公式的合?。總€公式都是它的變量的代換實例）。因此， ∧i有兩個前提，

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

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

54、之間的關(guān)系，推廣∨e，可得：Note： ?xφ為真，所以φ至少對一個x的取值是真的，x0就是所有可能取的一個一般的值 若通過φ[x0/x]能證明某個不涉及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))事實：如果所有的學生會成員都是黨員，且存在科協(xié)成員是學生會成員，則必有科協(xié)成員是黨員,,61,例子:證明矢列?xP(x), ?x ?y (P(x) → Q(y)) ├ ?yQ(y),,,62,注意：啞變量不能出現(xiàn)在它們控制的范圍框以外例子：?xP(x),

56、?x (P(x) → Q(x)) ├ ?yQ(y).,63,§3.3.2 量詞的等價 考察：“不是所有的鳥都會飛”¬?x (B(x) →F(x)) or ?x (B(x)∧ ¬F(x)). 定理：設φ和ψ是謂詞邏輯公式，具有下面的等價性：,64,1. (a) ¬?xφ┤├?x¬φ (b) ¬?xφ┤├?x¬φ.2. 假設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,進入正題： ¬?xφ├?x¬φ,68,再證： ?x¬φ├ ¬?xφ,69,證明2(a)： ?xφ ∧ ψ┤├?x (φ ∧ ψ)先證?xφ ∧ ψ├?x (φ ∧ ψ),與6相同，因為x在ψ中不是自由的,70,再證?x (φ ∧ ψ) ├ ?xφ ∧

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

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

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

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

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

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

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

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

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

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