離散數(shù)學(xué)第4章謂詞邏輯

離散數(shù)學(xué)電子科技大學(xué)信息與軟件工程學(xué)院主講教師 王慶先Tel：

QQ:6176754242021年7月20日星期二第4章 謂詞邏輯例如(著名的蘇格拉底三段論)（1）所有的人都是要死的；（2）蘇格拉底是人。（3）蘇格拉底是要死的。命題邏輯能夠解決的問題是有局限性的。只能進(jìn)行命題間關(guān)系的推理，無法解決與命題的結(jié)構(gòu)和成分有關(guān)的推理問題。2021/7/20蘇格拉底三段論2021/7/20P：所有的人都是要死的；

Q：蘇格拉底是人。

R：蘇格拉底是要死的?？梢姡琍，Q，R為不同的命題，無法體現(xiàn)三者相互之間的聯(lián)系。問題在于這類推理中，各命題之間的邏輯關(guān)系不是體現(xiàn)在原子命題之間，而是體現(xiàn)在構(gòu)成原子命題的內(nèi)部成分之間。對此，命題邏輯將無能為力。本章內(nèi)容謂詞邏輯中的基本概念1謂詞的翻譯原理2謂詞的合式公式3謂詞的標(biāo)準(zhǔn)型-范式4謂詞邏輯的推理理論2021/7/2054.1

本章學(xué)習(xí)要求重點(diǎn)掌握了解1謂詞邏輯符號化及真值謂詞公式的有效性和基本等價(jià)公式掌握謂詞邏輯的推理規(guī)則和公理3前束范式與SKOLEM范式2謂詞公式的解釋和真值自由變元和約束變元一般掌握2021/7/204.2謂詞邏輯中的基本概念與表示命題是具有真假意義的陳述句，從語法上分析，一個(gè)陳述句由主語和謂語兩部分組成。例如，“計(jì)算機(jī)是現(xiàn)代科學(xué)技術(shù)必不可少的工具”例如“陳華是電子科技大學(xué)的學(xué)生”“張強(qiáng)是電子科技大學(xué)的學(xué)生”；。若Ｐ：是電子科技大學(xué)的學(xué)生2021/7/20--P(陳華)--P(張強(qiáng))謂詞更一般地，P(x)：x是電子科技大學(xué)的學(xué)生。x：個(gè)體詞P：謂詞P(x):命題函數(shù)P(x)2021/7/20個(gè)體詞與謂詞單純的謂詞或單純的個(gè)體詞都無法構(gòu)成一個(gè)完整的邏輯含義，只有將它們結(jié)合起來時(shí)才能構(gòu)成一個(gè)獨(dú)立的邏輯斷言。定義4.2.1

在原子命題中，可以獨(dú)立存在的客體（句子中的主語、賓語等），稱為個(gè)體詞

(Individual)。而用以刻劃客體的性質(zhì)或客體之間的關(guān)系即是謂詞(Predicate)。例1

成都、北京、趙明、20060806班、計(jì)算機(jī)科學(xué)等等僅僅是簡單的個(gè)體常量；“是中國的首都”、“是計(jì)算機(jī)的基礎(chǔ)課程”等僅僅是簡單的謂詞，它們都不能構(gòu)成完整的句子。2021/7/20個(gè)體詞的分類2021/7/20表示具體的或特定的個(gè)體詞稱為個(gè)體常量

(IndividualConstant)，一般個(gè)體詞常量用帶或不帶下標(biāo)的小寫英文字母a,b,c，…，a1,b1,c1,…等表示；表示抽象的或泛指的個(gè)體詞稱為個(gè)體變量

(IndividualVariable)，一般用帶或不帶下標(biāo)的小寫英文字母x,y,z,…,x1,y1,z1,…等表示。例子2021/7/20例2

考察下列句子：北京是中國的首都；離散數(shù)學(xué)是計(jì)算機(jī)的基礎(chǔ)課程；劉翔是一個(gè)跨欄世界冠軍；中國人是很聰明的。個(gè)體域2021/7/20定義4.2.2個(gè)體詞的取值范圍稱為個(gè)體域(或論域)(Individual

Field)，常用D表示；宇宙間的所有個(gè)體域聚集在一起所構(gòu)成的個(gè)體域稱為全總個(gè)體域(Universal

IndividualField)。n元謂詞2021/7/20定義4.2.3

設(shè)D為非空的個(gè)體域，定義在Dn(表示n個(gè)個(gè)體都在個(gè)體域D上取值)上取值于{0,1}上的n元函數(shù)，稱為n元命題函數(shù)或n元謂詞(PropositionalFunction)，記為P(x1,x2,…,xn)。此時(shí)，個(gè)體變量x1,

x2,

…,

xn的定義域都為D，P(x1,

x2,

…,xn)的值域?yàn)閧0,

1｝。例4.2.1設(shè)有如下命題，并用n元謂詞進(jìn)行表示。

P：王童是一個(gè)三好學(xué)生；Q：李新華是李蘭的父親；SR(：x)張：強(qiáng)x與是謝一莉個(gè)是三好好朋學(xué)友生；FS(：x,武y漢)位：于x是北y京的和父廣親州之間。a：王童Tb(：x,李新y)華：x與y是好朋友命題P可表示為：S(a)dBc(：x張,李y強(qiáng)蘭,z)：x位于y和z之間ef命：題武Q漢可表g示：為北：京F(b,h：c廣)州命題RS可表示為：B(f,eg),h)2021/7/20結(jié)論2021/7/20謂詞中個(gè)體詞的順序是十分重要的，不能隨意

變更。如命題F(b,c)為“真”，但命題F(c,b)為“假”；一元謂詞用以描述某一個(gè)個(gè)體的某種特性，而n元謂詞則用以描述n個(gè)個(gè)體之間的關(guān)系。0元謂詞(不含個(gè)體詞的)實(shí)際上就是一般的命題；結(jié)論（續(xù)）2021/7/20具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。如上例中S(a)是有真值的，但S(x)卻沒有真值；一個(gè)n元謂詞不是一個(gè)命題，但將n元謂詞中的個(gè)體變元都用個(gè)體域中具體的個(gè)體取代后，就成為一個(gè)命題。而且，個(gè)體變元在不同的個(gè)體域中取不同的值對是否成為命題及命題的真值有很大的影響。4.2.2

量詞例4.2.2

符號化下述命題：所有的老虎都要吃人；每一個(gè)大學(xué)生都會說英語；所有的人都長著黑頭發(fā)；有一些人登上過月球；有一些自然數(shù)是素?cái)?shù)。PSQR(x)：x長會上吃著說過人黑英頭語球發(fā)T(x)：x是素?cái)?shù)則有：所有所每有有一的的個(gè)些x，RSQP(x)則有：有一些x，T(x)2021/7/20xx∈∈{{人{(lán)大老}學(xué)虎生}}x∈{自然數(shù)}量詞含義2021/7/20("

x)($x)有些x；至少有一個(gè)x；某一些x；存在x；等等。所有的x；任意的x；一切的x；每一個(gè)x；等等。全稱量詞與存在量詞2021/7/20定義4.2.4

稱("x)為全稱量詞（

UniversalQuantifier

），($x)為存在量詞（

ExistentialQuantifier），其中的x稱為作用變量（FunctionVariable）。一般將其量詞加在其謂詞之前，記為("x)F(x)，($x)F(x)。此時(shí)，F(xiàn)(x)稱為全稱量詞和存在量詞的轄域(Scope)。例4.2.2(續(xù))2021/7/20所有的老虎都要吃人；("x)P(x)

x∈{老虎}每一個(gè)大學(xué)生都會說英語；("x)Q(x)

x∈{大學(xué)生}所有的人都長著黑頭發(fā)；("x)R(x)

x∈{人}有一些人登上過月球；($x)S(x)

x∈{人}有一些自然數(shù)是素?cái)?shù)。($x)T(x)

x∈{自然數(shù)}。不便之處從書寫上十分不便，總要特別注明個(gè)體域；在同一個(gè)比較復(fù)雜的句子中，對于不同命題函數(shù)中的個(gè)體可能屬于不同的個(gè)體域，此時(shí)無法清晰表達(dá)；如例(1)和(4)的合取("

x)P(x)∧($x)R(x)x∈{老虎} x∈{人}2021/7/20不便之處(續(xù))2021/7/203.若個(gè)體域的注明不清楚，將造成無法確定其真值。即對于同一個(gè)n元謂詞，不同的個(gè)體域有可能帶來不同的真值。例如 對于語句“($x)(x+6=5)”可表示為：“有一些x，使得x+6=5”。該語句在下面兩種個(gè)體域下有不同的真值：（a）在實(shí)數(shù)范圍內(nèi)時(shí)，確有x=-1使得x+6=5，因此，($x)(x+6=5)為“真”；（b）在正整數(shù)范圍內(nèi)時(shí)，則找不到任何x，使得

x+6=5為“真”，所以，($x)(x+6=5)為“假”。不便之處的根源對了，都是因?yàn)樾枰貏e標(biāo)注每個(gè)謂詞的個(gè)體域所致！全總個(gè)體域2021/7/20特性謂詞新的問題出現(xiàn)了，U(x)如何與

("x)P(x)結(jié)合才符合邏輯呢？U(x)：x是老虎x∈｛老虎｝2021/7/20謂詞邏輯符號化的兩條規(guī)則2021/7/20統(tǒng)一個(gè)體域?yàn)槿倐€(gè)體域，而對每一個(gè)句子中個(gè)體變量的變化范圍用一元特性謂詞刻劃之。這種特性謂詞在加入到命題函數(shù)中時(shí)必定遵循如下原則：（1）對于全稱量詞("x)，刻劃其對應(yīng)個(gè)體域的特性謂詞作為蘊(yùn)涵式之前件加入。（2）對于存在量詞($x)，刻劃其對應(yīng)個(gè)體域的特性謂詞作為合取式之合取項(xiàng)加入。特性謂詞的例子想想，為什么要這樣規(guī)定特性謂詞加入的原則呢？若不遵循會出現(xiàn)什么樣的問題？例如，符號化“所有的老虎都要吃人”這個(gè)命題若P(x)：x會吃人U(x)：x是老虎2021/7/20則符號化的正確形式應(yīng)該是("

x)(U(x)→P(x))它的含義是：“對于任意的x,如果x是老虎，則x會吃人”，符合原命題的邏輯含義。若符號化為("x)(U(x)∧P(x))它的含義是：“對于任意的x,x是老虎，并且x會吃人”，與原命題“所有的老虎都要吃人”的邏輯含義不符。例4.2.32021/7/20用謂詞邏輯符號化下述語句：天下烏鴉一般黑；沒有人登上過木星；在美國留學(xué)的學(xué)生未必都是亞洲人；每個(gè)實(shí)數(shù)都存在比它大的另外的實(shí)數(shù)；盡管有人很聰明，但未必一切人都聰明；對于任意給定的e>0，必存在著d>0，使得對任意的x，只要|x-a|<d，就有|f(x)-f(a)|<e成立。例4.2.3(續(xù))2021/7/20天下烏鴉一般黑設(shè)F(x)：x是烏鴉；G(x,y)：x與y一般黑，則：

("x)("y)(F(x)∧F(y)→G(x,y))或者┐($x)($y)(F(x)∧F(y)∧┐G(x,y))；沒有人登上過木星設(shè)H(x)：x是人；M(x)：x登上過木星，則：┐($x)(H(x)∧M(x))或者("x)(H(x)→┐M(x))；例4.2.3(續(xù))2021/7/20在美國留學(xué)的學(xué)生未必都是亞洲人設(shè)A(x)：x是亞洲人；H(x)：x是在美國留學(xué)的學(xué)生，則：┐("

x)(H(x)→A(x))或者($x)(H(x)∧┐A(x))；每個(gè)實(shí)數(shù)都存在比它大的另外的實(shí)數(shù)設(shè)R(x)：x是實(shí)數(shù)；L(x,y)：x小于y，則：("

x)(R(x)→($y)(R(y)∧L(x,

y))；例4.2.3(續(xù))2021/7/20盡管有人很聰明，但未必一切人都聰明設(shè)M(x)：x是人；C(x)：x很聰明，則：($x)(M(x)∧C(x))∧┐("

x)(M(x)→C(x))；對于任意給定的e>0，必存在著d>0，使得對任意的x，只要|x-a|<d，就有|f(x)-f(a)|<e成立。設(shè)個(gè)體域?yàn)閷?shí)數(shù)集合，則原命題可符號化為：

("e)((e>0)→($d)((d>0)∧("x)((|x-a|<d)→(|f(x)-f(a)|<e))))。4.2.3

謂詞的語言翻譯2021/7/201,

"

x

?

D,G(x)

=

1("

x)G(x)

=

0,($x)G(x)

=$x0

?

D,G(x0

)

=

01,

$x0

?

D,G(x0

)

=

10,

"

x

?

D,G(x)

=

0特殊的，當(dāng)個(gè)體域D＝{x0,x1,…}是可數(shù)集合時(shí)，上述("x)G(x)、($x)G(x)的真值可表示為：("

x)G(x)=G(x0)∧G(x1)∧...($x)G(x)=G(x0)∨G(x1)∨...個(gè)體域可數(shù)或有限2021/7/20更特別的，當(dāng)個(gè)體域D＝{x0,x1,…xn}是有限集合時(shí)，上述("x)G(x)、($x)G(x)的真值可以用與之等價(jià)的命題公式來進(jìn)行表示。("

x)G(x)=G(x0)∧G(x1)∧...∧G(xn)($x)G(x)=G(x0)∨G(x1)∨...∨G(xn)例4.2.5設(shè)P(x)：x是素?cái)?shù)；I(x)：x是整數(shù)；Q(x,y)：x+y=0。用語句描述下述句子，并判斷其真假值。（1）("

x)(I(x)→P(x))；（2）($x)

(I(x)∧P(x))；（3）("

x)

("

y)(I(x)∧I(y)→Q(x,

y))；（4）("

x)(I(x)→($y)(I(y)∧Q(x,

y)))；（5）($x)("y)(I(x)∧(I(y)→Q(x,y)))。“對存任在意著的整“整數(shù)對“對x任存任，x意在意使的一的得整些整對數(shù)整數(shù)任x數(shù)x意，x整的y，x，一整x都是定數(shù)，有素是y使，x數(shù)素+得都”數(shù)y=有，”0+”xy，+=y0=”0”，真值為“假真”； 真值為“假真假”；2021/7/204.2.4

謂詞翻譯難點(diǎn)2021/7/20一元謂詞用以描述某一個(gè)個(gè)體的某種特性，而n元謂詞則用以描述n個(gè)個(gè)體之間的關(guān)系；如有多個(gè)量詞，則讀的順序按從左到右的順序；另外，量詞對變元的約束，往往與量詞的次序有關(guān)，不同的量詞次序，可以產(chǎn)生不同的真值，此時(shí)對多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒它們的順序，顛倒后會改變原有的含義。謂詞翻譯難點(diǎn)（續(xù)）2021/7/20根據(jù)命題的實(shí)際意義，選用全稱量詞或存在量詞。全稱量詞加入時(shí)，其刻劃個(gè)體域的特性謂詞將以蘊(yùn)涵的前件加入，存在量詞加入時(shí)，其刻劃個(gè)體域的特性謂詞將以合取項(xiàng)加入；有些命題在進(jìn)行符號化時(shí)，由于語言敘述不同，可能翻譯不同，但它們表示的意思是相同的，

即句子符號化形式可不止一種。4.2.5

謂詞翻譯的應(yīng)用謂詞設(shè)定：P(x)：x是兔子；Q(x)：x是烏龜；R(x,y)：x比y跑得快；

T(x,y)：x與y跑得同樣快。y)))例4┐.┐2.((4$"xx將))(下$(列"y)y命)(題(PP(符(xx號))∧∧化PQ((yy))→∧RT((xx,,y)y)))（或1者）者兔子("比$x烏)(龜$"y跑y))得((PP快((x；x))∧P((yy))∧→┐┐R(Tx(,x,y)y)))（2）有的兔子比所有烏龜跑得快；（3）并不是所有的兔子都比烏龜跑得快；(

($x)(P(x)∧("

y)(Q(y)→R(x,2021/7/20（4"）x)不存("在y跑)(得P(同x)樣∧快Q的(y兩)→只兔R(子x,。y))例4.2.5只要是需要室外活動的課，郝亮都喜歡；所有的公共體育課都是需要室外活動的課；籃球是一門公共體育課；郝亮喜歡籃球這門課。解：設(shè)O(x)：表示x是需要室外活動的課；

L(x,y)：表示x喜歡y；S

(x)：表示x是一門公共體育課；

Hao：表示郝亮；Ball：表示籃球。符號化("下x)述(一S(組x)語→句O：(x))S(ball)L(Hao,

Ball)("

x)(O(x)→L(Hao,

x))2021/7/20解：設(shè)E(x)：表示x進(jìn)入國境；V(x)：表示x是重要人物；

C(x)：表示x是海關(guān)人員；

P(x)：表示x是走私者；

B(x,y)：表示y檢查x。例("4x.)2((.E6(x)∧┐V(x))→($y)(C(y)∧B(x,y)))符號(化$x下)(述P(一x)組∧語E(句x)：∧("y)(B(x,y)→P(y)))("x海)(關(guān)(P人(員x)檢→查┐每V一(x個(gè)))進(jìn)或入┐本(國$x的)(不P重(x要)∧人V物(；x)某)些走私者進(jìn)入該國時(shí)僅僅被走私者所檢查；沒有一個(gè)走私者是重要人物；海關(guān)人員中的某些人是走私者。($x)(P(x)∧C(x)2021/7/20)4.3

謂詞合式公式與解釋2021/7/20謂詞公式涉及如下四種符號：常量符號：用帶或不帶下標(biāo)的小寫英文字母a,b,c,…,a1,b1,c1,…來表示。當(dāng)個(gè)體域名稱集合D給出時(shí)，它可以是D中的某個(gè)元素；變量符號：用帶或不帶下標(biāo)的小寫英文字母x,y,z,...,x1,y1,z1,...來表示。當(dāng)個(gè)體域名稱集合D給出時(shí)，它可以是D中的任意元素；符號定義2021/7/20函數(shù)符號：用帶或不帶下標(biāo)的小寫英文字母f,g,h,...,f1,g1,h1,...來表示。當(dāng)個(gè)體域名稱集合D給出時(shí)，n元函數(shù)符號f(x1,x2,…,xn)可以是Dn→D的任意一個(gè)函數(shù)；謂詞符號：用帶或不帶下標(biāo)的大寫英文字母P,Q,R,...,P1,Q1,R1...來表示。當(dāng)個(gè)體域名稱集合D給出時(shí)，n元謂詞符號P(x1,x2,…,xn)可以是

Dn→{0，1}的任意一個(gè)謂詞。為何需要函數(shù)符號？例如 符號化“周紅的父親是教授”：設(shè)

f(x)：x的父親；P(x)：x是教授；

c：周紅此時(shí)P(f(c))表示“周紅的父親是教授”這一命題。函數(shù)的使用給謂詞邏輯中的個(gè)體詞表示帶來了很大的方便2021/7/20項(xiàng)與原子公式2021/7/20定義4.3.1

謂詞邏輯中的項(xiàng)(Term)，被遞歸地定義為：任意的常量符號或任意的變量符號是項(xiàng)；若f(x1,x2,…,xn)是n元函數(shù)符號，t1,t2,…,tn是項(xiàng)，則f(t1,t2,…,tn)是項(xiàng)；僅由有限次使用(1)，(2)產(chǎn)生的符號串才是項(xiàng)。定義4.3.2

若P(x1,x2,…,xn)是n元謂詞，t1，t2，…，tn是項(xiàng)，則稱P(t1,t2,…,tn)為原子謂詞公式(Atomic

Propositional

Formulae)，簡稱原子公式(Atomic

Formulae)。定義4.3.32021/7/20滿足下列條件的表達(dá)式，稱為合式公式(Well-FormedFormulae/Wff)，簡稱公式(Formulae)。（1）原子公式是合式公式；（2）若G，H是合式公式，則

(┐G)、(┐H)、(G∨H)、(G∧H)、(G→H)、(G?H)也是合式公式；（3）若G是合式公式，x是個(gè)體變量，則

("x)G、($x)G

也是合式公式；（4）僅僅由(1)-(3)產(chǎn)生的表達(dá)式才是合式公式。例子2021/7/20("

x)($y)(P(x,

y)→(Q(x,

y)∨R(x,

a,

f(z))))，("

x)(P(x)∨($y)R(x,

y))，("x)(P(x)→R(x))。等都是公式。而("

x)P(x)→R(x)($y)，($y)("x)(∨P(x,y))。等則不是公式。4.3.2

自由變元和約束變元則稱它為自由出現(xiàn)(Free

Occurrence)，此時(shí)的變元x稱為自由變元(Free

Variable)。定義4.3.4

給定一個(gè)合適公式G，若變元x出現(xiàn)在使用變元的量詞的轄域之內(nèi)，則稱變元x的出現(xiàn)為約束出現(xiàn)(Bound

Occurrence)，此時(shí)的變元x稱為約束變元(Bound

Variable)。若x的出現(xiàn)不是約束出現(xiàn)，量詞轄域的確定方法：若量詞后有括號，則括號內(nèi)的子公式就是該量詞的轄域；若量詞后無括號，則與量詞鄰接的子公式為該量詞的轄域。2021/7/20例4.3.1確定以下公式各量詞的轄域以及各個(gè)體變量為自由變元還是約束變元。（1）("

x)(P(x)→($y)R(x,

y))；（2）($x)P(x)∧Q(x,

y)；（3）("

x)($y)(P(x,

y)∨Q(y,

z))

∧($x)R(x,y)；（4）("x)(P(x)→R(x))∧($y)Q(x,y)。2021/7/20例4.3.1（續(xù)）2021/7/20解

在(1)中，P(x)中x，R(x,y)的x，y都為約束變元。在(2)中，所以P(x)中的x為約束變元，Q(x,y)中的x，y是自由變元。在(3)中，P(y,z)、Q(x,y)中的x,y都為約束變元，R(x,y)中的x為約束變元，但y為自由變元。在(4)中，P(x)，R(x)中的x為約束變元，

Q(x,y)中的x為自由變元、y是約束變元。變元混淆（4）("

x)(P(x)→R(x))∧($y)Q(x,

y)約束變元自由變元2021/7/20在一個(gè)公式中，某一個(gè)變元的出現(xiàn)即可以是自由的，又可以是約束的，如(4)中的x。為了使得我們的研究更方便，而不致引起混淆，同時(shí)為了使其式子給大家以一目了然的結(jié)果，對于表示不同意思的個(gè)體變元，我們總是以不同的變量符號來表示之。兩個(gè)規(guī)則2021/7/20規(guī)則1(約束變元的改名規(guī)則)：將量詞中出現(xiàn)的變元以及該量詞轄域中此變量之所有約束出現(xiàn)都用新的個(gè)體變元替換；新的變元一定要有別于改名轄域中的所有其它變量。規(guī)則2(自由變元的代入規(guī)則)：將公式中出現(xiàn)該自由變元的每一處都用新的個(gè)體變元替換；新變元不允許在原公式中以任何約束形式出現(xiàn)例4.3.22021/7/20（1）將公式("x)(P(x)→Q(x,約束變元x進(jìn)行改名；y))∧R(x,y)中的（2）將公式("x)(P(x)→Q(x,自由變元y進(jìn)行代入。y))∧R(x,y)中的解利用規(guī)則1對x進(jìn)行改名，則：("z)(P(z)→Q(z,y))∧R(x,y)-------對("z)(P(z)→R(x,y))∧R(x,y)-------錯(cuò)("y)(P(y)→R(y,y))∧R(x,y)-------錯(cuò)利用規(guī)則2對y進(jìn)行代入，則：("x)(P(x)→Q(x,z))∧R(x,z)------對("x)(P(x)→Q(x,z))∧R(x,y)------錯(cuò)("x)(P(x)→Q(x,x))∧R(x,x)------錯(cuò)改名規(guī)則和代入規(guī)則的關(guān)系2021/7/20改名規(guī)則和代入規(guī)則之間的共同點(diǎn)都是不能改變原有的約束關(guān)系，而不同點(diǎn)是：施行的對象不同：改名規(guī)則是對約束變元施行，代入規(guī)則是對自由變元施行；施行的范圍不同：改名規(guī)則可以只對公式中的一個(gè)量詞及其轄域內(nèi)施行，即只對公式的一個(gè)子公式施行；而代入規(guī)則必須對整個(gè)公式同一個(gè)自由變元的所有自由出現(xiàn)同時(shí)施行，即必須對整個(gè)公式施行；改名規(guī)則和代入規(guī)則的關(guān)系（續(xù)）2021/7/20（3）施行后的結(jié)果不同：改名后，公式含義不變，因?yàn)榧s束變元只改名為另一個(gè)個(gè)體變元，約束關(guān)系不改變，約束變元不能改名為個(gè)體常量；代入后，不僅可用另一個(gè)個(gè)體變元進(jìn)行代入，并且也可用個(gè)體常量去代入，從而使公式由具有普遍意義變?yōu)閮H對該個(gè)體常量有意義，即公式的含義改變了。閉式的定義定義4.3.5設(shè)G是任意一個(gè)公式，若G中無自由出現(xiàn)的個(gè)體變元，則稱G為封閉的合適公式，簡稱閉式。例如("x)(P(x)→($y)R(x,y))是一個(gè)閉式。閉式一定是命題。2021/7/204.3.32021/7/20謂詞合式公式的解釋謂詞邏輯中公式G的每一個(gè)解釋定義4.3.6I(Explanation)由如下四部分組成：（1）非空的個(gè)體域集合D；（2）G中的每個(gè)常量符號，指定D中的某個(gè)特定的元素；（3）G中的每個(gè)n元函數(shù)符號，指定Dn到D中的某個(gè)特定的函數(shù)；（4）G中的每個(gè)n元謂詞符號，指定Dn到｛0,1｝中的某個(gè)特定的謂詞。公式的解釋例4.3.3

設(shè)有公式：("

x)(P(x)→Q(x))?

(($x)P(x)→("

x)Q(x))，在個(gè)體域D={a,b}上，構(gòu)造兩個(gè)使公式分別為真和假的解釋。思考一下，謂詞邏輯中的一個(gè)公式G可以像命題邏輯中的公式那樣列出真值表來研究它的真值情況么？2021/7/20例4.3.32021/7/20解1）構(gòu)造解釋I1為P(a)

=

0，P(b)

=

0，Q(a)

=

1，Q(b)

=

1，則(P(a)→Q(a))∧(P(b)→Q(b))在此解釋I1下真值為1，(P(a)∨P(b))→(Q(a)∧Q(b))在此解釋I1下真值為1，即I1使得等價(jià)聯(lián)結(jié)詞前面的("x)(P(x)→Q(x))為真，同樣使得等價(jià)聯(lián)結(jié)詞后面的(($x)P(x)→("x)Q(x))為真，因此，這樣的解釋使得原公式的真值為真。例4.3.3（續(xù)）2021/7/20（2）構(gòu)造解釋I2為P(a)

=

0，P(b)

=

1，Q(a)

=

0，Q(b)

=

1，則(P(a)→Q(a))∧(P(b)→Q(b))在此解釋I2下真值為1，(P(a)∨P(b))→(Q(a)∧Q(b))在此解釋I2下真值為0，即I2使得等價(jià)聯(lián)結(jié)詞前面的("x)(P(x)→Q(x))為真，而使得等價(jià)聯(lián)結(jié)詞后面的(($x)P(x)→("x)Q(x))為假，因此，這樣的解釋使得公式("x)(P(x)→Q(x))?(($x)P(x)→("x)Q(x))的真值為假。例4.3.42021/7/20設(shè)有公式($x)(P(f(x))∧Q(x，f(a)))。在如下給定的解釋下，判斷該公式的真值。①.個(gè)體域?yàn)镈＝{α，β}；②.a指定為：α；③.f(α)指定為：β,④.P(α)指定為：1,f(β)指定為：α；P(β)指定為：0，Q(α,α)指定為：0，Q(α,β)指定為：1，Q(β,α)指定為：1，Q(β,β)指定為：1。例4.3.4（續(xù)）2021/7/20解因當(dāng)x＝β時(shí)，有：

f(β)＝α，P(f(x))＝P(f(β))＝P(α)＝1,f(a)＝f(α)＝β，Q(x，f(a))＝Q(β，f(α))＝Q(β，β)＝1。所以：P(f(β))∧Q(β,f(a))＝1∧1＝1，即存在x＝β,使得P(f(β))∧Q(β，f(a))＝1，即：

($x)(P(f(x))∧Q(x，f(a)))＝1。4.3.42021/7/20謂詞合式公式的分類給出公式：P(a)→($x)P(x)和例4.3.5("x)P(x)→P(a)，判斷公式在給定的解釋下的真值。解（1）對于公式P(a)→($x)P(x)，對任何解釋I：當(dāng)P(a)取值為真時(shí)，($x)P(x)也必為真，此時(shí)，P(a)→($x)P(x)的真值為真；當(dāng)P(a)取值為假時(shí)，($x)P(x)可為真，也可為假，此時(shí)，P(a)→($x)P(x)的真值為真；所以，

P(a)→($x)P(x)在任何情況下的真值恒為真。例4.3.5（續(xù)）2021/7/20（2）對于公式("x)P(x)→P(a)，對任何的解釋I：當(dāng)("x)P(x)取值為真時(shí)，P(a)也必為真， 此時(shí)，("x)P(x)→P(a)的真值為真；當(dāng)("x)P(x)取值為假時(shí)，P(a)可為真，也 可為假，此時(shí)，("x)P(x)→P(a)的真值為 真。所以，("x)P(x)→P(a)在任何情況下的真值恒為真。例4.3.62021/7/20判斷下列公式的真假。（1）P(x,y)∧Q(x,y)→P(x,y)；（2）P(x,y)∨

P(x,

y)；（3）P(x,y)∧P(x,y)。解無論在何種結(jié)構(gòu)中，無論對變元作何種賦值，公式(1)，(2)均取真值T，而公式(3)均取真值F。從而(1)，(2)就是關(guān)于一切結(jié)構(gòu)與一切賦值下恒取“T”值的謂詞公式，(3)就是關(guān)于一切結(jié)構(gòu)與一切賦值下恒取“F”值的謂詞公式。謂詞合式公式的分類2021/7/20定義4.3.7公式G稱為有效公式，如果G在它所有的解釋I下都取值為“真”。公式G稱為矛盾公式，如果G在它所有的解釋I下都取值為“假”。公式G稱為可滿足公式，如果至少有一種解釋I使得G取值為“真”。公式之間的關(guān)系2021/7/20從上述定義可知三種特殊公式之間的關(guān)系：有效公式G的否定G為矛盾公式；矛盾公式G的否定G為有效公式。有效公式一定為可滿足公式。4.3.5謂詞合式公式的基本等價(jià)關(guān)系定理4.3.1

永真（假）公式的任意一個(gè)代入實(shí)例必為有效（矛盾）公式。定義4.3.8公式G，H稱為等價(jià)的(Equivalent)，記為G=H，如果公式G

?H是有效公式。定義4.3.9設(shè)Ｇ(P1,P2,…,Pn)是命題演算中的命題公式，P1,P2,…,Pn是G中的命題變元，當(dāng)用任意的謂詞公式Gi(1≤i≤n)分別代入Pi后，得到的新謂詞公式Ｇ(G1,G2,…,Gn)稱為原公式的代入實(shí)例。定理4.3.2設(shè)G1是G的子公式(即G1是公式G的一部分)，H1是任意的謂詞公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的謂詞公式H，若G1＝H1，則G＝H命題演算中的24個(gè)基本的等。2021/7/20價(jià)公式在謂詞演算中仍成立謂詞演算中的有效公式2021/7/20(改名規(guī)則)（1）E25：($x)G(x)

=

($y)G(y)；E26：("

x)G(x)

=

("

y)G(y)；（2）E27：E28：($x)G(x)

=

("

x)

G(x)；("

x)G(x)

=

($x)

G(x)；(量詞轉(zhuǎn)換律/量詞否定等值式)（3）E29：("

x)(G(x)∨S)E30：("

x)(G(x)∧S)==("

x)G(x)∨S；("

x)G(x)∧S；E31：($x)(G(x)∨S)=($x)G(x)∨S；E32：($x)(G(x)∧S)=($x)G(x)∧S；(量詞轄域的擴(kuò)張與收縮律)謂詞演算中的有效公式（續(xù)）2021/7/20(量詞分配律)（4）E33：("

x)(G(x)∧H(x))=("

x)G(x)∧("

x)H(x)；E34：($x)(G(x)∨H(x))=($x)G(x)∨($x)H(x)；（5）E35：("

x)G(x)∨("

x)H(x)=("

x)("

y)(G(x)∨H(y))；E36：($x)G(x)∧($x)H(x)=($x)($y)(G(x)∧H(y))；例12021/7/20設(shè)P(x)：x今天來上課，個(gè)體域?yàn)橛?jì)算機(jī)學(xué)院2006級全體同學(xué)的集合。則：1.("x)P(x)表示所有同學(xué)今天都來上課了；┐("x)P(x)表示不是所有的同學(xué)今天來上課了；

($x)┐P(x)表示今天有同學(xué)沒來上課。所以，┐("x)P(x)=($x)┐P(x)2.類似的，┐($x)P(x)=("x)┐P(x)例22021/7/201.設(shè)G(x)：x勤奮學(xué)習(xí)；H(x)：x喜歡體育活動。其中：個(gè)體域是大學(xué)里的學(xué)生。則("x)(G(x)∧H(x))表示：大學(xué)里的所有學(xué)生即勤奮學(xué)習(xí)又喜歡體育活動”；("x)G(x)∧("x)H(x)表示：

“大學(xué)里的所有學(xué)生都勤奮學(xué)習(xí)且大學(xué)里所有的學(xué)生都喜歡體育活動”。兩者意義是相同的。即有：("x)(G(x)∧H(x))=("x)G(x)∧("x)H(x)例2（續(xù)）2021/7/202.設(shè)G(x)：x勤奮學(xué)習(xí)；H(x)：x喜歡體育活動。其中：個(gè)體域是大學(xué)里的學(xué)生。則($x)(G(x)∨H(x))表示：

“大學(xué)里有些學(xué)生勤奮學(xué)習(xí)或喜歡體育活動”；($x)G(x)∨($x)H(x)表示：

“大學(xué)里有些學(xué)生勤奮學(xué)習(xí)或大學(xué)里有些學(xué)生喜歡體育活動”。兩者意義是相同的。所以,($x)(G(x)∨H(x))＝($x)G(x)∨($x)H(x)4.3.6

謂詞合式公式難點(diǎn)3命題邏輯與謂詞邏輯中的公式及其解釋的不同1掌握并能夠靈

活運(yùn)用謂詞，

個(gè)體詞和量詞；22021/7/20注意量詞的作用域。通過緊跟量詞后面的是否為括號進(jìn)行判定；4.3.72021/7/20謂詞合式公式的應(yīng)用利用謂詞之間的等價(jià)關(guān)系證明下列公式之例4.3.7間的關(guān)系：("x)P(x)→Q(x)=($y)(P(y)→Q(x))證明

("

x)P(x)→Q(x)=

┐("

x)P(x)∨Q(x)=

($x)┐P(x)∨Q(x)=

($y)┐P(y)∨Q(x)=

($y)(┐P(y)∨Q(x))=

($y)(P(y)→Q(x))例4.3.82021/7/20判斷(("x)P(x)→Q(x))→(("x)P(x)→("x)Q(x))是否為一個(gè)有效公式。解設(shè)個(gè)體域D={2,4,6,8}，P(x)：x能被2整除；Q(x)：x能被4整除。可知("x)P(x)真值為真，("x)Q(x)真值為假。1）自由變元x=4原式真值=（1→Q(4))→（1→0）=0故(("x)P(x)→Q(4))→(("x)P(x)→("x)Q(x))的真值為假。所以原式不是有效公式。例4.3.8（續(xù)）2021/7/202）自由變元x=6原式真值=（1→Q(6)）→（1→0）=1故(("x)P(x)→Q(6))→(("x)P(x)→("x)Q(x))的真值為真。綜上所述，個(gè)體域中有些個(gè)體使原式的真值為真，有些個(gè)體使原式的真值為假，因此，該公式只能是一

個(gè)可滿足公式。4.4 公式的標(biāo)準(zhǔn)型——范式2021/7/20在命題邏輯里，每一公式都有與之等值的范式，范式是一種統(tǒng)一的表達(dá)形式，當(dāng)研究一個(gè)公式的特點(diǎn)(如永真、永假)時(shí)，范式起著重要作用。對謂詞邏輯的公式來說，也有范式，其中前束范式與原公式是等值的，而其它范式與原公式只有較弱的關(guān)系。4.4.1

前束范式2021/7/20定義4.4.1

稱公式G是一個(gè)前束范式，如果G中的一切量詞都位于該公式的最前端(不含否定詞)且這些量詞的轄域都延伸到公式的末端。其標(biāo)準(zhǔn)形式如下：(Q1x1)(Q2x2)…(Qnxn)M(x1,

x2,

…,

xn)其中Q1為量詞"或$(i=1，…，n)，M稱作公式

G的母式(基式)，M中不再有量詞。前束范式的轉(zhuǎn)換方法2021/7/20定理4.4.1

謂詞邏輯中的任一公式都可化為與之等價(jià)的前束范式，但其前束范式并不唯一。證明

設(shè)G是任一公式，通過下述步驟可將其轉(zhuǎn)化為與之等價(jià)的前束范式：消去公式中包含的聯(lián)結(jié)詞“fi

”、“?”；反復(fù)運(yùn)用德?摩根定律，直接將“”內(nèi)移到原子謂詞公式的前端；使用謂詞的等價(jià)公式將所有量詞提到公式的最前端。例4.4.12021/7/20("

y)Q(y,b)fi

R(x)))求(("x)($y)P(a,x,y)fi

($x)(的前束范式。R(x)))解（1）消去聯(lián)結(jié)詞“fi

”、“?”，得：(

("

x)($y)P(a,

x,

y)

($x)( ("

y)Q(y,b)（2）

內(nèi)移，得：("

x)($y)P(a,

x,

y)

($x)(("

y)Q(y,

b)

R(x))=

("

x)($y)P(a,

x,

y)

("

x)(($y)

Q(y,

b)

R(x))例4.4.1（續(xù)）2021/7/20（3）量詞左移，得：

("x)(($y)P(a,x,y)=

("

x)(($y)P(a,

x,

y)($y)($z)=

("

x)($y)($z)(P(a,

x,

y)Q(y,

b)Q(z,

b)Q(z,

b)R(x))R(x))R(x))=

("

x)($y)($z)S(a,

b,

x,

y,

z)即：("x)($y)($z)S(a,b,x,y,z)為原式的前束范式，這里S(a,b,x,y,z)是原公式的母式。4.4.2

Skolem標(biāo)準(zhǔn)型2021/7/20定義4.4.2

設(shè)公式G是一個(gè)前束范式，如消去G中所有的存在量詞和全稱量詞，所得到的公式稱為Skolem標(biāo)準(zhǔn)型。定理4.4.2任意一個(gè)公式G都有相應(yīng)的Skolem標(biāo)準(zhǔn)形存在，但此Skolem標(biāo)準(zhǔn)形不一定與原公式等值。例4.4.2求公式($x)("y)("z)($u)("v)($w)P(x,y,z,u,v,w)的Skolem標(biāo)準(zhǔn)型。解：消去($w)消去("y)("

z)($u)("

v)($w)P(a,

y,

z,

u,v,

w)消去("z)($u)("

v)($w)P(a,

y,

z,

u,

v,

w)消去($u)P(a,

y,

z,

f(y,z),

v,

g(y,z,v))("

v)($w)P(a,

y,

z,

f(y,z),

v,w)消去("v)($w)P(a,

y,

z,

f(y,z),

v,

w)($x)("

y)("

z)($u)("

v)($w)P(x,y,z,u,v,w)消去($x)("

y)("

z)($u)("

v)($w)P(a,

y,

z,

u,

v,

w)2021/7/201、(1),(3),(5),(7),(9),(11)2、(2),(4),(5)3、(7),(8)4、(4),(6)5、(1),(3),(5)6、(2),(3)7、(1),(3),(5)10、(7),(8),(9),(10)11、(1),(3),(5)習(xí)題

134－137頁2021/7/204.5

謂詞邏輯的推理理論2021/7/204.5.1謂詞演算的演繹與推理定義4.5.1

設(shè)G1,G2,…,Gn,Ｈ是公式，稱H是G1,G2,…,Gn的邏輯結(jié)果(G1,G2,…,Gn共同蘊(yùn)涵H)，對任意解釋I，若I滿足G1,G2,…,Gn，則I滿足H。記為G1,G2,…,GnＨ，此時(shí)稱G1,G2,…,GnＨ是有效的(efficacious)，否則稱為無效的(inefficacy-ous).G1,G2,…,Gn稱為一組前提(Premise),有時(shí)用集合Г來表示，記Г={G1,G2,…,Gn},H稱為結(jié)論(conclusion),又稱H是前提集合的邏輯結(jié)果,記為Г

H。定理4.5.12021/7/20公式H是前提集合Г={G1,G2,…,Gn}的邏輯結(jié)果當(dāng)且僅當(dāng)G1∧G2∧…∧Gn→Ｈ為有效公式。一、推理規(guī)律2021/7/20（1）I16：("

x)G(x)

($x)G(x)；（2）I17：("

x)G(x)∨("

x)H(x)("

x)(G(x)∨H(x))；I18：($x)(G(x)∧H(x))($x)G(x)∧($x)H(x)；（3）I19：("

x)(G(x)→H(x))("

x)G(x)→("

x)H(x)；I20：("

x)(G(x)→H(x))($x)G(x)→($x)H(x)。推理規(guī)律（續(xù)）2021/7/20（4）I21：($x)("

y)G(x,y)

("

y)($x)G(x,y)；I22：("

x)("

y)G(x,y)

($y)("

x)G(x,y)；I23：("

y)("

x)G(x,y)

($x)("

y)G(x,y)；I24：($y)("

x)G(x,y)

("

x)($y)G(x,y)；I25：("

x)($y)G(x,y)

($y)($x)G(x,y)；I26：("

y)($x)G(x,y)

($x)($y)G(x,y)；量詞關(guān)系圖("

x)("

y)

E37I22($y)("

x)I24("

x)($y)I25($y)($x)E382021/7/20("

y)("

x)I23($x)("

y)I21("

y)($x)I26($x)($y)二、推理規(guī)則1、US（全稱特指規(guī)則，Universal

SPecify）：("x)G(x)

G(y)其中G(x)對y是自由的推廣：("

x)G(x)

G(c)其中c為任意個(gè)體常量2、ES（存在特指規(guī)則，Existential

SPecify

）：($x)G(x)

G(c)其中c為使G(c)為真的特定個(gè)體常量；若G(x)中還有除x以外的自由變量時(shí)，則必須用這些變量的函數(shù)符號來取代。在G(x)中，x不出現(xiàn)在量詞("y)或($y)的轄域之內(nèi)。2021/7/20推理規(guī)則（續(xù)）2021/7/203、UG（全稱推廣規(guī)則，Universal

Generalize

）：G(y)

("

x)G(x)其中G(y)對x是自由的且G(y)中無自由變量x4、EG（存在推廣規(guī)則，Existential

Generalize）：G(c)

($x)G(x)其中G(c)對x是自由的且G(c)中無自由變量x推廣：

G(y)

($x)G(x)其中G(y)對x是自由的且G(y)中無自由變量x推理規(guī)則的正確使用(1)例4.5.1

設(shè)實(shí)數(shù)集中，語句“不存在最大的實(shí)數(shù)”可其中：G(x,y)：y>x。符號化為：("x)($y)G(x,y)。推導(dǎo)1：（1）("

x)($y)G(x,

y)P（2）($y)G(z,

y)2021/7/20PUS,(1)注（意2：）使($用y)GU(Sy規(guī),y則)

來消去量詞時(shí)，US若,(選1)用分變析元：y推取導(dǎo)代1x是，錯(cuò)則誤要的求。在正原確公的式推中導(dǎo)x不如能下出：現(xiàn)在量（詞1(）"(y")x或)(($$yy)G)的(x轄,

y域)

之內(nèi)。推理規(guī)則的正確使用（2）P推導(dǎo)2：（1）("

x)($y)G(x,

y)（2）($y)G(z,

y)（3）G(z,

c)US,(1)ES,(2)分析：推導(dǎo)2是錯(cuò)誤的。正確的推導(dǎo)如下：（3）G(z,

f(z))

ES,(2)注意：使用ES規(guī)則來消去量詞時(shí)，若還2021/7/20有（其1）它(自"由x)

變($元y)G時(shí)(，x,

則y)必須P用關(guān)于自由變（元2）的(函$y數(shù))G符(z號,y來)取代常量U符S號,(1.)推理規(guī)則的正確使用（3）推導(dǎo)3：（1）($y)G(z,

y)（2）("

y)($y)G(y,

y)PUG,(1)分析：推導(dǎo)3是錯(cuò)誤的。正確的推導(dǎo)如下：（注1意）：($使y)用G(Uz,Gy規(guī))則來添加P量詞時(shí)，若選（用2變）元("xz取)($代y)yG，(z則,

y要)

求在UG原,(公1)式中y不能出現(xiàn)在量詞("

x)或($x)的轄域之內(nèi)。2021/7/20推理規(guī)則的正確使用（4）推導(dǎo)4：（1）G(x,

c)

P（2）($x)G(x,

x)

EG,(2)分析：推導(dǎo)4是錯(cuò)誤的。正確的推導(dǎo)如下：注（意1）：G使(x用,Ec)G規(guī)則來添加P

量詞時(shí)，若選用變（元2）x取($代y)cG，(x則,y要)求在原E公G,式(2)中c不能出現(xiàn)在量詞("x)或($x)的轄域之內(nèi)且原公式中中無自由變量x。2021/7/20判斷2021/7/20（1）("

x)($y)G(x,

y)（2）($y)G(z,

y)（3）G(z,

c)（4）("

x)G(x,

c)（5）($y)

("

x)G(x,

y)PUS,(1)ES,(2)UG,(3)EG,(4)4.5.2

謂詞演算的綜合推理方法2021/7/20推導(dǎo)過程中可以引用命題演算中的規(guī)則P和規(guī)則T

。如果結(jié)論是以蘊(yùn)涵形式(或析取形式)給出，我們還可以使用規(guī)則CP。若需消去量詞，可以引用規(guī)則US和規(guī)則ES。當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則UG和規(guī)則EG將其量詞加入。謂詞演算的綜合推理方法（續(xù)1）2021/7/20證明時(shí)可采用如命題演算中的直接證明方法和間接證明方法。在推導(dǎo)過程中，對消去量詞的公式或公式中不含量詞的子公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。在推導(dǎo)過程中，對含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。例4.5.1("

x)(H(x)fi

M(x))，H(s)證明蘇格拉底三段論：“所有的人都是要死的；蘇格拉底是人。所以蘇格拉底是要死的?！苯猓涸O(shè)H(x)：x是人；M(x)：x是要死的；s：蘇格拉底。則符號化為：證明：(1)(2)("

x)(H(x)fi

M(x))H(s)fi

M(s)PUS,(1)(3)H(s)P(4)M(s)T,(2),(3),I(4)錯(cuò)M(了s)

！證明：

(1) ("

x)(H(x)fi

M(x))

P(2)

H(x)fi

M(x)

US,(1)(3)

H(s)

P(4)

M(s)

T,(2),(3),I2021/7/20例4.5.22021/7/20證明：("

x)(P(x)fi

Q(x)),($x)P(x)($x)Q(x)有下面的推導(dǎo)：("

x)(P(x)fi

Q(x))P(x)fi

Q(x)($x)P(x)P(c)Q(c)($x)Q(x)PUS,(1)PES,(3)T,(2),(4),IEG,(5)例4.5.2（２)2021/7/20推導(dǎo)可修改為：("

x)(P(x)fi

Q(x))P(c)fi

Q(c)($x)P(x)P(c)Q(c)($x)Q(x)PUS,(1)PES,(3)T,(2),(4),IEG,(5)例4.5.2(３)請看推導(dǎo)：PES,(1)PUS,(3)($x)P(x)P(c)("

x)(P(x)fi

Q(x))P(c)fi

Q(c)Q(c)($x)Q(x)T,(2),(4),IEG,(5)正確！2021/7/20例4.5.32021/7/20證明：1)2)($x)(P(x)∧Q(x))P(c)∧Q(c)PES,1)3)P(c)T,2),I4)Q(c)T,2),I5)($x)P(x)EG,3)6)($x)Q(x)EG,4)7)($x)P(x)∧($x)Q(x)T,5),6),I證明：($x)(P(x)∧Q(x))($x)P(x)∧($x)Q(x)例4.5.3(續(xù)1)2021/7/20($x)P(x)∧($x)Q(x)($x)P(x)PT,1),I3)

P(c)ES,2)4)

($x)Q(x)T,1),I5)

Q(c)ES,4)6)

P(c)∧Q(c)T,3),4),I7)

($x)(P(x)∧Q(x))EG,6)請看上述推論的逆推導(dǎo)：例4.5.3(續(xù)2)2021/7/20正確地推導(dǎo)：($x)P(x)∧($x)Q(x)($x)P(x)PT,1),I3)

P(c)ES,2)4)

($x)Q(x)T,1),I5)

Q(b)ES,4)6)

P(c)∧Q(b)T,3),4),I7)

($y)(P(c)∧Q(y))EG,6)8)

($x)($y)(P(x)∧Q(y))EG,7)(("

x)P(x)∨($x)Q(x))("

x)P(x)∧

($x)Q(x)P(附加)T,1),E3) ("

x)P(x)T,2),I4)

($x)Q(x)T,2),I5)

($x)

P(x)T,3),E6)

P(c)ES,5)2021/7/20例4.5.4證明("x)(P(x)∨Q(x))("x)P(x)∨($x)Q(x)證明(采用反證法，CP規(guī)則的方法由學(xué)生完成)：例4.5.42021/7/20("

x)

Q(x)Q(c)P(c)∧

Q(c)10)(P(c)∨Q(c))("

x)(P(x)∨Q(x))(P(c)∨Q(c))13)

(P(c)∨Q(c))∧(P(c)∨Q(c))T,4),EUS,7)T,6),8),IT,9),EPUS,11)T,10),12)4.5.3

謂詞邏輯推理的難點(diǎn)2021/7/20在推導(dǎo)過程中，如既要使用規(guī)則US又要使用規(guī)則

ES消去公式中的量詞，而且選用的個(gè)體是同一個(gè)符號，則必須先先使用規(guī)則ES，再使用規(guī)則US。然后再使用命題演算中的推理規(guī)則，最后使用規(guī)則UG或規(guī)則EG引入量詞，得到所要的結(jié)論。如一個(gè)變量是用規(guī)則ES消去量詞，對該變量在添加量詞時(shí)，則只能使用規(guī)則EG，而不能使用規(guī)則

UG；如使用規(guī)則US消去量詞，對該變量在添加量詞時(shí)，則可使用規(guī)則EG和規(guī)則UG。謂詞邏輯推理的難點(diǎn)（續(xù)）2021/7/20如有兩個(gè)含有存在量詞的公式，當(dāng)用規(guī)則ES消去量詞時(shí)，不能選用同樣的一個(gè)常量符號來取代兩個(gè)公式中的變元，而應(yīng)用不同的常量符號來取代它們。在用規(guī)則US和規(guī)則ES消去量詞、用規(guī)則UG和規(guī)則

EG添加量詞時(shí)，此量詞必須位于整個(gè)公式的最前端，并且它的轄域?yàn)槠浜蟮恼麄€(gè)公式。謂詞邏輯推理的難點(diǎn)（續(xù)）2021/7/20在添加量詞("x)、($x)時(shí)，所選用的x不能在公式G(y)或G(c)中自由出現(xiàn)且G(y)或G(c)對x是自由的。在使用規(guī)則EG引入存在量詞($x)時(shí)，此x不得僅為G(c)或G(y)中的函數(shù)變元。在使用規(guī)則UG引入全稱量詞("x)時(shí)，此x不得為G(y)中的函數(shù)變元(因該函數(shù)變元不得作為自由變元)。在使用規(guī)則UG引入全稱量詞("x)時(shí)，G(y)中不得出現(xiàn)在使用規(guī)則US引入y之后由規(guī)則ES引入的常量或函數(shù)。4.5.42021/7/20謂詞邏輯推理的應(yīng)用每個(gè)喜歡步行的人都不喜歡坐汽車；每例4.5.5個(gè)人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車。因而有的人不喜歡步行。設(shè)