《真值表与等价公式.ppt》由会员分享，可在线阅读，更多相关《真值表与等价公式.ppt（31页珍藏版）》请在三一文库上搜索。
1、,第一章 命题逻辑,第三讲,回 顾,一、命题公式,命题公式也称命题演算的合式公式(Well form formula,简写为wff)。 定义1-6 命题公式的递归定义如下： (1)单个的命题常元或命题变元是命题公式； (2)如果A是一个命题公式，则 (A)也是命题公式； (3)如果A和B都是命题公式，则(AB)、(AB)、(AB)、(AB)也是命题公式； (4)当且仅当有限次地应用（1）、(2)、（3）所得到的符号串是命题公式。,思考：命题公式是命题吗？为什么？,解答：命题公式不一定是命题。,因为命题公式没有确定的真值。,把符号命题翻译成自然语言命题： 这种翻译比较简单，只要求用词准确，力求保
2、持原命题的意思。 例 设 A: 今天下雨。 B: 今天下雪。 C: 今天天晴。试把下列命题翻译成自然语言: 1) (AB) 2) C (AB) 3) ABC 解 :1) 说今天下雨且下雪是不对的。 2) 今天天晴当且仅当今天既不下雨又不下雪。 3) 如果今天下雨或者下雪, 今天就不是晴天。,天没下雨，我也没有进城。 如果我有时间，我将进城。 如果天不下雨而且我又有时间，我将进城。 （RQ） Q（RP） （QR）（RQ）,练习：设P: 天下雨。 Q：我将进城。 R：我有时间。 试将下列命题形式化或翻译成自然语言命题。,1.3.1 真值表 命题公式没有确定的真值，但可以假设公式中各个分量的不同取值
3、来分析命题公式的真值情况。这样命题公式的真值情况就依赖于命题公式的结构和命题公式中各分量的真值指派。 定义1-8 设A是一个命题公式， 为出现在A中的所有命题变元。给 指定一组真值，称为对A的一组赋值（或真值指派）。,为了使命题公式的真值情况一目了然，可采用真值表的形式表示。 定义1-9 对命题公式分量真值的各种可能指派，就确定了命题公式的各种真值情况，将其汇成表，就是该公式的真值表。,真值表的构造规则： （1）在真值表左栏按字母顺序列出所有分量，右栏列出结果命题。 （2）用02n -1的二进制计数顺序给命题分量指派真值。 （3）为了使真值表更加明了，可将中间命题列在命题分量和结果命题之间。
4、例1-9 构造命题公式 的真值表。,P q,0 0 0 1 0 1 1,1 1 0 0,0 1 0 0,1 0 1 1,例1-10 构造公式 的真值表。 解：,P q r,0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 1,0 1 0 0 0 1 0 0 0 1 0 0 1 1 0,0 1 0 1 1 0 1 1,1 0 1 0 1 0 1 1,练习：Q(PQ)Q,132 命题公式的分类 从真值表中可以发现，某些命题公式不论其分量真值作何指派，其真值总为真，或者总为假。 例1-11 构造下列命题的真值表。 （1） （2） （3） 解(1),解（2）,解（3）
5、,定理1-1 任何两个重言式的合取或析取仍然是一个重言式。 证明：根据定义，因为任何重言式不论分量真值作何指派，其真值总为真，而两个真值为真的命题的合取或析取一定为真。,练习,1.判别下列命题公式中哪些是重言式?矛盾式?偶然式? (PQ)(QP) (PQ)(Q P)(PQ) (PQ)(PQP),1.3.3 等价公式,从真值表中可以发现，两个有相同命题分量但结构不同的命题公式，对其分量真值的不同指派，其真值总相同，如： 例1-12 构造下列命题公式的真值表。 （1）构造命题公式 的真值表。 （2）构造命题公式 的真值表。 解(1),P q,0 0 0 1 0 1 1,1 1 0 0 1 0 0,
6、1 1 0 1,1 1 0 1,1 1 0 1,解（2）,P q,0 0 0 1 0 1 1,1 0 1 1 0 0 0 0 1 0 0 0 0 1 0,1 0 0 1,1 0 0 1,.命题公式的等价 定义1-11 给定两个命题公式A和B，设 是所有出现在A和B中的命题分量，若对 的任一组真值指派，A和B的真值都相同，则称A和B等价或逻辑相等。记为A B 。 从真值表中可知，命题公式 等价； 等价。,定理1-2 设A和B是任意两个命题公式，A B 当且仅当AB为重言式 。 证明： 若A B ，则A和B的真值相同，即同为真或同为假。根据双条件命题的定义AB 为真，所以 AB 为重言式。 若AB
7、 为重言式，则AB 为永真，根据双条件命题的定义，A和B的真值相同，所以A B 。,Notice：,常用的命题等价公式有：,其中包含否定、合取和析取联结词的等价命题公式称为命题定律，包含条件和双条件联结词的等价命题公式 称为联结词归化。,联结词归化,交换律 E1,结合律 E2,分配律 E3,同一律 E4,互否律 E5,双否律 E6,等幂律 E7,零一律 E8,吸收律 E9,德摩根律 E10,联结词归化,E12,E13,E11,E14,E15,134 命题公式的等价演算 在算术运算中,我们可以根据运算符的优先次序，将算术表达式中某一部分用其结果代替，得到的新表达式与原表达式相等。在命题演算中，我
8、们同样可以用命题公式某一部分的等价命题公式代入，所得的新命题公式与原公式等价，这个过程称为置换。置换时要求被置换部分应该是命题合式公式。 定义1-12 如果X是命题公式A的一部分，且X本身是一个合式公式，则称X为公式A的子公式。,定理1-3 设X是命题公式A的子公式，若XY，如果将A中的X用Y置换，所得的公式B与命题公式A等价。 证明： 因为在相应分量的任一种真值指派下，X和Y的真值都相同，用Y置换X后，公式B与A在相应分量的真值指派下，其真值仍相同，所以AB 。,例1-13 推导证明吸收律 。 证明： 同一律 分配律 零 律 同一律 例1-14 推导证明下列各式 （1） 证明： 联结词规化 分配律 德.摩根公式,（2） 证明： 联结词归化 联结词归化 结合律 德.摩根公式 联结词归化,例1-15 已知程序流程图如下,试化简该流程。,y,n,y,n,解：运行S程序段的条件： p(pr) 运行W程序段的条件： pr 经过等价变换：,执行程序段S的条件为： 执行程序段W的条件为：,y,n,例1-16 化简下列各式 （1） 解： （2） 解：,利用等价演算可以证明公式的等价，也可以化简形式较复杂的命题公式。除此之外，还可以利用等价演算判断命题公式的类型。若命题公式A通过等价演算后A等价于1，则A必为重言式；若A等价于0，则A必为矛盾式。,