離散數(shù)學(xué)命題邏輯4.ppt

《離散數(shù)學(xué)命題邏輯4.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、勿在浮沙筑高臺(tái)！38--1程序設(shè)計(jì)領(lǐng)域里，每一個(gè)人都想飛。但是，還沒有學(xué)會(huì)走之前，連怕跑都別想！勿在浮沙筑高臺(tái)！28七月2021勿在浮沙筑高臺(tái)！38--2單個(gè)的命題變元和一些命題變元的否定是一個(gè)基本和、基本積、析取范式、合取范式。單個(gè)的基本和是合取范式、析取范式單個(gè)的基本積是析取范式、合取范式析取范式、合取范式僅含聯(lián)結(jié)詞┐、∧、∨，且┐僅出現(xiàn)在命題變元前。結(jié)論從上述定義和例子可以得出如下關(guān)系：勿在浮沙筑高臺(tái)！38--3求一個(gè)命題公式的與之等價(jià)的析取范式和合取范式，其步驟如下：（1）利用恒等公式中的等值式和蘊(yùn)涵式將公式中的→、?用聯(lián)結(jié)詞┐、∧、∨來取代；（2）利用德?摩根定律將否定號(hào)

2、┐移到各個(gè)命題變元的前端；（3）利用結(jié)合律、分配律、吸收律、等冪律、交換律等將公式化成其等價(jià)的析取范式和合取范式。勿在浮沙筑高臺(tái)！38--4定義1.3-4在n個(gè)變元的基本積中,若每一個(gè)變元與其否定不同時(shí)存在,而兩者之一必出現(xiàn)一次且僅出現(xiàn)一次,則這種基本積叫極小項(xiàng)。1.3.2主析取范式和主合取范式勿在浮沙筑高臺(tái)！38--5對(duì)應(yīng)情況如下:P∧Q∧R——000——0P∧Q∧R——001——1P∧Q∧R——010——2P∧Q∧R——011——3P∧Q∧R——100——4P∧Q∧R——101——5P∧Q∧R——110——6P∧Q∧R—111—7勿在浮沙筑高臺(tái)！38--6我們把對(duì)應(yīng)的十進(jìn)制數(shù)當(dāng)作足標(biāo)

3、,用mi表示這一項(xiàng),即;m0P∧Q∧Rm1P∧Q∧Rm2P∧Q∧Rm3P∧Q∧Rm4P∧Q∧Rm5P∧Q∧Rm6P∧Q∧Rm7P∧Q∧R一般地,n個(gè)變元的極小項(xiàng)是:m0P1∧P2∧P3…∧Pnm1P1∧P2∧P3…∧Pn……m2n-1P1∧P2∧P3…∧Pn勿在浮沙筑高臺(tái)！38--7定義1.3-6在n個(gè)變元的基本和中,若每一個(gè)變元與其否定不同時(shí)存在,而二者之一必出現(xiàn)一次且僅出現(xiàn)一次,則這種基本和叫極大項(xiàng)。n個(gè)變元可構(gòu)成2n個(gè)不同的極大項(xiàng)。類似于(但不同)極小項(xiàng)的記法,它們是:M0P1∨P2∨…∨PnM1P1∨P2∨…∨PnM2P1∨P2∨…∨Pn

4、-1∨Pn…M2n-1P1∨P2∨…∨Pn勿在浮沙筑高臺(tái)！38--82.由有限個(gè)極小項(xiàng)組成的析取范式稱為主析取范式。3.由有限個(gè)極大項(xiàng)組成的合取范式稱為主合取范式。勿在浮沙筑高臺(tái)！38--9極小項(xiàng)與極大項(xiàng)的性質(zhì)對(duì)于n個(gè)命題變元，共有2n個(gè)不同的極小項(xiàng)和2n個(gè)不同的極大項(xiàng)，分別記為m0，m1，…，m2n-1和M0，M1，…，M2n-1。對(duì)于兩個(gè)命題變元P,Q，(┐P∧┐Q)、(┐P∧Q)、(P∧┐Q)、(P∧Q)為對(duì)應(yīng)的4個(gè)極小項(xiàng)，(P∨Q)、(P∨┐Q)、(┐P∨Q)、(┐P∨┐Q)為對(duì)應(yīng)的4個(gè)極大項(xiàng)。(┐P∧Q)是2個(gè)變元P和Q的極小項(xiàng)，但不是3個(gè)變元P、Q和R的極小項(xiàng)；(P

5、∨┐Q)是2個(gè)變元P和Q的極大項(xiàng)，但不是3個(gè)變元P、Q和R的極大項(xiàng)。勿在浮沙筑高臺(tái)！38--10如公式G1=（P→Q）∧QG2（P，Q，R）=（P→Q）∧Q其求出的相應(yīng)的主析取范式和主合取范式卻是不同的，前者是依賴于兩個(gè)命題變元的，后者應(yīng)依賴于三個(gè)命題變元。定理任何一個(gè)公式都有與之等價(jià)的主析取范式和主合取范式。方法：真值表技術(shù)，公式轉(zhuǎn)換法。勿在浮沙筑高臺(tái)！38--11例G=(P→Q)?R，求出它的主析取范式和主合取范式。真值表技術(shù)求主范式PQRP→Q(P→Q)?R0001000111010100111110001101001101011111解：首先列出其真值表如下：勿在浮沙筑高臺(tái)！38

6、--12將極小項(xiàng)全部進(jìn)行析取后，可得到相應(yīng)的主析取范式：G=（Ｐ→Ｑ）?Ｒ=（┐P∧┐Ｑ∧Ｒ）∨（┐P∧Ｑ∧Ｒ）∨（Ｐ∧┐Ｑ∧┐Ｒ）∨（Ｐ∧Ｑ∧Ｒ）勿在浮沙筑高臺(tái)！38--13將極大項(xiàng)全部進(jìn)行析取后，可得到相應(yīng)的主合取范式：G=（Ｐ→Ｑ）?Ｒ=（P∨Ｑ∨Ｒ）∧（P∨┐Ｑ∨Ｒ）∧（┐Ｐ∨Ｑ∨┐Ｒ）∧（┐Ｐ∨┐Ｑ∨Ｒ）勿在浮沙筑高臺(tái)！38--14求主析取范式和主合取范式的簡要方法：（a）從真值表知，選出公式的真值結(jié)果為真的所有的行，在這樣的每一行中，找到其每一個(gè)解釋所對(duì)應(yīng)的極小項(xiàng)，將這些極小項(xiàng)的析取即可得到相應(yīng)的主析取范式。（b）從真值表知，選出公式的真值結(jié)果為假的所有的行，在這樣的每一行中

7、，找到其每一個(gè)解釋所對(duì)應(yīng)的極大項(xiàng)，將這些極大項(xiàng)的合取即可得到相應(yīng)的主合取范式。勿在浮沙筑高臺(tái)！38--15PQRP→Q┐（P→Q）┐(P→Q)∨R000100001101010100011101100011101011110100111101解：首先列出其真值表如下：例G=┐(Ｐ→Ｑ)∨Ｒ，求主析取和主合取范式。勿在浮沙筑高臺(tái)！38--16(1).求主析取范式(a).從真值表知，該公式G恰有五個(gè)解釋使其公式取值為“真”。為此，