离散数学重点笔记.doc

《离散数学重点笔记.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章，0命题逻辑素数=质数，合数有因子和或假必真同为真(p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式【例】求下列公式的真值表，并求成真赋值和成假赋值。(┐p∧q)→┐r公式(1)的成假赋值为011，其余7个赋值都是成真赋值第二章，命题逻辑等值演算（1）双重否定律AA（2）等幂律A∧AA；A∨AA（3）交换律A∧BB∧A；A∨BB∨A（4）结合律（A∧B）∧CA∧（B∧C）；（A∨B

2、）∨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）等价否定等值式ABABBA（16）归缪式（A→B）∧（A→B）AAi(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨As为析取式(p∧┐q)∨(┐q∧┐

3、r)∨pA=A1∧A2∧…∧As为合取式(p∨q∨r)∧(┐p∨┐q)∧r一个析取式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取式是重言式当且仅当它的每个简单析取式都是重言式主式【∧小真，∨大假】∧成真小写【例】(p→q)→(┐q→┐p)=┐(┐p∨q)∨(q∨┐p)(消去→)=(p∧┐q)∨┐p∨q(┐移)(已为析取式)=(p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)（*）=m2∨m0∨m1∨m1∨m3=m0∨m1∨m2∨m3(幂等律、排序)(*)由┐p及q派生的极小项的过程如下：┐p=┐p∧(┐q∨q)=(┐p∧┐q)∨(┐p∧q)q=(

4、┐p∨p)∧q=(┐p∧q)∨(p∧q)熟练之后，以上过程可不写在演算过程中。该公式中含n=2个命题变项，它的主析取式中含了22=4个极小项，故它为重言式，00，01，10，11全为成真赋值。【例】(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)重言蕴涵式【例】用附加前提证明法证明下面推理。前提：P→（Q→R），S∨P，Q结论：S→R证明：（1）S∨P前提引入规则（2）S附

5、加前提引入规则（3）P（1）（2）析取三段论规则（4）P→（Q→R）前提引入规则（5）Q→R（3）（4）假言推理规则（6）Q前提引入规则（7）R（5）（6）假言推理规则【例】用归缪法证明。前提：P∨Q，P→R，Q→S结论：S∨R证明（1）（S∨R）附加前提引入规则（2）S∧R（1）置换规则（3）S（2）化简规则（4）R（2）化简规则（5）Q→S前提引入规则（6）Q∨S（5）置换规则（7）Q（3）（6）析取三段论（8）P∨Q前提引入规则（9）P（7）（8）析取三段论规则（10）P→R前提引入规则（11）P∨R（10）置换规则（12）R（9）（11）析取三段论规则（13）R∧

6、R（4）（12）合取引入规则全称量词""对"∨"无分配律。同样的，存在量词""对"∧"无分配律(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))谓词逻辑的等价公式定理1设A（x）是谓词公式，有关量词否定的两个等价公式：（1）﹁xA（x）x﹁A（x）（2）﹁xA（x）x﹁A（x）定理2设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有（1）x（A（x）∨B）xA（x）∨B（2）x（A（x）∧B）xA（

7、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设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有：（1）x（A（x）∧B（x））xA（x）∧xB（x）（2）x（A（x）∨B（x））xA（x）∨xB（x）定理4下列蕴涵式成立（1）xA（x）∨xB（x）x（A（x）∨B（x））（2）x（A（x）∧B（x））xA（x）∧xB（x）