离散数学复习资料.doc

第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取值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的真值为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命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式； 判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)范式法，该公式的主析取范式有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 析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)范式. 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个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为原命题公式的主析取(合取)范式。 每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式. 任意命题公式都存在与之等值的范式，存在与之等值的主范式，且是惟一的. 求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律. 求析取(合取)范式的步骤： ① 将公式中的联结词都化成?，ù，ú(即消去个数中