离散数学第二章.docVIP

2.1 等值式 一、等值式的概念 ????两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。 ????设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。 定义2.1 设A,B式两个命题公式，若A,B构成的等价式AB为重言式，则称A与B是等值的，记作AB. ????定义中给出的符号不是联结词符，它是用来说明A与B等值（AB是重言式）的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。 ????判断等值式有如下方法： ???1.真值表 ???2.等值演算???3.范式 二、用真值表判断公式的等值 例2.1 判断下面两个公式是否等值：????????┐(pq)与┐p┐q ???解 用真值表法判断┐(pq)(┐p∧┐q)是否为重言式。此等价式的真值表如表2.1所示，从表中可知它是重言式，因而┐(pq)与┐p┐q等值，即┐(pq)(┐p∧┐q)。 ????其实，在用真值表法判断AB是否为重言式时，真值表的最后一列（即AB的真值表的最后结果）可以省略。若A与B的真值表相同，则AB，否则，AB（用来表示A与B不等值，也是常用的元语言符号）。 表2.1 (pq)(┐p∧┐q)的真值表 例2.2 判断下列各组公式是否等值： ????（1）p→(q→r)与(pq)→r ????（2）(p→q)→r与(pq)→r ????解 表2.2中列出了p→(q→r)，(pq)→r，(p→q)→r的真值表，不难看出p→(q→r)与(pq)→r等值，即 ????????(p→q)→r(p∧q)→r 而(p→q)→r与(pq)→r的真值表不同，因而它们不等值，即 ????????(p→q)→r(p∧q)→r 表2.2 3个公式的真值表 三、等值演算 ????虽然用真值法可以判断任何两个命题公式是否等值，但当命题变项较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的重言式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。本书给出16组重要的等值式，希望读者牢牢记住它们。在下面公式中出现的A,B,C仍然是元语言符号，它们代表任意的命题公式。 ????1. 双重否定律????????A┐┐A （2.1） ????2. 幂等律????????AA∨A,AA∧A （2.2） ????3. 交换律????????ABB∨A，ABB∧A （2.3） ????4. 结合律????????(AB)∨CA∨(B∨C) ????????(A∧B)∧CA∧(B∧C) （2.4） ????5. 分配律????????A(B∧C)(A∨B)∧(A∨C) （对的分配律） ???? ???A(B∨C)(A∧B)∨(A∧C) （对的分配律） （2.5） ????6. 德摩根律????????┐(AB)┐A∧┐B，┐(AB)┐A∨┐B （2.6） ????7. 吸收律????????A(A∧B)A，A(A∨B)A （2.7） ????8. 零律????????A11,A∧00 （2.8） ????9. 同一律????????A0A，A1A （2.9） ????10. 排中律????????A┐A1 （2.10） ????11. 矛盾律????????A┐A0 （2.11） ????12. 蕴涵等值式????????A→B┐A∨B （2.12） ????13. 等价等值式????????(AB)(A→B)∧(B→A) （2.13） ????14. 假言易位????????A→B┐B→┐A （2.14） ????15. 等价否定等值式????????AB┐A┐B （2.15） ????16. 归谬论????????(A→B)(A→┐B)┐A （2.16） ????以上16组等值式包含了24个重要等值式。由于A,B,C可以代表任意的公式，因而以上各等值式都是用元语言符号书写的，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式（2.12）中，取A=p，B=q时，得等值式 ????????p→q┐ p∨q 当取A=pq∨r，B=pq时，得等值式????????(pq∨r)→(p∧q) ┐(p∨q∨r)∨(p∧q) 这些具体的等值式都被称为原来的等值式模式的代入实例。 每个具体的代入实例的正确性都可以用真值表证明之，而每个等值式模式可用归纳法证明之。 ????由已知的等值式可以推演出更多的等值式，简单快速推理，还需要