離散數(shù)學(xué)重點筆記.docx

《離散數(shù)學(xué)重點筆記.docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、離散數(shù)學(xué)重點筆記12020年4月19日文檔僅供參考，不當(dāng)之處，請聯(lián)系改正。第一章，0命題邏輯素數(shù)=質(zhì)數(shù)，合數(shù)有因子和或假必真同為真(p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而q)等不是合式公式。若公式A是單個的命題變項，則稱A為0層合式(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分別為3層和4層公式pq→r，（p→(r→【例】求下列公式的真值表，并求成真賦值和成假賦值。(┐p∧q)→┐r公式(1)的成假賦值為011，其余7個賦值都是成真賦值第二章，命題邏輯等值演算（1）雙重否定律AA22020年4月19日文檔僅供

2、參考，不當(dāng)之處，請聯(lián)系改正。（2）等律A∧AA；A∨AA（3）交律A∧BB∧A；A∨BB∨A（4）合律（A∧B）∧CA∧（B∧C）；（A∨B）∨CA∨（B∨C）（5）分配律（A∧B）∨C（A∨C）∧（B∨C）；（A∨B）∧C（A∧C）∨（B∧C）（6）德·摩根律（A∨B）A∧B；（A∧B）A∨B（7）吸收律A∨（A∧B）A；A∧（A∨B）A（8）零一律A∨11；A∧00（9）同一律A∨0A；A∧1A（10）排中律A∨A1（11）矛盾律A∧A0（12）涵等式A→BA∨B（13）假言易位A→BB→A（14）等價等式AB（A→B）∧（B→A）（15）等價否定等式AB

3、ABBA（16）式（A→B）∧（A→B）AAi(i=1,2,?,s)合取式，A=A1∨A2∨?∨As析取范式(p∧┐q)∨(┐q∧┐r)∨pA=A1∧A2∧?∧As合取范式(p∨q∨r)∧(┐p∨┐q)∧r一個析取范式是矛盾式當(dāng)且當(dāng)它的每個合取式都是矛盾式一個合取范式是重言式當(dāng)且當(dāng)它的每個析取式都是重言式32020年4月19日文檔僅供參考，不當(dāng)之處，請聯(lián)系改正。主范式【∧小真，∨大假】∧成真小寫【例】(p→q)→(┐q→┐p)=┐(┐p∨q)∨(q∨┐p)消(去→)=(p∧┐q)∨┐p∨q┐(內(nèi)移)(已為析取范式)=(p∧┐q)∨(┐p∧┐q)∨(┐p∧q)

4、∨(┐p∧q)∨(p∧q)（*）=m2∨m0∨m1∨m1∨m3=m0∨m1∨m2∨m3冪(等律、排序)(*)由┐p及q派生的極小項的過程如下：┐p=┐p∧(┐q∨q)=┐(p∧┐q)∨(┐p∧q)q=(┐p∨p)∧q=┐(p∧q)∨(p∧q)42020年4月19日文檔僅供參考，不當(dāng)之處，請聯(lián)系改正。熟練之后，以上過程可不寫在演算過程中。該公式中含n=2個命題變項，它的主析取范式中含了22=4個極小項，故它為重言式，00，01，10，11全為成真賦值?！纠?(p→q)∧┐p=(┐p∨q)∧┐p消(去→)=┐p∨(┐p∧q)分(配律、冪等律)已為析取范

5、式=(┐p∧┐q)∨(┐p∧q)=m0∨m1【例】(p∧┐q)∨(┐p∧q)=(p∨┐p)∧(p∨q)∧(┐q∨┐p)∧(┐q∨q)=(p∨q)∧┐(p∧q)重言蘊涵式52020年4月19日