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

命题演算的合式公式 翻译 例1、除非你努力，否则你将失败。 解：设P:你努力 Q:你失败 则符号化为 ?P ? Q 或 ?Q ? P 例4：将下列命题符号化 1、只有你主修计算机科学或者不是新生，才能从校园内访问因特网。 解：设P：你能从校园内访问因特网；Q：你是新生； R：你主修计算机科学。则原题译为： 真值表与翻译 翻译总结 （1）首先找出原子命题 （2）根据命题含义翻译，不可拘泥于句子形式 第4节：真值表与等价公式 （P12定义） 例2 ：永真式和永假式 2、等价定理与常用等价式 3. 常用的等价式 （P15表1-4.8） 4. 子公式与等价置换定理 等价置换例题 例5、求证： 证明： 兴趣题：用等价演算来解决下列问题 * * 第3节 命题公式与翻译 命题公式：当P、Q是命题变元时，则上述各式为命题公式。 注意： 命题公式没有真假值； 并不是所有的由命题变元、联结词、和一些括号组成的字符串都能成为命题公式。 例如：? P ∨ （P ? Q）不是合法的命题公式 仅有举例说明是不够的，需要给出命题公式的规格化定义 由第2节的内容，我们知道，若P、Q是任意两个命题，则? P， P ∨ Q，(P ∨ Q) ?(P Q)等等都是复合命题。 例1. 合式公式((P ?(Q ? R))∧((P ? Q) ∧(P ? R)))的生成过程： P Q R (Q ? R) (P ? Q) (P ? R) (P ?(Q ? R) ) ((P ? Q) ∧(P ? R)) 基础 （1）. 单个命题变元本身是个合式公式； 归纳 （2）. 如果A是一个合式公式，那么? A也是一个合式公式； （3）. 如果A、B是合式公式，那么，（A ∧ B)、 （A ∨ B)、 （A ? B)、 （A B)都是合式公式； 界限 （4）. 当且仅当能够有限次应用（1）、（2）、（3）所得到的包含命题变元、联结词和括号的符号串是合式公式。 约定(1)最外层的括号可以省去 (2)运算符优先次序： ? ， ∧， ∨， ?， 例2、仅当你走我将留下。 解：设P:你走 Q:我留下 则符号化为 Q ? P 例3、（1）只要充分考虑一切论证，就能得到可靠见解。 （2）只有充分考虑一切论证，才能得到可靠见解。 解：设P:我们充分考虑一切论证 Q:我们得到可靠见解 则符号化为 （1）P ? Q （2） Q ? P 2、除非你已满16周岁，否则只要你身高不足4英尺就不能乘公园滑行铁道。 解：设P：你已满16周岁； 　　Q：你身高不足4英尺； R：你能乘公园滑行铁道。 则原题译为： P ?(R ∨ ? Q) ? P ?(Q ? ? R ) 例5：M：张三或李四中一个人去了。 P：张三去了。 Q：李四去了。 P Q M T T F T F T F T T F F F 可见：M的真值和 (P Q)完全相反。 所以：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 作业 :P12. (5), (6), (7) 一些固定搭配： 不可兼或： ? (P Q ) P仅当 Q : P ?Q 除非P，否则Q： ? P ? Q 定义一般翻译为双条件 例1： 构造（P ?Q）和（ ? P ∨ Q）的真值表 P Q ? P?Q P?Q T T T T T F F F F T T T F F T T 定义1　真值表 　　在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。 （P ?Q） ? （ ? P ∨ Q） 定义2　命题公式A、B等价 　　对应于所有可能的真值指派，A、B的真值都相同。又称为两命题公式逻辑相等。记为：A ? B 1、真值表 思考： （（P ?Q）