离散数学复习资料

第1 章 命题逻辑 本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论. 一、重点内容 1. 命题 命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 2. 六个联结词及真值表 “”否定联结词，P 是命题，P 是P 的否命题，是由联结词  和命题P 组成的复合命题.P 取真值1，P 取真值0，P 取真值0，P 取真值1. 它是一元联结词.  “”合取联结词，PQ 是命题P，Q 的合取式，是“”和 P，Q 组成的复合命题. “”在语句中相当于“不但…而且…”，“既…又…”. PQ 取值1，当且仅当 P，Q 均取1；PQ取值为0，只有P，Q 之一取0.  “”析取联结词，“”不可兼析取(异或)联结词， 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.  “”蕴含联结词， 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”.  “” 等价联结词，PQ 是P，Q 的等价式，是“”和 P，Q 组成的复合命题. “”在语句中相当于“…当且仅当…”，PQ 取值1 当且仅当 P，Q 真值相同. 3. 命题公式、赋值与解释，命题公式的分类与判别  命题公式与赋值，命题P 含有n 个命题变项 P1，P2,…,Pn，给 P1，P2,…,Pn各指定一个真值，称为对 P 的一个赋值(真值指派). 若指定的一组值使P 的真值为1，则这组值为P的真指派；若使P 的真值为0，则称这组值称为P 的假指派.  命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A 不是矛盾式，称为可满足式； 判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表...