離散數(shù)學(xué)定義定理(上)

《離散數(shù)學(xué)定義定理(上)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、離散數(shù)學(xué)定義定理1.3.1命題演算的合式公式規(guī)定為：（1）單個(gè)命題變?cè)旧硎且粋€(gè)合式公式。（2）如果A是合式公式，那么┐A是合式公式。（3）如果A和B是合式公式，那么（A∨B）、（A∧B）、（A→B）、（ADB）、都是合式公式。（4）當(dāng)且僅當(dāng)有限次地應(yīng)用（1）（2）（3）所得到的包含命題變?cè)?，連接詞和圓括號(hào)的符號(hào)串是合式公式。1.3.2設(shè)Ai是公式A的一部分，且Ai是一個(gè)合式公式，稱Ai是A的子公式。1.3.3設(shè)P為一命題公式，P1,P2,……，Pn為出現(xiàn)在P中的所有命題變?cè)?，?duì)P1,P2,……，P

2、n指定一組真值稱為對(duì)P的一種指派。若指定的一種指派，使P的值為真，則稱這組指派為成真指派。若指定的一種指派，使P的值為假，則稱這種指派為成假指派。含n個(gè)命題變?cè)拿}公式，共有2n個(gè)指派。1.3.4給定兩個(gè)命題公式A和B，設(shè)P1,P2,……，Pn為所有出現(xiàn)于A和B中的原子變?cè)?，若給P1,P2,……，Pn任一組真值指派，A和B的真值都相同，稱A和B是等價(jià)的，記做A<=>B。1.3.5設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為真，則稱A為重言式或永真式。1.3.6設(shè)A為一命題公式，若A在它的

3、各種指派情況下，其取值均為假，則稱A為矛盾式或永假式。1.3.7設(shè)A為一命題公式，若A在它的各種指派情況下至少存在一組成真指派，則稱A為可滿足式。1.4.1設(shè)X式合式公式A的子公式，若有Y也是一個(gè)合式公式，且X<=>Y，如果將Ａ中的Ｘ用Ｙ置換，得到公式Ｂ，則A<=>B。1.4.2設(shè)A，B為兩個(gè)命題公式，A<=>B，當(dāng)且僅當(dāng)A←→B為一個(gè)重言式。P=>Q稱做P蘊(yùn)含Q或蘊(yùn)含式，又稱永真條件式。蘊(yùn)含式有下列性質(zhì)：（1）對(duì)任意公式A，又A=>A；（2）對(duì)任意公式A，B和C，若A=>B，B=>C，則A=>C；

4、（3）對(duì)任意公式A，B和C，若A=>B，A=>C，則A=>(B∧C);（4）對(duì)任意公式A，B和C，若A=>C，B=>C，則A∨B=>C.1.4.3設(shè)P，Q為任意兩個(gè)命題公式，P<=>Q的充分必要條件式P=>Q,，Q=>P。蘊(yùn)含式推理P∧Q=>P化簡(jiǎn)式P∧Q=>Q化簡(jiǎn)式P=>P∨Q附加式┐P=>P→Q變形附加式Q=>P→Q變形附加式┐(P→Q)=>P變形簡(jiǎn)化式┐(P→Q)=>┐Q變形簡(jiǎn)化式p∧(P→Q)=>Q假言推論┐Q∧(P→Q)=>┐P拒取式┐p∧(P∨Q)=>Q析取三段式(P→Q)∧(Q→R)=

5、>P→R條件三段式(PDQ)∧(QDR)=>PDR雙條件三段式(P→Q)∧(R→S)∧(P∧R)=>Q→S合取構(gòu)造二難(P→Q)∧(R→S)∧(P∨R)=>Q∨S析取構(gòu)造二難P→Q=>(P∨R)→(Q∨R)前后附加式P→Q=>(P∧R)→(Q∧R)前后附加式1.5.1一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式：A1∧A2∧…∧An(n≥1)，其中A1，A2，…，An都是有命題變?cè)捌浞穸ㄋM成的析取式。1.5.2一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式：A1∨A2∨…∨An(n≥1)，其中A1

6、，A2，…，An都是有命題變?cè)捌浞穸ㄋM成的合取式。1.5.3n個(gè)命題變?cè)暮先∈剑Q作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c他的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。小項(xiàng)有如下性質(zhì)：（1）每個(gè)小項(xiàng)具有一個(gè)相應(yīng)的編碼，當(dāng)該編碼與其真實(shí)指派相同時(shí)，該小項(xiàng)為T，在其余2n-1種指派情況下為F。（2）任意兩個(gè)不同小項(xiàng)的合取是永假。（3）全體小項(xiàng)的析取式為永真。定義1.5.4對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取組成，則該等價(jià)公式稱作原公式的主析取范式。定理1.5.1在真值表中，一個(gè)公式

7、的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式主析取范式。定理1.5.2任意含n個(gè)命題變?cè)姆怯兰倜}公式，其主析取范式是唯一的。定義1.5.5n個(gè)命題變?cè)奈鋈∈椒Q作布爾析取或大項(xiàng)。其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須出現(xiàn)僅出現(xiàn)一次。定理1.5.3在真值表中一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大項(xiàng)的合取，稱為此公式的主合取范式。定理1.5.4任意含有n個(gè)命題變?cè)姆怯兰倜}公式A，其主合取范式是唯一的。設(shè)命題公式中含有n個(gè)命題變?cè)?，且A的主析取范式中含有k個(gè)小項(xiàng)mi1,mi2,…，mik,則

8、A的主合取范式比含有2n-k個(gè)大項(xiàng)。如果命題公式A的主析取范式為∑(i1,i2,……，ik)，則A的主合取范式為：Π(0,1,2,…，i1-1,i1+1,…，ik-1,ik+1,……，2n-1)。從A的主析取范式求其主合取范式的步驟為：（1）求出A的主析取范式中未包含小項(xiàng)的下標(biāo)。（2）把（1）中求出的下標(biāo)寫成對(duì)應(yīng)大項(xiàng)。（3）做（2）中縣城大項(xiàng)合取，即為A的主合取范式。根據(jù)主范式（主析取范式、主合取范式）的定義和定理，可以判定含n個(gè)命題變?cè)墓剑海?）若A可化為與其等