离散数学基本公式

一、基本等值式⑴双重否定律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二、推理定律——重言蕴涵式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)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