離散數(shù)學(xué)重點(diǎn)筆記

《離散數(shù)學(xué)重點(diǎn)筆記》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實(shí)用標(biāo)準(zhǔn)文案第一章，0命題邏輯素?cái)?shù)=質(zhì)數(shù)，合數(shù)有因子和或假必真同為真(p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是單個(gè)的命題變項(xiàng)，則稱A為0層合式(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分別為3層和4層公式【例】求下列公式的真值表，并求成真賦值和成假賦值。(┐p∧q)→┐r公式(1)的成假賦值為011，其余7個(gè)賦值都是成真賦值第二章，命題邏輯等值演算（1）雙重否定律AA（2）等冪律A∧AA；A∨AA（3）交換律A∧BB∧A；A∨BB∨A（4）結(jié)合律（A∧B）∧CA∧（B∧C）；（A∨

2、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）蘊(yùn)涵等值式A→BA∨B（13）假言易位A→BB→A（14）等價(jià)等值式AB（A→B）∧（B→A）精彩文檔實(shí)用標(biāo)準(zhǔn)文案（15）等價(jià)否定等值式ABABBA（16）歸繆式（A→B）∧（A→B）AAi(i=1,2,…,s)為簡單合取式，則A=A1∨A2∨…∨As為析取范式(p∧┐q

3、)∨(┐q∧┐r)∨pA=A1∧A2∧…∧As為合取范式(p∨q∨r)∧(┐p∨┐q)∧r一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡單合取式都是矛盾式一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡單析取式都是重言式主范式【∧小真，∨大假】∧成真小寫【例】(p→q)→(┐q→┐p)=┐(┐p∨q)∨(q∨┐p)(消去→)=(p∧┐q)∨┐p∨q(┐內(nèi)移)(已為析取范式)=(p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)（*）=m2∨m0∨m1∨m1∨m3=m0∨m1∨m2∨m3(冪等律、排序)(*)由┐p及q派生的極小項(xiàng)的過程如下：┐p=┐p∧(┐q∨q)=(┐p∧┐q)∨(

4、┐p∧q)q=(┐p∨p)∧q=(┐p∧q)∨(p∧q)熟練之后，以上過程可不寫在演算過程中。該公式中含n=2個(gè)命題變項(xiàng)，它的主析取范式中含了22=4個(gè)極小項(xiàng)，故它為重言式，00，01，10，11全為成真賦值。精彩文檔實(shí)用標(biāo)準(zhǔn)文案【例】(p→q)∧┐p=(┐p∨q)∧┐p(消去→)=┐p∨(┐p∧q)(分配律、冪等律)已為析取范式=(┐p∧┐q)∨(┐p∧q)=m0∨m1【例】(p∧┐q)∨(┐p∧q)=(p∨┐p)∧(p∨q)∧(┐q∨┐p)∧(┐q∨q)=(p∨q)∧┐(p∧q)重言蘊(yùn)涵式【例】用附加前提證明法證明下面推理。前提：P→（Q→R），S∨P，Q結(jié)論：S→R證明：（1

5、）S∨P前提引入規(guī)則（2）S附加前提引入規(guī)則（3）P（1）（2）析取三段論規(guī)則（4）P→（Q→R）前提引入規(guī)則（5）Q→R（3）（4）假言推理規(guī)則（6）Q前提引入規(guī)則（7）R（5）（6）假言推理規(guī)則【例】用歸繆法證明。前提：P∨Q，P→R，Q→S結(jié)論：S∨R證明（1）（S∨R）附加前提引入規(guī)則（2）S∧R（1）置換規(guī)則（3）S（2）化簡規(guī)則（4）R（2）化簡規(guī)則（5）Q→S前提引入規(guī)則（6）Q∨S（5）置換規(guī)則精彩文檔實(shí)用標(biāo)準(zhǔn)文案（7）Q（3）（6）析取三段論（8）P∨Q前提引入規(guī)則（9）P（7）（8）析取三段論規(guī)則（10）P→R前提引入規(guī)則（11）P∨R（10）置換規(guī)則（12）R

6、（9）（11）析取三段論規(guī)則（13）R∧R（4）（12）合取引入規(guī)則全稱量詞""對"∨"無分配律。同樣的，存在量詞""對"∧"無分配律精彩文檔實(shí)用標(biāo)準(zhǔn)文案(3)xyF(x,y)x(F(x,a)∧F(x,b)∧F(x,c))(F(a,a)∧F(a,b)∧F(a,c))∨(F(b,a)∧F(b,b)∧F(b,c))∨(F(c,a)∧F(c,b)∧F(c,c))謂詞邏輯的等價(jià)公式定理1設(shè)A（x）是謂詞公式，有關(guān)量詞否定的兩個(gè)等價(jià)公式：（1）﹁xA（x）x﹁A（x）（2）﹁xA（x）x﹁A（x）定理2設(shè)A（x）是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B是不含x出現(xiàn)的公式，則有（1）x（A（x）

7、∨B）xA（x）∨B（2）x（A（x）∧B）xA（x）∧B（3）x（A（x）→B）xA（x）→B（4）x（B→A（x））B→xA（x）（5）x（A（x）∨B）xA（x）∨B（6）x（A（x）∧B）xA（x）∧B（7）x（A（x）→B）xA（x）→B（8）x（B→A（x））B→xA（x）定理3設(shè)A（x）、B（x）是任意包含自由出現(xiàn)個(gè)體變元x的公式,則有：（1）x（A（x）∧B（x））xA（x）∧xB（x）（2）x（A（x）∨B（x））xA（x）∨xB（x）定理4下列蘊(yùn)涵