理學(xué)數(shù)理邏輯

1

數(shù)理邏輯的主要任務(wù)是借助于數(shù)學(xué)的方法來(lái)研究推理的邏輯。

推理是從前題推出結(jié)論的思維過(guò)程，前提是已知的命題公式，結(jié)論是從前題出發(fā)應(yīng)用推理規(guī)則推出的命題公式。推理理論23.1推理的形式結(jié)構(gòu)定義3.1

設(shè)A1,A2,…,Ak,B為命題公式.若對(duì)于每組賦值，A1

A2

…

Ak

為假，或當(dāng)A1

A2

…

Ak為真時(shí)，B也為真，則稱由前提A1,A2,…,Ak推出結(jié)論B的推理是有效的或正確的,并稱B是有效結(jié)論.定理3.1

由命題公式A1,A2,…,Ak

推B的推理正確當(dāng)且僅當(dāng)A1

A2

…

Ak

B為重言式注意:推理正確不能保證結(jié)論一定正確3推理的形式結(jié)構(gòu)2.A1

A2

…

Ak

B

若推理正確,記為A1

A2

…

Ak

B3.前提：A1,A2,…,Ak

結(jié)論：B判斷推理是否正確的方法:

真值表法等值演算法主析取范式法推理的形式結(jié)構(gòu)1.{A1,A2,…,Ak}B

若推理正確,記為{A1,A2,,An}B4推理實(shí)例例1

判斷下面推理是否正確(1)若今天是1號(hào)，則明天是5號(hào).今天是1號(hào).所以,明天是5號(hào).(2)若今天是1號(hào)，則明天是5號(hào).明天是5號(hào).所以,今天是1號(hào).解設(shè)p：今天是1號(hào)，q：明天是5號(hào).(1)推理的形式結(jié)構(gòu):(p

q)

p

q用等值演算法

(p

q)

p

q

((

p

q)

p)

q

p

q

q

1

由定理3.1可知推理正確5推理實(shí)例(2)推理的形式結(jié)構(gòu):(p

q)

q

p

用主析取范式法

(p

q)

q

p

(

p

q)

q

p

((

p

q)

q)

p

q

p

(

p

q)

(p

q)

(p

q)

(p

q)

m0

m2

m3

結(jié)果不含m1,故01是成假賦值，所以推理不正確6例2判斷下列推理是否正確：如果天氣涼快，小王就不去游泳，天氣涼快，所以小王沒(méi)去游泳。

解這類推理問(wèn)題，應(yīng)先將命題符號(hào)化，然后寫(xiě)出前提、結(jié)論和推理的形式結(jié)構(gòu)，最后進(jìn)行判斷。設(shè)p：天氣涼快；q：小王去游泳。前提：p→﹁q,p。結(jié)論：﹁q。推理的形式結(jié)構(gòu)：((p→﹁q)∧p)→﹁q。下面分別用三種方法來(lái)判斷該蘊(yùn)含式是否為重言式。7（1）真值表法((p→﹁q)∧p)→﹁q(*)的真值表pq﹁qp→﹁q(p→﹁q)∧p(*)000110111010111000101111真值表的最后一列全為1，因而（*）是重言式，所以推理正確。8（2）等值演算法((p→﹁q)∧p)→﹁q((﹁p∨﹁q)∧p)→﹁q

﹁((﹁p∨﹁q)∧p)∨﹁q

﹁(﹁p∨﹁q)∨﹁p∨﹁q

﹁(﹁p∨﹁q)∨(﹁p∨﹁q)1該蘊(yùn)含式是重言式，所以推理正確。9((p→﹁q)∧p)→﹁q((﹁p∨﹁q)∧p)→﹁q

﹁((﹁p∨﹁q)∧p)∨﹁q

﹁(﹁p∨﹁q)∨﹁p∨﹁q(p∧q)∨(﹁p∧(q∨﹁q))∨(﹁q∧(p∨﹁p))(p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(﹁q∧p)∨(﹁q∧﹁p)(p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(p∧﹁q)m3∨m1∨m0∨m2（3）主析取范式法該蘊(yùn)含式的主析取范式中含有4個(gè)極小項(xiàng)，因而是重言式。10

為了更好地判斷推理的正確性，引入構(gòu)造證明的方法。在數(shù)理邏輯中，證明是一個(gè)描述推理過(guò)程的命題公式序列，其中的每個(gè)命題公式或者是已知的前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論。其中有些規(guī)則建立在推理定律（重言蘊(yùn)涵式）的基礎(chǔ)之上。

重要的9條推理定律：附加、化簡(jiǎn)、假言推理、拒取式、析取三段論、假言三段論、等價(jià)三段論、構(gòu)造性二難、

破壞性二難。除此之外，每個(gè)等值式均產(chǎn)生兩條推理定律。11推理定律——重言蘊(yùn)涵式1.A

(A

B)附加律2.(A

B)

A

化簡(jiǎn)律3.(A

B)

A

B

假言推理4.(A

B)

B

A

拒取式5.(A

B)

B

A

析取三段論6.(A

B)

(B

C)

(A

C)假言三段論7.(A

B)

(B

C)

(A

C)等價(jià)三段論8.(A

B)

(C

D)

(A

C)

(B

D)構(gòu)造性二難

(A

B)

(

A

B)

B

構(gòu)造性二難(特殊形式)9.(A

B)

(C

D)

(

B

D)

(

A

C)破壞性二難每個(gè)等值式可產(chǎn)生兩個(gè)推理定律如,由A

A可產(chǎn)生A

A

和A

A123.2自然推理系統(tǒng)P定義3.2

一個(gè)形式系統(tǒng)I由下面四個(gè)部分組成：

(1)非空的字母表，記作A(I).(2)A(I)中符號(hào)構(gòu)造的合式公式集，記作E(I).(3)E(I)中一些特殊的公式組成的公理集，記作AX(I).(4)推理規(guī)則集，記作R(I).

記I=<A(I),E(I),AX(I),R(I)>,其中<A(I),E(I)>是I的形式語(yǔ)言系統(tǒng),<AX(I),R(I)>是I的形式演算系統(tǒng).自然推理系統(tǒng):無(wú)公理,即AX(I)=

公理推理系統(tǒng)推出的結(jié)論是系統(tǒng)中的重言式,稱作定理13自然推理系統(tǒng)P定義3.3自然推理系統(tǒng)P定義如下:1.字母表

(1)命題變項(xiàng)符號(hào)：p,q,r,…,pi,qi,ri,…(2)聯(lián)結(jié)詞符號(hào)：

,

,

,

,

(3)括號(hào)與逗號(hào)：(,),，2.合式公式（同前）3.推理規(guī)則

(1)前提引入規(guī)則

(2)結(jié)論引入規(guī)則

(3)置換規(guī)則14推理規(guī)則(4)假言推理規(guī)則

(6)化簡(jiǎn)規(guī)則

(8)假言三段論規(guī)則

A

BA∴BA∴A

BA

B∴A(5)附加規(guī)則

(7)拒取式規(guī)則

(9)析取三段論規(guī)則

A

B

B∴AA

BB

C∴A

CA

B

B∴A15推理規(guī)則(10)構(gòu)造性二難推理規(guī)則

(11)破壞性二難推理規(guī)則

(12)合取引入規(guī)則

A

BC

DA

C∴B

DA

BC

D

B

D∴

A

CAB∴A

B16在自然推理系統(tǒng)P中構(gòu)造證明設(shè)前提A1,A2,,Ak,結(jié)論B及公式序列C1,C2,,Cl.如果每一個(gè)Ci(1

i

l)是某個(gè)Aj,或者可由序列中前面的公式應(yīng)用推理規(guī)則得到,并且Cl=B,則稱這個(gè)公式序列是由A1,A2,,Ak推出B的證明例3

構(gòu)造下面推理的證明：若明天是星期一或星期三，我明天就有課.若我明天有課，今天必備課.我今天沒(méi)備課.所以，明天不是星期一、也不是星期三.解(1)設(shè)命題并符號(hào)化設(shè)p：明天是星期一，q：明天是星期三，

r：我明天有課，s：我今天備課17直接證明法(2)寫(xiě)出證明的形式結(jié)構(gòu)前提：(p

q)

r,r

s,

s

結(jié)論：

p

q(3)證明①r

s

前提引入②

s

前提引入③

r①②拒取式④(p

q)

r

前提引入⑤

(p

q)③④拒取式⑥

p

q⑤置換18例4

寫(xiě)出對(duì)應(yīng)下面推理的證明：若數(shù)a是實(shí)數(shù)，則它不是有理數(shù)就是無(wú)理數(shù)。若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)。a是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a是無(wú)理數(shù)。解：將簡(jiǎn)單命題符號(hào)化：

p：a是實(shí)數(shù)；q：a是有理數(shù)；

r：a是無(wú)理數(shù)；s：a能表示成分?jǐn)?shù)。前提：p→(q∨r),﹁s→﹁q,p∧﹁s。結(jié)論：r。推理理論19證明：①p∧﹁s

前提引入②p①化簡(jiǎn)③﹁s①化簡(jiǎn)④p→(q∨r)

前提引入⑤q∨r②④假言推理⑥﹁s→﹁q

前提引入⑦﹁q③⑥假言推理⑧r⑤⑦析取三段論前提：p→(q∨r),﹁s→﹁q,p∧﹁s。結(jié)論：r。20

在使用構(gòu)造證明法來(lái)進(jìn)行推理時(shí)，常常采用一些技巧，下面介紹兩種：

1、附加前提證明法

2、歸謬法21附加前提證明法附加前提證明法適用于結(jié)論為蘊(yùn)涵式欲證前提：A1,A2,…,Ak

結(jié)論：C

B等價(jià)地證明前提：A1,A2,…,Ak,C

結(jié)論：B理由：

(A1

A2

…

Ak)

(C

B)

(A1

A2

…

Ak)

(

C

B)

(A1

A2

…

Ak

C)

B

(A1

A2

…

Ak

C)

B22附加前提證明法實(shí)例例5

構(gòu)造下面推理的證明

2是素?cái)?shù)或合數(shù).若2是素?cái)?shù)，則是無(wú)理數(shù).若是無(wú)理數(shù)，則4不是素?cái)?shù).所以，如果4是素?cái)?shù)，則2是合數(shù).解用附加前提證明法構(gòu)造證明

(1)設(shè)p：2是素?cái)?shù)，q：2是合數(shù)，

r：是無(wú)理數(shù)，s：4是素?cái)?shù)

(2)推理的形式結(jié)構(gòu)前提：p

q,p

r,r

s

結(jié)論：s

q

23附加前提證明法實(shí)例(3)證明

①s

附加前提引入②p

r

前提引入③r

s

前提引入④p

s②③假言三段論⑤

p①④拒取式⑥p

q

前提引入⑦q⑤⑥析取三段論前提：p

q,p

r,r

s

結(jié)論：s

q

24例6

如果小張去看電影，則當(dāng)小王去看電影時(shí)，小李也去。小趙不去看電影或小張去看電影。小王去看電影。所以當(dāng)小趙去看電影時(shí)，小李也去。解：將簡(jiǎn)單命題符號(hào)化：

p：小張去看電影；q：小王去看電影；

r：小李去看電影；s：小趙去看電影。前提：p→(q→r),﹁s∨p,q。結(jié)論：s→r。25證明：①﹁s∨p前提引入②s附加前提引入③p①②析取三段論④p→(q→r)

前提引入⑤q→r③④假言推理⑥q

前提引入⑦r

⑤⑥假言推理前提：p→(q→r),﹁s∨p,q。結(jié)論：s→r。26歸謬法（反證法）歸謬法(反證法)欲證前提：A1,A2,…,Ak

結(jié)論：B做法在前提中加入

B，推出矛盾.理由

A1

A2

…

Ak

B

(A1

A2

…

Ak)

B

(A1

A2

…

Ak

B)

(A1

A2

…

Ak

B)0

A1

A2

…

Ak

B027歸謬法實(shí)例例7

前提：

(p

q)

r,r

s,

s,p

結(jié)論：

q證明用歸繆法

①q

結(jié)論否定引入②r

s

前提引入③

s

前提引入④

r②③拒取式⑤

(p

q)

r

前提引入⑥

(p

q)④⑤析取三段論⑦

p

q⑥置換⑧

p①⑦析取三段論⑨p

前提引入

p

p⑧⑨合取28例8用歸謬法構(gòu)造下面推理的證明：前提：p→(﹁(r∧s)→﹁q),p,﹁s。結(jié)論：﹁q。29證明：①p→(﹁(r∧s)→﹁q)前提引入

②p前提引入③﹁(r∧s)→﹁q①②假言推理

④﹁(﹁q)否定結(jié)論引入⑤q④置換⑥r(nóng)∧s③⑤拒取式⑦s

⑥化簡(jiǎn)⑧﹁s前提引入⑨s∧﹁s⑦⑧合?、釣槊苁?，根據(jù)歸謬法說(shuō)明推理正確。前提：p→(﹁(r∧s)→﹁q),p,﹁s。結(jié)論：﹁q。30第三章習(xí)題課主要內(nèi)容推理的形式結(jié)構(gòu)判斷推理是否正確的方法真值表法等值演算法主析取范式法推理定律自然推理系統(tǒng)P構(gòu)造推理證明的方法直接證明法附加前提證明法歸謬法(反證法)31基本要求理解并記住推理形式結(jié)構(gòu)的兩種形式：

1.(A1

A2

…

Ak)

B2.前提：A1,A2,…,Ak

結(jié)論：B熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）牢記P系統(tǒng)中各條推理規(guī)則熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬法會(huì)解決實(shí)際中的簡(jiǎn)單推理問(wèn)題32練習(xí)1：判斷推理是否正確1.判斷下面推理是否正確:(1)前提：

p

q,

q

結(jié)論：

p解推理的形式結(jié)構(gòu):(

p

q)

q

p方法一：等值演算法

(

p

q)

q

p

((p

q)

q)

p

(

p

q)

q

p

((

p

q)

(

q

q))

p

p

q易知10是成假賦值，不是重言式，所以推理不正確.33練習(xí)1解答方法二：主析取范式法，

(

p

q)

q

p((p

q)q)p

p

q

M2

m0

m1

m3未含m2,不是重言式,推理不正確.34練習(xí)1解答方法三真值表法

不是重言式,推理不正確111001110100(

p

q)

q

pqp

p

q0111(p

q)

q0010方法四直接觀察出10是成假賦值35練習(xí)1解答用等值演算法

(q

r)

(p

r)(q

p)(q

r)(p

r)(q

p)

((q

r)(p

r))(q

p)

((q

p)(q

r)(r

p))(q

p)((q

p)(q

r)(r

p))(q

p)1推理正確(2)前提：q

r,p

r

結(jié)論：q

p

解推理的形式結(jié)構(gòu)：(q

r)

(p

r)(q

p)

36練習(xí)2：構(gòu)造證明2.在系統(tǒng)P中構(gòu)造下面推理的證明：如果今天是周六，我們就到頤和園或圓明園玩.如果頤和園游人太多，就不去頤和園.今天是周六，并且頤和園游人太多.所以,我們?nèi)A明園或動(dòng)物園玩.證明：

(1)設(shè)p：今天是周六，q：到頤和園玩，

r：到圓明園玩，s：頤和園游人太多

t：到動(dòng)物園玩

(2)前提：p

(q

r),s

q,p,s

結(jié)論：r

t37練習(xí)2解答(3)證明：①p

(q

r)前提引入②p

前提引入③q

r①②假言推理④s

q

前提引入⑤s

前提引入⑥

q④⑤假言推理⑦r③⑥析取三段論⑧r

t⑦附加前提：p

(q

r),s

q,p,s

結(jié)論：r

t38作業(yè)：習(xí)題三（52頁(yè)）

9,12,14(5),15(1),16(2)39第四章一階邏輯基本概念問(wèn)題的提出：一個(gè)原子命題只用一個(gè)字母表示，而不再對(duì)命題中的句子成分細(xì)分。這樣有一些邏輯問(wèn)題無(wú)法解決。

所有的人都是要死的；

蘇格拉底是人；所以，蘇格拉底是要死的。令P：所有的人都是要死的；

Q：蘇格拉底是人；

R：蘇格拉底是要死的。則原問(wèn)題符號(hào)化為：P∧QR。40主要內(nèi)容一階邏輯命題符號(hào)化個(gè)體詞、謂詞、量詞一階邏輯命題符號(hào)化一階邏輯公式及其解釋一階語(yǔ)言合式公式合式公式的解釋永真式、矛盾式、可滿足式414.1一階邏輯命題符號(hào)化

個(gè)體詞——所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體

個(gè)體常項(xiàng)：具體的事物，用a,b,c表示

個(gè)體變項(xiàng)：抽象的事物，用x,y,z表示

個(gè)體域(論域)——個(gè)體變項(xiàng)的取值范圍有限個(gè)體域，如{a,b,c},{1,2}

無(wú)限個(gè)體域，如N,Z,R,…

全總個(gè)體域——由宇宙間一切事物組成42謂詞定義：用以刻畫(huà)客體的性質(zhì)或者客體之間關(guān)系的即是謂詞。用一個(gè)大寫(xiě)英文字母后邊有括號(hào)，括號(hào)內(nèi)是若干個(gè)客體變?cè)硎局^詞，如果括號(hào)內(nèi)有n個(gè)客體變?cè)?，稱該謂詞為n元謂詞。例如

S(x):表示x是大學(xué)生。一元謂詞

G(x,y)：表示x>y。二元謂詞

B(x,y,z)：表示x在y與z之間。三元謂詞一般地

P(x1,x2,…,xn)是n元謂詞。43

n（n

1）元謂詞一元謂詞(n=1)——表示性質(zhì)多元謂詞(n

2)——表示事物之間的關(guān)系

如,L(x,y)：x與y有關(guān)系L，L(x,y)：x

y，…0元謂詞——不含個(gè)體變項(xiàng)的謂詞,即命題常項(xiàng)或命題變項(xiàng)謂詞常項(xiàng)如,F(a)：a是人

謂詞變項(xiàng)如,F(x)：x具有性質(zhì)F44量詞量詞——表示數(shù)量的詞

全稱量詞

:表示所有的.

x:對(duì)個(gè)體域中所有的x

如,

xF(x)表示個(gè)體域中所有的x具有性質(zhì)F

x

yG(x,y)表示個(gè)體域中所有的x和y有關(guān)系G

存在量詞

:表示存在,有一個(gè).

x:個(gè)體域中有一個(gè)x

如,

xF(x)表示個(gè)體域中有一個(gè)x具有性質(zhì)F

x

yG(x,y)表示個(gè)體域中存在x和y有關(guān)系G

x

yG(x,y)表示對(duì)個(gè)體域中每一個(gè)x都存在一個(gè)y使得

x和y有關(guān)系G

x

yG(x,y)表示個(gè)體域中存在一個(gè)x使得對(duì)每一個(gè)y,

x和y有關(guān)系G45解：在命題邏輯中：

(1)p,p為墨西哥位于南美洲（真命題）

(2)p→q,其中,p：是無(wú)理數(shù)，q：是有理數(shù).是假命題

(3)p

q,其中，p：2>3，q：3<4.是真命題實(shí)例1例1

用0元謂詞將命題符號(hào)化

(1)墨西哥位于南美洲

(2)是無(wú)理數(shù)僅當(dāng)是有理數(shù)

(3)如果2>3，則3<446在一階邏輯中：

(1)F(a)，其中，a：墨西哥，F(xiàn)(x)：x位于南美洲.(2)F()

G(),

其中，F(xiàn)(x)：x是無(wú)理數(shù)，G(x)：x是有理數(shù)

(3)F(2,3)

G(3,4)，其中，F(xiàn)(x,y)：x>y，G(x,y)：x<y實(shí)例1解答例1用0元謂詞將命題符號(hào)化

(1)墨西哥位于南美洲

(2)是無(wú)理數(shù)僅當(dāng)是有理數(shù)

(3)如果2>3，則3<447實(shí)例2例2

在一階邏輯中將下面命題符號(hào)化

(1)人都愛(ài)美

(2)有人用左手寫(xiě)字個(gè)體域分別為

(a)D為人類集合

(b)D為全總個(gè)體域解(a)(1)

xG(x),G(x)：x愛(ài)美(2)

xG(x),G(x)：x用左手寫(xiě)字

(b)F(x)：x為人，G(x)：x愛(ài)美

(1)

x(F(x)

G(x))

(2)

x(F(x)

G(x))1.引入特性謂詞F(x)2.(1),(2)是一階邏輯中兩個(gè)“基本”公式48實(shí)例3例3

在一階邏輯中將下面命題符號(hào)化

(1)正數(shù)都大于負(fù)數(shù)

(2)有的無(wú)理數(shù)大于有的有理數(shù)解注意：題目中沒(méi)給個(gè)體域，一律用全總個(gè)體域

(1)令F(x)：x為正數(shù)，G(y)：y為負(fù)數(shù),L(x,y)：x>y

x(F(x)

y(G(y)

L(x,y)))或者

x

y(F(x)

G(y)

L(x,y))(2)令F(x)：x是無(wú)理數(shù)，G(y)：y是有理數(shù)，L(x,y)：x>y

x(F(x)

y(G(y)

L(x,y)))或者

x

y(F(x)

G(y)

L(x,y))49實(shí)例4例4在一階邏輯中將下面命題符號(hào)化

(1)沒(méi)有不呼吸的人

(2)不是所有的人都喜歡吃糖解(1)F(x):x是人,G(x):x呼吸

x(F(x)G(x))

x(F(x)G(x))(2)F(x):x是人,G(x):x喜歡吃糖

x(F(x)G(x))

x(F(x)G(x))50實(shí)例5例5

設(shè)個(gè)體域?yàn)閷?shí)數(shù)域,將下面命題符號(hào)化

(1)對(duì)每一個(gè)數(shù)x都存在一個(gè)數(shù)y使得x<y(2)存在一個(gè)數(shù)x使得對(duì)每一個(gè)數(shù)y都有x<y解L(x,y):x<y(1)x

yL(x,y)注意:與不能隨意交換顯然(1)是真命題,(2)是假命題(2)x

yL(x,y)514.2一階邏輯公式及解釋定義4.1

設(shè)L是一個(gè)非邏輯符集合,由L生成的一階語(yǔ)言L

的字母表包括下述符號(hào)：非邏輯符號(hào)

(1)個(gè)體常項(xiàng)符號(hào)：a,b,c,…,ai,bi,ci,…,i

1(2)函數(shù)符號(hào)：f,g,h,…,fi,gi,hi,…,i

1(3)謂詞符號(hào)：F,G,H,…,Fi,Gi,Hi,…,i

1邏輯符號(hào)

(4)個(gè)體變項(xiàng)符號(hào)：x,y,z,…,xi,yi,zi,…,i

1(5)量詞符號(hào)：

,

(6)聯(lián)結(jié)詞符號(hào)：

,

,

,

,

(7)括號(hào)與逗號(hào)：(,),，52一階語(yǔ)言L

的項(xiàng)與原子公式定義4.2

L的項(xiàng)的定義如下：(1)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng).(2)若

(x1,x2,…,xn)是任意的n元函數(shù)，t1,t2,…,tn是任意的

n個(gè)項(xiàng)，則

(t1,t2,…,tn)是項(xiàng).(3)所有的項(xiàng)都是有限次使用(1),(2)得到的如,a,x,x+y,f(x),g(x,y)等都是項(xiàng)定義4.3

設(shè)R(x1,x2,…,xn)是L

的任意n元謂詞，t1,t2,…,tn

是L

的任意n個(gè)項(xiàng)，則稱R(t1,t2,…,tn)是L

的原子公式.

如，F(xiàn)(x,y),F(f(x1,x2),g(x3,x4))等均為原子公式53定義4.4

L

的合式公式定義如下：

(1)原子公式是合式公式.(2)若A是合式公式，則(

A)也是合式公式

(3)若A,B是合式公式，則(A

B),(A

B),(A

B),(A

B)也是合式公式

(4)若A是合式公式，則

xA,

xA也是合式公式

(5)只有有限次地應(yīng)用(1)—(4)形成的符號(hào)串才是合式公式.合式公式簡(jiǎn)稱公式如,F(x),F(x)

G(x,y),x(F(x)G(x))

x

y(F(x)G(y)L(x,y))等都是合式公式一階語(yǔ)言L

的公式54封閉的公式定義4.5

在公式

xA和

xA中，稱x為指導(dǎo)變?cè)?，A為相應(yīng)量詞的轄域.在

x和

x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的.例如，

x(F(x,y)

G(x,z))，x為指導(dǎo)變?cè)?F(x,y)

G(x,z))為

x的轄域，x的兩次出現(xiàn)均為約束出現(xiàn)，y與z均為自由出現(xiàn)又如,

x(F(x,y,z)y(G(x,y)H(x,y,z))),x中的x是指導(dǎo)變?cè)?轄域?yàn)?F(x,y,z)y(G(x,y)H(x,y,z))).y中的y是指導(dǎo)變?cè)?轄域?yàn)?G(x,y)H(x,y,z)).x的3次出現(xiàn)都是約束出現(xiàn),y的第一次出現(xiàn)是自由出現(xiàn),后2次是約束出現(xiàn),z的2次出現(xiàn)都是自由出現(xiàn)55封閉的公式定義4.6

若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡(jiǎn)稱閉式.例如，

x

y(F(x)

G(y)

H(x,y))為閉式，而

x(F(x)

G(x,y))不是閉式56公式的解釋定義4.7

設(shè)L

是L生成的一階語(yǔ)言,L的解釋I由4部分組成：

(a)非空個(gè)體域DI.(b)

對(duì)每一個(gè)個(gè)體常項(xiàng)符號(hào)a

L,有一個(gè)DI,稱

為a在I

中的解釋.(c)對(duì)每一個(gè)n元函數(shù)符號(hào)f

L,有一個(gè)DI上的n元函數(shù)

,稱

為f在I中的解釋.(d)對(duì)每一個(gè)n元謂詞符號(hào)F

L,有一個(gè)DI上的n元謂詞常項(xiàng),

稱

為F在I中的解釋.

設(shè)公式A,取個(gè)體域DI,把A中的個(gè)體常項(xiàng)符號(hào)a、函數(shù)符號(hào)f、謂詞符號(hào)F分別替換成它們?cè)贗中的解釋、、,稱所得到的公式A

為A在I下的解釋,或A在I下被解釋成A.57實(shí)例例6

給定解釋I如下：

(a)個(gè)體域D=R(b)(c)(d)

寫(xiě)出下列公式在I下的解釋,并指出它的真值.(1)

xF(f(x,a),g(x,a))

x(x+0=x0)真(2)

x

y(F(f(x,y),g(x,y))F(x,y))

x

y(x+y=x

y

x=y)假(3)

xF(g(x,y),a)

x(x

y=0)真值不定,不是命題58公式的類型定理4.1

閉式在任何解釋下都是命題注意:不是閉式的公式在解釋下可能是命題,也可能不是命題.定義4.8若公式A在任何解釋下均為真,則稱A為永真式(邏輯有效式).若A在任何解釋下均為假,則稱A為矛盾式(永假式).若至少有一個(gè)解釋使A為真,則稱A為可滿足式.幾點(diǎn)說(shuō)明：永真式為可滿足式，但反之不真判斷公式是否是可滿足的(永真式,矛盾式)是不可判定的59代換實(shí)例定義4.9

設(shè)A0是含命題變項(xiàng)p1,p2,…,pn的命題公式，A1,A2,…,An是n個(gè)謂詞公式，用Ai

(1

i

n)處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例.例如，F(xiàn)(x)

G(x),

xF(x)

yG(y)等都是p

q的代換實(shí)例.定理4.2

重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式.60實(shí)例例7

判斷下列公式中，哪些是永真式，哪些是矛盾式？

(1)

xF(x)

(

x

yG(x,y)

xF(x))重言式p

(q

p)的代換實(shí)例，故為永真式.(2)

(

xF(x)

yG(y))

yG(y)矛盾式

(p

q)

q的代換實(shí)例，故為永假式.(3)

x(F(x)

G(x))解釋I1:個(gè)體域N,F(x):x>5,G(x):x>4,公式為真解釋I2:個(gè)體域N,F(x):x<5,G(x):x<4,公式為假結(jié)論:非永真式的可滿足式61作業(yè)：習(xí)題四（65頁(yè)）

2,4,9

62第四章習(xí)題課主要內(nèi)容個(gè)體詞、謂詞、量詞一階邏輯命題符號(hào)化一階語(yǔ)言L

項(xiàng)、原子公式、合式公式公式的解釋量詞的轄域、指導(dǎo)變?cè)€(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋公式的類型永真式(邏輯有效式)、矛盾式(永假式)、可滿足式63基本要求

準(zhǔn)確地將給定命題符號(hào)化理解一階語(yǔ)言的概念深刻理解一階語(yǔ)言的解釋熟練地給出公式的解釋記住閉式的性質(zhì)并能應(yīng)用它深刻理解永真式、矛盾式、可滿足式的概念,會(huì)判斷簡(jiǎn)單公式的類型64練習(xí)11.在分別取個(gè)體域?yàn)?/p>

(a)D1=N

(b)D2=R(c)D3為全總個(gè)體域的條件下,將下面命題符號(hào)化，并討論真值

(1)對(duì)于任意的數(shù)x，均有解設(shè)G(x):(a)

xG(x)(b)

xG(x)(c)又設(shè)F(x):x是實(shí)數(shù)

x(F(x)

G(x))

真

真

假65練習(xí)1(續(xù))解設(shè)H(x)：x+7=5(a)

xH(x)(2)存在數(shù)x，使得

x+7=5(b)

xH(x)(c)又設(shè)F(x)