會(huì)計(jì)學(xué)1命題邏輯與謂詞邏輯會(huì)計(jì)學(xué)1命題邏輯與謂詞邏輯2.1命題邏輯

1．命題

定義2-1

命題：具有真假意義的語句。

定義2-2

原子命題：如果一個(gè)命題不能被進(jìn)一步分解成更為簡單的命題，則該命題就稱為原子命題。第1頁/共47頁2.1命題邏輯

1．命題第1頁/共47頁2．連接詞～：稱為“非”或“否定”。∨：稱為“析取”，P∨Q讀作“P或Q”。∧：稱為“合取”，P∧Q讀作“P與Q”?！悍Q為“條件”。P→Q。：稱為“雙條件”。PQ,“P當(dāng)且僅當(dāng)Q”。連接詞優(yōu)先級：～，∧，∨，→，第2頁/共47頁2．連接詞第2頁/共47頁

3．合式公式定義2-3

合式公式（Well-FormedFormula，WFF）①孤立的命題變元或邏輯常量（T，F(xiàn)）是合式公式；②如果A是一個(gè)合式公式，則～A也是一個(gè)合式公式；③如果A、B是合式公式，則A∨B，A∧B，A→B，AB也都是合式公式；④當(dāng)且僅當(dāng)有限次使用規(guī)則①～③后得到的公式才是合式公式。第3頁/共47頁3．合式公式第3頁/共47頁

永真式（或重言式）：給定一個(gè)公式，如果對于所有的真值指派，它的值都為真（T），則稱該公式為永真式（或重言式）；

永假式（或稱該公式為不可滿足的）：如對于所有的真值指派，它的值都為假（F），則稱該公式為永假式（或稱該公式為不可滿足的）。非永假的公式稱為可滿足的公式。第4頁/共47頁永真式（或重言式）：給定一個(gè)公式，如果對4．等價(jià)和永真蘊(yùn)涵定義2-4

等價(jià)：設(shè)A，B是兩個(gè)命題公式，P1，P2，…，Pn是出現(xiàn)在A、B中的所有命題變元。如果對于這n個(gè)變元的任何一個(gè)真值指派的集合，A和B的真值都相等，則稱公式A等價(jià)于公式B，記作AB?！暗葍r(jià)”又可定義為：AB當(dāng)且僅當(dāng)AB是一個(gè)永真式。第5頁/共47頁4．等價(jià)和永真蘊(yùn)涵第5頁/共47頁

定義2-5

永真蘊(yùn)涵：命題公式A永真蘊(yùn)涵命題公式B，當(dāng)且僅當(dāng)A→B是一個(gè)永真式，記作AB，讀作“A永真蘊(yùn)涵B”，簡稱“A蘊(yùn)涵B”。第6頁/共47頁定義2-5永真蘊(yùn)涵：命題公式A永真蘊(yùn)2.2謂詞邏輯

1．謂詞與個(gè)體原子命題被分解為謂詞和個(gè)體兩部分。個(gè)體是指可以單獨(dú)存在的事物，它可以是一個(gè)抽象的概念，也可以是一個(gè)具體的東西。謂詞是用來刻畫個(gè)體性質(zhì)或個(gè)體間關(guān)系的詞。如：

POET(libai)POET(dufu)GREAT(libai,dufu)

一般用大寫字母表示謂詞，小寫字母表示個(gè)體。第7頁/共47頁2.2謂詞邏輯

1．謂詞與個(gè)體如：第7頁/共47頁

元數(shù):謂詞中包含的個(gè)體數(shù)目稱為謂詞的。一元謂詞:與一個(gè)個(gè)體相連的謂詞，如POET(x)；

多元謂詞:與多個(gè)個(gè)體相連的謂詞叫，如GREAT(x,y)(二元謂詞)。個(gè)體域:任何個(gè)體的變化都有范圍。謂詞變元命名式:一個(gè)n元謂詞常被表示成P(x1,x2,…,xn)。第8頁/共47頁元數(shù):謂詞中包含的個(gè)體數(shù)目稱為謂詞的。第8頁/共2．量詞全稱量詞:“(x)P(x)”表示命題“對個(gè)體域中所有的個(gè)體x，謂詞P(x)均為T”。存在量詞:“(x)Q(x)”表示命題“在個(gè)體域中存在某個(gè)個(gè)體使謂詞Q(x)為T”。其中“”叫存在量詞。設(shè)x的取值范圍是{甲，乙，丙}三人，y的取值范圍是{bora,jetta,santana}三種車型。(x)(y)LIKE(x,y)表示甲、乙、丙三人都喜愛{bora,jetta,santana}中的某一種車型；(x)(y)LIKE(x,y)表示甲、乙、丙三人都喜愛{bora,jetta,santana}三種車型。第9頁/共47頁2．量詞設(shè)x的取值范圍是{甲，乙，丙}三人，y的取值范3．合式謂詞公式原子公式:若P為不能再分解的n元謂詞變元，x1,x2,…,xn是個(gè)體變元，則稱P(x1,x2,…,xn)為原子公式或原子謂詞公式。當(dāng)n?=?0時(shí)，P表示命題變元或原子命題公式。所以命題邏輯是謂詞邏輯的特例第10頁/共47頁3．合式謂詞公式第10頁/共47頁

定義2-6

謂詞合式公式（簡稱公式）的定義如下：①原子公式是合式公式；②若A是合式公式，則～A也是合式公式；③若A和B都是合式公式，則(A∧B)，(A∨B)，(A→B)，(AB)也都是合式公式；④若A是合式公式，x是任意變元，且A中無(x)或(x)出現(xiàn)，則(x)A或(x)A也都是合式公式；⑤當(dāng)且僅當(dāng)有限次使用規(guī)則①～④得到的公式是合式公式。第11頁/共47頁定義2-6謂詞合式公式（簡稱公式）的4．量詞的轄域與變元的約束約束變元,

自由變元。

公式約束變元自由變元

(x)P(x,y)xy

(x)Q(y)無y

(x)(P(x)→(y)Q(x,y))x,y(y)P(x)∧Q(x)yx第12頁/共47頁4．量詞的轄域與變元的約束第12頁/共47頁5．謂詞公式的解釋謂詞公式中的謂詞變元、命題變元和自由個(gè)體變元，個(gè)體常量和函數(shù)的一種指派就是一個(gè)解釋。在每一種解釋下，謂詞公式都具有一種真值（T或F）。第13頁/共47頁5．謂詞公式的解釋第13頁/共47頁

定義2-7

設(shè)D為謂詞公式P的個(gè)體域，若對P中的個(gè)體常量、函數(shù)和謂詞按照如下規(guī)定賦值：（a）為每個(gè)個(gè)體常量指派D中的一個(gè)元素；（b）為每個(gè)n元函數(shù)指派一個(gè)從Dn到D的映射，其中

Dn?=?{(x1,x2,…,xn)?|?x1,x2,…,xn

D}

（c）為每個(gè)n元謂詞指派一個(gè)從Dn到{F，T}的映射；則稱這些指派為公式P在D上的一個(gè)解釋I。第14頁/共47頁定義2-7設(shè)D為謂詞公式P的個(gè)體域，

例2-1

給定公式B?=?(x)(y)P(x,y)和個(gè)體域D1?=?{1，2}。求：公式B的解釋及在該解釋下B的真值。解：x,y都可以取D1中的任何值，于是可有以下幾種情況：P(1,1)，P(1,2)，P(2,1)，P(2,2)。對這4個(gè)公式，每一個(gè)都可以指派真假（T，F(xiàn)）兩個(gè)值，則共有24=16個(gè)不同的組合，構(gòu)成16個(gè)不同的解釋。

第15頁/共47頁例2-1給定公式B?=?(x)(

P(1,1)P(1,2)P(2,1)P(2,2)I1TTTTI2TTTFI3TTFTI4TTFFI5TFTTI6TFTFI7TFFTI8TFFFI9FTTTI10FTTFI11FTFTI12FTFFI13FFTTI14FFTFI15FFFTI16FFFF如對I6，則有B(I6)?=?T。因?yàn)椋簩?=?1時(shí)，存在一個(gè)y?=?1，有P(x,y)?=?P(1,1)?=?T。對x?=?2時(shí)，存在一個(gè)y?=?1，有P(x,y)?=?P(2,1)?=?T。所以在I6解釋下，公式B為真。第16頁/共47頁P(yáng)(1,1)P(1,2)如D2?=?{1，2，3}

根據(jù)上面的分析，在D2上的解釋應(yīng)有29個(gè)。下面是其中的一個(gè)解釋：I:P(1,1)

P(1,2)

P(1,3)

P(2,1)

P(2,2)

P(2,3)

P(3,1)

P(3,2)

P(3,3)

T

T

T

F

F

T

F

F

F

由于x?=?3時(shí)，不存在一個(gè)y使P(x,y)?=?T。所以在這個(gè)解釋下公式B為假，即B(I

)?=?F。第17頁/共47頁如D2?=?{1，2，3}第17頁/共47頁

例2-2

給定公式

A?=?(x)(P(x)→Q(?f?(x),a))和個(gè)體域

D?=?{0，1}。公式中有個(gè)體常量a和一元函數(shù)f?(x)，所以按定義可以如下構(gòu)造對它的解釋I1：（a）給個(gè)體常量a賦一個(gè)D中的元素如：（b）給一元函數(shù)f?(x)指派一個(gè)由D1到D的映射，如：第18頁/共47頁例2-2給定公式第18頁/共47頁（c）對每個(gè)謂詞符號指派一個(gè)由D1到{F，T}的映射（對P(x)）或D2到{F，T}的映射（對Q(f(x),a)），如：

P(0)

P(1)

Q(0,0)

Q(0,1)

Q(1,0)

Q(1,1)

F

T

T

(T)

F

(T)

其中（T）表示不可能出現(xiàn)的狀態(tài)，因?yàn)閍已經(jīng)取值0，不可能再取值1，所以不可能出現(xiàn)Q(0,1)或Q(1,1)這兩種狀態(tài)。要考察在這個(gè)解釋下公式A的真假，根據(jù)量詞(x)要對所有x進(jìn)行考察。由于：對x?=?0時(shí)，P(x)→Q(?f?(x),a)?=?P(0)→Q(?f?(0),0)?=?P(0)→Q(1,0)?=?F→F?=?T對x?=?1時(shí)P(x)→Q(?f?(x),a)?=?P(1)→Q(?f?(1),0)?=?P(1)→Q(0,0)?=?T→T?=?T所以在此解釋下，公式A為真，即A(I1)?=?T。第19頁/共47頁（c）對每個(gè)謂詞符號指派一個(gè)由D1到{F，T}的映射（對P(

還可以在D上定義如下的解釋I2：f?(0)f?(1)01a1P(0)P(1)Q(0,0)Q(0,1)Q(1,0)Q(1,1)TF(T)F(T)F則當(dāng)x?=?0時(shí)，P(x)→Q(?f?(x),a)?=?P(0)→Q(?f?(0),1)?=?P(0)→Q(0,1)?=?T→F?=?F當(dāng)x?=?1時(shí)，P(x)→Q(?f?(x),a)?=?P(1)→Q(?f?(1),1)?=?P(1)→Q(1,1)?=?F→T?=?T所以在解釋I2下公式A為假，即A(I2)?=?F。第20頁/共47頁還可以在D上定義如下的解釋I2：f?(0)f?(1

在上述個(gè)體域D上，公式A有多少種解釋？對a有兩種解釋，對f?(x)有22種解釋（nn

），對P(x)有22種解釋（2n

），對Q(?f?(x),a)有22種解釋（2n

），則在D上，A共有2222222?=?27種有意義的解釋。如果D中含有n個(gè)元素，則公式A的有意義解釋的個(gè)數(shù)為：

nnn2n2n?=?22nnn+1

將解釋中各個(gè)值一一代入P(x)→Q(?f?(x),a)中就可得出其真值。第21頁/共47頁在上述個(gè)體域D上，公式A有多少種解釋？第21

定義2-8

公式B是相容的（又叫可滿足的或非永假的），當(dāng)且僅當(dāng)存在一個(gè)解釋I，使得B在I下為T，即

B相容（可滿足）

(I?)B(I)

這時(shí)就稱I滿足B，又稱I是B的一個(gè)模型。

定義2-9

公式B是不相容的（又叫不可滿足的或永假的），當(dāng)且僅當(dāng)沒有任何能滿足B的解釋存在，即

B不相容（不可滿足）～(I?)B(I)第22頁/共47頁定義2-8公式B是相容的（又叫可滿足

定義2-10

公式B是永真的，當(dāng)且僅當(dāng)所有解釋I都滿足B，即

B永真

(I?)B(I)

定義2-11

公式B是非永真的，當(dāng)且僅當(dāng)不是所有的解釋I都滿足B，即

B非永真～(I

)B(I)

這就是說公式B在有些解釋下為真，有些解釋下為假。第23頁/共47頁定義2-10公式B是永真的，當(dāng)且僅當(dāng)

推論①B相容

(～B)非永真②B不相容（永假）

(～B)永真③B永真

B相容④B不相容（永假）

B非永真第24頁/共47頁推論第24頁/共47頁

定義2-12

公式G是B1,B2,…,Bn的邏輯結(jié)論（推論），當(dāng)且僅當(dāng)對每一個(gè)解釋I，如果B1,B2,…,Bn都為T，則G也為T。這時(shí)稱B1,B2,…,Bn為G的前提。第25頁/共47頁定義2-12公式G是B1,B2,

定理2-1

G為B1,B2,…,Bn的邏輯結(jié)論，當(dāng)且僅當(dāng)

(B1?∧?B2?∧?…?∧?Bn)

G

證明：若(B1?∧?B2?∧?…?∧?Bn)G

成立，即（B1?∧?B2?∧?…?∧?Bn)→G

是永真式，也就是說在任一個(gè)使B1,B2,…,Bn都為真的解釋下，G也為真，可見G是B1,B2,…,Bn的邏輯結(jié)論。反之，若

(B1?∧?B2?∧?…?∧?Bn)G

不成立，即

(B1?∧?B2?∧?…?∧?Bn)→G

為非永真式，也就是說存在使B1,B2,…,Bn都為真的解釋，但卻不滿足G，所以G不是B1,B2,…,Bn的邏輯結(jié)論。（證畢）第26頁/共47頁定理2-1G為B1,B2,…,Bn的

定理2-2

G為B1,B2,…,Bn的邏輯結(jié)論，當(dāng)且僅當(dāng)

(B1?∧?B2?∧?…?∧?Bn)?∧?～G

是不相容的（永假）。證明：由定理1知，G是B1,B2,…,Bn的邏輯結(jié)論，當(dāng)且僅當(dāng)

(B1?∧?B2?∧?…?∧?Bn)

G

即

(B1?∧?B2?∧?…?∧?Bn)→G

為永真式，也就是說～((B1?∧?B2?∧?…?∧?Bn)?→?G?)

是不相容（永假）的，因?yàn)橛勒媸降姆穸ㄊ遣幌嗳莸?。而?(B1?∧?B2?∧?…?∧?Bn)?→?G?)

～(～(B1?∧?B2?∧?…?∧?Bn)?∨?G?)(B1?∧?B2?∧?…?∧?Bn)?∧?～G

故(B1?∧?B2?∧?…?∧?Bn)?∧?～G是不相容的。（證畢）定理2-2是反證法的理論依據(jù)。第27頁/共47頁定理2-2G為B1,B2,…,Bn的邏6．謂詞公式中的等價(jià)和蘊(yùn)涵式

定義2-13

設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域。若對D上的任何一個(gè)解釋，P與Q的真值都相同，則稱公式P和Q在域D上是等價(jià)的。如果在任何個(gè)體域上P和Q都等價(jià)，則稱P和Q是等價(jià)的，記做：P

Q。第28頁/共47頁6．謂詞公式中的等價(jià)和蘊(yùn)涵式第28頁/共47頁

下面是一些常用的等價(jià)式：交換律 P∨QQ∨P

P∧QQ∧P結(jié)合律 (P∨Q)∨RP∨(Q∨R) (P∧Q)∧RP∧(Q∧R)分配律 P∨(Q∧R)(P∨Q)∧(P∨R)

P∧(Q∨R)(P∧Q)∨(P∧R)德·摩根定律 ～(P∨Q)

～P∧～Q

～(P∧Q)

～P?∨～Q雙重否定律 ～(～P)

P第29頁/共47頁下面是一些常用的等價(jià)式：第29頁/共47頁吸收律 P∨(P∧Q)

P

P∧(P∨Q)

P補(bǔ)余律P∨～P

T

P∧～P

F逆否定律 P→Q

～Q→～P連結(jié)詞化歸律 P→Q

～P∨Q

PQ

(P→Q)∧(Q→P)

PQ

(P∧Q)∨(～P∧～Q)量詞轉(zhuǎn)換律 ～(x)P

(x)(～P)

～(x)P

(x)(～P)量詞分配律 (x)(P∧Q)(x)P∧(x)Q (x)(P∨Q)(x)P∨(x)Q

注意，量詞分配律是全稱量詞對合取的分配、存在量詞對析取的分配。第30頁/共47頁吸收律 P∨(P∧Q)P第30頁/共47頁

定義2-14

對于謂詞公式P和Q，如果P→Q是永真式，則稱P永真蘊(yùn)涵Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記作PQ。第31頁/共47頁定義2-14對于謂詞公式P和Q，

下面是一些常用的永真蘊(yùn)涵式：化簡式 P∧QP

P∧QQ附加式 PP∨Q

QP∨Q析取假論 ～P并且P∨QQ假言推理 P并且P→QQ拒取式 ～Q并且P→Q

～P假言三段論 P→Q且Q→RP→R兩難推理 P∨Q且P→R且Q→RR（證明：如果～R，則～P，～Q，此時(shí)P∨Q為假，與前提相矛盾）全稱固化 (x)P(x)

P(y)，其中y是個(gè)體域上的任一個(gè)體，利用此蘊(yùn)涵式可以消去公式中的全稱量詞。存在固化 (x)P(x)

P(y)，其中y是個(gè)體域上某個(gè)使P(y)為真的個(gè)體，利用此式可以消去公式中的存在量詞。第32頁/共47頁下面是一些常用的永真蘊(yùn)涵式：第32頁/共47頁7．子句集合為了便于進(jìn)行謂詞演算，應(yīng)先將公式在不失原意的情況下進(jìn)行變形，使之成為某種標(biāo)準(zhǔn)形，這種標(biāo)準(zhǔn)形也稱為范式。前束范式和斯克林（skolem）范式。第33頁/共47頁7．子句集合第33頁/共47頁

（1）前束范式所謂前束范式，就是指在一個(gè)謂詞公式中，如果它的所有量詞均非否定地出現(xiàn)在公式的最前面，且它的轄域一直延伸到公式之尾，同時(shí)公式中不出現(xiàn)連結(jié)符號→、，則這種形式的公式就是前束范式，形如

(Q1x1)(Q2x2)…(Qnxn)M

其中Qi或?yàn)榛驗(yàn)?，M稱為母式。例如，公式

(x)(y)(z)((～P(x,y)∧Q(x,z))∨R(x,y,z))第34頁/共47頁（1）前束范式第34頁/共47頁（2）斯克林范式在離散數(shù)學(xué)中，斯克林范式的定義是存在量詞全部位于全稱量詞的前面，形如：

(x)(y)(z)(P(x)∧Q(y)∧F(z))而在人工智能中，斯克林范式指在前束范式中消去全部存在量詞后得到的公式，形如

(x1)(x2)…(xn)M(x1,…,xn)

即母式M全部受全稱量詞約束。第35頁/共47頁（2）斯克林范式第35頁/共47頁

將合式公式WFF（wellformedformula）化成skolem標(biāo)準(zhǔn)形的步驟如下：（a）利用等價(jià)式P→Q

～P∨Q消去連結(jié)符號“→”。（b）在所有可能地方將否定符去掉或?qū)⒎穸ǚ麅?nèi)移，直至使其轄域減小到一個(gè)原子公式。（c）將合式公式WFF中的變量標(biāo)準(zhǔn)化，使得每一量詞的約束變量有唯一的名字。（d）用skolem函數(shù)將所有的存在量詞消去。（e）將合式公式化為前束范式，即把所有的全稱量詞都移到合式公式的左邊，使每個(gè)的轄域均為整個(gè)WFF。（f）將母式化為合取范式。（g）去掉全稱量詞。因?yàn)榇藭r(shí)公式中的所有變量都被全稱量詞約束，已無存在必要，故可以消去。至此已化為skolem標(biāo)準(zhǔn)形。第36頁/共47頁將合式公式WFF（wellformed

定義2-15

不含有任何連結(jié)詞的謂詞公式稱為原子公式，簡稱原子。原子和原子的否定統(tǒng)稱文字。例如，P(x),～Q(?y,z),R(u,v,w)都是原子公式。

定義2-16

子句是由文字組成的析取式。例如，P(x)∨Q(?y,z),

～P(x)∨R(u,v,w)∨Q(?y,z)都是子句。第37頁/共47頁定義2-15不含有任何連結(jié)詞的謂詞

定義2-17

不含任何文字的子句稱為空子句，記為NIL。由于空子句不含任何文字，它不能被任何解釋所滿足，所以空子句是永假的、不可滿足的。定義2-18

子句集即由子句構(gòu)成的集合。注意，可通過重新命名的方法，使子句集里各個(gè)子句間無同名變量。第38頁/共47頁定義2-17不含任何文字的子句稱為空子

將合式公式化成子句集的方法是：首先通過上面所列的步驟(a)～(g)把公式化成skolem標(biāo)準(zhǔn)形，接著進(jìn)行如下處理:

（h）消去skolem標(biāo)準(zhǔn)形中的∧符號，寫成集合的形式，各子句間用逗號分隔。（i）重命名子句中的變量，使得一個(gè)變量名只出現(xiàn)在一個(gè)子句中。比如：

P(x)∨Q(x)∨L(x,y)

～P(x)∨Q(y)

～Q(z)∨L(z,y)

可被重命名為

P(x1)∨

Q(x1)∨L(x1,y1)

～P(x2)∨Q(y2)

～Q(z)∨L(z,y3)第39頁/共47頁將合式公式化成子句集的方法是：首先通過上面所

例2-3

把公式

G?=?(x)((y)P(x,y)→～(y)(Q(x,y)→R(x,y)))化成子句集的形式。解：①消去條件符號→：

(x)(～(y)P(x,y)∨～(y)(～Q(x,y)∨R(x,y)))②否定符內(nèi)移：

(x)((y)～P(x,y)∨(y)(Q(x,y)∧～R(x,y)))③約束變量標(biāo)準(zhǔn)化，使每個(gè)量詞的約束變量唯一：

(x)((y)～P(x,y)∨(z)(Q(x,z)∧～R(x,z)))④把存在量詞skolem化：因(y)、(z)都在(x)的轄域內(nèi)，故y和z都是x的函數(shù)。即(x)(～P(x,f(x))∨(Q(x,g(x))∧～R(x,g(x)))第40頁/共47頁例2-3把公式第40頁/共47頁⑤把母式化成合取范式：

(x)((～P(x,f(x))∨Q(x,g(x)))∧(～P(x,f(x))∨R(x,g(x))))⑥去掉全稱量詞：

(～P(x,f(x))∨Q(x,g(x)))∧(～P(x,f(x))∨R(x,g(x)))⑦去掉∧符號，寫成子句集合形式：

S={～P(x,f(x))∨Q(x,g(x)),～P(x,f(x))∨R(x,g(x))}

或?qū)懗蔁o括號的子句形式：～P(x,f(x))∨Q(x,g(x))

～P(x,f(x))∨R(x,g(x))⑧重命名，使各子句中變量不同名：～P(x,f(x))∨Q(x,g(x))

～P(y,f(y))∨～R(y,g(y))

這種形式才是定理證明需要的標(biāo)準(zhǔn)形式。第41頁/共47頁⑤把母式化成合取范式：第41頁/共47頁

定理2-3