趙洪鑾《離散數(shù)學(xué)》第一章7-8節(jié).ppt

復(fù)習(xí),真值表 等價(jià)公式 證明方法（真值表、公式證明法）,16組重要等值式,1、雙重否定律 P P 2、冪等律 P P P P P P 3、交換律 P QQ P P Q Q P 4、結(jié)合律 (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、蘊(yùn)涵等值式 PQ P Q 13、等價(jià)等值式 P Q （PQ） （QP） 14、假言易位 PQ Q P 15、等價(jià)否定等值式 P Q P Q 16、歸謬論 （PQ） （ P Q ） P,記憶技巧：借助 集合的運(yùn)算式， 看成并， 看 成交， 看成 補(bǔ)，T看成全集， F看成空集， 再加12-16條。,其他等價(jià)公式,其他聯(lián)接詞 (1) P Q (P Q); 雙條件否定(不可兼析取或,異或) (2) P Q (P Q); 條件否定 (3) P Q (P Q); 與非 (4) P Q (P Q); 或非,1-7 對(duì)偶與范式,對(duì)偶 范式,一、對(duì)偶式,定義1-7.1：在給定的僅含有, , 的命題公式中，將換成，將換成，T和F互換，所得公式A稱為A的對(duì)偶式。,例1：寫出（PQ） R的對(duì)偶式,解：對(duì)偶式為 （PQ） R,寫出（P Q）T， PFT的對(duì)偶式,定理1-7.2: 設(shè)P1,P2, Pn是出現(xiàn)在公式A和B中的所有原子變?cè)?如果,A B,則A B.,二. 公式的標(biāo)準(zhǔn)型范式,1. 范式,定義1-7.2：一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有 A1A2An 其中A1,A2, ,An都是由命題變?cè)蚱浞穸ㄋM成的析取式.,定義1-7.3: 一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有 A1A2An 其中A1,A2, ,An都是由命題變?cè)蚱浞穸ㄋM成的合取式.,例如: (PQR) (PQ) Q P(PQ)(PQR),合取范式,析取范式,步驟,可以通過下面3個(gè)步驟將任一命題公式化為合取范式或析取范式： 將公式中的聯(lián)結(jié)詞化歸成，及； 利用德.摩根律將否定符號(hào)直接移到各個(gè)命題變?cè)埃?利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。,例5: 求（P（Q R）S 的析取范式和合取范式,解：原公式 (P（QR）)S,（P（QR）S, P（QR）S, （PSQ）（PSR）,析取范式,合取范式,所以 原式(PQ) (PQ) (PQ) (PQ),例6: 求(PQ) (PQ)的析取范式。,解：因?yàn)?(A B) (AB) (AB),(P QPQ) (PQ) (PQ),(P QPQ) (PP) (PQ) (QP) (QQ),注意：任一命題公式都可以化為合取范式或析取范式的形式,2. 范式的應(yīng)用,利用范式對(duì)公式進(jìn)行判斷： (1)公式A為永假式的充要條件是A的析取范式中每個(gè)簡單合取式至少包含一個(gè)命題變?cè)捌浞穸ā?例：A(P1,P2,Pn) (P1 P1 ) (P2 P2 ) (2)公式A為永真式的充要條件是A的合取范式中每個(gè)簡單析取式至少包含一個(gè)命題變?cè)捌浞穸ā?例：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) 分配律,對(duì)識(shí)別公式是否等價(jià)帶來一定困難， 解決方式：主范式,1. 主析取范式,小項(xiàng)的概念 定義1-7.4: n個(gè)命題變?cè)暮先∈?，稱作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。,例如：PQ，PQ，PQ，PQ 是 PQ P 不是 問題：n個(gè)變?cè)捎卸嗌傩№?xiàng)？,三.公式的主范式,見課本P33表1-7.2，三個(gè)變?cè)那闆r,下標(biāo)表示法：命題變?cè)醋值漤樞蚺帕?，命題變?cè)獙?duì)應(yīng)1，變?cè)姆穸▽?duì)應(yīng)0。對(duì)小項(xiàng)依二進(jìn)制編碼（或用十進(jìn)制編碼）。,如： PQ,PQ,m11(m3),m01(m1),PQ,m10(m2),PQ,m00(m0),小項(xiàng)的性質(zhì)：,(1)每一小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為T，在其余指派情況下均為F。 (2)任意兩個(gè)不同小項(xiàng)的合取為假。 例：m110m100 =(PQR) (PQR) PPQRR F (3)全體小項(xiàng)的析取值永為真。 2n-1 mi=m0 m1 m 2n-1T i=0,主析取范式,定義1-7.5：在給定公式的析取范式中，其簡單合取式都是小 項(xiàng)，則稱該范式為主析取范式。 例:P (QR) (PQ) (PR) 不是,可由兩種方法構(gòu)成: 1)公式推導(dǎo)法 2)列表法,(PQR) (PQR) (PQR),由基本等價(jià)公式推出主析取范式。其推演步驟可歸納為： 化為析取范式 . 刪除永假的簡單合取式 化簡重復(fù)出現(xiàn)的變?cè)ǖ葍缏桑?(4) 補(bǔ)進(jìn)未出現(xiàn)的變?cè)ㄍ宦桑?添加(PP),然后利用分配律展開,公式推導(dǎo)法,例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: 在真值表中,一個(gè)公式的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取,即為此公式的主析取范式。,例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),大項(xiàng)的概念,定義1-7.6 n個(gè)命題變?cè)奈鋈∈?，稱作布爾析取或大項(xiàng)。其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。,例如：PQ，PQ，PQ，PQ,下標(biāo)表示法：命題變?cè)醋值漤樞蚺帕?，命題變?cè)獙?duì)應(yīng)0，變?cè)姆穸▽?duì)應(yīng)1。對(duì)大項(xiàng)依二進(jìn)制編碼（或用十進(jìn)制編碼）。,PQ M01(M1) PQ M11(M3),2. 主合取范式,大項(xiàng)的性質(zhì),每一大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其值為F，在其余指派情況下均為T。 (2)任意兩個(gè)不同大項(xiàng)的析取式為永真。 Mi Mj T (ij) (3)全體大項(xiàng)的合取式必為永假，記為： 2n-1 Mi = M0M1M2n-1 F i=0,主合取范式,定義1-7.7 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由大項(xiàng)的合取所組成，則該等價(jià)式稱作原式的主合取范式。,同樣地求解主合取范式的方法也有兩種：列表法和公式推導(dǎo)法,定理1-7.4 在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。,列表法,m11 m01,例 求（ PQ）Q的主合取范式與主析取范式,( PQ）（PQ）；(PQ) (PQ),M10 M 00,公式推導(dǎo)法,步驟： (1)化為合取范式 (2)刪除永真的合取項(xiàng)(簡單析取式) (3)化簡重復(fù)出現(xiàn)的變?cè)ǖ葍缏桑?(4)補(bǔ)進(jìn)未出現(xiàn)的變?cè)ㄍ宦桑?(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.主析取范式與主合取范式之間的關(guān)系,例如: (PQ)Q m1m3, 則(PQ)Q M0M2,由主析取范式求主合取范式的步驟: a.找出主析取范式中所沒有的小項(xiàng)下標(biāo) b.對(duì)a中下標(biāo),求其對(duì)應(yīng)的大項(xiàng) c.寫出b中所得大項(xiàng)的合取,即為該式的主合取范式.,求(ABC) (A (BC)的主析（合）取范式。,解 原式(A(BC) (ABC) (A(BC) (AABC) (A(A(BC) (BC) (ABC) ) (BC) (A(BC),(ABC) (ABC) =m000m111=0,7,解1 利用主析取范式與主合取范式之間的關(guān)系 原式 1，2，3，4，5，6,4. 主范式的應(yīng)用,(1)用以判定為何種公式. 設(shè)A為含n個(gè)變?cè)闹鞣妒剑?a. 若A T，或A可化為與其等價(jià)的含 2n 個(gè)小項(xiàng)的主析取范式，則A為永真式。 b.若 A F，或A可化為與其等價(jià)的含 2n 個(gè)大項(xiàng)的主合取范式，則A為永假式。 c.若 A 不與F等價(jià)，且又不含 2n 個(gè)大項(xiàng)或者小項(xiàng)，則A為可滿足式。,例:判斷下列公式為何類公式(PQ)Q (PQ)Q M0M2 m1m3;大小項(xiàng)數(shù)目均不到4,故為可滿足式. (2)證明等價(jià)式成立:主范式相同，則給定的兩個(gè)命題公式等價(jià) 例 A(A(AB), AB(AB),1-8 推理理論,在邏輯學(xué)中，把從前提出發(fā)，依據(jù)公認(rèn)的推理規(guī)則，推導(dǎo)出一個(gè)結(jié)論，這一過程稱為有效推理或形式證明。所得的結(jié)論叫有效結(jié)論。,在數(shù)理邏輯中，集中研究的是用來從前提導(dǎo)出結(jié)論的推理規(guī)則和論證原理。這里最關(guān)心的不是結(jié)論的真實(shí)性，而是推理的有效性。與這些規(guī)則有關(guān)的理論稱為推理理論。,定義1-8. 1：設(shè)A和C是兩個(gè)命題公式，當(dāng)且僅當(dāng)AC為一重言式，即AC，稱C是A的有效結(jié)論。,這個(gè)定義可推廣到有n個(gè)前提的情況。,設(shè)H1，H2，Hn，C是命題公式，當(dāng)且僅當(dāng) H1H2HnC 稱C是一組前提H1，H2，Hn的有效結(jié)論。,一、基本定義,(1) 真值表法,二、論證方法,判斷有效結(jié)論的過程就是論證過程，論證方法基本分為,設(shè)P1，Pm是出現(xiàn)于前提H1，Hn和結(jié)論C中的全部命題變?cè)?，列出這個(gè)真值表，即可看出H1H2HnC是否成立。,例1：一份統(tǒng)計(jì)報(bào)表的錯(cuò)誤，或者是材料不可靠，或是因計(jì)算錯(cuò)誤，這份報(bào)表有錯(cuò)不是材料不可靠，所以這份報(bào)表是由于計(jì)算有錯(cuò)誤。,P(PQ)Q,解：P：材料不可靠 Q：計(jì)算錯(cuò)誤,由一組前提、公認(rèn)的推理規(guī)則，利用已知的等價(jià)或蘊(yùn)含公式，推出有效的結(jié)論。,(2)直接證法：,P規(guī)則：前提在推導(dǎo)中的任何時(shí)候都可引入使用。常用的蘊(yùn)含式和等價(jià)式見表P43。,T規(guī)則：前面已導(dǎo)出的有效結(jié)論可作為后續(xù)推導(dǎo)引入。,例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：假設(shè)公式H1，H2，Hn中的命題變?cè)獮镻1，P2，Pm的一些真值指派，如果能使H1H2Hn的真值為T ，則稱公式H1，H2，Hn是相容的。如果對(duì)于P1，P2，Pm的每一組真值指派，使得H1H2Hn的真值均為F，則稱公式H1，H2，Hn是不相容的。,(3) 間接證法,設(shè)要證：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規(guī)則：結(jié)論為RC時(shí)，R作為附加前提引入，推出后件C。,因?yàn)镾(RC) S(RC),(SR) C,(SR)C,(SR) C,將R作為附加前提，如有(SR)C，即證得S(RC)。,例4：證明A(BC)，DA，B蘊(yùn)含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規(guī)則，T規(guī)則。 3、間接證法：利用不相容的概念，CP規(guī)則。,1.命題及其表示法 基本概念：命題 命題標(biāo)識(shí)符:命題變?cè)?，命題常量 真值：T和F,1和0 重點(diǎn)：命題的判斷 （這句話是對(duì)的） 2.聯(lián)結(jié)詞 基本概念：聯(lián)接詞的定義及使用( ) 最小聯(lián)結(jié)詞組（,）（, ） 重點(diǎn)：聯(lián)結(jié)詞的使用,第一章小結(jié),練習(xí)1 1、判斷是否為命題 1)4+x=5. 2)若x=1,則x+1=5。 2、將下列命題符號(hào)化 1）氣候很好或很熱 2）天氣炎熱但濕度較低 3）控制臺(tái)打字機(jī)即可作輸入設(shè)備，又可作輸出設(shè)備 4）要求有使用C+或Java的經(jīng)驗(yàn),3.命題公式與翻譯 基本概念：命題公式（合式公式），命題的翻譯（命題公式符號(hào)化 ） 重點(diǎn)：命題的翻譯 4.真值表與等價(jià)公式 基本概念：真值表（真值指派），等價(jià)公式，子公式 重點(diǎn)：真值表的列法，等價(jià)公式的證明，16個(gè)命題定律,練習(xí)2 1、用符號(hào)形式寫出下列命題 a)假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào) b)我今天進(jìn)城，除非下雨 c)僅當(dāng)你走我將留下 2、列出真值表 (PQ)(PQ R),練習(xí)2 3、試證下式為重言式 (AB)(BC) (CA)(AB) (BC) (CA),5.重言式與蘊(yùn)含式 基本概念：重言式，矛盾式，可滿足式，蘊(yùn)含式 重點(diǎn)：重言式、矛盾式、可滿足式的判斷，等價(jià)公式 的證明，蘊(yùn)含式的證明，14個(gè)