离散数学课件真值表与等价公式.ppt

1-3命题公式与翻译,1-3.1 命题公式 P，PQ，(PQ)(PQ)都是复合命题。若P和Q是命题变元，则上述各式均称作命题公式。 P和Q称为命题公式的分量。 命题公式是没有确定的真值的，仅当在一个公式中命题变元用确定的命题代入时，才能得到一个命题。,1-3.1 命题公式,定义1-3.1 命题演算的合式公式（wff） (well formed formula) (1)单个命题变元本身是一个合式公式。 (2)如果A是合式公式，那么A是合式公式。 (3)如果A和B是合式公式，那么(AB), (AB), (AB), (A B)是合式公式。 (4)当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命题变元、联结词和括号的符号串是合式公式。,1-3.1 命题公式,注：这是一个递归方式的定义（递归定义） （1）是递归定义的基础 （2）、（3）是归纳 （4）是递归的界限 例： (PQ)就不是合式公式 联结词的运算次序： 使用括号 (2) 规定运算符运算优先次序：, , , ,1-3.2 翻译,例1. 除非你努力，否则你将失败。 解：设P：你努力。 Q：你将失败。 原命题可以符号化为： P Q 例2. 除非(仅当)我有时间，我才去看电影。 解：设P：我有时间。 Q：我去看电影。 原命题可以符号化为： P Q 或化为：QP,例3. 如果你和他都不固执己见的话，那么不愉快的事也不会发生了。 解：设P：你固执己见。 Q：他固执己见。 R：不愉快的事也不会发生了 原命题可以符号化为：（PQ）R 例4. 如果你和他不都是固执己见的话，那么不愉快的事也不会发生了。 解：设P：你固执己见。 Q：他固执己见。 R：不愉快的事也不会发生了 原命题可以符号化为： （PQ）R,作业(1-3),P12. (5),1-4真值表与等价公式,定义1-4.1真值表： 对于给定的命题公式，对其分量进行所有可能的真值指派得到该公式的相应的真值取值情况，将其汇列成表，称做该命题公式的真值表。 例：给出(PQ)的真值表。,1-4 真值表与等价公式,在真值表中，命题公式真值的取值数目，决定于分量的个数。n个命题变元组成的命题公式有2n种真值情况。 定义1-4.2 永真公式 永假公式： 无论对其分量作怎样的真值指派，其真值永为T，称为永真公式，记为T 。 无论对其分量作怎样的真值指派，其真值永为F，称为永假公式，记为F 。,1-4 真值表与等价公式,定义1-4.3 等价(equivalent)公式： 设A和B是两个命题公式，P1，P2，Pn是出现在A和B中的所有原子变元，若对P1，P2，Pn的任何真值指派， A和B真值相同，称A和B等价或逻辑相等。记作AB。 要证明两个命题公式等价，可用： （1）真值表法 （2）等价命题定律。,1-4 真值表与等价公式,例: PQ PQ P Q (PQ)(QP) P Q (PQ) (PQ) P15 表1-4.8 命题定律,1-4 真值表与等价公式,定义1-4.4 子公式 设A是一个命题公式，X是A的一部分且X本身也是公式，则称X为公式A的子公式。 定理1-4.1（等价置换） 设A是一个命题公式，X是A的一个子公式，若公式Y与X等价，用Y置换A中的X得到一个公式B，则 A B。 可用真值表法得证,1-4 真值表与等价公式,例：证明 Q(P(PQ) QP 证明：应用吸收律 P(PQ) P 左边 QP 得证！,1-4 真值表与等价公式,P19 (7) a) 证明 A(BA)