离散数学重点笔记.docx

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

1、离散数学重点笔记12020年4月19日文档仅供参考，不当之处，请联系改正。第一章，0命题逻辑素数=质数，合数有因子和或假必真同为真(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、参考，不当之处，请联系改正。（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一个析取范式是矛盾式当且当它的每个合取式都是矛盾式一个合取范式是重言式当且当它的每个析取式都是重言式32020年4月19日文档仅供参考，不当之处，请联系改正。主范式【∧小真，∨大假】∧成真小写【例】(p→q)→(┐q→┐p)=┐(┐p∨q)∨(q∨┐p)消(去→)=(p∧┐q)∨┐p∨q┐(内移)(已为析取范式)=(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日文档仅供参考，不当之处，请联系改正。熟练之后，以上过程可不写在演算过程中。该公式中含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日