老師第一章命題邏輯-3rd

1、對(duì)偶原理定義：設(shè)有公式A，其中對(duì)偶原理定義：設(shè)有公式A，其中僅含有邏輯聯(lián)結(jié)詞, , 和邏輯常T和F。在中將, ,T , F分別換以, , F,T，得公式則稱A*為的對(duì)偶式注意:式是相互舉例P(QPP的對(duì)偶對(duì)偶原理定理1.5-1 設(shè)A和A*互為對(duì)偶式，P, P 對(duì)偶原理定理1.5-1 設(shè)A和A*互為對(duì)偶式，P, P ,L, P A和A*中所有命題變?cè)?，于是nA(P,P,L,P ) A*(P,P,L,Pn12nA(P,P,L,P)A*(P,P,L,P12nn證明 由德PQ (PPQ (P律 可知，對(duì)公式A求否定，直到深入到命題變?cè)拔恢?，在這個(gè)過程中，所有的變， 變 ，T變F， 對(duì)偶原理定理1.

2、5-若A B，且、B為命題變?cè)?P2,LPn對(duì)偶原理定理1.5-若A B，且、B為命題變?cè)?P2,LPn詞的公式，則A* 證明：AB 意味AP1P2,PnB1P2,Pn)A(P1,P2,Pn)B(P1,P2,Pn于是永由定理1.5-1知，下式也永真Pi(i1,2,利用帶入規(guī)則，以永A(P,P,P) B(P,P,P nn 對(duì)偶原理若(P Q對(duì)偶原理若(P QPPQ) PQ，試證(PQ)(P(PQ) P證明：A (P Q)(P(PBP (PQ)(P(PP則A因此，A* 對(duì)偶原理試證明)(PQ對(duì)偶原理試證明)(PQPQ(2)(P Q)(PQ) (P(P Q)(P (PQ)(PQ)(P (PQ)(P

3、Q)(PE11, (PQ)(PQ)(PQ)(P (PQPQ)(P QP (PT)(QTE17,T E17,對(duì)偶原理試證明對(duì)偶原理試證明)(PQPQ(2)(P Q)(PQ) (P(PQ)(PQ)(P由(PQP(PQ)(PQ)(PE11,知(P QPQ)和(P QPQ)互為對(duì)偶式(PQ)(PQ) 對(duì)偶原理定理1.5-對(duì)偶原理定理1.5-的公式，則B*ABB(P1,P2,Pn)A(P1,P2,Pn根據(jù)定理1.5-BP1P2,Pn) AP1P2,Pn永i 利用帶入規(guī)則，以Pi (i 1,2 1.6范式和判定1.6范式和判定問題公式的標(biāo)準(zhǔn)形式范式用來在有限步內(nèi)判定公式永真、永假、可滿析取范式和合取范式定

4、義若一個(gè)析取范式和合取范式定義若一個(gè)命題公式是一些命題變?cè)捌浞穸ǖ姆e，則稱之為基本積；若這個(gè)命題公式是一些變?cè)捌浞穸ㄖ停Q為基本和。一個(gè)由基本積的和組成的公式，如果與給定的公式A等價(jià)，則稱它是A的析取范式。析取范式：PQPQPQ,(PQP題公式A一個(gè)由基本和的積組成的公式，如果與給定價(jià)，則稱它是A的合取范式。合取范式：PPQQPQ,(PQP析取范式和合取范式定理1.6-一個(gè)基本積是永假式，當(dāng)且僅當(dāng)它含PP形式的兩個(gè)因子證明：析取范式和合取范式定理1.6-一個(gè)基本積是永假式，當(dāng)且僅當(dāng)它含PP形式的兩個(gè)因子證明：QF （充分性）由于永假式P形式的兩個(gè)因子時(shí)基本積是，所以含永假式P （必要性）

5、用反證法。設(shè)基本積為假但不含 形式的因子，于是給這個(gè)基本積中題變?cè)概烧嬷礣，給帶有否定本積的真值是T題變?cè)概烧嬷礔，得基析取范式和合取范式定理1.6-2析取范式和合取范式定理1.6-2:一個(gè)基本和是永真式，當(dāng)且僅P, P 形式的兩個(gè)因子析取范式和合取范式例：求命題公式PR）的析取范式P析取范式和合取范式例：求命題公式PR）的析取范式PP Q解/*這是一個(gè)合取范式P Q） （P/*使用與對(duì)或的分配律，化成析取范式析取范式與合取范式析取范式與合取范式Q)(P(PQ)/*使用或?qū)εc的分配律及補(bǔ)余律，現(xiàn)在是合析取范式和析取范式和合取范式例：求(P Q) (P Q)的析取范式解：(PQ) (P (P

6、Q)(PQ)(PQ)(P (PQPQ)(PQ)(P F (PQ)(P (PQ)(P (PQ)P)(PQ) PPPQPQQ F PQPQ (PQ)(P析取范式和析取范式和合取范式例：求(PQ) (P Q)的合取范式解：令A(yù) (PQ (PQ)A (PQ) (P (PQ)(PQ)(PQ)(P (PQPQ)(PQ)(PPQP由于A A(PQP所以A (PQP主析取范式定義1.6-4：在含n個(gè)主析取范式定義1.6-4：在含n個(gè)變?cè)幕痉e中若每個(gè)變?cè)c其否定不同時(shí)存在，而者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本積為極小項(xiàng)。例兩個(gè)命題變?cè)狿、Q的極小項(xiàng)PPQ,PQ,Pn個(gè)變?cè)?，極小項(xiàng)個(gè)數(shù)主析取范式假定有P、

7、Q、主析取范式假定有P、Q、R三個(gè)變?cè)狿QP Q R P Q R P Q RPQ01234567主析取范式主析取范式每個(gè)極小項(xiàng)只有一個(gè)真值指派任何兩個(gè)極小項(xiàng)的合取必為假（因?yàn)樵诜N真值指派中，只有一個(gè)極小項(xiàng)取值為真所有極小項(xiàng)的析取必為真主析取范式定義主析取范式定義1.6-5：一個(gè)由極小項(xiàng)的和組成的公式，如果與命題公式A等價(jià)，則稱它是公式A的主析取范式對(duì)任何命題公式(永假式除外)都可求得與其等價(jià)的主析取范式，而且主析取范式的形主析取范式求主析取范式的方法：先化成與其等價(jià)的析取范式；主析取范式求主析取范式的方法：先化成與其等價(jià)的析取范式；若析取范式的基本積中同一命題變?cè)霈F(xiàn)多次，則將其化成只出現(xiàn)一次

8、；去掉析取范式中所有為永假式的基本積，即去掉基本積中含有形如PP的子公式的那些基本積；若析取范式中缺少某一命題變?cè)鏟，則可 并利用分配律展開，然后合并相同的基本積主析取范式A主析取范式A PQ(PQ)(RR)(PP)(PQR)(PQR)(PR)(P(PQR)(PQR)PR(Q(PR)(Q(PQR)(PQR)(PQ(PQR)(PQR)(PQ(PQR)(PQR)(PQ(PQR)(PQm7 m6 m5 m3 (1,3,5,6,主析取范式右圖APQ對(duì)應(yīng)的真值表：PQRPQ000P主析取范式右圖APQ對(duì)應(yīng)的真值表：PQRPQ000PQ0001PQ1010PQ0011PQ1100PQ0101PQ1110

9、PQ1111PQ1主合取范式定義1.6-6：在含n個(gè)主合取范式定義1.6-6：在含n個(gè)變?cè)幕竞椭腥裘總€(gè)變?cè)c其否定不同時(shí)存在，而者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本和為極大項(xiàng)。例兩個(gè)命題變?cè)狿、Q的極大項(xiàng)PPQ,PQ,Pn個(gè)變?cè)?，極大項(xiàng)個(gè)數(shù)主合取范式假定有P、Q、主合取范式假定有P、Q、R三個(gè)變?cè)狿 Q R PQR PQPQPQ01234567MM每個(gè)極大項(xiàng)只有一組真值指派使其為每個(gè)極大項(xiàng)只有一組真值指派使其為任何兩個(gè)極大項(xiàng)的析取必為真（因?yàn)樵诜N真值指派中，只有一個(gè)極大項(xiàng)取值為假所有極大項(xiàng)的合取必為假。主合取范定義1.6-7：一個(gè)由極大項(xiàng)的積組成的公式，主合取范定義1.6-7：一個(gè)由極大

10、項(xiàng)的積組成的公式，的主合取范式。對(duì)任何命題公式(永真式除外)都可求得與其等價(jià)的主合取范式，而且主合取范式的形主合取范式A主合取范式A PQ(PR)(Q(PR)(QQ)(QR)(P(PQR)(PQR)(PQ(PQ(PQR)(PQR)(PQ M0 M2 M(0,2,主合取范式右圖APQ對(duì)應(yīng)的真值表：PQRPQ000PQ主合取范式右圖APQ對(duì)應(yīng)的真值表：PQRPQ000PQ0001PQ1010PQ 0011PQ1100PQ0101PQ1110PQ 1111PQ1極小項(xiàng)和極大項(xiàng)的關(guān)系極小項(xiàng)和極大項(xiàng)的關(guān)系極小項(xiàng)mi和極大項(xiàng)M i下列的關(guān)系：Mimi 由合取（析?。┓妒角笾魑鋈∮珊先。ㄎ鋈。┓妒角笾魑鋈。ê先。┓妒蕉呖梢曰ハ噢D(zhuǎn)化已知公式A的主合取范式為：(PQR)(PQ求主析取范式。解A的主合取范式為M1M3，可知A的主析取式于是可直接寫出A的主析取(PQR)(P Q R)(P Q(PQR)(PQR)(PQ主析取范式和主合取范式一個(gè)命題公式是主析取范式和主合取范式一個(gè)命題公式是永真式，它題變?cè)乃袠O出現(xiàn)在其主析取范式中，不存在與其等價(jià)的主合取范一個(gè)命題公式是永假式，它題變?cè)袠O出現(xiàn)在其主合取范式中，不存在與其等價(jià)的主析取范式；一個(gè)命題公式是可滿足的，它既有與其等價(jià)的主析取范式，也有與其等價(jià)的主合取范主析取范式和主合取范式主析取范式和主合取范式)主析取范式和主合取范式例