資源描述：
《離散數(shù)學(xué)-命題邏輯3.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、最小聯(lián)結(jié)詞組指可表示出其它所有聯(lián)結(jié)詞的最小聯(lián)結(jié)詞集合。如：{┒，∨}，{┒，∧}，{↑}，{↓}都可構(gòu)成最小聯(lián)結(jié)詞組。例：寫出P∨Q分別用{┒，∧}，{↑}，{↓}表示的等價(jià)式。解：(1)用{┒，∧}表示的等價(jià)式P∨Q?┒(┒P∧┒Q)德.摩根定理(2)用{↑}表示的等價(jià)式P∨Q?┒(┒P∧┒Q)德.摩根定理?(┒P)↑(┒Q)?(P↑P)↑(Q↑Q)(3)用{↓}表示的等價(jià)式P∨Q?┒(P↓Q)?(P↓Q)↓(P↓Q)對(duì)偶與范式從上節(jié)可看到命題公式的最小聯(lián)結(jié)詞組為{┒,∨}或{┒,∧}，但實(shí)際上為了使用方便，命題公式常常同時(shí)包含{┒,∨,∧}。我們認(rèn)為這樣的公式∨與∧存在對(duì)偶規(guī)律。定義1-
2、7、1在給定的命題公式中，將聯(lián)結(jié)詞∨換成∧，將∧換成∨，若有特殊變?cè)狥和T亦相互取代，所得公式A*稱為A的對(duì)偶式。顯然A也是A*的對(duì)偶式。例題1寫出下列表達(dá)式的對(duì)偶式。（A）（B）（C）例題2求的對(duì)偶式定理1-7.1設(shè)A和A*是對(duì)偶式，P1，P2，…，Pn是出現(xiàn)在A和A*中的原子變?cè)?，則定理1-7.2設(shè)P1，P2，…，Pn是出現(xiàn)在公式A和B中的所有原子變?cè)?，如果A?B，則A*?B*。定義7、2一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有型式：其中A1，A2，…An都是由命題變?cè)蚱浞穸ㄋM成的析取式。定義7、3一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有型式：其中A1，A2，…An都是由命題變?cè)蚱?/p>
3、否定所組成的合取式。注：任何一個(gè)命題公式，求它的合取范式或析取范式，可以通過(guò)下面三個(gè)步驟進(jìn)行：（1）將公式中的聯(lián)結(jié)詞化歸成∧，∨及┒。（2）利用德·摩根律將否定符號(hào)┒直接到各個(gè)命題變?cè)?。?）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。例題3求的合取范式。例題4求的析取范式。定義1-7、4n個(gè)命題變?cè)暮先∈?，稱作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。注：小項(xiàng)有如下幾個(gè)性質(zhì)：（1）每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為T，在其余2n-1種指派情況下均為F。（2）任意兩個(gè)不同小項(xiàng)的合取式永假。（3）全體小項(xiàng)的析取式永為真，記為：定義1-
4、7、5對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取所組成，則該等價(jià)式稱作原式的主析取范式。定理1-7、3在真值表中，一個(gè)公式的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式的主析取范式。例題5給定P→Q，P∨Q和┒(P∧Q)，求這些公式的主析取范式。例題6求的主析取范式。由上例我們看到，一個(gè)命題公式的主析取范式，可由兩種方法構(gòu)成。一是由公式的真值表得出，另一是由基本等價(jià)公式推出。其推演步驟可歸納為：（1）化歸為析取范式。（2）除去析取范式中所有永假的析取項(xiàng)。（3）將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變?cè)喜ⅰ＃?）對(duì)合取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添?P∨┒P)式，然后，應(yīng)用分配律
5、展開公式。定義1-7、6n個(gè)命題變?cè)奈鋈∈?，稱作布爾析取或大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。注：大項(xiàng)有如下性質(zhì)：（1）每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為F，在其余2n-1種指派情況下均為T。（2）任意兩個(gè)不同大項(xiàng)的析取式為永真。（3）全體大項(xiàng)的合取式永為假，記為：定義1-7、7對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由大項(xiàng)的合取所組成，則該等價(jià)式稱作原式的主合取范式。定理1-7、4在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。例給定P→Q，P∨Q和┒(P∧Q)，求這些公式的主合取范式解：PQP→QP∨Q┒(
6、P∧Q)TTTTFTFFTTFTTTTFFTFT注意:T對(duì)應(yīng)變?cè)姆穸?，F(xiàn)對(duì)應(yīng)變?cè)ⅲ阂粋€(gè)公式的主合取范式，亦可用基本等價(jià)式推出，其推演步驟為：（1）化歸為合取范式。（2）除去合取范式中所有為永真的合取項(xiàng)。（3）合并相同的析取項(xiàng)和相同的變?cè)＃?）對(duì)析取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添?P∧┒P)式，然后，應(yīng)用分配律展開公式。例題7化為主合取范式。BACK注意:任何式子的主析取范式和主合取范式只需 要求得其一即可.例：求（P?Q）?（?Ｐ?Ｒ）主析取范式和主合取范式由前例，該式的主合取范式為(?Ｐ?Ｑ??Ｒ)?(?Ｐ?Ｑ?Ｒ)?(Ｐ??Ｑ?Ｒ)?(Ｐ?Ｑ?Ｒ)其編碼為１０１,１００,０１０
7、,０００即０,２,４,５所以（P?Q）?（?Ｐ?Ｒ）?（?Ｐ?Ｑ??Ｒ）?（?Ｐ?Ｑ?Ｒ）?（Ｐ??Ｑ?Ｒ）?（Ｐ?Ｑ?Ｒ）=?０，２，４，５??１，３，６，７=（?Ｐ??Ｑ?Ｒ）?（?Ｐ?Ｑ?Ｒ）?（Ｐ?Ｑ??Ｒ）?（Ｐ?Ｑ?Ｒ）本節(jié)結(jié)束例1解：這些表達(dá)式的對(duì)偶式是：（A）(P∧Q)∨R（B）(P∨Q)∧F（C）┒(P∧Q)∨(P∧┒(Q∨┒S))例2解：因?yàn)镻↑Q?┒(P∧Q)，故P↑Q的對(duì)偶式為┒(P∨
