离散数学部分概念和公式总结(精简版).pdf

《离散数学部分概念和公式总结(精简版).pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学复习材料第一章命题逻辑一、等价公式(真值表)1)常用联结词：┐否定∨析取∧合取P┐PPQP∨QPQP∧QTFTTTTTTFTTFTTFFFTTFTFFFFFFF→：条件：双条件当且仅当Q取值为F时P→Q为F，否则为TPQP→Q(┐P∨Q)PQPQTTTTTTTFFTFFFTTFTFFFTFFT★等价公式表(等值公式表)常用的其它真值表双重否┐┐P<=>P定P→Q<=>┐P∨QP∨P<=>PPQ<=>(P→Q)∧(Q→P)幂等律P∧P<=>PPQ<=>QP(P∧Q)∧R<=>P∧(Q∧R)PQ<=>(P∧Q)∨(┐P∧

2、┐Q)结合律(P∨Q)∨R<=>P∨(Q∨R)┐(PQ)<=>P┐QP∧Q<=>Q∧PR∨(P∨┐P)<=>T交换律P∨Q<=>Q∨PR∧(P∧┐P)<=>FP∧(Q∨R)<=>(P∧Q)∨(P∧R)P→Q<=>┐Q→┐P分配律P∨(Q∧R)<=>(P∨Q)∧(P∨R)┐(P→Q)<=>P∧┐QP∨(P∧Q)<=>P(P→Q)∧(P→┐Q)<=>┐P吸收P∧(P∨Q)<=>PP→(Q→R)<=>(P∧Q)→R┐(P∧Q)<=>┐P∨┐Q德摩根(PQ)R<=>P(QR)┐(P∨Q)<=>┐P∧┐QP∨F<=>P同一律P∧T<=

3、>PP∨T<=>T零律P∧F<=>FP∨┐P<=>T否定律P∧┐P<=>F常用的其它真值表Page1of25离散数学复习材料命题公式的类型：(1)若A在它的各种赋值下均取值为真，则称A为重言式或永真式。(2)若A在它的赋值下取值均为假，则称A为矛盾式或永假式。(3)若A至少存在一组赋值是成真赋值，则A是可满足式。当P→Q是一个重言式(永真式)称P蕴含Q记做P=>Q★蕴含公式表：此表可以理解为子集=>全集)1P∧Q=>P2P∧Q=>Q3P=>P∨Q4┐P=>P→Q5Q=>P→Q6┐(P→Q)=>P7┐(P→Q)=>┐Q8P∧(P→Q)=>

4、Q9┐Q∧(P→Q)=>┐P10┐P∧(P∨Q)=>Q11(P→Q)∧(Q→R)=>P→R12(PQ)∧(QR)=>PR13(P∨Q)∧(P→S)∧(Q→R)=>R14(P→Q)∧(R→S)=>(P∧R)→(Q∧S)对偶式与范式：性质：┐A(P1,P2…..Pn)<=>A*(┐P1,┐P2……┐Pn)A(┐P1,┐P2……┐Pn)<=>┐A*(P1,P2…..Pn)主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是小项，则称该析取范式为A的主析取范式。(即A1∨A2∨…..∨An形式)例如：P,Q的小项

5、是P∧Q,┐P∧Q,P∧┐Q,┐P∧┐Q(不能同时出现┐Q和Q)小项性质：a)每个小项当指派真值与编码相同时，其值为T，否则全为F(共2n-1个)(例如当P，Q，R全部为T的时候小项P∧Q∧R才为T，否则全部为F)b)任意两个小项合取值为Fc)全部小项析取值为T找主析取范式的方法步骤a)划归为析取范式；b)去除范式中的永假析取值项(例如P∧┐P)；c)重复合取项和相同的变元合并；d)对合取补没有出现的命题变元，即添加(P∨┐P)式，应用分配律展开公式。主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是大项，则

6、称该析取范式为A的主析取范式。例如：P,Q的大项是P∨Q,┐P∨Q,P∨┐Q,┐P∨┐Q(不能同时出现┐Q和Q)大项性质：a)每个大项当指派真值与编码相同时，其值为F，否则全为T(共2n-1个)(例如当P，Q，R全部为F的时候大项P∨Q∨R才为F，否则全部为T)Page2of25离散数学复习材料b)任意两个大项合取值为Tc)全部大项合取值为T找主合取范式的方法步骤e)划归为合取范式；f)去除范式中的永真合取值项(例如P∨┐P)；g)重复析取项和相同的变元合并；h)对析取补没有出现的命题变元，即添加(P∧┐P)式，应用分配律展开公式。主合

7、取范式与主析取范式关系及整理技巧(以3个变元为例)小项解释记法大项解释记法┐P∧┐Q∧┐R000m0P∨Q∨R000M0┐P∧┐Q∧R001m1P∨Q∨┐R001M1┐P∧Q∧┐R010m2P∨┐Q∨R010M2┐P∧Q∧R011m3P∨┐Q∨┐R011M3P∧┐Q∧┐R100m4┐P∨Q∨R100M4P∧┐Q∧R101m5┐P∨Q∨┐R101M5P∧Q∧┐R110m6┐P∨┐Q∨R110M6P∧Q∧R111m7┐P∨┐Q∨┐R111M7小项大项反过来合取范式∑(m1,m3,m5,m6,m7)<==>析取范式∏(M0,M2,M4)例如：

8、(P∨(Q∧R))→(P∧Q∧R)主析取范式和主合取范式<=>┐(P∨(Q∧R))∨(P∧Q∧R)<=>(┐P∧┐(Q∧R))∨(P∧Q∧R)<=>(┐P∧┐Q)∨(┐P∧┐R)∨(P∧Q∧R)<=>(┐P