离散数学公式.doc

AÛ┐┐ AÛA∨A, AÛA∧ A∨BÛB∨A, A∧BÛB∧(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∨┐         A∨(A∧B)ÛA,A∧(A∨B)Û        A∨1Û1,A∧0Û          A∨0ÛA,A∧1Û         A∨┐AÛ    A∧┐AÛ     A→BÛ┐A∨    A«BÛ(A→B)∧(B→A)       A→BÛ┐B→┐     A«BÛ┐A«┐       (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}集合恒等式幂等律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=Æ