復習,真值表 等價公式 證明方法（真值表、公式證明法）,16組重要等值式,1、雙重否定律 P P 2、冪等律 P P P P P P 3、交換律 P QQ P P Q Q P 4、結合律 (P Q) R P (Q R) (P Q) R P (Q R),5、分配律 P (Q R) (P Q) (P R) P (Q R) (P Q) (P R) 6、吸收律 P (P Q) P P (P Q) P 7、德摩根律 (P Q) P Q (P Q) P Q 8、零律 P T T P F F 9、同一律 P F P P T P,10、排中律 P P T 11、矛盾律 P P F 12、蘊涵等值式 PQ P Q 13、等價等值式 P Q （PQ） （QP） 14、假言易位 PQ Q P 15、等價否定等值式 P Q P Q 16、歸謬論 （PQ） （ P Q ） P,記憶技巧：借助 集合的運算式， 看成并， 看 成交， 看成 補，T看成全集， F看成空集， 再加12-16條。,其他等價公式,其他聯接詞 (1) P Q (P Q); 雙條件否定(不可兼析取或,異或) (2) P Q (P Q); 條件否定 (3) P Q (P Q); 與非 (4) P Q (P Q); 或非,1-7 對偶與范式,對偶 范式,一、對偶式,定義1-7.1：在給定的僅含有, , 的命題公式中，將換成，將換成，T和F互換，所得公式A稱為A的對偶式。,例1：寫出（PQ） R的對偶式,解：對偶式為 （PQ） R,寫出（P Q）T， PFT的對偶式,定理1-7.2: 設P1,P2, Pn是出現在公式A和B中的所有原子變元,如果,A B,則A B.,二. 公式的標準型范式,1. 范式,定義1-7.2：一個命題公式稱為合取范式，當且僅當它具有 A1A2An 其中A1,A2, ,An都是由命題變元或其否定所組成的析取式.,定義1-7.3: 一個命題公式稱為析取范式，當且僅當它具有 A1A2An 其中A1,A2, ,An都是由命題變元或其否定所組成的合取式.,例如: (PQR) (PQ) Q P(PQ)(PQR),合取范式,析取范式,步驟,可以通過下面3個步驟將任一命題公式化為合取范式或析取范式： 將公式中的聯結詞化歸成，及； 利用德.摩根律將否定符號直接移到各個命題變元之前； 利用分配律、結合律將公式歸約為合取范式或析取范式。,例5: 求（P（Q R）S 的析取范式和合取范式,解：原公式 (P（QR）)S,（P（QR）S, P（QR）S, （PSQ）（PSR）,析取范式,合取范式,所以 原式(PQ) (PQ) (PQ) (PQ),例6: 求(PQ) (PQ)的析取范式。,解：因為 (A B) (AB) (AB),(P QPQ) (PQ) (PQ),(P QPQ) (PP) (PQ) (QP) (QQ),注意：任一命題公式都可以化為合取范式或析取范式的形式,2. 范式的應用,利用范式對公式進行判斷： (1)公式A為永假式的充要條件是A的析取范式中每個簡單合取式至少包含一個命題變元及其否定。 例：A(P1,P2,Pn) (P1 P1 ) (P2 P2 ) (2)公式A為永真式的充要條件是A的合取范式中每個簡單析取式至少包含一個命題變元及其否定。 例：B(P1,P2,Pn) (P1 P1 ) (P2 P2 ) ,例如: 判斷下列公式為何種公式： (1) P（Q R） (PR) (2) （PQ）P,解:(1) P（QR）（PR） （P QRP）（PQRR）永真,(2) （PQ）P （ PQ）P （ PP）（QP）可滿足式,3. 范式不唯一性,P(QR) (PQ)(PR) (PP)(PR)(QP)(QR) 分配律,對識別公式是否等價帶來一定困難， 解決方式：主范式,1. 主析取范式,小項的概念 定義1-7.4: n個命題變元的合取式，稱作布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現且僅出現一次。,例如：PQ，PQ，PQ，PQ 是 PQ P 不是 問題：n個變元可有多少小項？,三.公式的主范式,見課本P33表1-7.2，三個變元的情況,下標表示法：命題變元按字典順序排列，命題變元對應1，變元的否定對應0。對小項依二進制編碼（或用十進制編碼）。,如： PQ,PQ,m11(m3),m01(m1),PQ,m10(m2),PQ,m00(m0),小項的性質：,(1)每一小項當其真值指派與編碼相同時，其真值為T，在其余指派情況下均為F。 (2)任意兩個不同小項的合取為假。 例：m110m100 =(PQR) (PQR) PPQRR F (3)全體小項的析取值永為真。 2n-1 mi=m0 m1 m 2n-1T i=0,主析取范式,定義1-7.5：在給定公式的析取范式中，其簡單合取式都是小 項，則稱該范式為主析取范式。 例:P (QR) (PQ) (PR) 不是,可由兩種方法構成: 1)公式推導法 2)列表法,(PQR) (PQR) (PQR),由基本等價公式推出主析取范式。其推演步驟可歸納為： 化為析取范式 . 刪除永假的簡單合取式 化簡重復出現的變元（等冪律） (4) 補進未出現的變元（同一律） 添加(PP),然后利用分配律展開,公式推導法,例8 求(PQ) (PR) (QR)的主析取范式。,解 原式(PQ(RR) (PR(QQ) (QR(PP) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR),注意 主析取范式的唯一性,例9 求P(PQ) (QP)的主析取范式,解 原式 P(PQ) (QP) P(PQP) (QQP), P(PQP) (QP) P(QP), (P(QQ) (QP) (PQ) (PQ) (PQ),列表法,定理1-7.3: 在真值表中,一個公式的真值為T的指派所對應的小項的析取,即為此公式的主析取范式。,例6.求下列公式的主析取范式: P Q，PQ，(PQ)，A,PQ ,(PQ) (PQ) (P Q),PQ ,(PQ) (PQ) (PQ),(PQ) ,(PQ) (PQ) (PQ),A ,(PQ) (PQ),如： PQ M00(M0) PQ M10(M2),大項的概念,定義1-7.6 n個命題變元的析取式，稱作布爾析取或大項。其中每個變元與它的否定不能同時存在，但兩者必須出現且僅出現一次。,例如：PQ，PQ，PQ，PQ,下標表示法：命題變元按字典順序排列，命題變元對應0，變元的否定對應1。對大項依二進制編碼（或用十進制編碼）。,PQ M01(M1) PQ M11(M3),2. 主合取范式,大項的性質,每一大項當其真值指派與編碼相同時，其值為F，在其余指派情況下均為T。 (2)任意兩個不同大項的析取式為永真。 Mi Mj T (ij) (3)全體大項的合取式必為永假，記為： 2n-1 Mi = M0M1M2n-1 F i=0,主合取范式,定義1-7.7 對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則該等價式稱作原式的主合取范式。,同樣地求解主合取范式的方法也有兩種：列表法和公式推導法,定理1-7.4 在真值表中，一個公式的真值為F的指派所對應的大項的合取，即為此公式的主合取范式。,列表法,m11 m01,例 求（ PQ）Q的主合取范式與主析取范式,( PQ）（PQ）；(PQ) (PQ),M10 M 00,公式推導法,步驟： (1)化為合取范式 (2)刪除永真的合取項(簡單析取式) (3)化簡重復出現的變元（等冪律） (4)補進未出現的變元（同一律） (QQ),例11 化(PQ) (PR)為主合取范式,解 原式(PP) (PR) (QP) (QR) (PR) (QP) (QR) 合取范式, (PQR) (PQR) (PQR) (PQR) 課本上采用真值表法,(PR(QQ) (QP(RR) (PP) QR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR),3.主析取范式與主合取范式之間的關系,例如: (PQ)Q m1m3, 則(PQ)Q M0M2,由主析取范式求主合取范式的步驟: a.找出主析取范式中所沒有的小項下標 b.對a中下標,求其對應的大項 c.寫出b中所得大項的合取,即為該式的主合取范式.,求(ABC) (A (BC)的主析（合）取范式。,解 原式(A(BC) (ABC) (A(BC) (AABC) (A(A(BC) (BC) (ABC) ) (BC) (A(BC),(ABC) (ABC) =m000m111=0,7,解1 利用主析取范式與主合取范式之間的關系 原式 1，2，3，4，5，6,4. 主范式的應用,(1)用以判定為何種公式. 設A為含n個變元的主范式： a. 若A T，或A可化為與其等價的含 2n 個小項的主析取范式，則A為永真式。 b.若 A F，或A可化為與其等價的含 2n 個大項的主合取范式，則A為永假式。 c.若 A 不與F等價，且又不含 2n 個大項或者小項，則A為可滿足式。,例:判斷下列公式為何類公式(PQ)Q (PQ)Q M0M2 m1m3;大小項數目均不到4,故為可滿足式. (2)證明等價式成立:主范式相同，則給定的兩個命題公式等價 例 A(A(AB), AB(AB),1-8 推理理論,在邏輯學中，把從前提出發，依據公認的推理規則，推導出一個結論，這一過程稱為有效推理或形式證明。所得的結論叫有效結論。,在數理邏輯中，集中研究的是用來從前提導出結論的推理規則和論證原理。這里最關心的不是結論的真實性，而是推理的有效性。與這些規則有關的理論稱為推理理論。,定義1-8. 1：設A和C是兩個命題公式，當且僅當AC為一重言式，即AC，稱C是A的有效結論。,這個定義可推廣到有n個前提的情況。,設H1，H2，Hn，C是命題公式，當且僅當 H1H2HnC 稱C是一組前提H1，H2，Hn的有效結論。,一、基本定義,(1) 真值表法,二、論證方法,判斷有效結論的過程就是論證過程，論證方法基本分為,設P1，Pm是出現于前提H1，Hn和結論C中的全部命題變元，列出這個真值表，即可看出H1H2HnC是否成立。,例1：一份統計報表的錯誤，或者是材料不可靠，或是因計算錯誤，這份報表有錯不是材料不可靠，所以這份報表是由于計算有錯誤。,P(PQ)Q,解：P：材料不可靠 Q：計算錯誤,由一組前提、公認的推理規則，利用已知的等價或蘊含公式，推出有效的結論。,(2)直接證法：,P規則：前提在推導中的任何時候都可引入使用。常用的蘊含式和等價式見表P43。,T規則：前面已導出的有效結論可作為后續推導引入。,例2：證明( PQ)(PR)(QS)SR,(1) PQ P,(2) PQ T(1)E,(3) QS P,(4) PS T(2)(3)I,(5) SP T(4)E,(6) PR P,(7) SR T(5)(6)I,(8) SR T(7)E,定義1-8.2：假設公式H1，H2，Hn中的命題變元為P1，P2，Pm的一些真值指派，如果能使H1H2Hn的真值為T ，則稱公式H1，H2，Hn是相容的。如果對于P1，P2，Pm的每一組真值指派，使得H1H2Hn的真值均為F，則稱公式H1，H2，Hn是不相容的。,(3) 間接證法,設要證：H1H2HnC，記為SC。,即證其逆反式CS為永真，,即CS為永真，,故CS為永假，,所以要證H1H2HnC。,只要證明C與 H1H2Hn是不相容的。,例3：證明AB， (BC)可邏輯推出A,(1) AB P,(2) A P(附加前提),(3) (BC) P,(4) B C T(3) E,(5) B T(1),(2),I,(6) B T(4) I,(7) BB T(5),(6) I,若要證：H1H2Hn(RC)，記為SRC,CP規則：結論為RC時，R作為附加前提引入，推出后件C。,因為S(RC) S(RC),(SR) C,(SR)C,(SR) C,將R作為附加前提，如有(SR)C，即證得S(RC)。,例4：證明A(BC)，DA，B蘊含DC,(1) D P(附加前提),(2) DA P,(3) A T(1),(2) I,(4) A(BC) P,(5) BC T(3),(4) I,(6) B P,(7) C T(5),(6) I,(8) DC CP,推理理論： 1、真值表法： 2、直接證法：P規則，T規則。 3、間接證法：利用不相容的概念，CP規則。,1.命題及其表示法 基本概念：命題 命題標識符:命題變元，命題常量 真值：T和F,1和0 重點：命題的判斷 （這句話是對的） 2.聯結詞 基本概念：聯接詞的定義及使用( ) 最小聯結詞組（,）（, ） 重點：聯結詞的使用,第一章小結,練習1 1、判斷是否為命題 1)4+x=5. 2)若x=1,則x+1=5。 2、將下列命題符號化 1）氣候很好或很熱 2）天氣炎熱但濕度較低 3）控制臺打字機即可作輸入設備，又可作輸出設備 4）要求有使用C+或Java的經驗,3.命題公式與翻譯 基本概念：命題公式（合式公式），命題的翻譯（命題公式符號化 ） 重點：命題的翻譯 4.真值表與等價公式 基本概念：真值表（真值指派），等價公式，子公式 重點：真值表的列法，等價公式的證明，16個命題定律,練習2 1、用符號形式寫出下列命題 a)假如上午不下雨，我去看電影，否則就在家里讀書或看報 b)我今天進城，除非下雨 c)僅當你走我將留下 2、列出真值表 (PQ)(PQ R),練習2 3、試證下式為重言式 (AB)(BC) (CA)(AB) (BC) (CA),5.重言式與蘊含式 基本概念：重言式，矛盾式，可滿足式，蘊含式 重點：重言式、矛盾式、可滿足式的判斷，等價公式 的證明，蘊含式的證明，14個