离散数学基本公式.doc

一、基本等值式⑴双重否定律ØØAÛA⑵幂等律A∧AÛAA∨AÛA⑶交换律A∧BÛB∧AA∨BÛB∨A⑷结合律A∨(B∨C)Û(A∨B)∨CA∧(B∧C)Û(A∧B)∧C⑸分配律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)ÛAA∧(A∨B)ÛA(8)零律A∨1Û1A∧0Û0(9)同一律A∧1ÛAA∨0ÛA(10)排中律A∨ØAÛ1(11)矛盾律A∧ØAÛ0(12)蕴含等值式A®BÛØA∨B(13)等价等值式A«BÛ(A®B)∧(B®A)A«BÛ(ØA∨B)∧(A∨ØB)A«BÛ(A∧B)∨(ØA∧ØB)(14)假言易位A®BÛØB®ØA(15)等价否定等值式A«BÛØA«ØB(16)归谬论(A®B)∧(A®ØB)ÛØ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)ÞB构造性二难(特殊形式)9.(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难三、量词辖域收缩与扩张"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)四、量词分配"x(A(x)∧B(x))Û"xA(x)∧"xB(x)$x(A(x)∨B(x))Û$xA(x)∨$xB(x)"x(A(x)∨B(x))Ü"xA(x)∨"xB(x)"x(A(x)∨B(x))Þ"xA(x)∨"xB(x)个体域为全体自然数;A(x):x是偶数,B(x):x是奇数;左Û1,右Û0$x(A(x)∧B(x))Þ$xA(x)∧$xB(x)$x(A(x)∧B(x))Ü$xA(x)∧$xB(x)个体域为全体自然数;A(x):x是偶数B(x):x是奇数;左Û0,右Û1