邏輯簡介Introductionto

Logic中山大學(xué)

楊超yangch8@一、命題邏輯

(Propositional

Logic)命題(Proposition)

：能判斷真假的陳述句。命題的真值(Truth

Value): 真(T)

或

假

(F)用大寫字母P,Q,R

等等表示命題●例子(

下列是否命題？如果是，是真還是假？）sin(x)

在x=0

處可導(dǎo)。若f(x)

在x_0

處連續(xù)，則f(x)

在x_0

處可導(dǎo)。f(x)

在區(qū)間[a,b]

上可積。火星上有生命。五個命題聯(lián)結(jié)詞●否定●●●(

讀作“非”

)P: f(x)=|x|

在x=0

處不可導(dǎo)。?P: f(x)=|x| 在

x=0 處可導(dǎo)。?P ?

PT FF T●●●P:

f(x)=|x|

在x=0

處連續(xù)。Q:

f(x)=|x|

在x=0

處可導(dǎo)?！窈先?/p>

∧P

∧Q: f(x)=|x|

在

x=0

處即連續(xù)又可導(dǎo)。P Q P∧QTTTTFFFTFFFF●●●P:

f(x)=|x|

在x=0

處連續(xù)。Q:

f(x)=|x|

在x=0

處可導(dǎo)。●析取

∨P

∨Q: f(x)=|x|

在

x=0

處連續(xù)或者可導(dǎo)。P Q P∨QTTTTFTFTTFFF●●●P:

f(x)=|x|

在x=0

處連續(xù)。Q:

1+1=2●條件

P

Q1+1=2: 如果

f(x)=|x|

在x=0

處連續(xù)，那么P Q P

QTTTTFFFTTFFT●●假設(shè)

A

是B

的子集，考慮下面命題P: x

是A

的元素?！馫

：

x

是B

的元素?！瘛瘛馪→Q:如果

x

是A

的元素，那么

x

是B

的元素。●雙條件 ?●●●P:

f(x)=|x|

在x=0

處連續(xù)。Q:

1+1=2P?Q: f(x)=|x|

在x=0

處連續(xù)當(dāng)且僅當(dāng)

1+1=2P Q P

?QTTTTFFFTFFFT命題公式●●●命題變元

P,

Q,R

等等是命題公式若A

是命題公式，則

?A

是命題公式若A

和B

都是命題公式，則A∧B

,

A∨B

,

A

B

,

A?

B

都是命題公式真值表PQ?

P?

P∨QTTFTTFFFFTTTFFTT永真式P Q P

Q P

∧

P

Q

P∧

P

Q

QTTTTTTFFFTFTTFTFFTFT●若無論命題變元的真值作何種指派，命題公式的真值都為真，則該命題公式稱為永真式。●更多永真式的例子

P

Q

∧Q

R

P

R

P

Q

??Q

?P

命題邏輯的永真式符合我們進(jìn)行數(shù)學(xué)推理的基本規(guī)律。等價(jià)的命題公式●若對所有不同的真值指派，命題公式

A

和B

都具有相同的真值，就稱

A

和B

是等價(jià)的。記作●●●●●注意：要和命題聯(lián)結(jié)詞?區(qū)分A?B

是永真式的充分必要條件是則

A

和B

等價(jià)。A

?B●若A

→

B

是永真式，則稱命題公式

A

蘊(yùn)涵B

，記作A?

BP

?Q

?

P

Q

∧Q

P

P Q P

Q Q

P

P

Q

∧Q

P

TTTTTTFFTFFTTFFFFTTTPQ?

P?P

∨QP

QTTFTTTFFFFFTTTTFFTTTPQ

??P∨QDe

MorganP Q ?

PT T FT F FF T TF F T?Q ?P

∨?Q ??P∨?Q

F F TT T FF T FT T FP

∧Q

???

P∨?Q

?

P

∧Q

?

?P

∨?Q●最小聯(lián)結(jié)詞組{?

,

∨}{?

,

∧}P

?Q

?

P

Q

∧Q

P

PQ

??P∨QP

∧Q

???

P∨?Q

分配律P

∧Q

∨

R?P∧Q

∨

P

∧RP

∨Q

∧

R?P∨Q

∧

P

∨R合取范式CNF(ConjunctiveNormal

Form)●●●●●一個命題公式稱為合取范式，若它具有下面形式，A1∧

A2

∧?∧

An其中

A_i 都是若干個命題變元或其否定的析取。如?

P∧

P∨?Q

∧

P∨Q

∨R●任何一個命題公式都可以表示成一個等價(jià)的合取范式?；静襟E如下：

(1)

先消滅?和→；

(2)用

De

Morgan

律把否定聯(lián)結(jié)詞直接作用到命題變元；

(3)

用分配律作最后的變換

P?Q

R?[

P

Q

∧Q

P

]

R?

?[

P

Q

∧Q

P

]∨R??[

?P

∨Q

∧?Q

∨P

]∨

R?[??

P

∨Q

∨??Q

∨P

]∨R?[

P∧?Q

∨Q

∧?

P

]∨

R?[

P∧?Q

∨Q

∧?

P

]∨

R?[

P

∨Q

∧?P

∧?Q

∨Q

∧?

P

]∨R?[

P

∨Q

∧

P

∨?

P

∧?Q∨Q

∧?Q

∨?

P]∨R?[

P∨Q

∧T

∧T

∧?Q

∨?

P

]∨R?[

P∨Q

∧?Q

∨?

P

]∨

R?[

P∨Q

∨

R]∧[

?Q

∨?

P

∨R]?

P

∨Q

∨R∧?Q

∨?P

∨R可滿足的

(Satisfiable)●●●●●若存在一個真值指派，使得命題公式是真的，則稱該命題公式是可滿足的?？蓾M足性問題

(SAT): 給定一個命題公式，這個公式是否可滿足的？可滿足性問題是

NP

完全問題的一個重要例子。NP

問題：給出問題的一個實(shí)例，和這個實(shí)例的一個猜想，能有算法在多項(xiàng)式時間內(nèi)驗(yàn)證這個猜想是否正確。3-SAT

問題二、謂詞邏輯

Predicate Logic●●●●●●個體和謂詞是偶數(shù)是偶數(shù)用P(x) 來表示

x 是偶數(shù)那么兩個命題就可以用

P(3),

P(4) 來表示，這里

P(x) 是一元謂詞，

3,4

是個體一般用小寫字母表示個體，大寫字母表示謂詞●●謂詞可以是多元的如用

P(x,y)

表示

x>y●●那么

P(4,3)

就表示命題

4>3也可以用

Q(x)

表示

x>3那么

Q(4) 也表示命題

4>3命題可以看成

0

元謂詞●●存在量詞●●量詞只作用到個體變元上，謂詞和量詞結(jié)合，可以構(gòu)成意思完整的命題如“任何整數(shù)都是偶數(shù)“這一命題可以如下表示。●●P(x)

:

x

是整數(shù)Q(x):

x 是偶數(shù)?

x

P

x

Q

x量詞全稱量詞

(

任意

)

???

x

P

x∧Q

x

?x

11=2●注意：量詞只作用到個體變元上，不作用到謂詞變元上。所以我們這里介紹的謂詞邏輯更準(zhǔn)確地也叫一階邏輯

(First-order

Logic)

，區(qū)別于高階謂詞邏輯?！癖热缯f，在一階謂詞邏輯里面，我們不說這樣的話：?

P

P

x

?

P

y

謂詞邏輯的公式●●●●●●(4) 若A

是公式，則都是公式●例：P,P(a)

，

P(x,y) 等是公式若A

是公式，則

?A

是公式若A

和B

都是公式，則A∧B

,

A∨B

,

A

B

,

A?

B

都是公式?x

Ax

,?x

Ax

?

x

R

x

?

P

Q

量詞的作用域自由變元和約束變元●●●量詞的作用域是跟在量詞后最小的命題公式受量詞限制的變元是約束變元不受量詞限制的為自由變元?

x

P

x

Q

x?

x

P

x

Q

y●例子：閉區(qū)間上的連續(xù)函數(shù)可積?！瘛瘛瘛瘛駁(x)

在閉區(qū)間

[a,b]

上連續(xù)。所以，

g(x)

在閉區(qū)間

[a,b]

上可積。P(f,a,b)

表示

f(x)

是

[a,b]

的連續(xù)函數(shù)。Q(f,a,b)

表示

f(x)

在

[a,b]

上可積。

?f

P

f ,

a

,

b

Q

f ,

a

,

b

∧P

g,

c

,

d

Q

g

,

c

,

d

?

x

P

x

Q

x

∧

P

a

Qa●謂詞公式的賦值：把

(

自由

)

個體變元用特定的個體代替，把謂詞變元用確定的謂詞代替?！瘛瘛袢魧λ械馁x值，謂詞公式的真值都為真，則稱為有效的。（類似于命題公式的永真式）若存在一種賦值使得謂詞公式為真，則稱為可滿足的。

?

x

P

x

Q

x

∧

P

a

Q

a等價(jià)式與蘊(yùn)涵式●若A?B

是有效的，就稱

A

和B

是等價(jià)的。記作●A

?B若A