离散数学2重言式与范式.pptVIP

离散数学(2) 陈斌 chenbin@ 2008.09.30 目录 数理逻辑 集合论 图论 抽象代数 形式语言与自动机 数理逻辑 命题演算 命题与联结词 重言式 范式 命题演算形式系统 谓词演算 个体、谓词和量词 谓词演算永真式 谓词公式的前束范式 一阶谓词演算形式系统 上次我们讲到…… 数理逻辑发展史 命题（proposition）的定义 关于排中律和直觉主义 逻辑联结词 命题和联结词的符号化 联结词符号的定义和真值表 命题公式的定义、真值函数、赋值和真值表 对命题语句进行形式化 命题演算：重言式 几种命题公式 重言式（永真式）tautology 命题变元的所有赋值都是命题公式的成真赋值 矛盾式（永假式、不可满足式）contradiction 命题变元的所有赋值都是命题公式的成假赋值 可满足式(contingency) 命题公式至少有一个成真赋值 性质 永真式是可满足式，但非永真式不一定是永假式 如果命题公式A是永真式，则?A是永假式，反之亦然 命题演算：重言式 例子：对于任何公式A A∨?A是重言式（排中律） A∧?A是矛盾式（矛盾律） 采用命题公式的真值表证明重言式 证明(p∨q)∧?p→q是重言式 命题演算：重言式 逻辑等价式(logical equivalent) 当命题公式A?B是重言式时，则称A逻辑等价于B，记作A╞╡B，称作逻辑等价式 也可以理解为公式A和公式B等值 命题演算：重言式 一些重要的逻辑等价式（A,B,C是任意公式） E1：??A╞╡A（双重否定律） E2：A∨A╞╡A，A∧A╞╡A（幂等律） E3：A∨B╞╡B∨A， A∧B╞╡B∧A（交换律） E4：(A∨B)∨C╞╡A∨(B∨C)，(A∧B)∧C╞╡A∧(B∧C)（结合律） E5：A∧(B∨C)╞╡(A∧B)∨(A∧C)，A∨(B∧C)╞╡(A∨B)∧(A∨C)（分配律） 命题演算：重言式 一些重要的逻辑等价式（A,B,C是任意公式） E6：?(A∨B)╞╡?A∧?B， ?(A∧B)╞╡?A∨?B（德摩根律） E7：A∨(A∧B)╞╡A， A∧(A∨B)╞╡A（吸收律） E8：A→B╞╡?A∨B（蕴涵等值式） E9：A?B╞╡(A→B)∧(B→A)（等价等值式） E10：A∨t╞╡t，A∧f╞╡f（零律） E11：A∨f╞╡A，A∧t╞╡A（同一律） 命题演算：重言式 一些重要的逻辑等价式（A,B,C是任意公式） E12：A∨?A╞╡t， A∧?A╞╡f（排中律和矛盾律） E13：?t╞╡f，?f╞╡t E14：A∧B→C╞╡A→(B→C) E15：A→B╞╡?B→?A（假言易位） E16：(A→B)∧(A→?B)╞╡?A（归谬论） E17：A?B╞╡(A∧B)∨(?A∧?B) 命题演算：重言式 逻辑蕴涵式(logical implication) 当命题公式A→B是重言式时，则称A逻辑蕴涵B，记作A╞B，称作逻辑蕴涵式 也可以理解为公式A的所有成真赋值都是公式B的成真赋值 每个逻辑等价式可以看作两个逻辑蕴涵式，也就是说A╞╡B也有A╞B,B╞A A和B等值，所以A→B和B→A都是重言式 命题演算：重言式 一些重要的逻辑蕴涵式（A,B,C,D是任意公式） I1：A╞A∨B I2：A∧B╞A I3：A∧(A→B)╞B I4：(A→B)∧?B╞?A I5：?A∧(A∨B)╞B I6：(A→B)∧(B→C)╞A→C I7：(A→B)∧(C→D)╞(A∧C)→(B∧D) I8：(A?B)∧(B?C)╞A?C 命题演算：重言式 逻辑等价式和逻辑蕴涵式的几个重要性质 A╞╡B当且仅当╞A?B A╞B当且仅当╞A→B 若A╞╡B，则B╞╡A 若A╞╡B， B╞╡C，则A╞╡C 若A╞B，则?B╞?A 若A╞B， B╞C，则A╞C 若A╞B，A╞╡A’，B╞╡B’，则A’╞B’ 命题演算：重言式 重言式的代入原理(rule of substitution) 将重言式A中的某个命题变元p的所有出现都代换为命题公式B，得到的命题公式记作A(B/p)，A(B/p)也是重言式。 因为重言式A的真值与p的取值状况无关，恒为t，所以将p全部代换后的公式A(B/p)的真值也恒为t 注意：仅代换部分出现本原理不成立，为什么？ 注意：如果B中包含了p或者A中的其它变元，本原理还成立么？ 命题演算：重言式 命题公式的替换原理(rule of replacement) 将命题公式A中的子公式C的部分出现替换为和C逻辑等价的公式D（C╞╡D ），得到的命题公式记作B，则A╞╡B。 因为C和D（在任何赋值下）等值，所以用D替换C不会改变A的真值 注意：不要求全部出现都替换 命题演算：重言式 证明逻辑等价式和逻辑蕴涵式的三种方法 真值表法：要证明A╞╡B，A╞B，只要分别列出A?B和A→