重慶大學(xué)《離散數(shù)學(xué)》課件第2章-謂詞邏輯

1離散數(shù)學(xué)

Lecture2謂詞邏輯(PredicateLogic)胡春強(qiáng)重慶大學(xué)大數(shù)據(jù)與軟件學(xué)院第二章謂詞邏輯（PredicateLogic）

2-1謂詞的概念與表示2-2命題函數(shù)與量詞2-3謂詞公式與翻譯2-4變?cè)募s束2-5謂詞演算的等價(jià)式與蘊(yùn)含式2-7前束范式2-7謂詞演算的推理理論2-1謂詞的概念與表示(PredicateandItsExpression)命題邏輯的局限性：

在命題邏輯中，命題是命題演算的基本單位，不再對(duì)原子命題進(jìn)行分解，因而無法研究命題的內(nèi)部結(jié)構(gòu)、成分及命題之間的內(nèi)在聯(lián)系，甚至無法處理一些簡(jiǎn)單而又常見的推理過程。2-1謂詞的概念與表示(PredicateandItsExpression)例如，下列推理：所有的人都是要死的。蘇格拉底是人。蘇格拉底是要死的。眾所周知,這是真命題。但在命題邏輯中,如果用P,Q,R表示以上三個(gè)命題，則上述推理過程為：（P∧Q）

R。借助命題演算的推理理論不能證明其為重言式。

2-1謂詞的概念與表示(PredicateandItsExpression)原因：命題邏輯不能將命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系反映出來。解決辦法：將命題進(jìn)行分解。2.1謂詞的概念與表示(PredicateandItsExpression)2-1.1客體和謂詞

在謂詞邏輯中，可將原子命題劃分為客體和謂詞兩部分?？腕w：可以獨(dú)立存在的具體事物的或抽象的概念。例如，電子計(jì)算機(jī)、李明、玫瑰花、黑板、實(shí)數(shù)、中國(guó)、思想、唯物主義等，客體也可稱之為主語(yǔ)。2-1謂詞的概念與表示(PredicateandItsExpression)謂詞：用來刻劃客體的性質(zhì)或客體之間的相互關(guān)系的詞。例如在下面命題中：（1）張明是個(gè)勞動(dòng)模范。（2）李華是個(gè)勞動(dòng)模范?？虅澘腕w的性質(zhì)（3）王紅是個(gè)大學(xué)生。（4）小李比小趙高2cm。（5）點(diǎn)a在b與c之間?？虅澘腕w之間的相互關(guān)系（6）小李與小趙同歲。

“是個(gè)勞動(dòng)模范”、“是個(gè)大學(xué)生”、“…比…高2cm”、“…在…與…之間”都是謂詞。2-1謂詞的概念與表示(PredicateandItsExpression)刻劃一個(gè)客體性質(zhì)的詞稱之為一元謂詞,刻劃n個(gè)客體之間關(guān)系的詞稱之為n元謂詞.一般我們用大寫英文字母表示謂詞，用小寫英文字母表示客體名稱，例如，將上述謂詞分別記作大寫字母F、G、H、R，S則上述命題可表示為：

(1)F(a)a：張明(2)F(b)b：李華

(3)G(c)c：王紅(4)H(s,t)s：小李t：小趙

(5)R(a,b,c)(6)S(a,b)a:小李。b:小趙。其中(1)、(2)、(3)為一元謂詞，(4)、(6)為二元謂詞，

(5)為三元謂詞。2-1謂詞的概念與表示(PredicateandItsExpression)注:(1)單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母后填上客體所得到的式子稱之為謂詞填式。(2)在謂詞填式中，若客體確定，則A(a1，a2...an)就變成了命題(3)在多元謂詞表達(dá)式中，客體字母出現(xiàn)的先后次序與事先約定有關(guān),一般不可以隨意交換位置(如,上例中H(s,t)與H(t,s)代表兩個(gè)不同的命題)。

2-1謂詞的概念與表示(PredicateandItsExpression)設(shè)謂詞H表示“是勞動(dòng)模范”,a表示客體名稱張明,b表示客體名稱李華,c表示客體名稱這只老虎，那么H(a)、H(b)、H(c)表示三個(gè)不同的命題,但它們有一個(gè)共同的形式,即H(x).一般地，H(x)表示客體x具有性質(zhì)H。這里x表示抽象的或泛指的客體，稱為客體變?cè)?，常用小寫英文字母x,y,z,…表示。相應(yīng)地，表示具體或特定的客體的詞稱為客體常項(xiàng)，常用小寫英文字母a,b,c,…表示。

2-1謂詞的概念與表示(PredicateandItsExpression)同理，客體變?cè)獂，y具有關(guān)系L，記作L(x,y);客體變?cè)獂,y,z具有關(guān)系A(chǔ)，記作A(x,y,z).H(x)、L(x,y)、A(x,y,z)本身并不是一個(gè)命題.只有用特定的客體取代客體變?cè)獂,y,z后，它們才成為命題。2-2命題函數(shù)與量詞2-2.1命題函數(shù)一般來說，當(dāng)謂詞P給定，x1,x2,…,xn是客體變?cè)琍(x1,x2,…,xn)不是一個(gè)命題，因?yàn)樗恼嬷禑o法確定，要想使它成為命題，要用n個(gè)客體常項(xiàng)代替n個(gè)客體變?cè)?。P(x1,x2,…,xn)就是命題函數(shù)。比如L(x,y)表示“x小于y”，那么L(2,3)表示了一個(gè)真命題“2小于3”。而L(5,1)表示了一個(gè)假命題“5小于1”2-2.1命題函數(shù)定義2-2.1：簡(jiǎn)單命題函數(shù)(simplepropositionalfunction)：由一個(gè)謂詞，一些客體變?cè)M成的表達(dá)式稱為簡(jiǎn)單命題函數(shù)。比如：A(x)，B(x,y)，L(x,y,z)簡(jiǎn)單命題函數(shù)不是命題，只有當(dāng)變?cè)獂,y,z等取特定的客體才確定了一個(gè)命題。對(duì)于n元謂詞，當(dāng)n=0時(shí)，稱為0元謂詞，它本身就是一個(gè)命題，故命題是n元謂詞的一個(gè)特殊情況。2-2.1命題函數(shù)比如：L(x,y)表示“x小于y”是二元謂詞，L(x,3)表示“x小于3”是一元謂詞，L(2,3)表示“2小于3”是0元謂詞。因此可以將命題看成n元謂詞的一個(gè)特殊情況。

0元謂詞都是命題，命題邏輯中的簡(jiǎn)單命題都可以用0元謂詞表示。2-2.1命題函數(shù)定義2-2.2：復(fù)合命題函數(shù)（compoundpropositionalfunction）：由一個(gè)或n個(gè)簡(jiǎn)單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式。命題邏輯中的聯(lián)結(jié)詞在謂詞邏輯中含義完全相同。2-2.1命題函數(shù)定義2-2.3：謂詞填式單獨(dú)一個(gè)謂詞不是完整的命題，把謂詞字母以客體填后所得的式子稱為謂詞填式。例如：P(x)表示x>3，則P(1)、P(2)、P(5)分別表示1大于3，2大于3，5大于3，P(1)、P(2)、P(5)即是謂詞填式。2-2.1命題函數(shù)定義2-2.4：謂詞表達(dá)式簡(jiǎn)單命題函數(shù)與邏輯聯(lián)結(jié)詞組合而成。示例分析P59(1)a),b),c)設(shè)W(x):x是工人，z:小張，則原命題表示為：

W(z)設(shè)S(x):x是田徑運(yùn)動(dòng)員，B(x):x是球類運(yùn)動(dòng)員，h:他，則原命題表示為：S(h)

B(h)設(shè)C(x):x是聰明的，B(x):x是美麗的，a:小莉，則原命題表示為：C(a)

B(a)\\\注意：命題函數(shù)不是一個(gè)命題，只有客體變?cè)√囟腕w時(shí)，才能成為一個(gè)命題。但是客體變?cè)谀男┓秶√囟ǖ闹?，?duì)命題函數(shù)以下兩方面有極大影響：(1)命題函數(shù)是否能成為一個(gè)命題；(2)命題的真值是真還是假。2-2.1命題函數(shù)2-2.1命題函數(shù)個(gè)體域(universeofdiscourse)：在命題函數(shù)中，命題變?cè)恼撌龇秶Q為個(gè)體域。全總個(gè)體域：個(gè)體域可以是有限的，也可以是無限的，把各種個(gè)體域綜合在一起，作為論述范圍的域，稱為全總個(gè)體域。2-2.2量詞例題：符號(hào)化以下命題所有人都要死去。有的人的年齡超過百歲。以上給出的命題，除了有個(gè)體詞和謂詞以外，還有表示數(shù)量的詞，稱表示數(shù)量的詞為量詞。量詞有兩種：全稱量詞(universalquantifier)存在量詞(existentialquantifier)2-2.2量詞定義2-2.5．全稱量詞(universalquantifier)用符號(hào)“

”表示，“

x”表示對(duì)個(gè)體域里的所有個(gè)體。(

x)P(x)表示對(duì)個(gè)體域里的所有個(gè)體都有屬性P。表達(dá)“對(duì)所有的”，“每一個(gè)”，“對(duì)任一個(gè)”，“凡”，“一切”等詞。定義2-2-7．存在量詞(existentialquantifier)用符號(hào)“

”表示。

x表示存在個(gè)體域里的個(gè)體。(

x)P(x)表示存在個(gè)體域里的個(gè)體具有性質(zhì)P。符號(hào)“

”稱為存在量詞，用以表達(dá)“某個(gè)”，“存在一些”，“至少有一個(gè)”，“對(duì)于一些”等詞。2-2.2量詞現(xiàn)在對(duì)以上兩個(gè)命題進(jìn)行符號(hào)化，在進(jìn)行符號(hào)化之前必須確定個(gè)體域。第一種情況．個(gè)體域D為人類集合。設(shè)：F(x)：x是要死的。

G(x)：x活百歲以上。則有(

x)F(x)

和(

x)G(x)這兩個(gè)命題都是真命題2-2.2量詞

第二種情況．個(gè)體域D為全總個(gè)體域。不能符號(hào)化為(

x)F(x)和(

x)G(x)，因?yàn)?(x)F(x)表示宇宙間一切事物都要死的，這與原命題不符。(x)G(x)表示宇宙間一切事物中存在百歲以上，這與原命題不符。2-2.2量詞因此必須引入一個(gè)新的謂詞，將人分離出來。在全總個(gè)體域的情況下，以上兩個(gè)命題敘述如下：(1)對(duì)于所有個(gè)體而言，如果它是人，則它要死去。(2)存在著個(gè)體，它是人并且活過百歲以上。于是，再符號(hào)化時(shí)必須引入一個(gè)新的謂詞M(x)：x是人。稱這個(gè)謂詞為特性謂詞。2-2.2量詞定義：特性謂詞在討論帶有量詞的命題函數(shù)時(shí)，必須確定其個(gè)體域，為了方便，可使用全總個(gè)體域。限定客體變?cè)兓秶闹^詞，稱作特性謂詞。利用特性謂詞，對(duì)以上兩個(gè)命題進(jìn)行符號(hào)化(1)(

x)(M(x)→F(x))(2)(

x)(M(x)∧G(x))使用量詞時(shí)應(yīng)注意的問題：在討論有量詞的命題函數(shù)時(shí)如果事先沒有給出個(gè)體域，那么都應(yīng)以全總個(gè)體域?yàn)閭€(gè)體域。對(duì)全稱量詞，特性謂詞常做蘊(yùn)含的前件。對(duì)存在量詞，特性謂詞常做合取項(xiàng)。2-2.2量詞舉例說明：例1．“有些人是要死的”.解1：采用全體人作為個(gè)體域.

設(shè):G(x):x是要死的.原命題符號(hào)化成:(

x)G(x)解2：采用全總個(gè)體域.設(shè):M(x):x是人;G(x):x是要死的.原命題符號(hào)化成:(

x)(M(x)∧G(x))2-2.2量詞例2．“凡人都是要死的”.解1:采用全體人作為個(gè)體域.設(shè):G(x):x是要死的.原命題符號(hào)化成:(

x)G(x) 解2:

采用全總個(gè)體域.設(shè):M(x):x是人;G(x):x是要死的.原命題符號(hào)化成:(

x)(M(x)→G(x))2-2.2量詞例3:“存在最小的自然數(shù)”。解1:

采用全體自然數(shù)作為個(gè)體域.設(shè):G(x,y):x≤y;原命題符號(hào)化成:(

x)(

y)G(x,y)注意量詞順序:(y)(

x)G(x,y):“沒有最小的自然數(shù)”.解2:

設(shè):F(x):x是自然數(shù);G(x,y):x<y;原命題符號(hào)化成:(x)(F(x)∧(

y)(F(y)→G(x,y)))2-2.2量詞例4:“不存在最大的自然數(shù)”。解:

設(shè):F(x):x是自然數(shù);G(x,y):x＞y;原命題符號(hào)化成:(x)(F(x)(y)(F(y)

G(x,y)))或:(

x)(F(x)(y)(F(y)

G(y,x)))2-2.2量詞例5:“火車比汽車快”。解:

設(shè):F(x):x是火車;G(x):x是汽車;H(x,y):x比y快原命題符號(hào)化成:(x)(F(x)(y)(G(y)

H(x,y)))或:(

x)(

y)((F(x)

G(y))

H(x,y))2-2.2量詞例6:“有的汽車比火車快”。解:

設(shè):F(x):x是汽車;G(x):x是火車;H(x,y):x比y快原命題符號(hào)化成:(x)(F(x)(y)(G(y)

H(x,y)))或:(

x)(

y)(F(x)

G(y)

H(x,y))2-2.2量詞例7:“有些病人相信所有的醫(yī)生”。解:

設(shè):F(x):x是病人;G(x):x是醫(yī)生;H(x,y):x相信y原命題符號(hào)化成:(x)(F(x)(y)(G(y)

H(x,y)))2-2.2量詞例8:“存在唯一的對(duì)象滿足性質(zhì)P”。解:

設(shè):P(x):x滿足性質(zhì)P原命題符號(hào)化成:(!x)P(x)或:設(shè): P(x):x滿足性質(zhì)P;E(x,y):x和y是同一個(gè)個(gè)體原命題符號(hào)化成:(x)(P(x)

(

y)(P(y)

E(x,y)))2-2.2量詞第二章謂詞邏輯（PredicateLogic）

小結(jié):本節(jié)將原子命題進(jìn)行分解,分為客體和謂詞兩部分.進(jìn)而介紹了客體和謂詞、一元謂詞和n元謂詞、命題函數(shù)、全稱量詞和存在量詞等概念。重點(diǎn)掌握一元謂詞和n元謂詞的概念、全稱量詞和存在量詞及量化命題的符號(hào)化。2-3謂詞公式與翻譯(Predicateformulae)

n元謂詞A(x1，x2...xn)

稱為謂詞演算的原子公式。定義2-3.1謂詞演算的合式公式,可由下述各條組成:（1）原子謂詞公式是合式公式。（2）若A是合式公式，則(┐A)也是合式公式。（3）若A，B是合式公式，則(A∧B)，(A∨B)，

(A

B)，(A

B)也是合式公式。（4）若A是合式公式，x是A中出現(xiàn)的任何變?cè)?則(x)A,(x)A，也是合式公式。

(5)只有有限次應(yīng)用(1)~(4)得到的公式是合式公式.2-3謂詞公式與翻譯(Predicateformulae)例1：在謂詞邏輯中將下列命題符號(hào)化.（1）凡正數(shù)都大于零。（2）存在小于2的素?cái)?shù)。（3）沒有不能表示成分?jǐn)?shù)的有理數(shù)。（4）并不是所有參加考試的人都能取得好成績(jī)。解：（1）令F(x):x是正數(shù)。M(x):x大于零。則符號(hào)化為：（x）(F(x)M(x))2-3謂詞公式與翻譯(Predicateformulae)（2）令E(x):x小于2。S(x):x是素?cái)?shù)。則符號(hào)化為：

（x)(E(x)∧S(x))

真值為0。（3）令D(x):x是有理數(shù)。F(x):x能表示成分?jǐn)?shù)。則符號(hào)化為：(x)(D(x)

F(x))

或

┐(x)(D(x)∧┐F(x))

真值為１。（4）令M(x)：x是人.Q(x):x參加考試。H(x):x取得好成績(jī)。則符號(hào)化為：

┐(x)(M(x)∧Q(x)H(x))

或

(x)(M(x)∧Q(x)∧┐H(x))2-3謂詞公式與翻譯(Predicateformulae)例2：在謂詞邏輯中將下列命題符號(hào)化.

（1）所有運(yùn)動(dòng)員都?xì)J佩某些教練.（2）有些運(yùn)動(dòng)員不欽佩教練.設(shè)：L(x):x是運(yùn)動(dòng)員J(y):y是教練

A(x,y):x欽佩y(1)(x)(L(x)

（y)(J(y)∧A(x,y)))(2)（x)(L(x)

∧(y)(J(y)

┐A(x,y)))2-3謂詞公式與翻譯(Predicateformulae)小結(jié)：本節(jié)介紹了謂詞合式公式的概念，重點(diǎn)掌握謂詞公式的翻譯.2-4變?cè)募s束(Boundofvariable)2-4變?cè)募s束(Boundofvariable)2-4.1變?cè)募s束2-4.2約束變?cè)膿Q名與自由變?cè)拇?/p>

2-4變?cè)募s束(Boundofvariable)2-4.1變?cè)募s束(Boundofvariable)定義2-4.1:在謂詞公式中,形如(x)P(x)和(x)P(x)的部分,稱為謂詞公式的x約束部分.

(x)P(x)或(x)P(x)中的x叫做量詞的指導(dǎo)變?cè)蜃饔米冊(cè)?，P(x)稱為相應(yīng)量詞的作用域或轄域。

2-4變?cè)募s束(Boundofvariable)在

x和

x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，相應(yīng)的x稱為約束變?cè)?P(x)中除約束變?cè)酝獬霈F(xiàn)的變?cè)Q為是自由變?cè)＠?：1、x(H(x,y)y(W(y)

∧L(x,y,z)))2、x(H(x)W(y))y(F(x)∧L(x,y,z))

2-4變?cè)募s束(Boundofvariable)說明:(1)n元謂詞公式A(x1，x2...xn)

中有n個(gè)自由變?cè)?若對(duì)其中的k(k≤n)個(gè)進(jìn)行約束,則構(gòu)成了n-k元謂詞;如果一個(gè)公式中沒有自由變?cè)霈F(xiàn),則該公式就變成了一個(gè)命題(2)一個(gè)公式的約束變?cè)褂玫拿Q符號(hào)是無關(guān)緊要的,如(x)M(x)與(y)M(y)意義相同.

2-4變?cè)募s束(Boundofvariable)2-4.2約束變?cè)膿Q名與自由變?cè)拇胍?guī)則在例1中,一個(gè)變?cè)谕粋€(gè)公式中既是自由出現(xiàn)又是約束出現(xiàn),這樣在理解上容易發(fā)生混淆.為了避免這種混亂,可對(duì)約束變?cè)M(jìn)行換名.換名規(guī)則:(對(duì)約束變?cè)裕?duì)約束變?cè)M(jìn)行換名,使得一個(gè)變?cè)谝粋€(gè)公式中只呈一種形式出現(xiàn).

2-4變?cè)募s束(Boundofvariable)(1)約束變?cè)梢該Q名,其更改的變?cè)Q范圍是量詞中的指導(dǎo)變?cè)约霸摿吭~作用域中所出現(xiàn)的該變?cè)?公式的其余部分不變.(2)換名時(shí)一定要更改為作用域中沒有出現(xiàn)的變?cè)Q.

2-4變?cè)募s束(Boundofvariable)例1:x(P(x)R(x,y))∧L(x,y)換名為

t(P(t)R(t,y))∧L(x,y)x(H(x,y)y(W(y)

∧L(x,y,z)))換名為

x(H(x,y)s(W(s)

∧L(x,s,z)))2-4變?cè)募s束(Boundofvariable)代入規(guī)則（對(duì)自由變?cè)裕?duì)公式中自由變?cè)母姆Q為代入(1)對(duì)于謂詞公式中的自由變?cè)梢宰鞔?代入時(shí)需要對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行;(2)用以代入的變?cè)c原公式中所有變?cè)拿Q不能相同.例如對(duì)例1中的公式

x(P(x)R(x,y))∧L(x,y)自由變?cè)獃用z來代入,得

x(P(x)R(x,z))∧L(x,z)

2-4變?cè)募s束(Boundofvariable)小結(jié)：本節(jié)介紹了約束變?cè)?、自由變?cè)母拍?，重點(diǎn)掌握約束變?cè)膿Q名與自由變?cè)拇?

2-5謂詞演算的等價(jià)式與蘊(yùn)含式2-5謂詞演算的等價(jià)式與蘊(yùn)含式(Equivalences&implicationsofpredicatecalculus)2-5.1謂詞的等價(jià)和永真的概念2-5.2謂詞演算的等價(jià)式與蘊(yùn)含式2-5謂詞演算的等價(jià)式與蘊(yùn)含式2-5.1謂詞的等價(jià)和永真的概念定義2-5.1:給定任何兩個(gè)謂詞公式WffA和WffB，設(shè)他們有共同的個(gè)體域E，若對(duì)A和B的任一組變?cè)M(jìn)行賦值，所得命題的真值都相同，則稱謂詞公式A和B在E上是等價(jià)的，并記作A

B。

定義2-5.2

給定任意謂詞公式wffA,其個(gè)體域?yàn)镋，對(duì)于A的所有賦值，wffA都為真，則稱wffA在E上是有效的（或永真的）。

2-5謂詞演算的等價(jià)式與蘊(yùn)含式

定義2-5.3

一個(gè)謂詞公式wffA，如果在所有賦值下都為假，則稱該wffA為不可滿足的。公式A不可滿足時(shí)也稱A為永假式。

定義2-5.4

一個(gè)謂詞公式wffA，如果至少在一種賦值為真，則稱該wffA為可滿足的。

有了謂詞公式的等價(jià)和永真等概念，就可以討論謂詞演算的一些等價(jià)式和蘊(yùn)含式。

2-5謂詞演算的等價(jià)式與蘊(yùn)含式1、命題公式的推廣在命題公式中成立的式子，用謂詞公式去代換其中相應(yīng)的命題變?cè)?，得到的公式依然成立如?/p>

x(P(x)Q(x))

x(┐P(x)∨

Q(x))┐

xP(x)∨┐

xQ(x)

┐(

xP(x)∧

xQ(x))2、量詞與┐之間的關(guān)系

┐(x)P(x)

(

x)┐P(x)

┐(

x)P(x)

(x)┐P(x)2-5謂詞演算的等價(jià)式與蘊(yùn)含式3、量詞轄域的擴(kuò)張與收縮量詞轄域中如果有合取或析取項(xiàng)，且其中有一個(gè)是命題，則可將該命題移至量詞轄域之外。如：（x）（A(x)∨B）

（x）A(x)∨B（x）（A(x)∧B）

（x）A(x)∧

B（

x）（A(x)∨B）

（

x）A(x)∨B（

x）（A(x)∧B）

（

x）A(x)∧B

2-5謂詞演算的等價(jià)式與蘊(yùn)含式量詞轄域的擴(kuò)張（

xA(x)B）

（x)(A(x)

B）

(（x)A(x)

B)

(x)(A(x)B）

(B(x)A(x)）

（x)(B

A(x)）

(B(x)A(x))

(x)(B

A(x))

2-5謂詞演算的等價(jià)式與蘊(yùn)含式4、量詞分配等價(jià)式設(shè)A(x)、B(x)是任意的含自由出現(xiàn)個(gè)體變?cè)獂的公式，則(1)x(A(x)∧B(x))xA(x)∧xB(x)(2)x(A(x)∨B(x))

xA(x)∨

xB(x)(3)x(A(x)∨B(x))xA(x)∨xB(x)(4)x(A(x)∧B(x))xA(x)∧xB(x)2-5謂詞演算的等價(jià)式與蘊(yùn)含式5.謂詞演算蘊(yùn)含式

xA(x)∨xB(x)

x(A(x)∨B(x))

x(A(x)∧B(x))xA(x)∧xB(x)

6.多個(gè)量詞的使用

多個(gè)量詞同時(shí)出現(xiàn)時(shí),其順序是至關(guān)重要的.

2-5謂詞演算的等價(jià)式與蘊(yùn)含式

2-5謂詞演算的等價(jià)式與蘊(yùn)含式小結(jié)：本節(jié)介紹了謂詞公式的概念及謂詞演算的等價(jià)式與蘊(yùn)涵式，重點(diǎn)掌握謂詞演算的等價(jià)式與蘊(yùn)涵式

2-6前束范式(PrenexNormalForm)2-6前束范式(Prefixnormalform)2-6.1前束范式(Prefixnormalform)

2-6.2前束析取范式和前束合取范式(Prefixdisjunctivenormalform&Prefixconjunctivenormalform)

2-6前束范式(PrenexNormalForm)它具有如下形式：

(□

x1)(□

x2)…(□

xk)B其中□為

或

，B為不含有量詞的公式。稱□

x1□

x2…□

xk為公式的首標(biāo)。特別地，若Ａ中無量詞，則Ａ也看作是前束范式。

定義2-6.1一個(gè)公式，如果量詞均非否定地出現(xiàn)在公式的最前面，且它們的作用域，延伸到整個(gè)公式的末尾，則該公式叫做前束范式(prenexnormalforms)

2-6前束范式(PrenexNormalForm)定理2-6.1:任意一個(gè)謂詞公式，均和一個(gè)前束范式等價(jià)。前束范式的求法：第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié)詞深入到命題變?cè)椭^詞填式的前面。第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變?cè)拿Q，以便消除混亂。第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量詞移到前面。這樣便可求出與公式等價(jià)的前束范式。2-6前束范式(PrenexNormalForm)例2:求下列公式的前束范式。

2-6前束范式(PrenexNormalForm)解:例子（0）舉例說明“

對(duì)

無分配律”。解：

對(duì)

無分配律指：不存在等價(jià)關(guān)系

x(A(x)

B(x))

xA(x)

xB(x)。例如，取解釋I：個(gè)體域?yàn)槿说募?，F(xiàn)(x)：x是男人，G(x)：x是女人。

x(A(x)

B(x))的真值為真，而

xA(x)

xB(x)的真值為假。（1）舉例說明“

對(duì)

無分配律”。解：

對(duì)

無分配律指：不存在等價(jià)關(guān)系

x(A(x)

B(x))

xA(x)

xB(x)。例如，取解釋I：個(gè)體域?yàn)槿说募?，F(xiàn)(x)：x是男人，G(x)：x是女人。

x(A(x)

B(x))的真值為假，而

xA(x)

xB(x))的真值為真。652-6前束范式(PrenexNormalForm)

2-6前束范式(PrenexNormalForm)

2-6前束范式(PrenexNormalForm)

2-6前束范式(PrenexNormalForm)2-6.2前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)

在前束范式的基礎(chǔ)上,可以定義前束析(合)取范式.定義2-6.2:任何一個(gè)謂詞公式A，如果具有如下形式則稱為前束合取范式：

(□x1)(□x2)…(□xn)[(A11∨A12∨…∨A1k1)∧

(A21∨A22∨…∨A2k2)∧…∧(Am1∨Am2∨…∨Amkm)]

其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)為原子謂詞公式或其否定,□為量詞或量詞，xi（i=1，…n）為客體變?cè)?2-6前束范式(PrenexNormalForm)定義2-6.3任何一個(gè)謂詞公式A，如果具有如下形式則稱為前束析取范式：

(□x1)(□x2)…(□xn)[(A11∧A12∧…∧A1k1)∨(A21∧A22∧…∧A2k2)∨…∨(Am1∧Am2∧…∧Amkm)]

其中m大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)為原子謂詞公式或其否定,□為量詞或量詞，xi（i=1，…n）為客體變?cè)?定理2-6.2:每一個(gè)謂詞公式都可以轉(zhuǎn)化為與其等價(jià)的前束析(合)取范式.2-6前束范式(PrenexNormalForm)例2:求下面公式的前束析取范式和前束合取范式解:

2-6前束范式(PrenexNormalForm)小結(jié)：本節(jié)介紹了謂詞公式的前束范式、前束析取范式和前束合取范式.重點(diǎn)掌握前束析取范式和前束合取范式求法。2-7謂詞演算的推理理論2-7謂詞演算的推理理論(Inferencetheoryofpredicatecalculus)2-7.1推理規(guī)則(Rulesofinference)

2-7.2證明舉例

(Examplesofproof)

2-7謂詞演算的推理理論2-7.1推理規(guī)則(Rulesofinference)在謂詞演算中，推理的形式結(jié)構(gòu)仍為

H1

H2

H3

....

Hn

C若H1

H2

H3

....

Hn

C是永真式，則稱由前提H1,H2,H3,.…,Hn邏輯的推出結(jié)論C，但在謂詞邏輯中,H1,H2,H3,.…,Hn,C均為謂詞公式。命題演算中的推理規(guī)則，可在謂詞推理理論中應(yīng)用。2-7謂詞演算的推理理論與量詞有關(guān)的四條重要推理規(guī)則：1、全稱指定規(guī)則（US規(guī)則）2、全稱推廣規(guī)則（UG規(guī)則）3、存在指定規(guī)則（ES規(guī)則）4、存在推廣規(guī)則（EG規(guī)則）注意：只能對(duì)前束范式適用上述規(guī)則。

2-7謂詞演算的推理理論1.全稱指定規(guī)則（US

）：

xP(x)

∴P(c)2.全稱推廣規(guī)則（UG）：

P(y)

∴xP(x)2-7謂詞演算的推理理論3.存在指定規(guī)則(ES):

xP(x)∴P(c)注:c是論域中的某些客體,c并不是任意的

4.存在推廣規(guī)則(EG):

P(c)∴

xP(x)2-7謂詞演算的推理理論例1證明蘇格拉底三段論:凡是人都是要死的。蘇格拉底是人。蘇格拉底是要死的。設(shè)：M(x):x是人。D(x):x是要死的。a:蘇格拉底。則前提：

x(M(x)D(x))，M(a）.

結(jié)論：D(a).證明：①x(M(x)D(x))P②M(a)D(a)US①③M(a)P④D(a)T②③I11

(直接證法)2-7.2證明舉例

(Examplesofproof)2-7謂詞演算的推理理論例2:前提：

x(F(x)∨G(x))，┐

xG(x).

結(jié)論：xF(x).證明：①┐

xG(x)P②x┐G(x)T①置換規(guī)則③┐G(a)US②④x(F(x)∨G(x))P⑤F(a)∨G(a)US④⑥F(a)T③⑤⑦xF(x)

EG⑥否定在量詞

之前時(shí)不可

直接做指定2-7謂詞演算的推理理論例3 所有獅子都是兇猛的。 有些獅子不喝咖啡。