第一部分：集合论 知识点：
集合关系（?，?,?,?,=）
集合运算（并、交、差、对称差、补集、幂集），
特殊集合（?，E，P(A)）
集合恒等式（幂等律、交换律、结合律、分配律、吸收律、德摩根律、补交转换律(A-B=A?~B)、德·摩根律?(B?C)=?B??C，A?(B?C)=(A?B)?(A?C)）
证明集合包含或相等（根据定义, 通过逻辑等值演算证明、利用已知集合等式或包含式, 通过集合演算证明） 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
第二部分：逻辑学
命题的定义（凡具有确定真假意义的陈述句均称为命题。）
联结词（?、∧、∨、?、?、?、?（公式转化为只含?、?的表达形式）） 例：将p ? q化为只含?的公式
p ? q ??p ?q??(p∧?q) ? p??q?p??( q∧q) ? p? q? q
命题符号化(1、王晓虽然聪明，但不用功.
2、张辉与王丽都是三好生. 3、张辉与王丽是同学.4、除非天冷，小王才穿羽绒服. 5、除非小王穿羽绒服，否则天不冷.)
等值演算（幂等律、交换律、结合律、分配律、吸收律、 蕴涵等值式A?B? ?A?B
等价等值式 A?B?(A?B)?(B?A) 假言易位等值式 A?B? ?B? ?A 等价否定等值式 A?B? ?A? ?B） 证明 p?(q?r) ? (p?q)?r 证 p?(q?r)
? ?p?(?q?r) （蕴涵等值式） ? (?p??q)?r （结合律） ? ?(p?q)?r （德摩根律） ? (p?q) ?r （蕴涵等值式） 判断下列公式的类型 q??(p?q) 解 q??(p?q)
? q??(?p?q) （蕴涵等值式） ? q?(p??q) （德摩根律）
? p?(q??q) （交换律，结合律） ? p?0 （矛盾律） ? 0 （零律） 该式为矛盾式.
命题公式（重言式、矛盾式、可满足式）， 利用真值表判断，等值演算，范式。
范式（析取范式、合取范式）
求 ?p?(p?q??r)的主合取范式和主析取范式
解 ?p ? (?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r) ? M4?M5?M6?M7 p?q??r ? M1
得 ?p?(p?q??r)? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7) ? ?(0,2,3)
主析取范式的用途:
(1) 求公式的成真赋值和成假赋值
例如 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6
成真赋值: 000,010,100,101,110; 成假赋值: 001,011,111 (2) 判断公式的类型
B ? ? p?(p?q) ? 1 ? m0?m1?m2?m3 重言式 (3) 判断两个公式是否等值 p与(?p?q)?(p?q)
解 p ? p?(?q?q) ? (p??q)?(p?q) ? m2?m3 (?p?q)?(p?q) ? ?(?p?q)?(p?q) ? (p??q)?(p?q) ? m2?m3 故 p ? (?p?q)?(p?q) (4)选派人员
某单位要从A,B,C三人中选派若干人出国考察, 需满 足下述条件:
(1) 若A去, 则C必须去; (2) 若B去, 则C不能去;
(3) A和B必须去一人且只能去一人. 问有几种可能的选派方案?
解 记p:派A去, q:派B去, r:派C去
(1) p?r, (2) q??r, (3) (p??q)?(?p?q) 求下式的成真赋值
A=(p?r)?(q??r)?((p??q)?(?p?q)) 求A的主析取范式
A=(p?r)?(q??r)?((p??q)?(?p?q)) ? (?p?r)?(?q??r)?((p??q)?(?p?q)) ? ((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q))
? ((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q)) ?((?p??r)?(?p?q))?((r??q)?(?p?q)) ? (p??q?r)?(?p?q??r)
成真赋值:101,010
结论: 方案1 派A与C去, 方案2 派B去
推理规则（附加律A ? (A?B) 化简律 (A?B) ? A
假言推理 (A?B)?A ? B 拒取式 (A?B) ??B ? ?A 析取三段论(A?B) ??B ? A
假言三段论(A?B)?(B?C) ? (A?C)） (1)直接证明法
在自然推理系统P中构造下面推理的证明: 前提: p?q, q?r, p?s, ?s 结论: r?(p?q)
证明 ① p?s 前提引入
② ? s 前提引入 ③ ? p ①②拒取式 ④ p?q 前提引入
⑤ q ③④析取三段论 ⑥ q?r 前提引入
⑦ r ⑤⑥假言推理 ⑧ r?(p?q) ⑦④合取 推理正确, rù(púq)是有效结论 (2)附加前提证明法
例4 构造下面推理的证明: 前提: ?p?q,??q?r, r?s 结论: p?s
证明 ① p 附加前提引入 ②??p?q 前提引入
③ q ①②析取三段论 ④ ?q?r 前提引入
⑤ r ③④析取三段论
⑥ r?s 前提引入
⑦ s ⑤⑥假言推理 推理正确, p?s是有效结论 (3)归谬法(反证法) 构造下面推理的证明
前提: ?(p?q)?r, r?s, ?s, p 结论: ?q
证明 用归缪法
① q 结论否定引入 ② r?s 前提引入 ③ ?s 前提引入 ④ ?r ②③拒取式 (4)归结证明法
用归结证明法构造下面推理的证明: 前提: (p?q)?r, r?s, ?s 结论: (p?q)?(p?s)
解 (p?q)?r ? ?(?p?q)?r ? (p??q)?r ??(p?r)?(?q?r) r?s ? ?r?s
? (p?q)?(p?s) ? ?(?p?q)?(p?s) ? (p??q)?(p?s) ? ? p?(?q?s)
? 一个公安人员审查一件盗窃案，已知的事实如下：A或B盗窃了钻石；若A盗窃了
钻石，则作案时间不能发生在午夜前；若B证词正确，则在午夜时屋里灯光未灭；若B证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。谁盗窃了钻石呢？
一阶逻辑
个体词、谓词与量词 命题符号化
(1) 人都爱美; (2) 有人用左手写字
个体域分别取(a) 人类集合, (b) 全总个体域 . 解: (a) (1) 设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(B?A(x))?B??xA(x) 关于存在量词的:
?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(B?A(x))?B??xA(x) 量词否定等值式
设A(x)是含x自由出现的公式 ??xA(x)? ?x ?A(x) ? ?xA(x)??x ?A(x) 量词分配等值式
?x(A(x)?B(x))??xA(x)??xB(x) ?x(A(x)?B(x))??xA(x)??xB(x) 置换规则，换名规则，代替规则
例：消去公式中既约束出现、又自由出现的个体变项 ?x(F(x,y) ? ?yG(x,y,z))
? ?x(F(x,y) ? ?tG(x,t,z)) 换名规则
或者 ? ?x(F(x,t) ? ?yG(x,y,z)) 代替规则 例：设个体域D={a,b,c}, 消去下面公式中的量词:
(1) ?x(F(x)?G(x))
? (F(a)?G(a))?(F(b)?G(b))?(F(c)?G(c)) 前束范式
例：求公式?xF(x) ???xG(x) 的前束范式
解 ? ?xF(x)??x?G(x) 量词否定等值式 ? ?x(F(x) ?? G(x)) 量词分配等值式 第三部分：关系 有序对与笛卡儿积
例： <2,x+5>=<3y?4,y>，求 x, y. 解 3y?4=2, x+5=y ? y=2, x= ?3 例：A={0, 1}, B={a, b, c}，求A?B。
A?B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} 二元关系
有序对集合或空集
关系的表示（关系的集合表达式、关系矩阵、关系图 ） 例： A={a, b, c, d}, R={
离散数学总复习
