教案第3章-一階邏輯

第3

章—階邏輯（謂詞邏輯）本章主要學(xué)習(xí)以下內(nèi)容：3.1

一階邏輯基本概念3.2

一階邏輯等值演算＊3.3

一階邏輯推理理論第3章

一階邏輯3.1.1

命題邏輯的局限性例1：考慮下述推理:凡偶數(shù)都能被2整除，6是偶數(shù)，所以，6能被2整除。令p：凡偶數(shù)都能被2整除q：6是偶數(shù)r：6能被2整除符號化為：(p

q)

r顯然，110是其成假賦值。所以，在命題邏輯中不能證明其正確性。3.1

一階邏輯的基本概念例2：熊貓是動(dòng)物。長頸鹿是動(dòng)物。命題符號化：令p：熊貓是動(dòng)物

q：長頸鹿是動(dòng)物命題符號不能揭示這兩個(gè)命題的共性。因此，需要對簡單命題的成分、結(jié)構(gòu)、簡單命題間的共性等作進(jìn)一步分析。這正是一階邏輯所要研究的問題。3.1.1

命題邏輯的局限性例3：分析以下命題的成份。計(jì)算機(jī)

是科學(xué)技術(shù)的工具。是個(gè)大學(xué)生。在一階邏輯中，將進(jìn)一步地把簡單命題分解為主語（

詞）與謂語（謂詞）兩部分。3.1.2

詞 謂詞 量詞1、詞所研究對象中，可以獨(dú)立存在的具體的或抽象的客體（事物）稱為

詞。例如：計(jì)算機(jī),熊貓,愛國主義,

,,10。2、

常項(xiàng)， 變項(xiàng)常項(xiàng)：表示具體、特指的

詞。常用a,b,c…表示。變項(xiàng)：表示抽象、泛指的

詞。常用x,

y,z…

表示。一、詞及相關(guān)概念3、域(

)或論域域，是指

變項(xiàng)的取值范圍。常用字母D表示。說明：（1）

域可以是有限集或無限集例：{1,3,5,7}，實(shí)數(shù)集R

等。（2）全總

域是包含宇宙全體事物的最大

域。若無特別

，

域總是指全總

域。一. 詞及相關(guān)概念1、謂詞概念謂詞是用來刻劃

詞性質(zhì)或

詞之間關(guān)系的詞。常用大寫字母

F,

G,

H…表示。例：分析以下命題或命題變項(xiàng)位于

與杭州之間。比

高(1)

熊貓是動(dòng)物。(2)(4)(5)3大于2，x

<y，x+y=z二、謂 詞

(predicate)（1）一般地：

“

x

是…

”

類型 題，可符號化為F(x)

。例：熊貓是動(dòng)物、

是動(dòng)物。F：是動(dòng)物

x：熊貓

y：則

F(x)：熊貓是動(dòng)物F(y)：

是動(dòng)物2、用謂詞表示命題（2）

一般地：“x

＜y”、“…比…高”等類型題，可符號化為F(x,

y)。例：

3

>

2，

比設(shè)

F：大于高。G：…比…高a：3

b：2則

F(a,

b)：

3

>

2F(b,

a)：

2

>

3c：

d：例：G(c,

d)：

比

高位于

與杭州之間，如何用謂詞表示？3、謂詞常項(xiàng)，謂詞變項(xiàng)表示有具體性質(zhì)或關(guān)系的謂詞，稱為謂詞常項(xiàng)，否則就稱為謂詞變項(xiàng)。例：（1）他是三好生。（2）每天做廣播操是好（3）a

與b

滿足關(guān)系P。符號化為P(a,

b)。。

謂詞常項(xiàng)謂詞常項(xiàng)P是謂詞變項(xiàng)4、n元謂詞稱包含

n

個(gè)（n≥1）

詞（常項(xiàng)或變項(xiàng)）的域?yàn)槎x域、謂詞為n元謂詞。可表示為：P(x1,x2,…,xn)。n元謂詞，可以看成是以以｛0,1｝為值域的n元函數(shù)。例：F(x)

－－

一元謂詞，x

為

變項(xiàng)。F(a,

b)－－

二元謂詞，a,

b為

常項(xiàng)。注意：謂詞P(x1,x2,…,xn)，還不是命題。變項(xiàng)的謂詞，稱為0元謂詞。a：約定：將不含例如：H(a)P(c,

d)c：

d：月亮當(dāng)謂詞H、P

確定含義后，0元謂詞H(a)、P(c,

d)為命題。注意：命題邏輯中

題，都可以用0元謂詞表示。因此，可以把命題看作是謂詞的特殊情況。命題邏輯中的聯(lián)結(jié)詞也是謂詞，在一階邏輯中均可使用。例

3.1

將下列命題用0元謂詞符號化，并

它們的真值。(1)

2

是素?cái)?shù)且是偶數(shù)。解：設(shè)F(x)：x

是素?cái)?shù)，G(x)：x

是偶數(shù)，a：2則命題可符號化為：F(a)∧G(a)或F(2)∧G(2)。其真值為1。(2)

若2＞3，則2＞4。解：

設(shè)

L(x，y)：

x

＞ya：

2

b：3

c：4則命題可符號化為：L(a，b)

→

L(a，c)或L(2，3)→L(2，4)真值為1。y：鳥例1：所有的鳥都會飛。設(shè)F(x)：x

都會飛F(y)：鳥都會飛－－－－語氣不足例2：有的人活百歲以上。設(shè)

G(x)：

x

活百歲以上

y：人G(y)：人活百歲以上－－－－不合題意三、

量

詞

稱表示

常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞，為量詞。1、全稱量詞表示“所有”、“任意”等的詞，稱為全稱量詞。記為“”。域中的所有

x。域中的所有

x，都x

－－表示對x

F(x)－－表示有性質(zhì)F。三、

量

詞2、存在量詞表示“存在著”、“有某些”等的詞，稱為存在量詞。記為“

”符號。x－－表示存在

域中的

x

。x

F(x)－－表示存在

域中的有性質(zhì)F。注意：（1）量詞可看作是對x

，具詞附加的約束詞。（2）量詞的使用，要配合域的取值范圍。域D：鳥集合。例子：設(shè)F(x)：x

會飛，x

F(x)－－“所有的鳥都會飛”。(2)

設(shè)G(x)：x

是白的， 域

D：菊花集。x

G(x)－－“有些菊花是白的”。題的真值，與

域的范圍有關(guān)。注意：

含有量詞三、

量

詞例子：(3)

設(shè)F(x)：x會飛，D為全總

域。x

F(x)－－“宇宙間的一切事物都會飛”。(假命題)引進(jìn)特性謂詞，一般用字母M表示設(shè)M(x)：x

是鳥，則x

(M(x)→F(x))－－“所有的鳥都會飛”。(真命題)例子：(4)

有些菊花是白的。

全總

域上

。設(shè)

G(x)：x

是白的，xG(x)－－“有些事物是白的”。(真命題，不合題意)設(shè)M(x)：x是菊花。x

(M(x)∧G(x))－－“有些菊花是白的”(真命題，合題意)3、特性謂詞在

域D中，為某部分

的性質(zhì)而引入的謂詞，稱為特性謂詞。常用字母M表示。在全總

域中，特性謂詞用于限制

變項(xiàng)的取值范圍。注意：量詞后的特性謂詞，接蘊(yùn)涵（→）聯(lián)結(jié)詞；量詞后的特性謂詞，接合取（∧）聯(lián)結(jié)詞。一、命題符號化的步驟二、命題符號化示例三、命題符號化的注意事項(xiàng)3.1.3

一階邏輯命題符號化一、一階邏輯命題符號化的步驟1、把每個(gè)簡單命題分解成

詞、謂詞；在全總

域中

，要給出特性謂詞。2、找出恰當(dāng)量詞。注意：全稱量詞(x)后，跟條件式，存在量詞(x)后，跟合取式。3、用恰當(dāng)?shù)穆?lián)結(jié)詞。把給定

題表示出來。3.1.3一階邏輯命題符號化例3.2

在一階邏輯中將下面命題符號化:人都愛美。域D

分別?。?a)人類集合,解:

(a)

設(shè)

F(x):(b)

全總

域。x

愛美命題符號化為：x

F(x)(b)

設(shè)

F(x):

x

愛美M(x):

x

是人命題符號化為：x

(M(x)F(x))二、一階邏輯命題符號化示例例3.3

將下列命題符號化，并

其真值：對任意x，均有

x23x+2=(x1)(x2)。存在x，使得x+5=3。D分別?。?a)

域

D1=N,

(b)

域

D2=R解：

設(shè)

F(x)：x23x+2=(x1)(x2),G(x):

x+5=3(a)

命題(1)

符號化為：x

F(x)命題(2)符號化為：x

G(x)(b)

命題(1)符號化為：xF(x)命題(2)

符號化為：x

G(x)真值為1真值為0真值為1真值為1真值。例3.4

(P.88)

將下面命題符號化，并所有的人都長著黑頭發(fā)有的人登上過月球沒有人登上過木星留學(xué)的學(xué)生未必都是亞洲人(4)在注意：沒有給出域，一般在全總域上考慮。二、一階邏輯命題符號化示例例3.5

(P.89)

將下面命題符號化:兔子比烏龜跑得快。有的兔子比所有的烏龜跑得快。并不是所有的兔子都比烏龜跑得快。不存在跑得一樣快的兔子和烏龜。解：在全總

域上考慮。令

F(x)：x是兔子,

G(y)：y是烏龜,H(x,y)：x

比y

跑得快,L(x,y)：x

和y跑得一樣快x

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

(

F(x)

y

(G(y)H(x,y))

)x

y

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

y(F(x)G(y)L(x,y))例子：將下列命題符號化：沒有最大的自然數(shù)。解：即“對任意的自然數(shù)x，一定存在自然數(shù)y，且y

比x

大”。令N(x)：x

是自然數(shù)G(x,y)：x

大于y則原命題表示為：x

(

N(x)

y

(N(y)G(y,

x))

)例子：本章開頭之例如何符號化？課堂練習(xí)（

p102

習(xí)題

3.5）二、一階邏輯命題符號化示例2、

域不同，命題符號化的形式可能不同。3、若沒給出

域的范圍，則考慮全總

域。4、在引入特性謂詞后，使用全稱量詞或存在量詞符號化的形式，是不同的。5、多個(gè)量詞同時(shí)出現(xiàn)時(shí)，一般不能隨意顛倒它們的次序，因?yàn)橛锌赡軙淖冊}的含義。三、一階邏輯命題符號化注意事項(xiàng)1、分析命題中表示性質(zhì)和關(guān)系的謂詞，分別符號化為1元和n（n≥2）元謂詞。例子：yx

F(x,y)，F(xiàn)(x,y)：x<y域?yàn)閷?shí)數(shù)集R。：原命題是真命題。若將量詞次序改為：xy

F(x,y)表示存在一個(gè)實(shí)數(shù)

x，對任何實(shí)數(shù)y，均有x<y，是假命題。三、一階邏輯命題符號化注意事項(xiàng)6、

當(dāng)

域是有限集時(shí)，量詞可用聯(lián)結(jié)詞替代。設(shè)

域

D

={a1,

a2,…,

an}，則包含有全稱量詞的謂詞公式：x

A(x)表示a1

有性質(zhì)A，a2

有性質(zhì)A,…an

有性質(zhì)A。因此：x

A(x)

A(a1)∧A(a2)∧…∧A(an)思考：x

A(x)

A(a1)∨A(a2)∨…∨A(an)三、一階邏輯命題符號化注意事項(xiàng)一、一階語言

?二、謂詞的

合式公式三、量詞的

轄域四、謂詞公式的解釋及分類3.1.4

一階邏輯公式與分類一、一階語言?定義3.1（P.90）一階語言?的字母表定義如下：(3)函數(shù)符號：f,g,h,…,fi,gi,hi,…,常項(xiàng)：a,

b,c,…,

ai,

bi,ci,…,

i1變項(xiàng)：x,

y,

z,

…,

xi,

yi,

zi,

…,

i

1i1謂詞符號：F,G,H,…,Fi,Gi,Hi,…,i

1量詞符號：,聯(lián)結(jié)詞符號：,,,,括號與逗號：(),，定義3.2

(P.90)?的項(xiàng)的定義如下：常項(xiàng)、

變項(xiàng)是項(xiàng)。若

(x1,x2,…,xn)是任意的n

元函數(shù)，t1,t2,…,tn

是任意的n個(gè)項(xiàng)，則

(t1,t2,…,tn)是項(xiàng)。所有的項(xiàng)都是有限次使用

(1),(2)得到的。說明：①

項(xiàng)是

詞，而非謂詞。一、一階語言?說明②：有了項(xiàng)的概念，常項(xiàng)、變項(xiàng)可以利用函數(shù)表示。例子：試?yán)煤瘮?shù)及謂詞表示：“5

是自然數(shù)”令

函數(shù)

f

(x,y)=

x+y，謂詞N(x)：x

是自然數(shù)，則

f

(2,3)

表示

常項(xiàng)

5，而

N(f

(2,3))

表示

5

是自然數(shù)。一、一階語言?例子：試用函數(shù)及謂詞表示“的父親是教授”。設(shè)

P(x)：x

是教授f

(x)：x

的父親c：（f

(x)仍是詞）則命題可符號化為：P

(f(c))注意：函數(shù)與謂詞的區(qū)別（謂詞是特殊的函數(shù)）。一、一階語言?說明③：函數(shù)的使用，使謂詞表示更方便。例子：用謂詞表示以下命題：對任意整數(shù)

x，

x2-1=(x+1)(x-1)。令

F(x)：x

是整數(shù)f

(x)

=

x2-1g(x)

=

(x+1)(x-1)E(x,

y)：x=y則該命題可表示成：x

(F(x)E

(f(x),g(x)))。一、一階語言?定義3.3

(P.90)設(shè)

R

(x1,

x2,…,

xn)

是

?

的任意

n

元謂詞，t1,

t2,…,

tn是

?

的任意

n

個(gè)項(xiàng)，則稱R

(t1,t2,…,tn)是?的原子公式。即：一個(gè)n

元謂詞：R

(t1,t2,…,tn)是一個(gè)原子公式。其中，t1,

t2,

…,

tn

是?

的任意

n

個(gè)項(xiàng)。二、謂詞公式定義3.4

（

P.91）?的合式公式定義如下：原子公式是合式公式。若A

是合式公式，則(A)也是合式公式。若A，B是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式。若A是合式公式，則xA，xA

也是合式公式。只有有限次地應(yīng)用(1)~(4)形成的符號串才是合式公式。合式公式又稱謂詞公式，簡稱公式。注意：命題公式是謂詞公式。二、謂詞公式三、量詞的轄域定義3.5

（P.91）在公式xA

和xA

中，稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域。在x

和x

的轄域中，

x

的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他

變項(xiàng)稱為

出現(xiàn)。說明：①若量詞后有括號，該量詞的轄域，為括號內(nèi)的子公式；②若量詞后無括號，該量詞的轄域，為與其鄰接的子公式。例子

：求下列公式中的指導(dǎo)變元、各量詞的轄域、

出現(xiàn)、約束出現(xiàn)的 變項(xiàng)。(1)

x

P(x)∧Q(y)解：x

是指導(dǎo)變元，約束出現(xiàn)。x

的轄域：P(x)y

是

出現(xiàn)。(2)

x

(A(x)∨yB(x,

y))解：x，y

是指導(dǎo)變元，都是約束出現(xiàn)。x

的轄域：(A(x)∨y

B(x,

y))y

的轄域：B(x,

y)三、量詞的轄域例子

：求下列公式中的指導(dǎo)變元、各量詞的轄域、

出現(xiàn)、約束出現(xiàn)的

變項(xiàng)。(3)x

A(x)

B(x)解：x

的轄域：A(x)x

在A(x)

中，是約束出現(xiàn)，x

在

B(x)

中，是

出現(xiàn)。三、量詞的轄域例3.6

公式

x

(F(x,

y)

y

G(x,

y,

z))x

的轄域：(F(x,y)y

G(x,y,z))，指導(dǎo)變元為x；x

的兩次出現(xiàn)，均為約束出現(xiàn)。y

的轄域：G(x,y,z)，指導(dǎo)變元為y；y

的第1次出現(xiàn)，為

出現(xiàn)，第2次出現(xiàn)，為約束出現(xiàn)。出現(xiàn)。z

為三、量詞的轄域例：公式x

(F(x)xG(x))x

的轄域:(F(x)xG(x))，指導(dǎo)變元為

xx

的轄域:G(x)，指導(dǎo)變元為

xx

的兩次出現(xiàn)均為約束出現(xiàn)。但是,第一次出現(xiàn)的

x

是x

中的x,第二次出現(xiàn)的x

是x

中的x.三、量詞的轄域說明：本書用A(x1,x2,…,xn)表示含

x1,x2,…,xn

為

出現(xiàn)的公式。在公式⊿xi

A(x1,x2,…xi-1,xi

,xi+1

,…,xn)中，只有xi

為約束出現(xiàn)。其中，⊿表示

或。在公式⊿x1⊿x2

…

⊿

xn

A(x1,x2,

…,

xn)

中，無

出現(xiàn)的

變項(xiàng)。課堂練習(xí)（

p103

習(xí)題

3.14）三、量詞的轄域定義3.6

（P.92）設(shè)

A為任意一個(gè)公式，若

A中無

出現(xiàn)的個(gè)體變項(xiàng)，則稱

A為封閉的公式，簡稱閉式。變項(xiàng)，均為約束出現(xiàn)。即：閉式中所有例子：x

(P(x)Q(x))，是閉式，xy

(P(x)Q(x,y))x

(P(x)Q(x,y))，

yz

L(x,y,z)不是閉式。三、量詞的轄域1、公式的解釋

一般謂詞公式中含有：

常項(xiàng)、

變項(xiàng)（約束出現(xiàn)或

出現(xiàn)）、函數(shù)變項(xiàng)、謂詞變項(xiàng)等。對各種變項(xiàng)，用指定的特殊常項(xiàng)去代替，就構(gòu)成了一個(gè)公式的解釋。被賦予解釋的謂詞公式才可能成為命題，才可能有確定的真值。四、謂詞公式解釋與類型例3.7：將公式

x

(F(x)G(x))中的變項(xiàng)，指定成常項(xiàng)，使其成為命題。解：指定1：令

域

D：全總

域，F(xiàn)(x)：x

是人，G(x)：x

是黃種人假命題。指定2:

令

域D

:實(shí)數(shù)集,F(x)：x

>10，G(x)：x

>0真命題。對于其它不同的指定，可以得到不同題。四、謂詞公式解釋與類型定義3.7

設(shè)一階語言?

的常項(xiàng)集為{ai

|i1},函數(shù)符號集為{fi

|

i1}，謂詞符號集為{Fi

|

i1},?的解釋I

由下面4

部分組成:(1)

非空

域

D。(2)

對每一個(gè)(3)對每一個(gè)n

元的函數(shù)fi，

D上的n元函數(shù)稱作函數(shù)fi

的解釋。常項(xiàng)

ai,

ai

D，稱作

ai

的解釋。fi

，(4)

對每一個(gè)n

元謂詞符號Fi，

D上的n元謂詞Fi

,稱作謂詞Fi

的解釋。四、謂詞公式解釋與類型(d)

謂詞其真值。試說明下列公式在解釋I

下的含義，并(1)

x

F(g(x,

a),

x)例3.8（P.93）

給定解釋I

如下：域D

=Na

2f

(x,

y)

x

y,

g(x,

y)

xyF

(

x,

y)

:

x

y公式解釋為：

x

(

2x

=

x

)

假命題(2)

xy

(F

(

f(x,

a),

y

)

F

(

f(y,

a),

x

))公式解釋為：xy

(

x+2=y

y+2=x

)

假命題四、謂詞公式解釋與類型xyz

(x+y=z)

真命題x

(2x

=x2

)

真命題x+2

=

2x例3.8（P.93）

給定解釋I

如下：(c)域D=Na

2f

(

x,

y)

x

y,

g(

x,

y)

xy(d)謂詞F

(x,y):x

yxyz

F

(f

(x,y),z

)x

F

(

f(x,x),

g(x,

x)

)F

(

f(x,

a),g(x,

a)

)不是命題(6)

x

(

F(x,y)