1、第1篇數(shù)理邏輯主講人：任長(zhǎng)安計(jì)算機(jī)與信息科學(xué)系2009.07,引言,邏輯學(xué)是研究推理過程之規(guī)律的科學(xué)。數(shù)理邏輯則是用數(shù)學(xué)的方法研究思維規(guī)律的一門學(xué)科。由于它使用了一套符號(hào)，簡(jiǎn)潔的表達(dá)出各種推理的邏輯關(guān)系，因此數(shù)理邏輯又稱為符號(hào)邏輯或理論邏輯。數(shù)理邏輯和計(jì)算機(jī)的發(fā)展有著密切的聯(lián)系，它為機(jī)器證明、自動(dòng)程序設(shè)計(jì)、計(jì)算機(jī)輔助設(shè)計(jì)等計(jì)算機(jī)應(yīng)用和理論研究提供必要的理論基礎(chǔ)。,主要內(nèi)容,1命題邏輯2一階邏輯,第1章命題邏輯,主要內(nèi)容：1.1命題與聯(lián)結(jié)詞1.2命題公式及其分類1.3真值表與真值函數(shù)1.4等值式與等值演算1.5聯(lián)結(jié)詞完備集1.6范式1.7命題邏輯的推理理論,1.1命題與聯(lián)結(jié)詞,一、命題1定義能判

2、斷真假的陳述句稱為命題。當(dāng)判斷正確或符合客觀實(shí)際時(shí)，稱該命題真（true），否則稱該命題假（false）。“真、假”常被稱為命題的真值，分別記為T(1)和F(0)。顯然，判斷一個(gè)語(yǔ)句是否為命題，有兩個(gè)要點(diǎn)：1）命題是一個(gè)陳述句，而命令句、疑問句和感嘆句都不是命題。2）這個(gè)陳述句所表達(dá)的內(nèi)容可決定是真還是假，而且不是真的就是假的，不能不真又不假，也不能又真又假。,1.1命題與聯(lián)結(jié)詞,例1.1判斷下列語(yǔ)句是否為命題。（1）雪是白的。（2）2是偶數(shù)且3也是偶數(shù)。（3）陳勝吳廣起義那天杭州下雨。（4）大于2的偶數(shù)均可分解為兩個(gè)質(zhì)數(shù)的和（哥德巴赫猜想）。（5）真舒服?。。?）別的星球上有生物存在。（7）

3、您去學(xué)校嗎？（8）x+y1,pq:今天上課有人遲到且2+51；,1.1命題與聯(lián)結(jié)詞,3析取式和析取聯(lián)結(jié)詞p或者q稱為p，q的析取式，記為pq；符號(hào)即為析取聯(lián)結(jié)詞。例：(1)文文或華華今天出差。(2)他今天騎車或走路來(lái)上課。(3)從理科2號(hào)樓到圖書館要3分鐘或5分鐘。,相容或（析?。┫喑饣颍ó惢颍┐蠹s,1.1命題與聯(lián)結(jié)詞,4）異或式和異或聯(lián)結(jié)詞p或者q中只能一個(gè)為真稱為p,q的異或式，記為pq；符號(hào)即為異或聯(lián)結(jié)詞。,1.1命題與聯(lián)結(jié)詞,5蘊(yùn)涵式（或條件式）和蘊(yùn)涵（或條件）聯(lián)結(jié)詞如果p則q稱作p、q的條件式（或蘊(yùn)涵式），記為pq。為蘊(yùn)涵聯(lián)結(jié)詞，p、q分別為蘊(yùn)涵式的前件和后件。示例:一位父親對(duì)兒子說

4、：“如果星期天天氣好，就一定帶你去動(dòng)物園?！眴枺涸谑裁辞闆r下父親食言？父親的可能情況有如下四種：(1)星期天天氣好，帶兒子去了動(dòng)物園；(2)星期天天氣好，卻沒帶兒子去動(dòng)物園；,1.1命題與聯(lián)結(jié)詞,(3)星期天天氣不好，卻帶兒子去了動(dòng)物園；(4)星期天天氣不好，也沒帶兒子去動(dòng)物園。顯然，(1),(4)兩種情況父親都沒有食言；(3)這種情況和父親原來(lái)的話沒有相抵觸的地方，當(dāng)然也不算食言；只有(2)這種情況，答應(yīng)的事卻沒有做，應(yīng)該算是食言了。(2)對(duì)應(yīng)著“前件真后件假”的情況，使得蘊(yùn)涵式為假，而其它三種情況都使得蘊(yùn)涵式為真。所以，條件式的真值情況用表格表示為：（下表所示）,1.1命題與聯(lián)結(jié)詞,這里注

5、意到：在蘊(yùn)涵式pq中，p是q的充分條件，q是p的必要條件。這類的聯(lián)結(jié)詞還有：pq：“只要p就q”，“p僅當(dāng)q”，“只有q才p”等,1.1命題與聯(lián)結(jié)詞,6雙條件式（或等價(jià)式）和雙條件（或等價(jià)）聯(lián)結(jié)詞p當(dāng)且僅當(dāng)q稱作p、q的雙條件式（等價(jià)式），記為pq。稱為雙條件（等價(jià)）聯(lián)結(jié)詞。,1.1命題與聯(lián)結(jié)詞,三、命題符號(hào)化符號(hào)化基本步驟：1)找出各個(gè)支命題，并逐個(gè)符號(hào)化；2)找出各個(gè)連接詞，符號(hào)成相應(yīng)聯(lián)結(jié)詞；3)用聯(lián)結(jié)詞將各支命題逐個(gè)聯(lián)結(jié)起來(lái)；示例：將下列命題符號(hào)化：(1)李明是計(jì)算機(jī)系的學(xué)生，他住在312室或313室(2)辱罵和恐嚇決不是戰(zhàn)斗；(3)李瑞和李珊是姐妹。(4)除非天氣好，否則我是不會(huì)去公園

6、的；,1.1命題與聯(lián)結(jié)詞,分析并符號(hào)化，強(qiáng)調(diào)在進(jìn)行命題符號(hào)化以前，必須明確含義，刪除歧義，這是命題翻譯的關(guān)鍵之點(diǎn)。（1）p：李明是計(jì)算機(jī)系的學(xué)生；q：李明住在312室；r：李明住在313室。因?yàn)槔蠲鞑豢赡芗茸≡?12室又住在313室，所以這里應(yīng)該用，而不用，符號(hào)化為p(qr)。（2）p：辱罵是戰(zhàn)斗；q：恐嚇是戰(zhàn)斗。符號(hào)化為pq。,1.1命題與聯(lián)結(jié)詞,（3）p：李瑞和李珊是姐妹。符號(hào)化為p。（4）p：今天天氣好；q：我去公園。符號(hào)化為qp。,1.2命題公式及其分類,一、合式公式1定義（1）p,q,r,1,0是合式公式；（2）如果A是合式公式，則A也是；（3）如果A和B是合式公式，則由邏輯聯(lián)結(jié)詞聯(lián)

7、結(jié)A和B的符號(hào)串也是；（4）有限次應(yīng)用(1)-(3)構(gòu)成的符號(hào)串才是合式公式。上述定義方法稱為遞歸定義法，遞歸法定義是離散數(shù)學(xué)中常用的方法。,1.2命題公式及其分類,2省略括號(hào)的約定：(1)公式最外層的括號(hào)可以省略；(2)規(guī)定聯(lián)結(jié)詞的運(yùn)算優(yōu)先級(jí)別由高到低是：、，若無(wú)括號(hào)，優(yōu)先級(jí)高的先運(yùn)算；(3)若同一個(gè)聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無(wú)括號(hào)，則按從左到右的順序運(yùn)算合式公式判定示例(1)(pq)(qr)(pr)p、q是公式，(pq)是公式；q、r是公式，(qr)是公式；(pq)(qr)是公式；,1.2命題公式及其分類,p、r是公式，(pr)是公式；(pq)(qr)(pr)是公式。這樣一個(gè)命題公式的形成過程簡(jiǎn)

8、單表述為：p，q，(pq)；q，r，(qr)；(pq)(qr)；p，r，(pr)；(pq)(qr)(pr)。(2)(pq)qr)p，q，(pq)；q，r，qr不是；(pq)qr)不是。顯然，有些公式的字符串很長(zhǎng)，有些很短，甚至只有單個(gè)字母，這樣公式的復(fù)雜性必然有所不同，為了描述這種復(fù)雜性，引入公式層次來(lái)描述。,1.2命題公式及其分類,二合式公式的層次：(1)如果A是單個(gè)命題常項(xiàng)或命題變項(xiàng)p,q,r,s,0,1，則稱A是0層公式；(2)稱A是n+1(n0)層公式，是指A符合下列情況之一：(a)A=B，B是n層公式；(b)A=(BC)，其中B、C分別是i層和j層公式，且n=max(i,j)；(c)

9、A=(BC)，其中B、C的層次同(b)；(d)A=(BC)，其中B、C的層次同(b)；,1.2命題公式及其分類,(e)A=(BC)，其中B、C的層次同(b)；(f)A=(BC)，其中B、C的層次同(b)；(3)若A的最高層次為k，則稱A是k層公式。示例：(1)(pq)(r(ps)(2)q(ps)(1)p,s是0層公式，ps是1層公式;r是0層公式,r(ps)是2層公式；p,q是0層公式，但pq是1層公式；(pq)(r(ps)是3層公式。公式層次是3。(2)q是0層公式,q是1層公式；p,s是0層公式，ps是1層公式;(ps)是2層公式；但q(ps)不是公式。,1.2命題公式及其分類,一般來(lái)說，

10、一個(gè)含有命題變項(xiàng)的命題形式，其真值是不確定的。只有給其每個(gè)命題變項(xiàng)都指定確定的真值，命題形式才會(huì)有確定的真值。給定一個(gè)真值，就是給命題變項(xiàng)一個(gè)賦值，相當(dāng)于給定一個(gè)日常語(yǔ)言中某個(gè)具體的句子，即給定一個(gè)解釋。,1.2命題公式及其分類,三、真值賦值1賦值令A(yù)是命題形式，p1,p2,pn是出現(xiàn)在A中的所有命題變項(xiàng)，給p1,p2,pn指派一組真值，稱為對(duì)A的一個(gè)賦值，也稱為一個(gè)解釋。成真賦值：若一個(gè)賦值使得A的真值為真，此賦值滿足A；成假賦值：若一個(gè)賦值使得A的值為假，此賦值不滿足A，一個(gè)含有n個(gè)命題變項(xiàng)的命題形式，共有2n個(gè)賦值。,1.2命題公式及其分類,例已知A是含命題變項(xiàng)p,q,r的命題形式，其成

11、真賦值為000,010,101，求A的成真賦值和成假賦值。A的成真賦值為：001,011,100,110,111；成假賦值為：000,010,101。例已知A、B是含命題變項(xiàng)p,q,r的命題形式，A成真賦值為000,011,111，B成真賦值為000,010,100，求AB、AB的成真賦值。AB：000,001,010,100,101,110,111AB：000,001,101,110,1.2命題公式及其分類,2替換實(shí)例替換實(shí)例：用命題形式B1,B2,Bn分別替換命題形式A中的命題變項(xiàng)p1,p2,pn得到的新的命題形式。示例：例如，p(pq)，以pq替換p，以r替換q，則得到原式的一個(gè)替換實(shí)例

12、為(pq)(pq)r)。我們知道一個(gè)公式有多個(gè)賦值，一般來(lái)說既有成真賦值，又有成假賦值，但完全可能只有成真賦值，或全是成假賦值，根據(jù)這種不同，我們將公式分成不同類型。,1.2命題公式及其分類,四、公式分類重言式（永真式）：值總是為真的命題形式。矛盾式（永假式）：值總是為假的命題形式?？蓾M足式從定義看來(lái)，重言式也是可滿足式，不過還是將命題形式分成三類：重言式、矛盾式、可滿足式；即可滿足式不包含重言式。這種分類主要是為了體現(xiàn)重言式的重要性，實(shí)際上在命題邏輯中公理、定理都是重言式，在自然推理的過程中，一個(gè)正確的推理也必須是重言式。,1.2命題公式及其分類,設(shè)A命題形式，則(1)若A是重言式，則A的任

13、何替換實(shí)例都是重言式；(2)若A是矛盾式，則A的任何替換實(shí)例都是矛盾式；示例：例合式公式(pq)(pq)、(pqr)(pqr)都是pp的一個(gè)替換實(shí)例，而pp是重言式，所以它們也是重言式。,1.3真值表和真值函數(shù),一、真值表1定義：命題形式在其命題變項(xiàng)取所有可能真值時(shí)對(duì)應(yīng)的真值列成的表。所有命題變項(xiàng)取一組值，即是命題形式的一個(gè)賦值，所以真值表包含了所有賦值情況下的公式所取得的值。而一個(gè)賦值使得公式為真，就稱為成真賦值，為假就是成假賦值，所以從真值表可以直接獲得一個(gè)命題公式的成真賦值、成假賦值。,1.3真值表和真值函數(shù),2構(gòu)成方法：找出給定命題形式中的所有命題變項(xiàng)，列出所有可能的取值;由低到高列出

14、命題形式的各層次；計(jì)算各層次的的值，直至最后計(jì)算命題形式的值。例構(gòu)造合式公式(p(pq)(pq)的真值表：真值表如下表所示：,1.3真值表和真值函數(shù),注意：上述真值表的構(gòu)成方法中，如果公式層次比較高，則表的寬度將變得很寬，甚至無(wú)法寫下,1.3真值表和真值函數(shù),二、真值函數(shù)一個(gè)n元真值函數(shù)是指F：0，1n0，1，(n1)，即此函數(shù)以n個(gè)命題變項(xiàng)為變?cè)?，其定義域和值域均由真、假兩值構(gòu)成。真值函數(shù)同樣可以用真值表表示，這是真值函數(shù)在其命題變項(xiàng)所有可能取值下得到的值列成的表。對(duì)于n個(gè)命題變項(xiàng)，可能的賦值有2n個(gè)。對(duì)于每個(gè)賦值，真值函數(shù)的取值又有真、假兩種可能。因此，對(duì)于n個(gè)命題變項(xiàng)來(lái)說，它們可以構(gòu)成的

15、不同的真值函數(shù)有22n個(gè)。,1.4等值式與等值演算,1概念如果兩個(gè)邏輯形式對(duì)其中的命題變項(xiàng)的任何取值，都具有相同的值，則稱它們是相等的。另一種說法即為前面所提到的，A、B等值是指等價(jià)式AB為重言式，記為AB。兩個(gè)命題形式是否等值可以通過真值表來(lái)判斷或驗(yàn)證。下面給出一些常用的等值式，其中很多正是通常所說的的布爾代數(shù)或邏輯代數(shù)的主要組成部分。,1.4等值式與等值演算,2各種等值關(guān)系模式：（只列出部分）雙重否定律：AA等冪律：(2a)A(AA)(2b)A(AA)交換律：(3a)(AB)(BA)(3b)(AB)(BA)結(jié)合律：(4a)(AB)C)(A(BC)(4b)(AB)C)(A(BC)分配律：(5

16、a)(A(BC)(AB)(AC)(5b)(A(BC)(AB)(AC),1.4等值式與等值演算,德摩根律：(6a)(AB)(BA)(6b)(AB)(BA)吸收律：(7a)(A(AB)A(7b)(A(AB)A(7c)(A(AB)AB(7d)(A(AB)AB零律：(8a)(A1)1(8b)(A0)0同一律：(9a)(A0)A(9b)(A1)A排中律：(AA)1,1.4等值式與等值演算,矛盾式：(AA)0蘊(yùn)涵等值式：(AB)(AB)等價(jià)等值式：(AB)(AB)(BA)假言易位：(AB)(BA)等價(jià)否定等值式：(AB)(AB)歸謬律：(AB)(AB)A香農(nóng)定理：,1.4等值式與等值演算,示例：香農(nóng)定理應(yīng)

17、用對(duì)于公式A(p1,p2,pn,0,1,)，完全可能省略了括號(hào)，這時(shí)應(yīng)用香農(nóng)定理時(shí)要注意將省略的括號(hào)添加上，否則等值演算會(huì)出問題。如：(pqr)(p(qr)p(qr)，但如果不將省略的括號(hào)添上，就演算成pqr，顯然該式是先運(yùn)算pq，而不是先運(yùn)算qr，結(jié)果不正確。,1.4等值式與等值演算,對(duì)偶定理對(duì)偶式：公式A僅含有聯(lián)結(jié)詞，則將A中的，0，1分別換以，1，0后得到的公式為A的對(duì)偶式A*。a)香農(nóng)定理用對(duì)偶式表示即為：b)如果AB，則A*B*。(對(duì)偶定理)根據(jù)已知的等值式，可以推演出另外許多的等值式，這種推演過程稱為等值演算。,1.4等值式與等值演算,3等值演算在等值演算時(shí)，除了要用到上面給出的等

18、值式外，通常還用到一些重要的演算規(guī)則。(1)等值式模式(2)重言式替換規(guī)則(3)置換規(guī)則置換規(guī)則：設(shè)是含有公式A的命題形式，是用公式B置換中的公式A(不一定是每一處)而得到的命題形式，如果AB，則。,1.4等值式與等值演算,例證明ABCABC證明的方法當(dāng)然可以用真值表方法，但是直接應(yīng)用等值式及替換和置換規(guī)則通常會(huì)簡(jiǎn)單的多。證明：ABCA(BC)蘊(yùn)涵等值式(AB)C結(jié)合律(AB)C德摩根律(AB)C置換規(guī)則和蘊(yùn)涵等值式邏輯等值演算不僅僅停留在符號(hào)級(jí)，總要用來(lái)解決實(shí)際問題，如簡(jiǎn)化語(yǔ)句，確定一些命題的真值等等，可以首先符號(hào)化命題，然后由已知條件列出這些命題應(yīng)該滿足的方程組，從而達(dá)到要求。,1.4等值

19、式與等值演算,例化簡(jiǎn)語(yǔ)句：“情況并非如此：如果他不來(lái)，那么我也不去”。解：設(shè)p:他來(lái)，q：我去；上述語(yǔ)句符號(hào)化為(pq)將詞進(jìn)行等值化簡(jiǎn)得(pq)(pq)(pq)pq化簡(jiǎn)后語(yǔ)句為：“我去了，而他沒來(lái)”。,1.4等值式與等值演算,例小李或小張是先進(jìn)工作者；如果小李是先進(jìn)工作者，你是會(huì)知道的；如果小張是先進(jìn)工作者，小趙也是；你不知道小李是先進(jìn)工作者，問誰(shuí)是先進(jìn)工作者。解：設(shè)p:小李是先進(jìn)工作者；q:小張是先進(jìn)工作者;r你知道小李是先進(jìn)工作者;s:小趙是先進(jìn)工作者則(pq)(pr)(qs)r1其中左邊(pq)(pr)(qs)r(pq)(qs)(pr)r),1.4等值式與等值演算,(pq)(qs)(p

20、r)(吸收律)(p(pq)(qs)r(pq)(qs)rp(q(qs)rp(qs)rpqsr1顯然p=0,q=1,s=1,r=0；即小張和小趙是先進(jìn)工作者。,1.4等值式與等值演算,從前面給出的等值式模式可以發(fā)現(xiàn)，常用的六種聯(lián)結(jié)詞不是相互獨(dú)立的，在表示邏輯關(guān)系時(shí)并不都是缺一不可的。其中有些聯(lián)結(jié)詞的邏輯功能可以用其它聯(lián)結(jié)詞代替，如：ABAB，AB(AB)(BA)(AB)(BA)，AB(AB)(AB)。這里我們討論聯(lián)結(jié)詞集合問題。我們把幾個(gè)聯(lián)結(jié)詞放在一起，稱為一個(gè)聯(lián)結(jié)詞集合。,1.5聯(lián)結(jié)詞完備集,正如前面所講述的，在聯(lián)結(jié)詞集合中，一般一些聯(lián)結(jié)詞可以用另外的聯(lián)結(jié)詞來(lái)表示，這就是說有冗余聯(lián)結(jié)詞和獨(dú)立聯(lián)結(jié)

21、詞之分。1冗余聯(lián)結(jié)詞，獨(dú)立聯(lián)結(jié)詞聯(lián)結(jié)詞組成一個(gè)集合，如果一個(gè)聯(lián)結(jié)詞可由集合中的其它聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余聯(lián)結(jié)詞，否則稱為獨(dú)立聯(lián)結(jié)詞。冗余聯(lián)結(jié)詞是可以由集合中的獨(dú)立聯(lián)結(jié)詞來(lái)定義。,1.5聯(lián)結(jié)詞完備集,2全功能集及極小全功能集全功能集：任意真值函數(shù)僅用此集合中聯(lián)結(jié)詞的命題形式就可以表示極小全功能集：不含冗余聯(lián)結(jié)詞的全功能集。說明：（1）任何真值函數(shù)都能表示；（2）定理：如果一個(gè)全功能集S1中的所有聯(lián)結(jié)詞都可由一個(gè)聯(lián)結(jié)詞集合S2定義，則S2也是全功能集。,是全功能集,都是極小全功能集,1.6范式,判斷兩個(gè)命題公式是否等值，前面已經(jīng)介紹了真值表法和等值演算法。相比較而言，等值演算法可能簡(jiǎn)單得多

22、，特別是在命題變項(xiàng)數(shù)目較多的時(shí)候。然而有時(shí)想將一個(gè)命題形式等值變換成另一個(gè)，卻可能很難找到適當(dāng)?shù)倪^程。一個(gè)有效的方法式將兩個(gè)命題公式等值演算某種標(biāo)準(zhǔn)形式，然后在比較，這種標(biāo)準(zhǔn)就稱為范式。1基本概念文字：命題變項(xiàng)及其否定的統(tǒng)稱。簡(jiǎn)單析取式：由有限個(gè)命題變項(xiàng)及其否定構(gòu)成的析取式。一個(gè)簡(jiǎn)單合取式是矛盾式，當(dāng)且僅當(dāng)其含有一個(gè)文字及其否定,1.6范式,簡(jiǎn)單合取式：由有限個(gè)命題變項(xiàng)及其否定構(gòu)成的合取式。一個(gè)簡(jiǎn)單析取式是重言式，當(dāng)且僅當(dāng)其含有一個(gè)文字及其否定。示例pq,pqp,pqrs等都是簡(jiǎn)單合取式，pq,pqr,ppr等都是簡(jiǎn)單析取式。單個(gè)文字既可看作是簡(jiǎn)單合取式，也可看作是簡(jiǎn)單析取式。,1.6范式,2

23、析取范式與合取范式A定義析取范式：簡(jiǎn)單合取式的析取合取范式：簡(jiǎn)單析取式的合取B性質(zhì)一個(gè)析取范式是矛盾式，當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。一個(gè)合取范式是重言式，當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式。,1.6范式,C范式的獲得任何一個(gè)命題形式都可以等值演算成合取范式和析取范式，具體步驟：1)利用等值式模式將其它聯(lián)結(jié)詞轉(zhuǎn)化成,；2)簡(jiǎn)化雙重否定號(hào)，并利用香農(nóng)定理將所有寫到文字里；3)利用分配律，將A最終變成合取范式和析取范式。,1.6范式,示例通過等值演算將(pq)r)p化成合取范式和析取范式。解：(pq)r)p(pq)r)p(pq)r)p(pr)(qr)p(析取范式)(pr)p)(qr)p(

24、qr)(析取范式)(pq)(pr)。(合取范式),1.6范式,一個(gè)命題形式的析取范式不是唯一的，同樣，合取范式也不是唯一的。這就給我們想通過比較標(biāo)準(zhǔn)形式的異同判斷命題形式是否等值的要求帶來(lái)困難，因此不能將析取范式和合取范式作為標(biāo)準(zhǔn)形式。3主析取范式與主合取范式：A極小項(xiàng)：在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中，每個(gè)命題變項(xiàng)作為文字出現(xiàn)且僅出現(xiàn)一次。,1.6范式,主要性質(zhì)：(1)每個(gè)極小項(xiàng)的成真賦值僅有一個(gè)；(2)兩個(gè)不同的極小項(xiàng)的合取構(gòu)成的命題形式為矛盾式；(3)所有極小項(xiàng)的析取構(gòu)成的命題形式為重言式。了書寫方便，通常用mi表示某個(gè)極小項(xiàng)，下標(biāo)i的規(guī)定如下：極小項(xiàng)的命題變項(xiàng)按一定的次序排好后，下標(biāo)i

25、化為二進(jìn)制后正是該值。這樣每個(gè)mi與其成真賦值建立了一一對(duì)應(yīng)的關(guān)系。示例：三個(gè)變量的極小項(xiàng)m7pqr,m5pqr,1.6范式,B主析取范式極小項(xiàng)的析取性質(zhì)：(1)如mi是主析取范式A的一個(gè)極小項(xiàng)，則mi的成真賦值一定是A的成真賦值；(2)A、B是相同的n個(gè)命題變項(xiàng)的主析取范式，則AB將包含A和B的所有極小項(xiàng)；AB將包含A和B的所有的公共極小項(xiàng)；(3)A包含主析取范式A的所有極小項(xiàng)之外的全部極小項(xiàng)。,1.6范式,唯一性任何一個(gè)命題形式都存在一個(gè)且唯一一個(gè)主析取范式或主合取范式。任何一個(gè)命題形式可以等值演算成合取范式和析取范式。演算步驟：(1)等值演算變換成析取范式，不妨設(shè)A=B1B2Bn(n1)

26、。(2)不是極小項(xiàng)的簡(jiǎn)單合取式，如不含有p的文字，則等值演算:BiBi1Bi(pp)(Bip)(Bip)，其所缺少的命題變項(xiàng)重復(fù)上述過程，直到所有簡(jiǎn)單合取式都是極小項(xiàng)為止。(3)將所有相同的極小項(xiàng)合并。,1.6范式,C主合取范式極大項(xiàng)在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單析取式中，每個(gè)命題變項(xiàng)作為文字出現(xiàn)且僅出現(xiàn)一次。性質(zhì)：（1）每個(gè)極大項(xiàng)的成假賦值有且僅有一個(gè)；（2）兩個(gè)不同的極大項(xiàng)的析取構(gòu)成的命題形式為重言式；（3）所有極大項(xiàng)的合取構(gòu)成的命題形式為矛盾式。,1.6范式,簡(jiǎn)單表示：三個(gè)變量的極大項(xiàng)M7pqr,M5pqr主合取范式：極大項(xiàng)的合取。表示：MiMjMk或(i,j,k)我們已經(jīng)討論了兩個(gè)主范式，在

27、演算過程中，為了方便，可以以任何一種范式作為基礎(chǔ)，實(shí)際上兩種范式是相通的。,1.6范式,D兩種主范式的互換mi和Mi之間的關(guān)系：Mimi，miMi主范式關(guān)系：主析取范式不包含的極小項(xiàng)標(biāo)號(hào)正是其主合取范式所包含的極大項(xiàng)標(biāo)號(hào)。示例：m2m4m5m6m7M0M1M3,1.7命題邏輯的推理理論,命題邏輯的任務(wù)在于推理，前面討論了基本概念，也討論了等值演算方法，但最終目的還是為了實(shí)現(xiàn)推理。本節(jié)學(xué)習(xí)推理的有關(guān)理論。邏輯學(xué)的主要任務(wù)就是提供一套推理規(guī)則，并按照這套規(guī)則，從前提集合中推導(dǎo)出一個(gè)結(jié)論來(lái)，這里主要討論推論過程中推論規(guī)則使用的有效性，而并不關(guān)心前提的具體真值。問題：推理是什么？要了解推理理論，首先要

28、了解推理是什么。,1.7命題邏輯的推理理論,一、推理的形式結(jié)構(gòu)數(shù)理邏輯研究的主要的演繹推理，即前提與結(jié)論間的聯(lián)系是必然的這一類的推理。一個(gè)蘊(yùn)含式就是一個(gè)推理。1推理的正確性：如果AB是一個(gè)重言式，則稱由A推出B；(A1A2An)B是重言式，則稱B是由A1,A2,An推出的，稱推理是正確的，否則是不正確的。其中A或A1,A2,An是前提，B是結(jié)論。,1.7命題邏輯的推理理論,由蘊(yùn)涵式真值表可知，當(dāng)A或A1,A2,An的真值為假時(shí)，無(wú)論B真值如何，蘊(yùn)涵式的真值總為真，所以通?！巴瞥觥本鸵馕吨喝绻鸄為真或A1,A2,An均為真，則B也一定為真。前面提到，重言蘊(yùn)涵式AB可以表示成AB。顯然和不同，前

29、者是運(yùn)算符，后者則是表示“推出”的關(guān)系符，是推出關(guān)系。2形式結(jié)構(gòu)：1)(A1A2An)B,1.7命題邏輯的推理理論,2)推理圖式：3)A1,A2,AnB,1.7命題邏輯的推理理論,3推理的一致性如果一個(gè)推理的前提的合取式是可滿足式，則稱前提是一致的，否則是不一致的。注意前提是否一致的與推理是否正確是不同的，不能混淆。不一致的推理一定正確。所有的數(shù)學(xué)定理均由形式(A1A2An)B組成?，F(xiàn)在我們已經(jīng)知道，正確的推理是一個(gè)重言的蘊(yùn)涵式。所以要判斷一個(gè)推理是否正確，直接的方法當(dāng)然是判斷蘊(yùn)涵式是否重言式。按照前面的方法，有真值表法、等值演算法、主范式法等,1.7命題邏輯的推理理論,示例：判斷推理A(AB

30、)的正確性。在等值演算中，我們通常要用到一些被稱為等值式模式的常用等值式，這些是經(jīng)過證明了的，并且應(yīng)用很廣泛，同樣在推理理論中，也有一些常用的正確推理，我們稱之為推理定律。4推理定律(1)附加：A(AB)(2)化簡(jiǎn)：(AB)A(3)假言推理：(AB)A)B,1.7命題邏輯的推理理論,(4)拒取式：(AB)B)A(5)析取三段論：(AB)A)B(6)假言三段論：(AB)(BC)(AC)(7)等價(jià)三段論：(AB)(BC)(AC)(8)構(gòu)造性二難：(8a)(AB)(CD)(AC)(BD)(8b)(AB)(AB)B因?yàn)?AA1)(9)破壞性二難：(AB)(CD)(BD)(AC)(10)A，B均僅含有聯(lián)

31、結(jié)詞如果，如果AB，則B*A*。,1.7命題邏輯的推理理論,示例證明:,1.7命題邏輯的推理理論,判斷推理是否正確，或者說證明一個(gè)推理是否正確，我們可以用等值演算的方法，然而這樣的方法里我們并不了解如何從前提一步一步推出結(jié)論的，在實(shí)際的過程中，我們更加需要的了解如何從前提推出結(jié)論，即如何構(gòu)造一個(gè)證明。要推理，就要構(gòu)造一個(gè)證明，且只能在形式系統(tǒng)中進(jìn)行。形式系統(tǒng)：1)公理系統(tǒng)：從幾個(gè)給定的公理出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推演，得到的結(jié)論是系統(tǒng)中的定理。,1.7命題邏輯的推理理論,2)自然推理系統(tǒng)：從任意的前提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推演，得到的結(jié)論在系統(tǒng)中被認(rèn)為是有效的。本節(jié)主要討論自然推

32、理系統(tǒng)，當(dāng)然自然推理系統(tǒng)也是有許多，我們集中闡述其中的P系統(tǒng)。二、自然推理系統(tǒng)P1證明即為一個(gè)描述推理過程的命題序列。2自然推理系統(tǒng)P：a)字母表b)合式公式,1.7命題邏輯的推理理論,c)推理規(guī)則(1)前提引入規(guī)則P：在證明的任何步上，都可以引入前提；(2)結(jié)論引用規(guī)則T：在證明的任何步上所得的結(jié)論都可作為后續(xù)證明的前提；(3)置換規(guī)則E：在證明的任何步上，命題的任何形式都可進(jìn)行等值置換；(4)所有的推理定律構(gòu)成相應(yīng)的推理規(guī)則（I規(guī)則）。,1.7命題邏輯的推理理論,證明中的每個(gè)命題(形式)都是根據(jù)系統(tǒng)P的推理規(guī)則得到的。實(shí)際上，在應(yīng)用推理規(guī)則證明時(shí)，只有上述推理規(guī)則及在前面任何步上得到的結(jié)論

33、(T規(guī)則)可作為推證的依據(jù)，而沒有其它推證依據(jù)。特別是在推理證明時(shí)不能對(duì)推證步驟進(jìn)行省略，否則將被視為邏輯錯(cuò)誤，而在等值推演時(shí)這是允許的。示例例1前提：pq，rp，q；結(jié)論：r。,1.7命題邏輯的推理理論,pq前提引入Pq前提引入Pp拒取式TIrp前提引入Pr拒取式TI在以上證明中，中間是構(gòu)成證明的命題(形式)序列，左邊是每個(gè)命題(形式)的序號(hào)，右邊兩列是每個(gè)命題(形式)得以引入的根據(jù)，通常只要選擇一種即可，當(dāng)用字母表示時(shí)，應(yīng)用的P規(guī)則、T規(guī)則分別用P、T表示；使用了推理定律，表示為I，使用了置換規(guī)則，表示為E，同時(shí)必須寫出推理前提。,1.7命題邏輯的推理理論,例2如果a是奇數(shù)，則a不能被2整

34、除，如果a是偶數(shù)，則a能被2整除，因此如果a是偶數(shù)，則a不是奇數(shù)。符號(hào)化：p：a是奇數(shù)；q：a是偶數(shù)；r：a能被2整除；前提:pr,qr;結(jié)論:qp。證明：前提：pr，qr；結(jié)論：qp。pr前提引入Ppr置換TErp置換TErp置換TE,1.7命題邏輯的推理理論,qr前提引入Pqp假言三段論TI需要強(qiáng)調(diào)的是引入依據(jù)只需要寫出其中一種即可，顯然用漢字描述時(shí)，需要知道推理定理的具體名稱，而用字母表示時(shí)，則所有的推理定律均用I表示，所以用字母表示會(huì)簡(jiǎn)單些，以后我們主要用字母表示。,1.7命題邏輯的推理理論,例3一個(gè)偵探在調(diào)查某珠寶店的鉆石項(xiàng)鏈盜竊案后，根據(jù)以下事實(shí)：(1)營(yíng)業(yè)員A或B盜竊了鉆石項(xiàng)鏈；(2)若A作案，則作案不再營(yíng)業(yè)時(shí)間內(nèi)；(3)若B提供的證明正確，則貨柜未上鎖；(4)若B提供的證明不正確，則作案在營(yíng)業(yè)時(shí)間內(nèi)；(5)貨柜是上了鎖的。推出B盜竊了鉆石項(xiàng)鏈。試驗(yàn)證推理的正確性。,1.7命題邏輯的推理理論,解這也是運(yùn)用數(shù)理邏輯解決實(shí)際問題。符號(hào)化：p：A盜竊了鉆石項(xiàng)鏈，q：B盜竊了鉆石項(xiàng)鏈，r：作案在營(yíng)業(yè)時(shí)間內(nèi)，s：B提供的證明正確,t：貨柜上了鎖；前提：pq,pr,st,sr,t結(jié)論：