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

离散数学复习材料Page1of25第一章命题逻辑一、等价公式(真值表)1)常用联结词：┐否定∨析取∧合取→：条件：双条件当且仅当Q取值为F时P→Q为F，否则为T★等价公式表(等值公式表)常用的其它真值表┐┐P=P双重否定P∨P=PP∧P=P幂等律(P∧Q)∧R=P∧(Q∧R)(P∨Q)∨R=P∨(Q∨R)结合律P∧Q=Q∧PP∨Q=Q∨P交换律P∧(Q∨R)=(P∧Q)∨(P∧R)P∨(Q∧R)=(P∨Q)∧(P∨R)分配律P∨(P∧Q)=PP∧(P∨Q)=P吸收┐(P∧Q)=┐P∨┐Q┐(P∨Q)=┐P∧┐Q德摩根P∨F=PP∧T=P同一律P∨T=TP∧F=F零律P∨┐P=TP∧┐P=F否定律常用的其它真值表P┐PTFFTPQP∨QTTTTFTFTTFFFPQP∧QTTTTFFFTFFFFPQPQTTTTFFFTFFFTPQP→Q(┐P∨Q)TTTTFFFTTFFTP→Q=┐P∨QPQ=(P→Q)∧(Q→P)PQ=QPPQ=(P∧Q)∨(┐P∧┐Q)┐(PQ)=P┐QR∨(P∨┐P)=TR∧(P∧┐P)=FP→Q=┐Q→┐P┐(P→Q)=P∧┐Q(P→Q)∧(P→┐Q)=┐PP→(Q→R)=(P∧Q)→R(PQ)R=P(QR)离散数学复习材料Page2of25命题公式的类型：(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)=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的小项是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得析取范式中的简单合析式全是大项，则称该析取范式为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)离散数学复习材料Page3of25b)任意两个大项合取值为Tc)全部大项合取值为T找主合取范式的方法步骤e)划归为合取范式；f)去除范式中的永真合取值项(例如P∨┐P)；g)重复析取项和相同的变元合并；h)对析取补没有出现的命题变元，即添加(P∧┐P)式，应用分配律展开公式。主合取范式与主析取范式关系及整理技巧(以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)例如：(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∧┐Q∧R)∨(┐P∧┐Q∧┐R)∨(┐P∧Q∧┐R)∨(┐P∧┐Q∧┐R)∨(P∧Q∧R)001000010000111=(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(P∧Q∧R)主析取范式000001010111求主合取范式过程按照上面的取值取反应该是(011,100,101,110)的编号次序，但是大项小项的编码是相反的，然后吧∧互换∨，因而住合取范式为：=(P∨┐Q∨┐R)∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)推理理论：(必考☆☆☆☆)☆直接证明：由一组前提，利用公认的推理规则，根据已知的等价和蕴含公式，推演出有效的结论P规则：前提在推导过程中的任何时候都可以引入使用T规则：在推导中，如果有一个或多个公式、重言蕴含着公式S，则S可以引入推导中。常用蕴含式和等价(等值)式表：I1P∧Q=PE1┐┐P=PI2P∧Q=QE2P∧Q=Q∧P离散数学复习材料Page4of25I3P=P∨QE3P∨Q=Q∨PI4Q=P∨QE4(P∧Q)∧R=P∧(Q∧R)I5┐P=P→QE5(P∨Q)∨R=P∨(Q∨R)I6Q=P→QE6P∧(Q∨R)=(P∧Q)∨(P∧R)I7┐(P→Q)=PE7P∨(Q∧R)=(P∨Q)∧(P∨R)I8┐(P→Q)=┐QE8┐(P∧Q)=┐P∨┐QI9P,Q=P∧QE9┐(P∨Q)=┐P∧┐QI10┐P,P∨Q=QE10P∧P=PI11P,P→Q=QE11P∨P=PI12┐Q,P→Q=┐PE12R∨(P∧┐P)=RI13P→Q,Q→R=P→RE13R∧(P∨┐P)=RI14P∨Q,P→R,Q→R=RE14R∨(P∨┐P)=TI15P→Q=(P∨R)→(Q∨R)E15R∧(P∧┐P)=FI16P→Q=(P∧R)→(Q∧R)E16P→Q=┐P∨QE17┐(P→Q)=P∧┐QE18P→Q=┐Q→┐PE19P→(Q→R)=(P∧Q)→RE20PQ=(P→Q)∧(Q→P)E21PQ=(P∧Q)∧(┐P∧┐Q)E22┐(PQ)=P┐Q☆实例直接证明：即根据条件命题，通过利用蕴含表或等价表中的某些规则，将条件转化为右值命题的过程，因此可能证明方式和过程不唯一。☆间接证明方法：把需要推导出的结论，取┐后，作为附加条件引入证明中，且最后证明结论是矛盾的。(P∨Q)∧(P→R)∧(Q→S)=S∨R证明：(1)P∨QP（已知条件）(2)┐P→QT(1)E(P∨Q=┐P→Q)(3)Q→SP（已知条件）(4)┐P→ST(2)(3)I(┐P→Q,Q→S=┐P→S)传递关系(5)┐S→PT(4)E(┐P→S=P∨S=S∨P=┐S→P）(6)P→RP（已知条件）(7)┐S→RT(5)(6)I(┐S→P,P→R)传递关系(8)S∨RT(7)IP∨Q，Q→R，P→S，┐S=R∧(P∨Q)证明：(1)┐SP(2)P→SP(3)┐PT(1)(2)E(4)P∨QP(5)┐P∧QT(3)(4)E(6)QT(5)I(7)Q→RP(8)RT(6)(7)I(9)R∧(P∨Q)T(4)(8)I(P∨Q)∧(P→R)∧(Q→S)=S∨R证明：(1)┐(S∨R)P(附加条件)(2)┐S∧┐RT(1)E(3)P∨QP(4)┐P→QT(3)(5)Q→SP(6)┐P→ST(4)(5)I(7)┐S→PT(6)E(8)(┐S∧┐R)→(P∧┐R)T(7)I(9)P∧┐RT(8)IP∨Q，Q→R，P→S，┐S=R∧(P∨Q)证明：(1)┐(R∧(P∨Q))P(附加条件)(2)P∨QP(用了2次)(3)P→SP(4)┐SP(5)┐PT(3)(4)E(6)┐P∧QT(2)(5)E(7)QT(6)I(8)Q→RP(9)RT(7)(8)E离散数学复习材料Page5of25第二章谓词逻辑☆量词：全称量词：x：对于所有的客体变元(设S={x1,x2,…xn})存在量词：x：对于一部分客体变元(至少是1个)合式公式：1）原子谓词公式是合式公式；2）若A是合式公式，则┐A也是合式公式；3）若A，B都是合式公式，则，A∧B，A∨B，A→B，AB都是合式公式；4）若A是合式公式，则(x)A，(x)A都是合式公式；5）有限次的应用规则1)2)3)4)所得的公式都是合式公式。☆约束变元和自由变元：在合式公式xA和xA中，称x为指导变元(作用变元)，称A为相应量词的辖域(作用域)，x称为约束变元，x的出现称为约束出现，A中其他出现的变元称为自由出现(自由变元)。例子：(x)(y)(A(x,y)∧B(y,z))∧(x)A(x,y)n元谓词：若P(x1,x2,…….,xn)，含有n个相互独立的自由变元，对其中的k个变元进行约束，则称之为n-k元谓词。例子：(y)A(x,y,z)是二元谓词，(x)(y)A(x,y,z)则是一元谓词。约束变元换名：(x)(P(x)→R(x,y))∧Q(x,y)(x)(P(x)→R(x,y))为一元谓词，x约束变元，y为自由变元，且原式中x未对Q(x,y)约束。故而可以把约束变元x换成z，即(z)(P(z)→R(z,y))∧Q(x,y)(不要出现与已有的重名)自由变元代入：(x)(P(y)∧R(x,y))，自由变元y被z代入得到(x)(P(z)∧R(x,z))(不要出现与已有的重名)☆☆☆谓词演算的等价式与蕴含式命题逻辑和谓词逻辑存在相同的等价公式运算和蕴含运算(前边等价式和蕴含运算皆起作用)例如：┐┐PP┐┐P(x)P(x)P∨PPP(x)∨P(x)P(x)因此可以证明下面一系列等价式和蕴含式(x)(P(x)∨Q(x))(x)(P(x))∨(x)(Q(x))E23(x)(P(x)∧Q(x))(x)(P(x))∧(x)(Q(x))E24┐(x)P(x)(x)┐P(x)E25┐(x)P(x)(x)┐P(x)E26(x)(P(x)∨Q)((x)P(x))∨Qx未对Q有约束E27(x)(P(x)∧Q)((x)P(x))∧Qx未对Q有约束E28(x)(P(x)→Q(x))(x)P(x)→(x)Q(x)E29(x)(P(x)∧Q)((x)P(x))∧Qx未对Q有约束(x)(P(x)∨Q)((x)P(x))∨Qx未对Q有约束(x)P(x)→Q(x)(P(x)→Q)x未对Q有约束E30约束约束约束自由约束自由(x)P(x)P(x1)∧P(x2)…∧P(xn)(x)P(x)P(x1)∨P(x2)…∨P(xn)离散数学复习材料Page6of25(x)P(x)→Q(x)(P(x)→Q)x未对Q有约束E31Q→(x)P(x)(x)(Q→P(x))x未对Q有约束E32Q→(x)P(x)(x)(Q→P(x))x未对Q有约束E33☆(x)P(x)∨(x)Q(x)(x)(P(x)∨Q(x))I17☆(x)(P(x)∧Q(x))(x)P(x)∧(x)Q(x)I18☆(x)P(x