《离散数学--总复习》由会员分享，可在线阅读，更多相关《离散数学--总复习（8页珍藏版）》请在金锄头文库上搜索。
1、第一部分：集合论 知识点： 集合关系（ ， , , ,=） 集合运算（并、交、差、对称差、补集、幂集） ， 特殊集合（，E，P(A)） 集合恒等式（幂等律、交换律、结合律、分配律、吸收律、德摩根律、补交转 换律(A-B=AB)、德摩根律 (B C)= BC，A (B C)=(A B) (A C)） 证明集合包含或相等（根据定义, 通过逻辑等值演算证明、利用已知集合等式 或包含式, 通过集合演算证明） 1. 证:A(BC)=(AB)(AC) 证 x xA(BC) xA(xB xC) (并,交的定义)(xAxB)(xAxC) (逻辑演算的分配律) x(AB)(AC) 2. 证明 (A-B)-C=(
2、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 第二部分：逻辑学命题的定义（凡具有确定真假意义的陈述句均称为命题。 ）联结词（、（公式转化为只含、的表达形式） ） 例：将 p q 化为只含的公式p q p q(pq) pqp( qq) p q q命题符号化(1、王晓虽然聪明，但不用功.2、张辉与
3、王丽都是三好生. 3、张辉与王丽是同学.4、除非天冷，小王才穿羽绒服.5、除非小王穿羽绒服，否则天不冷.)等值演算（幂等律、交换律、结合律、分配律、吸收律、 蕴涵等值式 AB AB 等价等值式 AB(AB)(BA) 假言易位等值式 AB B A 等价否定等值式 AB A B） 证明 p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式） 判断下列公式的类型q(pq) 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 该式
4、为矛盾式.命题公式（重言式、矛盾式、可满足式） ， 利用真值表判断，等值演算，范式。范式（析取范式、合取范式） 求 p(pqr)的主合取范式和主析取范式 解 p (pqr)(pqr)(pqr)(pqr) M4M5M6M7pqr M1 得 p(pqr) M1M4M5M6M7 (1,4,5,6,7) (0,2,3) 主析取范式的用途: (1) 求公式的成真赋值和成假赋值 例如 (pq)r m0 m2 m4 m5 m6 成真赋值: 000,010,100,101,110; 成假赋值: 001,011,111 (2) 判断公式的类型 B p(pq) 1 m0m1m2m3 重言式 (3) 判断两个公式是
5、否等值 p 与(pq)(pq) 解 p p(qq) (pq)(pq) m2m3(pq)(pq) (pq)(pq) (pq)(pq) m2m3 故 p (pq)(pq) (4)选派人员 某单位要从 A,B,C 三人中选派若干人出国考察, 需满 足下述条件: (1) 若 A 去, 则 C 必须去; (2) 若 B 去, 则 C 不能去; (3) A 和 B 必须去一人且只能去一人. 问有几种可能的选派方案? 解 记 p:派 A 去, q:派 B 去, r:派 C 去(1) pr, (2) qr, (3) (pq)(pq) 求下式的成真赋值A=(pr)(qr)(pq)(pq) 求 A 的主析取范式A
6、=(pr)(qr)(pq)(pq) (pr)(qr)(pq)(pq) (pq)(pr)(rq)(rr)(pq)(pq) (pq)(pq)(pr)(pq)(rq)(pq)(pq)(pq)(pr)(pq)(rq)(pq) (pqr)(pqr)成真赋值:101,010 结论: 方案 1 派 A 与 C 去, 方案 2 派 B 去推理规则（附加律 A (AB) 化简律 (AB) A 假言推理 (AB)A B 拒取式 (AB) B A 析取三段论(AB) B A 假言三段论(AB)(BC) (AC)） (1)直接证明法直接证明法 在自然推理系统在自然推理系统 P 中构造下面推理的证明中构造下面推理的证明
7、: 前提前提: p q, qr, ps, s 结论结论: r (p q) 证明证明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r (p q) 合取合取 推理正确推理正确, r(pq)是有效结论是有效结论 (2)附加前提证明法附加前提证明法 例例 4 构造下面推理的证明构造下面推理的证明: 前提前提: p q, q r, rs 结论结论: ps 证明证明 p 附加前提引入附加前提引入p q 前提引入前提引入 q 析取三段论析取三段论 q r 前提引入前提引入 r 析取三段论析取
8、三段论 rs 前提引入前提引入 s 假言推理假言推理 推理正确推理正确, ps 是有效结论是有效结论 (3)归谬法归谬法(反证法反证法) 构造下面推理的证明构造下面推理的证明 前提前提: (p q) r, rs, s, p 结论结论: q 证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (4)归结证明法归结证明法 用归结证明法构造下面推理的证明用归结证明法构造下面推理的证明: 前提前提: (pq)r, rs, s 结论结论: (pq)(p s) 解解 (pq)r ( p q) r (pq) r (p r) ( q r)r
9、s r s (pq)(p s) ( p q) (p s) (pq) (p s) p ( q s) 一个公安人员审查一件盗窃案，已知的事实如下：A 或 B 盗窃了钻石；若 A 盗窃 了钻石，则作案时间不能发生在午夜前；若 B 证词正确，则在午夜时屋里灯光未 灭；若 B 证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。谁盗窃 了钻石呢？ 一阶逻辑一阶逻辑 个体词、谓词与量词个体词、谓词与量词 命题符号化命题符号化 (1) 人都爱美人都爱美; (2) 有人用左手写字有人用左手写字 个体域分别取个体域分别取(a) 人类集合人类集合, (b) 全总个体域全总个体域 . 解解: (a) (1) 设
10、设 F(x): x 爱美爱美, 符号化为符号化为 x F(x)(2) 设设 G(x): x 用左手写字用左手写字, 符号化为符号化为 x G(x)(b) 设设 M(x): x 为人，为人， F(x), G(x)同同(a)中中(1) x (M(x)F(x)(2) x (M(x) G(x) M(x)称作特性谓词称作特性谓词 量词的辖域、约束出现、自由出现量词的辖域、约束出现、自由出现 一阶逻辑等值演算一阶逻辑等值演算 消去量词等值式消去量词等值式 设设 D=a1,a2,an xA(x)A(a1) A(a2) A(an) xA(x)A(a1) A(a2) A(an) 量词辖域收缩与扩张等值式：量词辖域收缩与扩张等值式： 关于全称量词的：关于全称量词的： x(A(x) B)xA(x) B x(A(x) B)xA(x) B x(A(x)B) xA(x)B x(BA(x)BxA(x) 关于存在量词的关于存在量词的: x(A(x) B)xA(x) B x(A(x) B)xA(x) B x(A(x)B)xA(x
