离散数学__复习资料

《离散数学__复习资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章命题逻辑本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定,(主)析取(合取)范式，命题逻辑的推理理论.一、重点内容1.命题命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2.六个联结词及真值表h“Ø”否定联结词，P是命题，ØP是P的否命题，是由联结词Ø和命题P组成的复合命题.P取真值1，ØP取真值0，P取真值0，ØP取真值1.它是一元联结词.h“Ù”合取联结词，PÙQ是命题P，Q的合取式，是“Ù”和P，Q组成的复合命题.“Ù”在语句中相当于“不但…而且…”，“既…又…”.PÙQ取值

2、1，当且仅当P，Q均取1；PÙQ取值为0，只有P，Q之一取0.h“Ú”析取联结词，“`Ú”不可兼析取(异或)联结词，PÚQ是命题P，Q的析取式，是“Ú”和P，Q组成的复合命题.P`ÚQ是联结词“`Ú”和P，Q组成的复合命题.联结词“Ú”或“`Ú”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或.即“P`ÚQ”«“(ØPÙQ)Ú(PÙØQ)”.PÚQ取值1，只要P，Q之一取值1，PÚQ取值0，只有P，Q都取值0.h“®”蕴含联结词，P®Q是“®”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，P®Q取值为0；其余各种情况，均有P®Q

3、的真值为1，亦即1®0的真值为0，0®1，1®1，0®0的真值均为1.在语句中，“如果P则Q”或“只有Q，才P，”表示为“P®Q”.h“«”等价联结词，P«Q是P，Q的等价式，是“«”和P，Q组成的复合命题.“«”在语句中相当于“…当且仅当…”，P«Q取值1当且仅当P，Q真值相同.3.命题公式、赋值与解释，命题公式的分类与判别h命题公式与赋值，命题P含有n个命题变项P1，P2,…,Pn，给P1，P2,…,Pn各指定一个真值，称为对P的一个赋值(真值指派).若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.h命题公式

4、分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法.利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的

5、可满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.h等值式AÛB，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。定理1设F(A)是含命题公式A的命题，F(B)是用命题公式B置换F(A)中的A之后得到的命题公式.如果AÛB，则F(A)ÛF(B).4.范式h析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)范

6、式.h极小项(极大项)，n个命题变项P1,P2,…,Pn，每个变项或它的否定两者只有其一出现且仅出现一次，第i个命题变项或者其否定出现在从左起第i个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项).以两个命题变项为例，m00=ØPÙØQ，m01=ØPÙQ,m10=PÙØQ,m11=PÙQ是极小项;M00=PÙQ，M01=PÙØQ,M10=ØPÙQ,M11=ØPÙØQ是极大项.h主析取范式(主合取范式)含有n个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为原命题公式的主析取

7、(合取)范式。每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式.任意命题公式都存在与之等值的范式，存在与之等值的主范式，且是惟一的.求范式，包括求析取范式、合取范式、主析取范式和主合取范式.关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律.求析取(合取)范式的步骤：①将公式中的联结词都化成Ø，Ù，Ú(即消去个数中的联结词®，«，`Ú)；②将否定联结词Ø消去或移到各命题变项之前；③利用分配律、结合律等，将公式化为析取(合取)范式.求命题公式A的主析取(合取)

8、范式的步骤①求公式A的析取(合取)范式