人工智能的數(shù)學(xué)基礎(chǔ)

李凌均鄭州大學(xué)振動工程研究所九月23第二章人工智能的數(shù)學(xué)基礎(chǔ)第二章人工智能的數(shù)學(xué)基礎(chǔ)人工智能的數(shù)學(xué)基礎(chǔ)有：邏輯學(xué)、概率論、模糊理論。邏輯經(jīng)典命題邏輯一階謂詞邏輯2.1命題邏輯與謂詞邏輯2.2多值邏輯2.3概率論2.4模糊理論非經(jīng)典邏輯多值邏輯、模糊邏輯模態(tài)邏輯、時態(tài)邏輯具有真假意義本章內(nèi)容：鄭州大學(xué)振動工程研究所電話0371678817922.2.1.命題一個具有真假意義的陳述句，稱為命題。命題通常用大寫的英文字母P，Q，R等來表示,命題是具有或真或假的含義的。如果一個命題的真值為真則用T(或1)表示，若為假則用F(或0)表示下面的例子均是命題：(1)鄭州大學(xué)是一所綜合性大學(xué)。（T）(2)2+2=5（F）。(3)今天是個好天氣。（T）(4)每一個奇數(shù)都是素數(shù)。（F）2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792下面的例子都不是命題：(1)現(xiàn)在是幾點鐘？(疑問句）(2)x-y>2（其真假值隨x、y的變化而變化，不能確定。）(3)我在說假話。（悖論，真作假時假亦真，假作真時真亦假）(4)請安靜?。ㄆ硎咕洌?.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792命題邏輯的局限性：

在命題邏輯中我們研究的最小單位是句子,即命題，它無法把所要描述的客觀事物的結(jié)構(gòu)及邏輯關(guān)系反映出來。也無法把不同對象的共同特征表述出來。很多問題僅用命題邏輯是解決不了的、表達(dá)不清的。由此發(fā)展了謂詞邏輯。2.1.2.謂詞：在謂詞邏輯中引入謂詞來表示命題。一個謂詞分為謂詞名和個體2部分，謂詞用于描述個體的性質(zhì)、狀態(tài)或個體之間的關(guān)系。個體就是要被描述的某個獨立存在的事物或某個抽象的概念。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792例1：張華是大學(xué)生。其中“張華”是個體，“是大學(xué)生”是謂語。于是我們可引入一個謂詞S（x)來表示x是大學(xué)生，張華代以x就表示張華是大學(xué)生。S（x)涉及到一個變元，稱為一元謂詞，一元謂詞表示個體的屬性。例2：張華比李玲高。其中“張華”和“李玲”是個體，“…比…高”是謂詞，因為涉及到兩個個體，所以我們可以用一個二元謂詞G（x,y)表示x高于y,將張華代以x,李玲代以y,則表示張華比李玲高。若用李玲代以x,張華代以y,則表示李玲高于張華。也就是說謂詞中客體變元的順序一經(jīng)定義就不能隨意改變了。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792有多個變元的謂詞稱為多元謂詞，多元謂詞表示多個客體之間的關(guān)系。謂詞中的個體可以是常量，也可以是變元或函數(shù)。謂詞的語義是由使用者定義的，一旦被定義意義就明確。當(dāng)謂詞中的變元全部用特定的個體取代時，謂詞就有了確定的真值TorF。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792連接詞象在整數(shù)或?qū)崝?shù)集合上可以進(jìn)行+，-，*，/運(yùn)算一樣，在命題集合上也可以進(jìn)行運(yùn)算，形成新的命題。常用的命題運(yùn)算符亦稱為連接詞有:?：非

：合取(與)，

：析取(或)，

：條件或蘊(yùn)涵，

：雙條件(當(dāng)且僅當(dāng))2.1命題邏輯與謂詞邏輯2.1.3.謂詞公式：鄭州大學(xué)振動工程研究所電話037167881792邏輯連接詞非“?”：如果P是一個命題，那麼?P是一個命題，它的真值是這樣定義的：P真(1)，?P假；P假(0)，?P真?？梢杂萌缦碌囊粋€所謂真值表來表示：這里應(yīng)該注意的是?P是對整個命題P的否定，而不是對命題P的部分成分否定。?是一個一元邏輯連接詞。2.1命題邏輯與謂詞邏輯P?P0110鄭州大學(xué)振動工程研究所電話037167881792邏輯連接詞合取“”：如果P是一個命題，Q是一個命題，那麼P

Q是一個命題，它的真值是這樣定義的：當(dāng)且僅當(dāng)P和Q同時為真時，P

Q的值為真，其余情況均為假。2.1命題邏輯與謂詞邏輯PQP

Q000010100111其真值表如右：“”是一個二元邏輯連接詞。這是一個復(fù)合命題，可以讀作合取或“和”、“and”。鄭州大學(xué)振動工程研究所電話037167881792例如令P：曹老師是教授。

Q：王曉離散數(shù)學(xué)不及格。則P

Q：曹老師是教授并且王曉離散數(shù)學(xué)不及格注意這兩件事在日常生活中可能是毫不相干的事情，但在命題邏輯中是有意義的，即P和Q的真值定下來，P

Q的真值就可求。再例如令P：今天是晴天。

Q：歡歡是大熊貓。于是P

Q：今天是晴天并且歡歡是大熊貓。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792邏輯連接詞析取“”:如果P是一個命題，Q是一個命題，那麼P

Q是一個命題，并且它的真值是這樣定義的：當(dāng)且僅當(dāng)P和Q同時為假的時候P

Q的值才為假，否則其值為真。其真值表如下：2.1命題邏輯與謂詞邏輯PQP

Q000011101111“”可以讀作析取也可以讀作“或”、“or”

，它是個二元邏輯連接詞。但它僅代表日常生活中的可兼容或，不代表排斥或。鄭州大學(xué)振動工程研究所電話037167881792例如令P：今天下午3點我去講課。

Q：今天下午3點我去游泳。日常生活中可能會說，今天下午3點我去講課或今天下午3點我去游泳。這里的或是一種排斥或(也稱異或），不能使用邏輯連接詞“”來表示，也就是說不能用P

Q：來表示今天下午3點我去講課或今天下午3點我去游泳。但下面的例子可以用析取來表示。P：李明在教室。Q：王鵬去公園。于是P

Q表示：李明在教室或王鵬去公園。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792邏輯連接詞單條件“”：如果P是一個命題，Q是一個命題，那麼P

Q是一個命題，表示P蘊(yùn)涵Q，即：如果P，則Q。P成為條件的前件，Q成為條件的后件。它的真值是這樣定義的：PQP

Q001011100111當(dāng)且僅當(dāng)前件為真后件為假的時候，P

Q的值才為假，其余情況均為真。其真值表如右：

2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792例如令P：今天有雨。Q：我?guī)в陚?。于是P

Q：如果今天有雨，那麼我?guī)в陚?。如果我們指定P為真代表今天有雨，那麼P為假表示今天沒有雨，指定Q真為我?guī)в陚?，那麼我沒帶雨傘為Q假?，F(xiàn)在我們來分析上面真值表的各種情況：1、P=0，Q=0即今天沒雨，我沒帶雨傘。P

Q=1即成功。2、P=0，Q=1即今天沒雨，我?guī)в陚?。P

Q=1也成功（帶雨傘也沒錯）2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話0371678817923、P=1，Q=0,P

Q=0即今天有雨，我沒帶雨傘，挨淋，失敗。4、P=1，Q=1,P

Q=1即今天有雨，我?guī)в陚?。成功。由上面的例子可以看出?/p>

P

Q真值的規(guī)定是符合常規(guī)邏輯的。再看一個例子令P：學(xué)生不聽話。（并指派為真）Q：老師管教學(xué)生。（并指派為真）于是P=0，Q=0，P

Q：如果學(xué)生聽話，那麼老師不管教學(xué)生，2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792沒毛病，所以P

Q=1。P=0，Q=1，P

Q：如果學(xué)生聽話，那麼老師管教學(xué)生。也沒毛病，P

Q=1；P=1，Q=0，P

Q：如果學(xué)生不聽話，那麼老師不管教學(xué)生。失敗，所以P

Q=0；最后一種情況：P=1，Q=1，P

Q：如果學(xué)生不聽話，那麼老師管教學(xué)生。沒毛病P

Q=1。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792邏輯連接詞雙條件“”：如果P是一個命題，Q是一個命題，那麼P

Q是一個命題，它的真值是這樣定義的：2.1命題邏輯與謂詞邏輯PQP

Q001010100111當(dāng)且僅當(dāng)P和Q同號時P

Q的值為真，否則為假。其真值表如下：鄭州大學(xué)振動工程研究所電話037167881792Q：老師管教學(xué)生。于是P

Q表示老師管教學(xué)生當(dāng)且僅當(dāng)學(xué)生不聽話。單條件和雙條件邏輯連接詞均是二元邏輯連接詞。只要P，Q的真值定下來，P當(dāng)且僅當(dāng)Q的值就可以定下來。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792邏輯連接詞異或“

”：如果P是一個命題，Q是一個命題，那麼P

Q是一個命題，并且它的真值是這樣定義的，當(dāng)且僅當(dāng)P和Q同號時，P

Q的值為假否則為真。由定義我們可以看出，異或和邏輯連接詞雙條件“”有如下的關(guān)系：P

Q?（P

Q）2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792量詞2.1命題邏輯與謂詞邏輯在把實際問題符號化的過程中，我們會遇到那樣的短語：1、所有的…;任何一個…;每一個…——allof……2、有一個…;有一些…;存在一個…——someof……我們使用量詞進(jìn)行符號化，謂詞邏輯中引入兩個量詞來表達(dá)全稱量詞（用來表示）——表示所有（或任一個……）存在量詞（用來表示）——表示存在（有某個……）鄭州大學(xué)振動工程研究所電話037167881792例：用謂詞邏輯符號化下列命題：所有的整數(shù)都是有理數(shù)；有些整數(shù)是素數(shù)；定義謂詞：I(x):x是整數(shù)

Q(x):x是有理數(shù)

S(x):x是素數(shù)于是上述命題可符號化為：（x)(I(x)Q(x));(x)(I(x)

S(x)).2.1命題邏輯與謂詞邏輯鄭州大學(xué)振動工程研究所電話037167881792謂詞公式（把實際問題符號化，公式化）命題演算的公式稱為合式公式，又稱命題公式，合式公式可按下列規(guī)則生成：(1)單個謂詞是合式公式，稱為原子謂詞公式。(2)如果A是合式公式，則?A是合式公式。(3)如果A和B是合式公式，那麼AB，AB，AB，AB是合式公式。(4)當(dāng)且僅當(dāng)有限次使用(1)、(2)、(3)條規(guī)則、由圓括號、邏輯連接詞所組成的有意義的字符串是合式公式。(5)若A是合式公式，x是個體變元。則(x)A和(x)A也是合式公式。2.1.4.謂詞公式及謂詞公式的解釋鄭州大學(xué)振動工程研究所電話037167881792根據(jù)上面的定義可以看出下面的字符串均是合式公式：P，?P，P

Q，?P（PQ），?P（PQ）R，（P

Q）

?（?P

?Q）。而下面的字符串則不是合式公式：?P，R，?P

，（PQ））邏輯連接詞的運(yùn)算優(yōu)先級為：?、

、、、,括號優(yōu)先。把一個實際問題符號化為一個命題公式的步驟如下：1.確定給定的句子是否為命題。2.找出各原子命題并確定句子中的連詞對應(yīng)的邏輯連結(jié)詞。3.用正確的語法把原命題表示成由原子命題、連結(jié)詞和圓括號組成的合式公式。2.1.4.謂詞公式及謂詞公式的解釋鄭州大學(xué)振動工程研究所電話037167881792例1：符號化下列命題：他既聰明又用功。他雖聰明但不用功。解：令P：他聰明Q：他用功于是PQ：表示他既聰明又用功。

P

?Q：表示他雖聰明但不用功。例2：符號化下列命題：老驥自知夕陽晚，無須揚(yáng)鞭自奮蹄。解：令P：老驥自知夕陽晚Q：無須揚(yáng)鞭自奮蹄P

Q：老驥自知夕陽晚，無須揚(yáng)鞭自奮蹄。2.1.4.謂詞公式及謂詞公式的解釋鄭州大學(xué)振動工程研究所電話037167881792謂詞公式的解釋：在命題邏輯中，對命題公式中各個命題變元的一次真值指派稱為命題公式的一個解釋。不同的變元真值賦值得到不同的命題公式解釋，一個解釋對應(yīng)一個命題公式的真值?？聪旅娴睦印?.1.4.謂詞公式及謂詞公式的解釋鄭州大學(xué)振動工程研究所電話037167881792設(shè)個體域D＝{1,2},求公式A＝(

x)(y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。指派一組真值：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,這是其中的一個解釋，在此解釋下，x=1和x=2時分別有P(1,1)和P(2,1)=T，即對于個體域中的所有x都有y使得P(x,y)=T,所以在這種解釋下公式A的值為T。還可以指派另外一組真值：P(1,1)=T,P(1,2)=T,P(2,1)=F,P(2,2)=F,這時公式A的值為F.這樣的真值指派共有16種2.1.4.謂詞公式及謂詞公式的解釋鄭州大學(xué)振動工程研究所電話037167881792定義：設(shè)A、B是兩個命題公式，P1，P2，，Pn

是出現(xiàn)在A和B中的所有命題變元。如果對于P1，P2，，Pn的2n

個真值指派的每一組，公式A和B的真值相同，則稱A和B等價。記作AB。顯然，要判斷兩個命題公式是否等價，用真值表法即可以實現(xiàn)。但是當(dāng)命題變元多時這種方法是不方便的。例如兩個公式若含有4個變元，則真值表要列出24行。所以，我們一般不采用這種方法，而是采用等價變換的方法。下面列出的是常用的一組等價變換公式。2.1.4.謂詞公式的等價性鄭州大學(xué)振動工程研究所電話0371678817922.1.4.謂詞公式的等價性常用等價變換公式：1、??PP雙重否定律2、PPP，P

PP等冪律3、（PQ）RP（QR）結(jié)合律

（P

Q）RP（QR）4、PQQP,P

QQ

P交換律5、P（QR）（PQ）（PR）分配律P（QR）（PQ）（PR）6、P（PQ）P吸收律P（PQ）P鄭州大學(xué)振動工程研究所電話0371678817922.1.4.謂詞公式的等價性7、?（PQ）?P?Q德.摩根律

?（PQ）?P?Q8、PQ?PQ，連接詞化歸律

PQ(PQ)(QP)

PQ(PQ)（?P?Q）9、(x)(PQ)(x)P(x)Q量詞分配律

(

x)(PQ)(

x)P(

x)Q10、?(x)P(x)(?P),量詞轉(zhuǎn)換律

?(

x)P(x)(?P),11、P?PT，P?PF補(bǔ)余律鄭州大學(xué)振動工程研究所電話037167881792下面我們給出子公式，及關(guān)于公式等價的一個定理。定義：設(shè)A是一個命題公式，A是A的一部分，且A也是一個命題公式，則稱A是A的子公式。定理：設(shè)A是公式A的子公式，B是一命題公式且AB，將A中的A用B來取代，則所得到的是一個新公式，

記為B，且AB。例1：證明（P(QR))(PQR)P證明：左邊(P(QR))(P(QR))

P((QR)

(QR))

PTP.2.1.4.謂詞公式的等價性鄭州大學(xué)振動工程研究所電話0371678817922.1.5永真式、永假式及蘊(yùn)涵式一個命題公式若含有N個變元，則應(yīng)有2n種組合，所以要證明兩個命題公式的等價，當(dāng)命題變元多時使用真值表法是不現(xiàn)實的，只能采用上面的等價變換的方法。有兩種特殊的命題公式值得一提，即不依賴變元的真值指派總是取值為T的公式(稱為永真式)，不依賴變元的真值指派總是取值為F的公式(稱為永假式)，其余的情況則為可滿足的式子。例如：P

PT,P

PF永真式與永假式取決于公式本身的結(jié)構(gòu)，不依賴變元的真值指派。例如(PQR)(PQR)就是一個永真式(PQR)(PQR)就是一個永假式永真式的性質(zhì)：若公式A是永真式，并且P1，P2，…，Pn是出現(xiàn)于A中的變元，若用公式B代換A中的原子變元Pi(i=1,2,…,n),所得到的公式設(shè)為A’，則A’也是永真式。（注意代換過程從左向右要進(jìn)行到底）。對非永真式，這條性質(zhì)不一定成立。

鄭州大學(xué)振動工程研究所電話037167881792定義：當(dāng)且僅當(dāng)AB是一個永真式時，則稱A蘊(yùn)涵B，記作AB.要證明AB.只要證明A為真時B必為真即可，也可以使用真值表來證明。即證明使A為真的那些組真值指派必然使B取值為真。下面是一些常用的永真蘊(yùn)涵式：1）PQP,PQQ化簡式2）PPQ,QPQ附加式3)PPQ,QPQ4)(PQ)P,(PQ)Q5)P(PQ)Q,Q(PQ)P6)P(PQ)Q7)(PQ)(QR)PR8)(PQ)(PR)(QR)R2.1.5永真式、永假式及蘊(yùn)涵式鄭州大學(xué)振動工程研究所電話037167881792以上永真蘊(yùn)涵公式的證明，均可以從定義出發(fā)：例如證明3）:PPQ,QPQ前件為真時P為假，于是使得PQ必為真，同理：Q為真時使得PQ必為真。再如證明5）:P(PQ)Q,Q(PQ)P

P和(PQ)同時為真時，保證了Q必為真。同理，Q為真，Q就為假，PQ又為真，P就得為假，于是保證了P為真。2.1.5永真式、永假式及蘊(yùn)涵式鄭州大學(xué)振動工程研究所電話037167881792等價式與永真蘊(yùn)涵式之間的聯(lián)系：設(shè)P，Q是命題公式，PQ的充分必要條件是：PQ且QP。永真蘊(yùn)涵具有傳遞性：即PQ且QR則PR。同理等價關(guān)系也具有傳遞性：PQ且QR則有PR。定義1.4-2假設(shè)H1,…,Hm,Q是命題公式。如果（H1

…

Hm）Q，則稱H1,…,Hm共同蘊(yùn)涵Q，并記作H1,…,HmQ定理：如果H1

…

Hm

PQ，則H1,…,HmPQ定理是顯然的：H1

…

Hm

P為真，保證了P為真，H1

…

Hm

PQ，保證了Q為真，于是有P

Q為真，得證。2.1.5永真式、永假式及蘊(yùn)涵式鄭州大學(xué)振動工程研究所電話0371678817922.2多值邏輯經(jīng)典的命題邏輯和謂詞邏輯的語義解釋只有2個真值：TorF，而在現(xiàn)實世界中，并非都是非真即假的情況，真真假假，有真有假的情況時常存在，所以，它們不能完全描述客觀世界的真實情況，在經(jīng)典邏輯的基礎(chǔ)上提出了多值邏輯。用T(A)表示命題A為真的程度。T(A)的取值介于0(假)與1(真)之間：0≤T(A)≤1多值邏輯的運(yùn)算：T(A)=1-T(A)T(AB)=min{T(A),T(B)}T(AB)=max

{T(A),T(B)}T(AB)=min{1,1-T(A)+T(B)}T(A

B)=1-|T(A)-T(B)|鄭州大學(xué)振動工程研究所電話0371678817922.2多值邏輯三值邏輯是多值邏輯的一個特例，有關(guān)真值表在書上有解釋,書中表2-2所示。三值邏輯的真值：除了“真”、“假”外，還存在另一個真值，第三個真值根據(jù)具體含義有不同的意義：不能判斷其真假：但真假必選其一，非真即假。不確定：不真也不假，無法確定其真值，或者就不存在真值。無意義：非真非假鄭州大學(xué)振動工程研究所電話037167881792在三值邏輯中，對于命題P和Q，由連接詞“與”（）、“或”（）、“非”（

）、“蘊(yùn)涵”（→）和“等價”（?）所構(gòu)成的復(fù)合命題與二值邏輯中復(fù)合命題的定義完全相同，所不同的僅僅是命題P和Q及其復(fù)合命題的真假值域由原來的二值{0，1}變?yōu)槿祘0，1/2，1}。于是復(fù)合命題的真假值可由下表給出。2.2多值邏輯鄭州大學(xué)振動工程研究所電話0371678817922.2多值邏輯三值邏輯運(yùn)算PQ

P

QPQPQP→QP?Q1100111111/201/21/211/21/2100101001/211/201/2111/21/21/21/21/21/21/2111/201/2101/21/21/20110011001/211/201/211/200110011鄭州大學(xué)振動工程研究所電話0371678817922.2多值邏輯根據(jù)上表，我們不難得到（