离散复习.ppt

离散数学复习与练习 第一部分：集合论 知识点： 集合关系（?，?,?,?,=） 集合运算（并、交、差、对称差、补集、幂集） 特殊集合（?，E，P(A)） ?：不含任何元素的集合，空集是任何集合的子集，空集是惟一的 E：限定所讨论的集合都是E的子集 P(A)：A的所有子集组成的集合, 即 P(A) = { x | x?A }。 如果 |A| = n，则 |P(A)| = 2n 设A={? ， {?}} A的0元子集: ? A的1元子集: {{?}}, {? } A的2元子集: ={? ， {?}} P(A) ={?, {{?}}, {? }，{? ,{?}} } 集合恒等式 幂等律、交换律、结合律、分配律、吸收律、补交转换律(A-B=A?~B)、德·摩根律?(B?C)=?B??C，A?(B?C)=(A?B)?(A?C)） 证明集合相等：1逻辑演算 2.集合恒等式 1. 证:A?(B?C)=(A?B)?(A?C) 证 ?x x?A?(B?C) ? x?A?(x?B? x?C) (并,交的定义) ?(x?A?x?B)?(x?A?x?C) (逻辑演算的分配律) ?x?(A?B)?(A?C) 2. 证明 (A-B)-C=(A-C)-(B-C) 证 (A-C)-(B-C) = (A ? ~C) ? ~(B ? ~C) (补交转换律) = (A ? ~C) ? (~B ? ~~C) (德摩根律) = (A ? ~C) ? (~B ? C) (双重否定律) = (A ? ~C ? ~B) ?(A ? ~C ? C) (分配律) = (A ? ~C ? ~B) ?(A ? ?) (矛盾律) = A ? ~C ? ~B (零律,同一律) = (A ? ~B) ? ~C (交换律,结合律) = (A – B) – C 第二部分：逻辑学 命题的定义（凡具有确定真假意义的陈述句均称为命题。） 联结词（?、∧、∨、?、?、?、?（公式转化为只含?、?的表达形式）） 例1：将p ? q化为只含?的公式 p ? q ??p ?q??(p∧?q) ? p??q?p??( q∧q) ? p? q? q 例2：命题符号化(1、王晓虽然聪明，但不用功. 2、张辉与王丽都是三好生. 3、张辉与王丽是同学.4、除非天冷，小王才穿羽绒服. 5、除非小王穿羽绒服，否则天不冷.) 等值演算 :幂等律、交换律、结合律、分配律、吸收律、 蕴涵等值式A?B? ?A?B 等价等值式 A?B?(A?B)?(B?A) 假言易位等值式 A?B? ?B? ?A 等价否定等值式 A?B? ?A? ?B） 例1：证明 p?(q?r) ? (p?q)?r 证 p?(q?r) ? ?p?(?q?r) （蕴涵等值式） ? (?p??q)?r （结合律） ? ?(p?q)?r （德摩根律） ? (p?q) ?r （蕴涵等值式） 例2：判断下列公式的类型 ?q?(p?q) 解 ?q?(p?q) ? ?q?(?p?q) （蕴涵等值式） ? q?(p??q) （德摩根律） ? p?(q??q) （交换律，结合律） ? p?0 （矛盾律） ? 0 （零律） 该式为矛盾式. 命题公式类型 分为：重言式、矛盾式、可满足式， 判断：利用真值表判断，等值演算，范式。 例：设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？ 例：指出下列公式哪些是恒真的哪些是恒假的： (1)P?（P? Q）?Q (2)（P? Q）?（?P?Q） (3)（P? Q）? （Q?R）?（P? R ） (4)（P? Q）?（P? Q??P?? Q） 真值表 请给出?P，P?Q，P?Q的真值表 范式 包括：析