基本等值式
1.双重否定律 A ? ┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律 A∨B ? B∨A， A∧B ? B∧A 4.结合律 (A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) 5.分配律 A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律 ┐(A∨B) ? ┐A∧┐B ┐(A∧B) ? ┐A∨┐B 7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A 8.零律 A∨1 ? 1,A∧0 ? 0 9.同一律 A∨0 ? A，A∧1 ? A 10.排中律 A∨┐A ? 1 11.矛盾律 A∧┐A ? 0 12.蕴涵等值式 A→B ? ┐A∨B 13.等价等值式 A?B ? (A→B)∧(B→A) 14.假言易位 A→B ? ┐B→┐A 15.等价否定等值式 A?B ? ┐A?┐B 16.归谬论 (A→B)∧(A→┐B) ? ┐A
求给定公式范式的步骤 (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 析取三段论 (6) (A→B) ∧ (B→C) ? (A→C) 假言三段论 (7) (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) 破坏性二难
设个体域为有限集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 ?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 ?x(A(x)∧B) ? ?xA(x)∧B ?x(A(x)→B) ? ?xA(x)→B ?x(B→A(x)) ? B→?xA(x)
设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)
全称量词“?”对“∨”无分配律。 存在量词“?”对“∧”无分配律。
?xA(x)?xA(x)UI规则。
或 ?A(y)?A(c)UG规则。
A(y)
??xA(x)
A(c)EG规则。
??xA(x)
?xA(x)EI规则。
?A(c)
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} ∩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＝E 矛盾律 A∩～A＝?
吸收律 A∪(A∩B)＝A A∩(A∪B)＝A
德摩根律 A－(B∪C)＝(A－B)∩(A－C) A－(B∩C)＝(A－B)∪(A－C) ～(B∪C)＝～B∩～C ～(B∩C)＝～B∪～C ～?＝E ～E＝? 双重否定律 ～(～A)＝A
集合运算性质的一些重要结果
A∩B?A，A∩B?B A?A∪B，B?A∪B A－B?A A－B＝A∩～B
A∪B＝B ? A?B ? A∩B＝A ? A－B＝? A?B＝B?A (A?B)?C＝A?(B?C) A??＝A A?A＝? A?B＝A?C ? B＝C
对偶(dual)式：一个集合表达式，如果只含有∩、∪、～、?、E、＝、?、?，那么同时把∩与∪互换，把?与E互换，把?与?互换，得到式子称为原式的对偶式。
有序对
（2）
笛卡儿积的符号化表示为 A×B＝{
(1)对任意集合A，根据定义有 A×?＝?, ?×A＝?
(2)一般的说，笛卡儿积运算不满足交换律，即 A×B≠B×A (当 A≠? ∧ B≠? ∧ A≠B 时) (3)笛卡儿积运算不满足结合律，即 (A×B)×C≠A×(B×C) (当 A≠? ∧ B≠? ∧ C≠? 时) (4)笛卡儿积运算对并和交运算满足分配律，即
A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A) A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A) (5)A?C ∧ B?D ? A×B ? C×D
常用的关系
对任意集合A，定义
相关推荐：
loading