数理逻辑重要公式(离散数学)剖析.ppt

基本等值式 双重否定律 : ??A?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?B?A, A?B?B?A 等幂律： A?A?A, A?A?A * 等值公式 德·摩根律 : ?(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 A,B,C代表任意的命题公式 * 重要的推理定律 A T (AúB) 附加律 (AùB) T A 化简律 (A?B)ùA T B 假言推理 (A?B)ù?B T ?A 拒取式 (AúB)ù?B T A 析取三段论 (A?B)ù(B?C) T (A?C) 假言三段论 (A?B)ù(B?C) T (A?C) 等价三段 (A?B)ù(C?D)ù(AúC) T (BúD) 构造性二难 * 推理定律——重言蕴涵式 推理定律 (续) (A?B)ù(?A?B)ù(Aú?A) T B 构造性二难（特殊形式） (A?B)ù(C?D)ù( ?Bú?D) T (?Aú?C) 破坏性二难 * 说明： A, B, C为元语言符号 若某推理符合某条推理定律，则它自然是正确的 A?B产生两条推理定律: A T B, B T A 基本等值式 1、基本等值式: 命题逻辑中基本等值式的代换实例 2、消去量词等值式 设D={a1,a2,…,an} ?xA(x)?A(a1)?A(a2)?…?A(an) ?xA(x)?A(a1)?A(a2)?…?A(an) 3、否定等值式 ??x?(x)= ?x??(x) ??x?(x)= ?x??(x) * 量词辖域收缩与扩张等值式 设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(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) 注意：?对?无分配律，?对?无分配律 * 推理规则 (1)前提引入规则 (2)结论引入规则 (3)置换规则 (4)假言推理规则 (5)附加规则 (6)化简规则 (7)拒取式规则 (8)假言三段论规则 (9)析取三段论规则 (10)构造性二难推理规则 (11)合取引入规则 * 推理规则(续) (12) 全称量词消去规则（简记为UI规则或UI