資源描述：
《離散數(shù)學(xué) 命題邏輯3.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第一章命題邏輯范式命題與聯(lián)結(jié)詞析取范式與合取范式主析取范式和主合取范式范式的引入同一命題公式可以有多種相互等價(jià)的表達(dá)形式，例如：P?Q??P∨Q??(P∧?Q)方便研究工作，需要將命題公式規(guī)范化，即制定范式。[定義]基本合取項(xiàng)(式)單個(gè)命題變?cè)?、單個(gè)命題變?cè)姆穸ɑ蛘呷舾蓚€(gè)命題變?cè)蚱浞穸ǖ暮先?gòu)成的命題公式稱(chēng)為基本合取項(xiàng)。如P，?Q，P∧Q，?P∧Q∧R[定義]基本析取項(xiàng)(式)單個(gè)命題變?cè)?、單個(gè)命題變?cè)姆穸ɑ蛘呷舾蓚€(gè)命題變?cè)蚱浞穸ǖ奈鋈?gòu)成的命題公式稱(chēng)為基本析取項(xiàng)。如P，?Q，P∨Q，?P
2、∨Q∨?R析取范式、合取范式[定義]析取范式一個(gè)命題公式A稱(chēng)為析取范式，當(dāng)且僅當(dāng)它具有形式如A1∨A2∨···∨An(n≥1)其中A1，A2，···，An是基本合取項(xiàng)。例如：(┓P∧Q)∨(P∧Q∧R)∨┓R[定義]合取范式一個(gè)命題公式稱(chēng)為合取范式，當(dāng)且僅當(dāng)它具有形式B1∧B2∧···∧Bn(n≥1)其中B1，B2，···，Bn是基本析取項(xiàng)。例如：(P∨┓Q(chēng))∧(Q∨R)∧(┓P∨┓Q(chēng)∨R)析取與合取范式定理定理：任意一個(gè)命題公式都可化為析取(合取)范式。證明思路：包含→，?，?的命題公式可化為
3、只有?，┐和?的命題公式。括號(hào)前的┐符號(hào)可通過(guò)德.摩根定律放到每個(gè)命題變?cè)懊?。利用分配率：P?（Q?R）?（P?Q）?（P?R）可得析取范式。范式的求法——命題(等價(jià))演算法利用常用的邏輯等價(jià)公式將命題公式轉(zhuǎn)換成符合析取范式的形式。步驟：（1）將命題公式中的聯(lián)結(jié)詞都轉(zhuǎn)化成∧、∨及┓。（2）利用德?摩根律，將┓符號(hào)移到各個(gè)命題變?cè)那懊?。?）利用分配律、結(jié)合律將公式轉(zhuǎn)化為合取范式或析取范式。（4）（添加）（4.1）若轉(zhuǎn)化為析取范式，則刪除永假的基本合取項(xiàng)，重復(fù)的基本合取項(xiàng)只保留一個(gè)。（4.2）
4、若轉(zhuǎn)化為合取范式，則刪除永真的基本析取項(xiàng)，重復(fù)的基本析取項(xiàng)只保留一個(gè)。重要的邏輯等價(jià)公式P?Q??P∨QP?Q?(P∧Q)∨(┐P∧┐Q)?(P∨┐Q)∧(┐P∨Q)P▽Q?(P∧┐Q)∨(Q∧┐P)?(P∨Q)∧(┐P∨┐Q)等價(jià)演算法：求析取范式舉例例1：求?(P∨Q)?(P∧Q)的析取范式。解:∵(A?B)?(A∧B)∨(?A∧?B)∴原式?(?(P∨Q)∧(P∧Q))∨((P∨Q)∧?(P∧Q))/*消去?*/?(?P∧?Q∧P∧Q)∨((P∨Q)∧(?P∨?Q))/*德?摩根律*/?(
5、?P∧?Q∧P∧Q)∨(P∧?P)∨(Q∧?P)∨(P∧?Q)∨(Q∧?Q)/*分配律，析取范式*/?(?P∧Q)∨(P∧?Q)/*消去重復(fù)項(xiàng)和值為0的項(xiàng)*/等價(jià)演算法：求合取范式舉例例2：求(P∧(Q?R))?S的合取范式。解:(P∧(Q?R))?S??(P∧(?Q∨R))∨S/*消去?*/?(?P∨?(?Q∨R))∨S/*德?摩根律*/??P∨(Q∧?R)∨S/*德?摩根律*/?(?P∨Q∨S)∧(?P∨?R∨S)/*分配律，沒(méi)有需要消去的項(xiàng)*/注意：（1）范式不一定唯一一個(gè)命題公式的合取范
6、式或析取范式并不是唯一的。例：求(P?Q)?P的析取范式和合取范式。解：(P?Q)?P???(?P∨Q)∨P/*消去?*/??(P∧?Q)∨P/*摩根律，析取范式*/??P(析取范式)/*吸收率*/(P?Q)?P??(P∧?Q)∨P(析取范式)??(P∨P)∧(?Q∨P)(合取范式)??P∧(?Q∨P)(合取范式)注意：（2）析取范式與合取范式有可能同一請(qǐng)判斷下列命題公式是析取范式還是合取范式？p??q?r?p?q??r回答：既是析取范式，又是合取范式。一個(gè)基本合取項(xiàng)或基本析取項(xiàng)既是析取范式，又
7、是合取范式。命題與聯(lián)結(jié)詞析取范式與合取范式主析取范式和主合取范式1.極小項(xiàng)[定義]極小項(xiàng)由n個(gè)命題變?cè)蚱浞穸ǖ暮先〗M成的基本合取項(xiàng)，稱(chēng)為n個(gè)變?cè)臉O小項(xiàng)，在一個(gè)極小項(xiàng)中每個(gè)變?cè)c它的否定兩者之一必須出現(xiàn)且僅出現(xiàn)一次。例如：兩個(gè)命題變?cè)猵和q構(gòu)成的極小項(xiàng)為：p?qp??q?p?q?p??q三個(gè)變?cè)猵、q和r的極小項(xiàng)為：?p??q??r?p??q?r?p?q??r?p?q?rp??q??rp??q?rp?q??rp?q?r思考：包含n個(gè)給定變?cè)臉O小項(xiàng)共有幾個(gè)？回答：2n個(gè)2.極大項(xiàng)[定義]極大項(xiàng)
8、n個(gè)命題變?cè)蚱浞穸ǖ慕M成的基本析取項(xiàng)，稱(chēng)為n個(gè)變?cè)臉O大項(xiàng)，在一個(gè)極大項(xiàng)中，每個(gè)變?cè)c它的否定兩者之一必須出現(xiàn)且僅出現(xiàn)一次。例如：兩個(gè)命題變?cè)猵和q構(gòu)成的極大項(xiàng)為：p?qp??q?p?q?p??q三個(gè)變?cè)猵、q和r的極大項(xiàng)為：p?q?rp?q??rp??q?rp??q??r?p?q?r?p?q??r?p??q?r?p??q??r注意：一般地，極小項(xiàng)和極大項(xiàng)中的變?cè)醋帜感蚺帕小Ｋ伎迹喊琻個(gè)命題變?cè)臉O大項(xiàng)共有幾個(gè)？回答：2n個(gè)極小項(xiàng)和極大項(xiàng)性質(zhì)每個(gè)極小項(xiàng)都只對(duì)應(yīng)一組真值指派，使得該極小項(xiàng)的真
