合式公式真值表等价置换定理 第二课.ppt

第3节命题公式与翻译 命题公式 当P Q是命题变元时 则上述各式为命题公式 注意 命题公式没有真假值 并不是所有的由命题变元 联结词 和一些括号组成的字符串都能成为命题公式 例如 P P Q 不是合法的命题公式 仅有举例说明是不够的 需要给出命题公式的规格化定义 命题演算的合式公式 例1 合式公式 P Q R P Q P R 的生成过程 PQR Q R P Q P R P Q R P Q P R 例1 除非你努力 否则你将失败 解 设P 你努力Q 你失败则符号化为 P Q或 Q P 例2 仅当你走我将留下 解 设P 你走Q 我留下则符号化为Q P 例3 1 只要充分考虑一切论证 就能得到可靠见解 2 只有充分考虑一切论证 才能得到可靠见解 解 设P 我们充分考虑一切论证Q 我们得到可靠见解则符号化为 1 P Q 2 Q P 翻译 例4 将下列命题符号化 1 只有你主修计算机科学或者不是新生 才能从校园内访问因特网 解 设P 你能从校园内访问因特网 Q 你是新生 R 你主修计算机科学 则原题译为 2 除非你已满16周岁 否则只要你身高不足4英尺就不能乘公园滑行铁道 解 设P 你已满16周岁 Q 你身高不足4英尺 R 你能乘公园滑行铁道 则原题译为 P R Q P Q R 真值表与翻译 例5 M 张三或李四中一个人去了 P 张三去了 Q 李四去了 例6 将下列命题符号化1 如果我上街 我就去书店 除非我很累 2 李四生于1980或1981年 他是计算机学院的学生 而且是优秀学生干部 1 解 P 我上街Q 我去书店R 我很累 R P Q 2 解 P 李四生于1980年Q 李四生于1981年R 李四是计算机学院学生S 李四是优秀学生干部 P Q P Q R S 翻译总结 1 首先找出原子命题 2 根据命题含义翻译 不可拘泥于句子形式 作业 P12 5 6 7 P仅当Q P Q除非P 否则Q P Q定义一般翻译为双条件 第4节 真值表与等价公式 P12定义 例1 构造 P Q 和 P Q 的真值表 定义1真值表在命题公式中 对于分量指派真值的各种可能组合 就确定了这个命题公式的各种真值情况 把它汇列成表 就是命题公式的真值表 P Q P Q 定义2命题公式A B等价 对应于所有可能的真值指派 A B的真值都相同 又称为两命题公式逻辑相等 记为 A B 1 真值表 对应于所有可能的真值指派 命题公式A的真值都为T 我们称命题公式A为永真式 记为 A T 定义3永真式 重言式 定义4永假式 矛盾式 对应于所有可能的真值指派 命题公式A的真值都为F 我们称命题公式A为永假式 记为 A F 例2 永真式和永假式 证明 1 由A B知 在所有可能的真值指派下 A B的真值总是相同的 从而 A B是一个重言式 2 由A B为重言式 可知 在所有可能的真值指派下 A B的真值总是相同的 所以A B 注意 当且仅当 的证明需要分为 当 和 仅当 两个部分 2 等价定理与常用等价式 双重否定律 A A 等幂律 A A A A A A 交换律 A B B A A B B 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 A B A B A B 吸收律 A A B AA A B A 3 常用的等价式 P15表1 4 8 蕴涵等值式 A B A B等价等值式 A B A B B A A B B A 4 子公式与等价置换定理 子公式定义 如果X是合式公式A的一部分 而且 X本身也是一个合式公式 则称X为公式A的子公式 等价置换定理 设X是合式公式A的子公式 若 X Y 如果将A中的X用Y来置换 所得到公式B与公式A等价 即A B P Q R S P Q R S P Q R S 等都是该公式的子公式 A P Q R S B P Q R S 因为 P Q P Q 所以 A B 例4 用等价置换定理来化简下列命题公式 证明 Q P P Q Q P 因为 P P P Q 所以 由等价置换定理可得Q P P Q Q P 2 P Q P Q P 证明 由分配律知 P Q P Q P Q Q 又由零律知 Q Q T所以 P Q Q P T同样由零律知 P T P于是有 P Q P Q P 等价置换例题 例5 求证 证明 作业 P19 7 a b c g 8 9 兴趣题 用等价演算来解决下列问题 A B C D四个进行百米赛跑 观众甲乙丙三人猜比赛名次 甲 C第一 B第二 乙 C第二 D第三 丙 A第二 D第四 结果是甲乙丙三人各猜对了一半 请您根据这些信息推断出ABCD四人的名次 甲 C1 B2乙 C