1
SpongeBob SquarePants
基本等值式
1.双重否定律 A ? ┐┐A 2.幂等律 3.交换律 4.结合律
A ? A∨A,
A ? A∧A
A∧B ? B∧A
A∨B ? B∨A，
(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律）
A∨(A∧B) ? A，A∧(A∨B) ? A A∨1 ? 1,A∧0 ? 0 A∨0 ? A，A∧1 ? A A∨┐A ? 1 A∧┐A ? 0 A→B ? ┐A∨B A?B ? (A→B)∧(B→A) A→B ? ┐B→┐A (A→B)∧(A→┐B) ? ┐A
5.分配律 A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） 6.德·摩根律 ┐(A∨B) ? ┐A∧┐B ┐(A∧B) ? ┐A∨┐B 7.吸收律 8.零律
9.同一律 11.矛盾律
10.排中律 12.蕴涵等值式 13.等价等值式 14.假言易位 16.归谬论
15.等价否定等值式 A?B ? ┐A?┐B
求给定公式范式的步骤 (1)消去联结词→、?(若存在)。
(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。
(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。
推理定律--重言蕴含式
(1) A ? (A∨B) (2) (A∧B) ? A
附加律 化简律 假言推理 拒取式 析取三段论 等价三段论
(3) (A→B)∧A ? B (4) (A→B)∧┐B ? ┐A (5) (A∨B)∧┐B ? A (7) (A?B) ∧ (B?C) ? (A ? C)
(6) (A→B) ∧ (B→C) ? (A→C) 假言三段论 (8) (A→B)∧(C→D)∧(A∨C) ?(B∨D) 构造性二难
(A→B)∧(┐A→B)∧(A∨┐A) ? B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) ?(┐A∨┐C)破坏性二难
1
2
SpongeBob SquarePants
设个体域为有限集D={a1,a2,…,an},则有 （1）?xA(x) ? A(a1)∧A(a2)∧…∧A(an) （2）?xA(x) ? A(a1)∨A(a2)∨…∨A(an)
设A(x)是任意的含自由出现个体变项x的公式，则 （1）┐?xA(x) ? ?x┐A(x) （2）┐?xA(x) ? ?x┐A(x)
设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则 （1） ?x(A(x)∨B) ? ?xA(x)∨B
设A(x)，B(x)是任意的含自由出现个体变项x的公式，则 （1）?x(A(x)∧B(x)) ? ?xA(x)∧?xB(x) （2）?x(A(x)∨B(x)) ? ?xA(x)∨ ?xB(x)
全称量词“?”对“∨”无分配律。 存在量词“?”对“∧”无分配律。
UI规则。
UG规则。
EI规则。
EG规则。
?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(B→A(x)) ? B→?xA(x)
（2） ?x(A(x)∨B) ? ?xA(x)∨B
?xA(x)?xA(x)或?A(y)?A(c)A(y)??xA(x)A(c)??xA(x)?xA(x)?A(c)2
3
SpongeBob SquarePants
A∪B＝{x|x∈A∨x∈B } 、 A∩B＝{x|x∈A∧x∈B } A－B＝{x|x∈A∧x?B } 幂集 P(A)＝{x | x?A}
对称差集 A?B＝(A－B)∪(B－A)
A?B＝(A∪B)－(A∩B)
绝对补集 ～A＝{x|x ? A }
广义并 ∪A＝{x | ?z(z∈A∧x∈z)} 广义交 ∩A＝{x | ?z(z∈A→x∈z)} 设 A＝{{a,b,c},{a,c,d},{a,e,f}} B＝{{a}} C＝{a,{c,d}} 则
∪A＝{a,b,c,d,e,f}
∪B＝{a} ∪C＝a∪{c,d}
集合恒等式
幂等律 A∪A＝A A∩A＝A 结合律 (A∪B)∪C＝A∪(B∪C) (A∩B)∩C＝A∩(B∩C) 交换律 A∪B＝B∪A A∩B＝B∩A 分配律 A∪(B∩C)＝(A∪B)∩(A∪C) A∩(B∪C)＝(A∩B)∪(A∩C) 同一律 A∪?＝A A∩E＝A 零律 A∪E＝E A∩?＝?
∪?＝? ∩A＝{a} ∩B＝{a} ∩C＝a∩{c,d}
3