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

《合式公式真值表等价置换定理-第二课.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3节命题公式与翻译命题公式：当P、Q是命题变元时，则上述各式为命题公式。注意：命题公式没有真假值；并不是所有的由命题变元、联结词、和一些括号组成的字符串都能成为命题公式。例如：P∨（PQ）不是合法的命题公式仅有举例说明是不够的，需要给出命题公式的规格化定义由第2节的内容，我们知道，若P、Q是任意两个命题，则P，P∨Q，(P∨Q)(PQ)等等都是复合命题。命题演算的合式公式例1.合式公式((P(QR))∧((PQ)∧(PR)))的生成过程：PQR(QR)(PQ)(PR)(P(QR

2、))((PQ)∧(PR))基础（1）.单个命题变元本身是个合式公式；归纳（2）.如果A是一个合式公式，那么A也是一个合式公式；（3）.如果A、B是合式公式，那么，（A∧B)、（A∨B)、（AB)、（AB)都是合式公式；界限（4）.当且仅当能够有限次应用（1）、（2）、（3）所得到的包含命题变元、联结词和括号的符号串是合式公式。约定(1)最外层的括号可以省去(2)运算符优先次序：，∧，∨，，例1、除非你努力，否则你将失败。解：设P:你努力Q:你失败则符号化为PQ或QP例2、仅当你走我将留

3、下。解：设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英

4、尺；R：你能乘公园滑行铁道。则原题译为：P(R∨Q)P(QR)真值表与翻译例5：M：张三或李四中一个人去了。P：张三去了。Q：李四去了。PQMTTFTFTFTTFFF可见：M的真值和(PQ)完全相反。所以：M可翻译为：(PQ）例6、将下列命题符号化1、如果我上街，我就去书店，除非我很累。2、李四生于1980或1981年，他是计算机学院的学生，而且是优秀学生干部。1、解：P：我上街Q：我去书店R：我很累R（PQ）2、解：P：李四生于1980年Q：李四生于1981年R：李四是计算机学院学生

5、S：李四是优秀学生干部((P∨Q)∧(P∧Q))∧R∧S翻译总结（1）首先找出原子命题（2）根据命题含义翻译，不可拘泥于句子形式作业:P12.(5),(6),(7)一些固定搭配：不可兼或：(PQ)P仅当Q:PQ除非P，否则Q：PQ定义一般翻译为双条件第4节：真值表与等价公式（P12定义）例1：构造（PQ）和（P∨Q）的真值表PQPQPQTTTTTFFFFTTTFFTT定义1　真值表在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公

6、式的真值表。（PQ）（P∨Q）定义2　命题公式A、B等价对应于所有可能的真值指派，A、B的真值都相同。又称为两命题公式逻辑相等。记为：AB1、真值表思考：（（PQ）（P∨Q））在真值表中值有何特征?对应于所有可能的真值指派，命题公式A的真值都为T。我们称命题公式A为永真式。记为：AT定义3　永真式（重言式）PQPPQ∧QTTTFTFTFFTTFFFTF定义4　永假式（矛盾式）对应于所有可能的真值指派，命题公式A的真值都为F。我们称命题公式A为永假式。记为：AF例2：永真式和永假式证明

7、：（1）由AB知，在所有可能的真值指派下，A、B的真值总是相同的，从而，AB是一个重言式。（2）由AB为重言式，可知：在所有可能的真值指派下，A、B的真值总是相同的，所以AB。注意：“当且仅当”的证明需要分为“当”和“仅当”两个部分2、等价定理与常用等价式定理：A和B是两个命题公式，AB当且仅当AB是一个重言式。双重否定律：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)(

8、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)A3.常用的等价式（P15表1-4.8）蕴涵等值式：ABAB等价等值式：AB(AB)(BA)(AB)(BA)4.子公式与等价置换定理子公式定义：如果X是合式公式A的一部