离散数学公式.doc

基本等值式
A Û ┐┐A
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∧(B∨C) Û (A∧B)∨(A∧C) (∧对∨的分配律)
·摩根律      ┐(A∨B) Û ┐A∧┐B ┐(A∧B) Û ┐A∨┐B
         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→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)
全称量词“"”对“∨”无分配律。
存在量词“$”对“∧”无分配律。
UI规则。
UG规则。

EG规则。
EI规则。
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}
集合恒等式