16数理逻辑复习课件.ppt

定义1-2 凡不能再分解的命题称为原子命题。由原子命题和联结词联结而成的命题称为复合命题。 定义1-3 如果一个命题标识符代表任意未知命题，则称该命题标识符为命题变元。如果一个命题标识符代表一个确定的命题，则称之为命题常元。 ;P;p;p;p;p;1．2．1 命题公式 命题公式也称命题演算的合式公式。 定义1-6 (1)单个的命题常元或命题变元是命题公式； (2)如果A是一个命题公式，则 (┐A)也是命题公式； (3)如果A和B都是命题公式，则(A∧B)、(A∨B)、(A→B)、(A?B)也是命题公式； (4)当且仅当有限次地应用（1）、(2)、（3）所得到的符号串是命题公式。; 1.3.1 真值表 命题公式没有确定的真值，但可以假设公式中各个分量的不同取值来分析命题公式的真值情况。这样命题公式的真值情况就依赖于命题公式的结构和命题公式中各分量的真值指派。 定义1-8 设A是一个命题公式， 为出现在A中的所有命题变元。给 指定一组真值，称为对A的一组赋值（或解释或真值指派）。若指定的一组值使A的值为真，则称这组值为A的成真赋值，使A的值为假，则称这组值为A的成假赋值。 ;纸陛扛鸭炬圾尖讹津垂捆殿五奢赎卒植出绚挟蚜汽凿济钙缮额肾兜愚瘸勺16数理逻辑复习课件16数理逻辑复习课件; 常用的命题等价公式有：;例1-14 推导证明下列各式 （1） 证明： 联结词规化 分配律 德.摩根公式 ;（3） 证明： 联结词归化 等幂律 结合律 联结词归化 ;定义2 若一个命题公式是若干个单式的析取，则称为析取子式，若一个命题公式是若干单式的合取，则称为合取子式。析取子式和合取子式简称为子式。 ??义3 若一个命题公式是若干析取子式的合取，则称之为合取范式；若一个命题公式是若干合取子式的析取，则称之为析取范式。; 即：一个命题公式称为合取范式，当且仅当它具有型式： 其中 都是由命题变元或其否定所组成的析取子式。 如 都是合取范式。 即 一个命题公式称为析取范式，当且仅当它具有型式： 其中 都是由命题变元或其否定所组成的合取子式。 如　 都是析取范式。 ;定理1-5 （范式存在定理）任一命题公式都存在与之等价的析取范式与合取范式。; 例如，2个命题变元p和q的小项为： 3个命题变元p、q、r的小项为： ; 每个小项可用n位二进制编码表示。以变元自身出现的用1 表示，以其否定出现的用0表示;且对应十进制编码。上表中的小项可表示为： ; 小项的性质如下： （1）每一个小项当其真值指派与编码相同时，其真值为1，其余的2n－1