離散數(shù)學-----命題邏輯

1、離散數(shù)學-命題邏輯邏輯：是研究推理的科學。公元前四世紀由希臘的哲學家亞里斯多德首創(chuàng)。作為一門獨立科學，十七世紀，德國的萊布尼茲(Leibniz)給邏輯學引進了符號, 又稱為數(shù)理邏輯(或符號邏輯)。 邏輯可分為：1. 形式邏輯（是研究思維的形式結(jié)構(gòu)和規(guī)律的科學，它撇開具體的、個別的思維內(nèi)容，從形式結(jié)構(gòu)方面研究概念、判斷和推理及其正確聯(lián)系的規(guī)律。）數(shù)理邏輯（是用數(shù)學方法研究推理的形式結(jié)構(gòu)和規(guī)律的數(shù)學學科。它的創(chuàng)始人Leibniz，為了實現(xiàn)把推理變?yōu)檠菟愕南敕?，把?shù)學引入了形式邏輯中。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學科。） 2. 辯證邏輯（是研究反映客觀世界辯證發(fā)展過程的人類思維

2、的形態(tài)的。）一、命題及其表示方法 1、命題 數(shù)理邏輯研究的中心問題是推理,而推理的前提和結(jié)論都是表達判斷的陳述句，因而表達判斷的陳述句構(gòu)成了推理的基本單位。基本概念：命題：能夠判斷真假的陳述句。 命題的真值：命題的判斷結(jié)果。命題的真值只取兩個值:真（用T(true)或1表示）、假（用F(false)或0表示） 。真命題：判斷為正確的命題，即真值為真的命題。 假命題：判斷為錯誤的命題，即真值為假的命題。 因而又可以稱命題是具有唯一真值的陳述句。 判斷命題的兩個步驟： 1、是否為陳述句； 2、是否有確定的、唯一的真值。說明：（1）只有具有確定真值的陳述句才是命題。 一切沒有判斷內(nèi)容的句子，無所謂是

3、非的句子，如感嘆句、祁使句、疑問句等都不是命題。（2） 因為命題只有兩種真值，所以“命題邏 輯”又稱 “二值邏輯”。 （3） “具有確定真值”是指客觀上的具有，與我們是否知道它的真值是兩回事。2、命題的表示方法 在書中，用大寫英文字母A,B,P,Q或帶下標的字母P1,P2,P3 , ,或數(shù)字(1),2, ,等表示命題，稱之為命題標識符。 命題標識符又有命題常量、命題變元和原子變元之分。命題常量：表示確定命題的命題標識符。命題變元：命題標識符如僅是表示任意命題的位置標志，就稱為命題變元。原子變元：當命題變元表示原子命題時，該變元稱為原子變元。命題變元也用A,B,P,Q,P1,P2,P3 , ,

4、表示。3、命題的分類：簡單/原子命題：不能分解為更簡單的陳述語句的命題。復合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。聯(lián)結(jié)詞就是復合命題中的運算符。 注意：（1）一個符號(如P), 它表示的是命題常量還是命題變元，一般由上下文來確定。（2）命題變元可以表示任意命題，它不能確定真值，故命題變元不是命題。這與“變數(shù)x不是數(shù)”是一樣的道理。 二、邏輯聯(lián)結(jié)詞在命題邏輯中,主要研究的是復合命題,而復合命題是由原子命題與邏輯聯(lián)結(jié)詞組合而成,聯(lián)結(jié)詞是復合命題的重要組成部分.1、否定聯(lián)結(jié)詞 定義：設(shè)P為一命題， P的否定是一個新的復合命題, 稱為P的否定式，記作 “P”讀作“非P”. 符號“ ” 稱為否定聯(lián)結(jié)

5、詞。 P為真當且僅當P為假.說明： “”屬于一元運算符. “”的定義也可用下表來說明. 聯(lián)結(jié)詞“”的定義真值表 PP01102、合取聯(lián)結(jié)詞 定義：設(shè)P,Q為二命題，復合命題“P并且Q”（或“P與Q”）稱為P與Q的合取式，記作PQ，符號“” 稱為合取聯(lián)結(jié)詞. PQ為真當且僅當P和Q同時為真. 聯(lián)結(jié)詞“”的定義真值表PQ PQ 000010100111注意：不要見到“與”或“和”就使用聯(lián)結(jié)詞！ 3、析取聯(lián)結(jié)詞 定義：設(shè)P, Q為二命題，復合命題“P或Q” 稱為P與Q的析取式，記作PQ ，符號稱為析取聯(lián)結(jié)詞. PQ為真當且僅當 P與Q中至少有一個為真. 聯(lián)結(jié)詞“”的定義真值表PQ PQ 000011

6、101111說明：“” 屬于二元(binary)運算符.析取運算特點：只有參與運算的二命題全為假時，運算結(jié)果才為假，否則為真。由析取聯(lián)結(jié)詞的定義可以看出， “”與漢語中的聯(lián)結(jié)詞“或”意義相近，但又不完全相同。在現(xiàn)代漢語中，聯(lián)結(jié)詞的“或”實際上有“可兼或”和“排斥或”之分。 注意：當P和Q客觀上不能同時發(fā)生時，“P或Q”可以符號化為“PQ”。4、 條件聯(lián)結(jié)詞(蘊涵聯(lián)結(jié)詞) 定義：設(shè)P, Q為二命題，復合命題“如果P則Q (若P則Q)” 稱為P與Q的條件命題,記作P ®Q. P®Q為假當且僅當P為真且Q為假.稱符號“®”為條件聯(lián)結(jié)詞。并稱P為前件，Q為后件. 聯(lián)結(jié)詞“

7、®”的定義真值表PQP Q001011100111 注：（1）P®Q表示的基本邏輯關(guān)系是,Q是P的必要條件或P是Q的充分條件. 因此復合命題“只要P就Q”、“因為P，所以Q”、“P僅當Q”、“只有Q才P”等都可以符號化為P®Q 的形式。（2） “®” 屬于二元運算.注意: (1)與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！(2) 在數(shù)學中，“若P則Q”往往表示前件P為真，則后件Q為真的推理關(guān)系. 但數(shù)理邏輯中，當前件P為假時， PQ的真值為真。5、 雙條件聯(lián)結(jié)(等值聯(lián)結(jié)詞) « 定義： 設(shè)P, Q為二命題，復合命題“P當且僅當Q” 稱為P

8、與Q的雙條件命題，記作P iff Q或P«Q，符號«稱為雙條件（等值）聯(lián)結(jié)詞。 P«Q為真當且僅當P，Q真值相同。 聯(lián)結(jié)詞“«”的定義真值表PQP«Q001010100111注：（1） P僅當Q 可譯為PQ P當Q可譯為QP P當且僅當Q 譯為P«Q （2）“«”屬于二元(binary)運算符。 （3）雙條件命題P«Q所表達的邏輯關(guān)系是, P與Q互為充分必要條件,相當于(P®Q)(Q®P). 只要P與Q的真值同為1或同為0, P«Q的真值就為1, 否則P«Q的真值為0. 雙條

9、件聯(lián)結(jié)詞連接的兩個命題之間可以沒有因果關(guān)系。約 定:1. 運算次序優(yōu)先級：,，«. 2. 相同的運算符按從左至右次序計算，否則要加上括號。 3.最外層圓括號可省去。 三、命題公式與翻譯1、命題合式公式 定義:單個命題變元和命題常量稱為原子公式。命題合式公式是由命題變元、命題常量、聯(lián)結(jié)詞和圓括號按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號串。 定義：（1）原子公式是合式公式(wff)。 （2）若A是合式公式，則(A)也是合式公式。 （3）若A,B是合式公式，則(AB)，(AB)，(A®B)，(A«B)也是合式公式。 （4）當且僅當有限次地應(yīng)用(1)(3)所得到的包含原子公式、聯(lián)結(jié)

10、詞和括號的符號串是合式公式。注: (1)合式公式也稱為命題公式，并簡稱為公式。 (2)命題公式一般不是命題,僅當公式中的命題變元用確定的命題代入時,才得到一個命題.其真值依賴于代換變元的那些命題的真值.2、復合命題的符號化(翻譯)把自然語言中的有些語句(復合命題),翻譯成數(shù)理邏輯中的符號形式.基本步驟如下:(1) 分析出各簡單命題,將它們符號化;(2) 使用合適的聯(lián)結(jié)詞,把簡單命題逐個的聯(lián)結(jié)起來,組成復合命題的符號化表示.四、真值表與等價公式定義：對公式的賦值或解釋)設(shè)P1 , P2 ,Pn是出現(xiàn)在公式A中的全部的命題變元, 給P1 , P2 ,Pn各指定一個真值，稱為對A的一個賦值或解釋。若

11、指定的一組值使A的真值為真(假), 稱這組值為A的成真(假)賦值.定義： (真值表)在命題公式A中, 對于命題變元的每一組賦值和由它們所確定的命題公式A的真值列成表，稱做命題公式A 的真值表。對公式A構(gòu)造真值表的具體步驟為：（1）找出公式中所有命題變元P1 , P2 ,Pn , 列出全部的2n組賦值。（2）按從小到大的順序列出對命題變元P1 , P2 ,Pn ,的全部2n組賦值。（3）對應(yīng)各組賦值計算出公式A的真值，并將其列在對應(yīng)賦值的后面。 等價公式：給定n個 命題變元, 按合式公式的形成規(guī)則可以形成無數(shù)多個命題公式, 但這些無窮盡的命題公式中，有些具有相同的真值表。定義: 給定兩個命題公式

12、A和B，設(shè)P1 ,P2 ,Pn為出現(xiàn)于A和B中的所有原子變元,若給P1 , P2 ,Pn任一組真值指派, A和B的真值都相同,則稱A和B是等價的或邏輯相等.記作AÛB。注: (1) “Û ”不是邏輯聯(lián)結(jié)詞.(2)命題公式之間的邏輯相等關(guān)系具有： 自反性：AÛA ； 對稱性：若AÛB，則BÛA； 傳遞性：若AÛB且BÛC，則AÛC。證明公式等價的方法：1. 真值表法 2. 等值演算法等值演算法等值演算中使用的一條重要規(guī)則：置換規(guī)則定義：(子公式)：如果X是wff A的一部分,且X本身也是wff，則稱X是A的子公式。定

13、理 (置換定理) 設(shè)X是wff A的子wff，若XÛY，則若將A中的X用Y來置換，所得公式B與A等價，即AÛB。注: 滿足定理(置換定理)的條件的置換稱為等價置換(或等價代換).定義 (等值演算)：根據(jù)已知的等價公式,推演出另外一些等價公式的過程稱等值演算.常用的等價式： 1.雙重否定律： PÛ P 2.結(jié)合律：(PQ)RÛP(QR) (PQ)RÛP(QR) (P«Q)«RÛP«(Q«R) 3.交換律: PQÛQP PQÛ QP P«Q ÛQ«P

14、 4. 分配律: P(QR )Û(PQ)(PR) P(QR)Û(PQ)(PR) 5.冪等律: PPÛ P PPÛ P 6.吸收律: P(PQ) ÛP P(PQ)ÛP 7.德.摩根律: (PQ)ÛPQ (PQ)ÛPQ 8.同一律: PFÛP PTÛP 9.零律: PTÛT PFÛF 10.否定律： PPÛT PPÛF 11. 蘊涵等值式: P®QÛ PQ 12. 等價等值式: P«QÛ(PQ)(QP) 13. 假言易位

15、: P®QÛQ®P 14. 等價否定等值式: P«QÛP«Q 15. 歸謬論: (P®Q )( P®Q)ÛP 其中P, Q, R等代表任意命題公式. 這樣上面的每一個公式都是一個模式, 它可以代表無數(shù)多個同類型的命題公式. 五、重言式與蘊含式1、定義： 設(shè)A為任一命題公式，(1)若A在其各種賦值下的取值均為真，則稱A是重言式或永真式, 記為T或1。(2)若A在其各種賦值下的取值均為假，則稱 A是矛盾式或永假式, 記為F或0。(3)若A不是矛盾式則稱A為可滿足式(satisfiable)。注: 由定義可知,

16、重言式一定是可滿足式,反之不真. 判別命題公式的類型有兩種方法: 真值表法和等值演算法. 等值演算法是將所給命題公式通過等值演算化為最簡單的形式, 然后再進行判別.2、重言式與矛盾式的性質(zhì)定理:任何兩個重言式的合取或析取,仍然是一重言式.（由冪等律立得）定理:一個重言式(矛盾式),對同一分量都用任何合式公式置換,其結(jié)果仍為一重言式(矛盾式).定理：A,B是兩個命題公式，AÛ B的充要條件是A « B為重言式。3、蘊含式定義：當且僅當P®Q是一個重言式時，我們稱“P蘊含Q”，并記作PÞQ. 原命題逆換式反換式逆反式P®Q Q®P P&#

17、174; QQ® P它們之間具有如下關(guān)系: P®Q Û Q® P Q®P Û P® Q 因此, 要證明PÞQ有三種方法:1)真值表法: 即列出P®Q的真值表,觀察其是否永為真。2)等值演算法：通過證明P®Q Û1來證PÞQ3)分析法：直接分析法: 假定前件P是真，推出后件Q是真。 間接分析法: 假定后件是假，推出前件是假,即證 QÞP 。4、等價式與蘊含式的關(guān)系:定理: 設(shè)P,Q為任意兩個命題公式,PÛQ的充要條件為PÞQ且QÞP.蘊含

18、的性質(zhì):設(shè)A，B，C為任意wff,1) 若AÞB，且A為永真式，則B必為永真式.2) 若AÞB，BÞC，則AÞC.3) 若AÞB，AÞC，則AÞBC.4) 若AÞB且CÞB，則ACÞB.六、其它聯(lián)結(jié)詞 1、 聯(lián)結(jié)詞“ ”的定義真值表PQ P Q 000011101110說明：“ ” 屬于二元運算符.聯(lián)結(jié)詞“ ”的性質(zhì): 設(shè)P, Q, R為命題公式, 則有(1) P Q Û Q P (交換律)(2) (P Q) R Û P (Q R) (結(jié)合律)(3) P(Q R) Û

19、; (PQ ) (PR) (分配律)(4) (P Q) Û (PQ) (PQ)(5) (P Q) Û (P«Q) (6) P P Û F, F P Û P, T P Û P 定理:設(shè)P, Q, R為命題公式, 如果 P QÛR,則 P RÛQ ,Q RÛP, 且P Q R 為一矛盾式.2、與非聯(lián)結(jié)詞() 定義：設(shè)P,Q為二命題，復合命題“P與Q的否定” 稱為P與Q的與非式，記作PQ，符號“” 稱為與非聯(lián)結(jié)詞. PQ為真當且僅當P和Q不同時為真. 聯(lián)結(jié)詞“”的定義真值表PQ PQ 001011101110說

20、明: (1) 由定義可知, PQ Û (PQ) (2)“” 屬于二元(binary)運算符.聯(lián)結(jié)詞“”的性質(zhì): (1) PP Û ( PP) Û P (2) (PQ)(PQ) Û ( PQ)Û(PQ) (3)(PP)(QQ)ÛPQ Û(PQ)Û PQ 3、或非聯(lián)結(jié)詞 定義1.6.3 設(shè)P,Q為二命題，復合命題“P或Q的否定” 稱為P與Q的或非式，記作PQ ，符號“”稱為或非聯(lián)結(jié)詞. PQ為真當且僅當 P與Q同為假. 聯(lián)結(jié)詞“”的定義真值表PQ PQ 001010100110說明: (1) 由定義可知, PQ 

21、19; (PQ) (2)“” 屬于二元(binary)運算符.聯(lián)結(jié)詞“”的性質(zhì): (1) PP Û ( PP) Û P (2) (PQ)(PQ) Û(PQ) Û(PQ) (3)(PP)(QQ)ÛPQ Û (PQ)ÛPQ 4、條件否定聯(lián)結(jié)詞定義：設(shè)P,Q為二命題，復合命題“P Q” 稱為命題P與Q的條件否定式, P Q為真當且當P為真且Q為假. 聯(lián)結(jié)詞“ ”的定義真值表PQP Q000010101110說明: (1) 由定義可知, P Q Û (P®Q)(2)“ ” 屬于二元(binary)運算符.有了聯(lián)結(jié)

22、詞 后，合式公式的定義1.3.2可加入這四個聯(lián)結(jié)詞.5、最小聯(lián)結(jié)詞組定義：在一個聯(lián)結(jié)詞的集合中,如果一個聯(lián)結(jié)詞可由該集合中的其它聯(lián)結(jié)詞定義,則稱此聯(lián)結(jié)詞為冗余聯(lián)結(jié)詞,否則稱為獨立聯(lián)結(jié)詞. 不含冗余聯(lián)結(jié)詞的聯(lián)結(jié)詞組稱為最小聯(lián)結(jié)詞組.說明:最小聯(lián)結(jié)詞組中的聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價的表達出來。七、對偶與范式 1、 對偶式與對偶原理 定義:設(shè)命題公式A僅含有聯(lián)結(jié)詞,在A中將,，F(xiàn)，T分別換以,，T，F(xiàn)得出公式A*，則A*稱為A的對偶公式。說明:(A*)*=A對偶式兩個定理:定理: 設(shè)A和A*是對偶式。P1, P2, Pn是出現(xiàn)于A和A *中的所有命題變元, 于是A(P1, P2, , P

23、n) A *(P1, P2, , Pn) A(P1, P2, , Pn) A *(P1, P2, , Pn)定理 (對偶原理):設(shè)A,B為兩個僅含有聯(lián)結(jié)詞,的命題公式, 若AÛB，則A*ÛB*.2、命題公式的析(合)取范式定義: (1)文字：命題變元及其否定統(tǒng)稱為文字。 (2)簡單析取式：僅由有限個文字組成的析取式。 (3)簡單合取式：僅由有限個文字組成的合取式。從定義可知:（1）一個簡單析取式是重言式當且僅當它同時含有某個命題變元及其否定式。（2）一個簡單合取式是矛盾式當且僅當它同時含有某個命題變元及其否定式。 定義1.7.3: (1)析取范式：一個命題公式稱為析取范式,

24、當且僅當它具有形式: A1A2An (n大于等于1)其中Ai(i=1,2,3,n)為簡單合取式.(2)合取范式：一個命題公式稱為合取范式,當且僅當它具有形式: A1A2An (n大于等于1)其中Ai(i=1,2,3,n)為簡單析取式. (3)范式：析取范式與合取范式統(tǒng)稱為范式。顯然, 任何合(析)取范式的對偶式是析(合)取范式.析取范式與合取范式的性質(zhì):(1) 一個析取范式是矛盾式,當且僅當它的每 一個簡單合取式都是矛盾式;(2)一個合取范式是重言式,當且僅當它的每一個簡單析取式都是重言式.定理 (范式存在定理)：任一個命題公式都存在著與之等價的析取范式與合取范式。求命題公式的范式的基本步驟：

25、（1）將公式中的聯(lián)結(jié)詞化歸成,及.（2）將否定聯(lián)結(jié)詞消去或內(nèi)移到各命題變元之前。 利用下列等價式：A Û A ( AB) Û AB ( AB) Û AB（3）利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取范式或析取范式. C( AB)Û(CA)(CB) C( AB)Û(CA)(CB)例1: 求(PQ)®R)®P 的析取范式與合取范式.例2: 求(P®Q)«R的析取范式與合取范式.例3: 求 (PQ)«(PQ)的析取范式與合取范式.注意：（1）單個命題變元既是簡單合取式，又是簡單析取式；公式PQR既可以看成是

26、合取范式，也可以看成是析取范式。（2）一個命題公式的析(合)取范式不是唯一的。3、命題公式的主析(合)取范式（1）命題公式的主析取范式定義：在含有n個命題變元的簡單合取式中,若每個命題變元和它的否定不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單合取式為小項.如三個命題變元P,Q,R,其小項共有8個: 小項 編碼 真值指派 小項的真值 PQR m000/ m0 000 1 PQR m001/m1 001 1 PQR m010/m2 010 1 PQR m011/m3 011 1 PQR m100/m4 100 1 PQR m101/m5 101 1 PQR m110/m6 110 1 P

27、QR m111/m7 111 1小項的性質(zhì):(1) 沒有兩個小項是等價的, 且每個小項有且僅有一個成真賦值，若成真賦值所對應(yīng)的二進制數(shù)轉(zhuǎn)化為十進制數(shù)為i，就將所對應(yīng)的小項記作mi。(2) 任意兩個不同的小項的合取為矛盾式.(3) 全體小項的析取為永真式.定義：設(shè)命題公式A中含有n個命題變元,如果A的析取范式中，所有的簡單合取式都是小項，則稱該析取范式為A的主析取范式。定理:任何命題公式都存在著與之等價的主析取范式，并且是唯一的。定理:在命題公式A的真值表中,真值為1的指派對應(yīng)的小項的析取, 即為A的主析取范式。一個命題公式A的主析取范式, 還可以通過等值演算的方法求出, 其推演步驟:(1) 將

28、A化為析取范式 ;(2) 除去 中所有永假的析取項;(3) 將 中重復出現(xiàn)的簡單合取式和相同變元都消去;(4)若 中某簡單合取式B中不含命題變元Pi, 添加 (PiPi), 然后應(yīng)用分配律展開. 即 B ÛB1ÛB(PiPi) Û(BPi)(BPi).（2）命題公式的主合取范式定義1.7.6：在含有n個命題變元的簡單析取式中,若每個命題變元和它的否定不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單析取式為大項.如三個命題變元P,Q,R,其大項共有8個: 大項 編碼 真值指派 大項的真值 PÚQÚR M000/M0 000 0 PÚ

29、;QÚR M001/M1 001 0 PÚQÚR M010/M2 010 0PÚQÚR M011/M3 011 0PÚQÚR M100/M4 100 0PÚQÚR M101/M5 101 0 PÚQÚR M110/M6 110 0 PÚQÚ R M111/M7 111 0大項的性質(zhì)(1) 沒有兩個大項是等價的, 且每個大項有且僅有一個成假賦值，若成假賦值所對應(yīng)的二進制數(shù)轉(zhuǎn)化為十進制數(shù)為i，就將所對應(yīng)的大項記作Mi。(2) 任意兩個不同的大項的析取為永真式.(3) 全

30、體大項的合取為矛盾式.定義：設(shè)命題公式A中含有n個命題變元, 如果A的合取范式中，所有的簡單析取式都是大項，則稱該合取范式為A的主合取范式。定理:任何命題公式都存在著與之等價的主合取范式，并且是唯一的。定理:在命題公式A的真值表中,真值為0的指派對應(yīng)的大項的合取, 即為A的主合取范式。一個命題公式A的主合取范式, 還可以通過等值演算的方法求出, 其推演步驟:(1) 將A化為合取范式 ;(2) 除去 中所有永真的合取項;(3) 將 中重復出現(xiàn)的簡單析取式和相同變元都消去;(4)若 中某簡單析取式B中不含命題變元Pi, 添加 (PiPi), 然后應(yīng)用分配律展開. 即 B ÛB0Û

31、;B(PiPi) Û(BPi)(BPi).注：1.命題公式的主析(合)取范式唯一。 2.兩命題公式若有相同的主析(合)取范式，則二命題公式等價.（3）主析取范式和主合取范式關(guān)系 設(shè)Z為命題公式A的主析取范式中所有小項的足標集合，R為命題公式A的主合取范式中所有大項的足標集合,則 R=0,1，2.2n-1-Z 或 Z=0,1，2.2n-1-R。故已知命題公式A的主析取范式，可求得其主合取范式；反之亦然。注意到小項與大項之間具有關(guān)系：miÛMi，MiÛmi（4）主析(合)取范式的應(yīng)用ü 求公式的成真/成假賦值： 若公式A中含有n個命題變元，且A的主析取范式含s個小項，則A有s個成真賦值，有2n-s個成假賦值。（即主析取范式中的小項對應(yīng)的編碼是公式A的成真賦值；反之主合取范式中的大項對應(yīng)的編碼是公式A的成假賦值）.