数理逻辑重要公式离散数学.ppt

基本等值式 双重否定律:AA结合律:(A B)CA(B C)(A B)CA(B C)分配律:A(B C)(A B)(A C)A(B C)(A B)(A C)交换律:A BB A,A BB A等幂律：A AA,A AA等值公式1德摩根律 :(A B)AB (A B)AB吸 收 律:A(A B)A,A(A B)A零 律:A 11,A 00 同一律:A 0A,A 1A排中律:AA1矛盾律:AA02蕴涵等值式:ABA B等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)AA,B,C代表任意的命题公式3重要的推理定律 A (A B)附加律 (A B)A 化简律 (AB)A B 假言推理 (AB)B A 拒取式 (A B)B A 析取三段论 (AB)(BC)(AC)假言三段论 (AB)(BC)(AC)等价三段 (AB)(CD)(A C)(B D)构造性二难 推理定律重言蕴涵式 4推理定律(续)(AB)(AB)(AA)B 构造性二难（特殊形式）(AB)(CD)(BD)(AC)破坏性二难说明：A,B,C为元语言符号若某推理符合某条推理定律，则它自然是正确的AB产生两条推理定律:A B,B A5基本等值式 1 1、基本等值式:命题逻辑中基本等值式的代换实例2 2、消去量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)3 3、否定等值式 x(x)=x(x)x(x)=x(x)6量词辖域收缩与扩张等值式 设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的：x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)关于存在量词的:x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：对 无分配律，对 无分配律 7推理规则 (1)(1)前提引入规则 (2)(2)结论引入规则(3)(3)置换规则 (4)(4)假言推理规则(5)(5)附加规则 (6)(6)化简规则(7)(7)拒取式规则 (8)(8)假言三段论规则(9)(9)析取三段论规则 (10)(10)构造性二难推理规则(11)(11)合取引入规则 8.推理规则(续)(12)全称量词消去规则（简记为UI规则或UI）(13)全称量词引入规则（简记为UG规则或UG）(14)存在量词引入规则（简记为EG规则或EG）(15)存在量词消去规则（简记为EI规则或EI）闭 式9.