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

李凌均鄭州大學(xué)振開工程研討所六月22第二章人工智能的數(shù)學(xué)根底第二章人工智能的數(shù)學(xué)根底人工智能的數(shù)學(xué)根底有：邏輯學(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等來表示,命題是具有或真或假的含義的。假設(shè)一個命題的真值為真那么用T(或1)表示，假設(shè)為假那么用F(或0)表示下面的例子均是命題：(1)鄭州大學(xué)是一所綜合性大學(xué)?！睺〕(2)2+2=5〔F〕。(3)今天是個好天氣?！睺〕(4)每一個奇數(shù)都是素數(shù)?！睩〕2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792下面的例子都不是命題：(1)如今是幾點(diǎn)鐘？(疑問句〕(2)x-y>2〔其真假值隨x、y的變化而變化，不能確定。〕(3)我在說假話?！层Ｕ?，真作假時假亦真，假作真時真亦假〕(4)請安靜！〔祈使句〕2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792命題邏輯的局限性：在命題邏輯中我們研討的最小單位是句子,即命題，它無法把所要描畫的客觀事物的構(gòu)造及邏輯關(guān)系反映出來。也無法把不同對象的共同特征表述出來。很多問題僅用命題邏輯是處理不了的、表達(dá)不清的。由此開展了謂詞邏輯。2.1.2.謂詞：在謂詞邏輯中引入謂詞來表示命題。一個謂詞分為謂詞名和個體2部分，謂詞用于描畫個體的性質(zhì)、形狀或個體之間的關(guān)系。個體就是要被描畫的某個獨(dú)立存在的事物或某個籠統(tǒng)的概念。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792例1：張華是大學(xué)生。其中“張華〞是個體，“是大學(xué)生〞是謂語。于是我們可引入一個謂詞S〔x)來表示x是大學(xué)生，張華代以x就表示張華是大學(xué)生。S〔x)涉及到一個變元，稱為一元謂詞，一元謂詞表示個體的屬性。例2：張華比李玲高。其中“張華〞和“李玲〞是個體，“…比…高〞是謂詞，由于涉及到兩個個體，所以我們可以用一個二元謂詞G〔x,y)表示x高于y,將張華代以x,李玲代以y,那么表示張華比李玲高。假設(shè)用李玲代以x,張華代以y,那么表示李玲高于張華。也就是說謂詞中客體變元的順序一經(jīng)定義就不能隨意改動了。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792有多個變元的謂詞稱為多元謂詞，多元謂詞表示多個客體之間的關(guān)系。謂詞中的個體可以是常量，也可以是變元或函數(shù)。謂詞的語義是由運(yùn)用者定義的，一旦被定義意義就明確。當(dāng)謂詞中的變元全部用特定的個體取代時，謂詞就有了確定的真值TorF。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792銜接詞象在整數(shù)或?qū)崝?shù)集合上可以進(jìn)展+，-，*，/運(yùn)算一樣，在命題集合上也可以進(jìn)展運(yùn)算，構(gòu)成新的命題。常用的命題運(yùn)算符亦稱為銜接詞有:?：非 ：合取(與)， ：析取(或)， ：條件或蘊(yùn)涵， ：雙條件(當(dāng)且僅當(dāng))2.1命題邏輯與謂詞邏輯2.1.3.謂詞公式：鄭州大學(xué)振開工程研討所037167881792邏輯銜接詞非“?〞：假設(shè)P是一個命題，那麼?P是一個命題，它的真值是這樣定義的：P真(1)，?P假；P假(0)，?P真?？梢杂萌缦碌囊粋€所謂真值表來表示：這里應(yīng)該留意的是?P是對整個命題P的否認(rèn)，而不是對命題P的部分成分否認(rèn)。?是一個一元邏輯銜接詞。2.1命題邏輯與謂詞邏輯P?P0110鄭州大學(xué)振開工程研討所037167881792邏輯銜接詞合取“〞：假設(shè)P是一個命題，Q是一個命題，那麼PQ是一個命題，它的真值是這樣定義的：當(dāng)且僅當(dāng)P和Q同時為真時，PQ的值為真，其他情況均為假。2.1命題邏輯與謂詞邏輯PQP

Q000010100111其真值表如右：“〞是一個二元邏輯銜接詞。這是一個復(fù)合命題，可以讀作合取或“和〞、“and〞。鄭州大學(xué)振開工程研討所037167881792例如令P：曹教師是教授。Q：王曉離散數(shù)學(xué)不及格。那么PQ：曹教師是教授并且王曉離散數(shù)學(xué)不及格留意這兩件事在日常生活中能夠是毫不相關(guān)的事情，但在命題邏輯中是有意義的，即P和Q的真值定下來，PQ的真值就可求。再例如令P：今天是晴天。Q：歡歡是大熊貓。于是PQ：今天是晴天并且歡歡是大熊貓。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792邏輯銜接詞析取“〞:假設(shè)P是一個命題，Q是一個命題，那麼PQ是一個命題，并且它的真值是這樣定義的：當(dāng)且僅當(dāng)P和Q同時為假的時候PQ的值才為假，否那么其值為真。其真值表如下：2.1命題邏輯與謂詞邏輯PQP

Q000011101111“〞可以讀作析取也可以讀作“或〞、“or〞，它是個二元邏輯銜接詞。但它僅代表日常生活中的可兼容或，不代表排斥或。鄭州大學(xué)振開工程研討所037167881792例如令P：今天下午3點(diǎn)我去講課。Q：今天下午3點(diǎn)我去游泳。日常生活中能夠會說，今天下午3點(diǎn)我去講課或今天下午3點(diǎn)我去游泳。這里的或是一種排斥或(也稱異或〕，不能運(yùn)用邏輯銜接詞“〞來表示，也就是說不能用PQ：來表示今天下午3點(diǎn)我去講課或今天下午3點(diǎn)我去游泳。但下面的例子可以用析取來表示。P：李明在教室。Q：王鵬去公園。于是PQ表示：李明在教室或王鵬去公園。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792邏輯銜接詞單條件“〞：假設(shè)P是一個命題，Q是一個命題，那麼PQ是一個命題，表示P蘊(yùn)涵Q，即：假設(shè)P，那么Q。P成為條件的前件，Q成為條件的后件。它的真值是這樣定義的：PQP

Q001011100111當(dāng)且僅當(dāng)前件為真后件為假的時候，PQ的值才為假，其他情況均為真。其真值表如右：2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792例如令P：今天有雨。Q：我?guī)в陚恪Ｓ谑荘Q：假設(shè)今天有雨，那麼我?guī)в陚恪＜僭O(shè)我們指定P為真代表今天有雨，那麼P為假表示今天沒有雨，指定Q真為我?guī)в陚?，那麼我沒帶雨傘為Q假。如今我們來分析上面真值表的各種情況：1、P=0，Q=0即今天沒雨，我沒帶雨傘。PQ=1即勝利。2、P=0，Q=1即今天沒雨，我?guī)в陚?。PQ=1也勝利〔帶雨傘也沒錯〕2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所0371678817923、P=1，Q=0,PQ=0即今天有雨，我沒帶雨傘，挨淋，失敗。4、P=1，Q=1,PQ=1即今天有雨，我?guī)в陚?。勝利。由上面的例子可以看出，PQ真值的規(guī)定是符合常規(guī)邏輯的。再看一個例子令P：學(xué)生不聽話?！膊⒅概蔀檎妗砆：教師管教學(xué)生?！膊⒅概蔀檎妗秤谑荘=0，Q=0，PQ：假設(shè)學(xué)生聽話，那麼教師不論教學(xué)生，2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792沒缺陷，所以PQ=1。P=0，Q=1，PQ：假設(shè)學(xué)生聽話，那麼教師管教學(xué)生。也沒缺陷，PQ=1；P=1，Q=0，PQ：假設(shè)學(xué)生不聽話，那麼教師不論教學(xué)生。失敗，所以PQ=0；最后一種情況：P=1，Q=1，PQ：假設(shè)學(xué)生不聽話，那麼教師管教學(xué)生。沒缺陷PQ=1。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792邏輯銜接詞雙條件“〞：假設(shè)P是一個命題，Q是一個命題，那麼PQ是一個命題，它的真值是這樣定義的：2.1命題邏輯與謂詞邏輯PQP

Q001010100111當(dāng)且僅當(dāng)P和Q同號時PQ的值為真，否那么為假。其真值表如下：鄭州大學(xué)振開工程研討所037167881792Q：教師管教學(xué)生。于是PQ表示教師管教學(xué)生當(dāng)且僅當(dāng)學(xué)生不聽話。單條件和雙條件邏輯銜接詞均是二元邏輯銜接詞。只需P，Q的真值定下來，P當(dāng)且僅當(dāng)Q的值就可以定下來。2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792邏輯銜接詞異或“〞：假設(shè)P是一個命題，Q是一個命題，那麼PQ是一個命題，并且它的真值是這樣定義的，當(dāng)且僅當(dāng)P和Q同號時，PQ的值為假否那么為真。由定義我們可以看出，異或和邏輯銜接詞雙條件“〞有如下的關(guān)系：PQ?〔PQ〕2.1命題邏輯與謂詞邏輯鄭州大學(xué)振開工程研討所037167881792量詞2.1命題邏輯與謂詞邏輯在把實踐問題符號化的過程中，我們會遇到那樣的短語：1、一切的…;任何一個…;每一個…——allof……2、有一個…;有一些…;存在一個…——someof……我們運(yùn)用量詞進(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)假設(shè)A是合式公式，那么?A是合式公式。(3)假設(shè)A和B是合式公式，那麼AB，AB，AB，AB是合式公式。(4)當(dāng)且僅當(dāng)有限次運(yùn)用(1)、(2)、(3)條規(guī)那么、由圓括號、邏輯銜接詞所組成的有意義的字符串是合式公式。(5)假設(shè)A是合式公式，x是個體變元。那么(x)A和(x)A也是合式公式。2.1.4.謂詞公式及謂詞公式的解釋鄭州大學(xué)振開工程研討所037167881792根據(jù)上面的定義可以看出下面的字符串均是合式公式：P，?P，PQ，?P〔PQ〕，?P〔PQ〕R，〔PQ〕?〔?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)鞭自奮蹄PQ：老驥自知夕陽晚，無須揚(yáng)鞭自奮蹄。2.1.4.謂詞公式及謂詞公式的解釋鄭州大學(xué)振開工程研討所037167881792謂詞公式的解釋：在命題邏輯中，對命題公式中各個命題變元的一次真值指派稱為命題公式的一個解釋。不同的變元真值賦值得到不同的命題公式解釋，一個解釋對應(yīng)一個命題公式的真值?？聪旅娴睦?。2.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是出如今A和B中的一切命題變元。假設(shè)對于P1，P2，，Pn的2n個真值指派的每一組，公式A和B的真值一樣，那么稱A和B等價。記作AB。顯然，要判別兩個命題公式能否等價，用真值表法即可以實現(xiàn)。但是當(dāng)命題變元多時這種方法是不方便的。例如兩個公式假設(shè)含有4個變元，那么真值表要列出24行。所以，我們普通不采用這種方法，而是采用等價變換的方法。下面列出的是常用的一組等價變換公式。2.1.4.謂詞公式的等價性鄭州大學(xué)振開工程研討所0371678817922.1.4.謂詞公式的等價性常用等價變換公式：1、??PP雙重否認(rèn)律2、PPP，PPP等冪律3、〔PQ〕RP〔QR〕結(jié)合律〔PQ〕RP〔QR〕4、PQQP,PQQP交換律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)涵式一個命題公式假設(shè)含有N個變元，那么應(yīng)有2n種組合，所以要證明兩個命題公式的等價，當(dāng)命題變元多時運(yùn)用真值表法是不現(xiàn)實的，只能采用上面的等價變換的方法。有兩種特殊的命題公式值得一提，即不依賴變元的真值指派總是取值為T的公式(稱為永真式)，不依賴變元的真值指派總是取值為F的公式(稱為永假式)，其他的情況那么為可滿足的式子。例如：PPT,PPF永真式與永假式取決于公式本身的構(gòu)造，不依賴變元的真值指派。例如(PQR)(PQR)就是一個永真式(PQR)(PQR)就是一個永假式永真式的性質(zhì)：假設(shè)公式A是永真式，并且P1，P2，…，Pn是出現(xiàn)于A中的變元，假設(shè)用公式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必為真即可，也可以運(yùn)用真值表來證明。即證明使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)PP和(PQ)同時為真時，保證了Q必為真。同理，Q為真，Q就為假，PQ又為真，P就得為假，于是保證了P為真。2.1.5永真式、永假式及蘊(yùn)涵式鄭州大學(xué)振開工程研討所037167881792等價式與永真蘊(yùn)涵式之間的聯(lián)絡(luò)：設(shè)P，Q是命題公式，PQ的充分必要條件是：PQ且QP。永真蘊(yùn)涵具有傳送性：即PQ且QR那么PR。同理等價關(guān)系也具有傳送性：PQ且QR那么有PR。定義1.4-2假設(shè)H1,…,Hm,Q是命題公式。假設(shè)〔H1…Hm〕Q，那么稱H1,…,Hm共同蘊(yùn)涵Q，并記作H1,…,HmQ定理：假設(shè)H1…HmPQ，那么H1,…,HmPQ定理是顯然的：H1…HmP為真，保證了P為真，H1…HmPQ，保證了Q為真，于是有PQ為真，得證。2.1.5永真式、永假式及蘊(yùn)涵式鄭州大學(xué)振開工程研討所0371678817922.2多值邏輯經(jīng)典的命題邏輯和謂詞邏輯的語義解釋只需2個真值：TorF，而在現(xiàn)實世界中，并非都是非真即假的情況，真真假假，有真有假的情況時常存在，所以，它們不能完全描畫客觀世界的真實情況，在經(jīng)典邏輯的根底上提出了多值邏輯。用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(AB)=1-|T(A)-T(B)|鄭州大學(xué)振開工程研討所0371678817922.2多值邏輯三值邏輯是多值邏輯的一個特例，有關(guān)真值表在書上有解釋,書中表2-2所示。三值邏輯的真值：除了“真〞、“假〞外，還存在另一個真值，第三個真值根據(jù)詳細(xì)含義有不同的意義：不能判別其真假：但真假必選其一，非真即假。不確定：不真也不假，無法確定其真值，或者就不存在真值。無意義：非真非假鄭州大學(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)算PQPQPQPQP→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ù)上表，我們不難得到〔P→Q〕→