离散数学复习资料--修订编选.pdf

v1.0 可编辑可修改 1 离散数学复习资料 第 1 章命题逻辑 本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, ( 主) 析取 ( 合取 ) 范式，命题逻辑的推理理论. 一、重点内容 1. 命题 命题表述为具有确定真假 意义的陈述句命题必须具备二个条件：其一，语句是陈述 句；其二，语句有唯一确定的真假意义 . 2. 六个联结词及真值表 h“”否定 联结词， P是命题，P是 P的否命题，是由联结词和命题 P组成的复 合命题 .P 取真值 1，P取真值 0，P取真值 0，P取真值 1. 它是 一元联结词 . h “”合取 联结词， PQ是命题 P，Q的合取式，是“”和 P ，Q组成的复合命题. “”在语句中相当于“不但而且 ”，“既又”. PQ取值 1，当且仅当P ， Q均 取 1；PQ取值为 0，只有 P，Q之一取 0. h “”析取 联结词，“”不可兼析取 ( 异或 ) 联结词， PQ 是命题P ，Q的析取 式，是“”和 P，Q组成的复合命题. PQ是联结词“”和 P，Q组成的复合命题. 联结词“”或“”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排 斥或 不相容 的或 . 即“ PQ ”“(PQ)(PQ)”. PQ取值 1，只要 P，Q之一 取值 1， PQ取值 0，只有 P，Q都取值 0. h “”蕴含 联结词， PQ是“”和 P，Q组成的复合命题，只有P取值为 1，Q取 值为 0 时，PQ取值为 0；其余各种情况，均有 PQ的真值为1，亦即 10 的真值为0， 01，11，00 的真值均为1. 在语句中，“如果P则 Q ”或“只有Q，才 P，”表示为 “PQ”. h “” 等价联结词 ，PQ是 P，Q的等价式， 是“”和 P ，Q组成的复合命题. “” 在语句中相当于“当且仅当 ”， PQ取值 1 当且仅当P，Q真值相同 . 3. 命题公式、赋值与解释，命题公式的分类与判别 h 命题公式与赋值，命题P含有 n 个命题变项P1，P2, ,Pn，给 P1，P2, ,Pn各指定一个 真值，称 为对 P的一个赋值 ( 真值指派 ). 若指定的一组值使P的真值为 1，则这组值为P的 真指派 ；若使 P的真值为0，则称这组值称为P的假指派 . h 命题公式分类，在各种赋值下均为真的命题公式A，称为 重言式 ( 永真式 ) ；在各种赋 值下均为假的命题公式A，称为 矛盾式 ( 永假式 ) ；命题 A不是矛盾式，称为可满足式 ； 判定命题公式类型的方法：其一是真值表法 ，任给公式，列出该公式的真值表，若真值 v1.0 可编辑可修改 2 表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式； 若真值表的最后一列既非全1，又非全 0，则该公式是可满足式. 其二是 推导演算法 . 利用基 本等值式 (教材的十六个等值式或演算律) ， 对给定公式进行等值推导，若该公式的真值为1， 则该公式是永真式；若该公式的真值为0，则该公式为永假式. 既非永真，也非用假，成为 非永真的可满足式. 其三 主析取 (合取 ) 范式法 ，该公式的主析取范式有2 n 个极小项 (即无极 大项 ) ，则该公式是 永真式 ；该公式的主合取范式有2 n 个极大项 ( 即无极小项 ) ，则该公式是 永假式；该公式的主析取( 或合取 ) 范式的极小项 ( 或极大项 ) 个数大于0 小于 2 n, ，则该公式 是可满足式 . h 等值式 AB，命题公式A ，B在任何赋值下，它们的真值均相同，称A，B等值。

定理 1 设(A) 是含命题公式A 的命题，(B) 是用命题公式B 置换(A) 中的 A之后 得到的命题公式. 如果 AB，则(A)(B). 4. 范式 h 析取 ( 合取 ) 范式，仅有 有限 个简单 合取式 ( 析取式 ) 构成的析取式(合取式 ) ，就是析取 ( 合取 ) 范式 . h 极小项 ( 极大项 ) ，n 个命题变项P1,P2, ,Pn，每个变项或它的否定两者只有其一 出现 且仅出现一次，第i 个命题变项或者其否定出现在从左起第i 个位置上 ( 无脚标时，按字典 序排列 ) ，这样的简单 合取式 ( 析取式 )为极小项 ( 极大项 ). 以 两 个 命 题 变 项 为 例 ， m00=PQ， m01=PQ,m10=PQ,m11=PQ 是 极 小 项;M00=PQ，M01=PQ,M10=PQ,M11=PQ是极大项 . h 主析取范式 ( 主合取范式 ) 含有n 个命题变项的命题公式，如果与一个仅有极小项 ( 极大项 ) 的析取 ( 合取 ) 构成的析取 ( 合取 ) 范式等值，则该等值式称为原命题公式的主析取 ( 合取 ) 范式 每项含有n 个命题变项 ( 变项字母齐全 ) 的合取式 ( 析取式 ) 的析取 ( 合取 ) 为主析取 ( 合取 ) 范式 . 任意命题公式都存在与之等值的范式，存在与之等值的主范式 ，且是惟一的 . 求范式，包括 求析取范式、合取范式、主析取范式和主合取范式. 关键有两点：其一是 准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一 步适当使用幂等律. 求析取 ( 合取 ) 范式的步骤： 将公式中的联结词都化成，，( 即消去个数中的联结词，，) ； 将否定联结词消去或移到各命题变项之前； 利用分配律、结合律等，将公式化为析取( 合取 ) 范式 . 求命题公式A的主析取 ( 合取 ) 范式的步骤： 求公式 A的析取 ( 合取 ) 范式； v1.0 可编辑可修改 3 “ 消 去 ” 析 取 ( 合 取 ) 范 式 中 所 有 永 假 式 ( 永 真 式 ) 的 析 取 项 ( 合 取 项 ) ， 如 PP(PP)用 0(1) 替代 . 用幂等律将析取( 合取 ) 范式中重复出现的合取项( 析取项 ) 或 相同的变项合并，如PP(PP)用 P替代， mimi(MiMi) 用 mi(Mi) 替代 . 若析取 ( 合取 ) 范式的某个合取项( 析取项 )B 不含有命题变项Pi或Pi，则添加 PiPi(PiPi) ，再利用分配律展开，使得每个合取项( 析取项 ) 的命题变项齐全； 将极小 ( 极大 ) 项按由小到大的顺序排列，用() 表示 . 5. 命题演算的推理理论 h 设 A1,A2, ,An,C 是命题公式，如果 CAAA n21 是重言式 ，称 C 是前提集 合 A1,A2, ,An的有效结论或A1,A2, ,An逻辑地推出C。

记作 CAAA n21 掌握演绎或形式证明. 要理解并掌握14 个重言蕴含式(即 I1I14) ，17 个等值式 (E1 E17) ；二是会使用三个规则(P 规则、 T 规则和 CP规则 ) 推理方法有： 真值表法；等值演算法；主析取范式法，构造证明法( 直接证明法、附加前提证明法和 间接证明法 ) 第 2 章谓词逻辑 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明. 一、重点内容 1. 谓词与量词 h 谓词，在谓词逻辑中， 原子命题分解成个体词和谓词. 个体词是可以独立存在的客体， 它可以是具体事物或抽象的概念谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项( 用 a,b,c, 表示 ) 和个体变项 ( 用 x,y,z,表示 ) ；谓词分谓词常项 ( 表示具体性质和关系) 和谓词变项 ( 表示抽象的或泛指的谓词) ，用 F,G,P, 表示 . 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题. h 量词，是在命题中表示数量的词，量词有两类：全称量词，表示“所有的”或“每 一个”；存在量词，表示“存在某个”或“至少有一个”. 在谓词逻辑中，使用量词应注意以下几点： (1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变. (2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域. (3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义. 谓词公式只是一个符号串，没有什么意义， 但我们给这个符号串一个解释，使它具有真 值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应. v1.0 可编辑可修改 4 在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。

一般地， 使用全称量词，特性谓词后用；使用存在量词，特性谓词后用. 2. 公式与解释 h 谓词公式，由原子公式、联结词和量词可构成谓词公式( 严格定义见教材). 命题的符 号化结果都是谓词公式. 例如x(F(x)G(x)) ，x(F(x)G(x)) ，xy(F(x)F(y)L(x,y)H(x,y))等都 是谓词公式 . h 变元与辖域，在谓词公式xA 和xA 中， x 是指导变元，A 是相应量词的辖域. 在 x 和x 的辖域 A中， x 的所有出现都是约束出现，即x 是约束变元，不是约束出现的变 元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效. h 换名规则， 就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现 的个体变元，公式的其余部分不变. h 代入规则， 就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代， 且要把该公式中所有的该自由变元都换成新引入的这个符号. h 解释 ( 赋值 ) ，谓词公式A的个体域D是非空集合，则 (1) 每一个常项指定D中一个元素； (2) 每一个 n 元函数指定D n 到 D的一个函数； (3) 每一个 n 元谓词指定D n 到 0,1 的一个谓词； 按这个规则做的一组指派，称为A的一个解释或赋值. 在有限个体域下，消除量词的规则为：如Da1,a2, ,an ，则 )(...)()()()(...)()()( 2121nn aAaAaAxxAaAaAaAxxA h 谓词公式分类， 在任何解释下， 谓词公式A取真值 1，公式 A为逻辑有效式( 永真式 ) ； 在任何解释下谓词公式A取真值 0，公式 A为永假式；至少有一个解释使公式A取真值 1， 公式 A称为可满足式 . 3. 前束范式一个谓词公式的前束范式仍是谓词公式. 若谓词公式F 等值地转化成 BxQxQxQ kk ... 2211 那么 BxQxQxQ kk ... 2211 就是 F的前束范式，其中Q1，Q2，，Qk只能是或，x1,x2, ,x k 是个体变元， B是不含量词的谓词公式. 每个谓词公式F都可以变换成与它等值的前束范式. 其步骤如下： 消去联结词，，； 将联结词移至原子谓词公式之前； 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符 号也不同； v1.0 可编辑可修改 5 将x,x 移至整个公式最左边； 得到公式的前束范式. 4. 谓词逻辑的推理理论 谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言 蕴含式以及P，T，CP规则在谓词演算中仍然使用. 在谓词演算推理中，某些前提和结论可 能受到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有 US规则 ( 全称量词 消去规则 ) ，UG规则 ( 全称量词附加规则) ，ES规则 ( 存在量词消去规则) ，EG规则 ( 存在量词 附加规则 )等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行. 第 3 章集合与关系 本章重点：集合概念，集合的运算，集合恒等式的证明，笛卡儿积. 一、重点内容 1. 集合的概念 h 集合与元素， 具有确定的， 可以区分的若干事物的全体称为集合，其中的事物叫元素. 集合 A中元素的个数为集合的元数A. h 集合的表示方法：列举法和描述法. 列举集合的元素，元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存 在属于“”或不属于“”关系 . 2. 集合的关系：包含，子集，集合相等. h包含 ( 子集 ) ， 若 B。