《离散数学课件真值表与等价公式》由会员分享，可在线阅读，更多相关《离散数学课件真值表与等价公式（14页珍藏版）》请在金锄头文库上搜索。
1、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)所
2、得到的包含命题变元、联结词和 括号的符号串是合式公式。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：你
3、固执己见。Q：他固执己见。R：不愉快的事也不会发生了 原命题可以符号化为：（PQ）R 例4. 如果你和他不都是固执己见的话，那 么不愉快的事也不会发生了。 解：设P：你固执己见。Q：他固执己见。R：不愉快的事也不会发生了 原命题可以符号化为： （PQ）R作业(1-3)P12. (5)1-4真值表与等价公式定义1-4.1真值表：对于给定的命题公式，对其分 量进行所有可能的真值指派得到该公式 的相应的真值取值情况，将其汇列成表 ，称做该命题公式的真值表。 例：给出(PQ)的真值表。PQPQ(PQ) TTTF TFFT FTTF FFTF1-4 真值表与等价公式在真值表中，命题公式真值的取值数 目，
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 PQP
5、 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) A(A B) 证明:原式左边 A(BA) A (BA) A BA A（AB） A (A B) A(A B)作业(1-4)P19 (7) d)，f)
