离散数学——公式与解释.ppt

在命题逻辑中，命题又有命题常元和命 题变元之分。一个确定的具体的命题， 称为命题常元；一个不确定的泛指的任 意命题，称为命题变元。 命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下： 以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。 命题公式 定义4.2.1 命题公式是由下列规则生成： ①命题变元是公式; ②若A是一个公式，则┐A也是一个公式。 ③若A、B是公式，则A∧B、A∨B、A→B和A?B都是公式。 ④所有的公式只能有限次地使用①、②和③生成。 简化规则： ①规定联结词的优先级由高到低的次序为： ┐、∧、∨、→、? ②公式(┐A)的括号可以省略，即(┐A) 写成┐A。 ③最外层的圆括号可以省略。 公式的解释和赋值： 设G为一个命题公式，P1, P2,…，Pn为出现在G中的所有的命题变元.给P1, P2,…，Pn指定一组真值，称为对G的一个赋值或解释，记作I，公式G在I下的真值记作TI(G). 例：公式G=p∧q→r，I:p=1,q=1,r=0是G的一个解释 在这个解释下G的真值为0，即TI(G)=0。 那么111，011，010…也是G的解释. 一般来说，有n个命题变元的公式共有2n 个不同的解释。 构造真值表的步骤： ① 命题变元按一定顺序排列。 ② 对每个赋值，以二进制数从小到大或从大到小顺序列出。 ③ 若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。 例1:G= p→(p∨q)，其真值表为： 例2:G =p∧(p→q)∧(p→┐q)，真值表为： (1)若A在它的各种赋值下取值都为真，则称A为重言式或恒真式 (2)若A在它的各种赋值下取值都为假，则称A为矛盾式或恒假式 (3)若A至少存在一组赋值使A为真(A不是恒假的)，则称A为可满足式 恒真式是可满足式，但可满足式不一定是恒真式 当公式G对赋值I为真时，称I满足G，或I是G的成真赋值，记为TI(G) = 1；反之I是G的成假赋值，或称I弄假G，记为TI(G) = 0。 （见教材P89） 等值演算 n个命题变项只能生成 个不同的真值表 定义4.2.5 给定两个公式A和B， 设P1，P2，…，Pn为所有出现于A和B中的命题变元， 若给P1，P2，…，Pn任一组赋值，A和B的真值 都相同，则称A和B是等价的或逻辑相等的,记作A?B. 可通过判断A与B的真值表是否相同，来判断A与B是否等价。 例： p∧(p→q)→q 与p→(p∨q)是否等价？ 定理1 A ? B当且仅当A?B是恒真式。 有时也称A ? B是恒真双条件式。 等价式有下列性质： ① 自反性，即对任意公式A，有A ? A。 ② 对称性，即对任意公式A和B，若A ? B，则B ? A。 ③ 传递性，即对任意公式A、B和C，若A ? B、B ? C，则A ? C。 基本等价式——命题定律 在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。现将这些命题定律列出如下： (1)双否定：? ?A?A。 (2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。 (3) 结合律：(A∧B)∧C?A∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。 (4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。 (5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。 (6) 幂等律：A∧A?A，A∨A?A。 (7) 同一律：A∧1 ?A，A∨0 ? A。 (8) 零 律：A∧0 ?0，A∨1 ?1。 (9) 吸收律：A∧(A∨B)?A， A∨(A∧B)?A。 (10)矛盾律：A∧?A ?0 (11) 排中律：A∨?A?1。 (12) 条件式转化律： A→B??B→?A ， A→B??A∨B。 (13) 双条件式转化律：A?B?(A→B)∧(B→A) ?(A∧B)∨(?A∧?B) ?A?B??(A?B) 输出律：(A∧B)→C?A→(B→C)。 归谬律：(A→B)∧(A→?B)??A。 恒真式与恒假式的判别法：A为恒真式当且仅当A?1， A为恒假式当且仅当A?0 例：证明下列命题的等价关系： (p ∨q) →r? (p →r) ∧( q →r) (q →(p →r) ? (p ∧q) →r * * 公式与解释 将公式G在其所有解释下所取的真值列成一个表， 称为G的真值表。 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 p→(