离散数学1.1-1.4

可通过判断A与B的真值表是否相同，来判断A与B是否等值。

24个重要的等值式：?∧∨→??

编号 表达式 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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?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)?A A ∧(A∨B)?A A∨1?1 A ∧0?0 A∨0?A A∧1?A A∨?A?1 德·摩根律 吸收律 零律 同一律 排中律 19 20 21 22 23 24

A∧?A?0 A→B??A∨B A?B?(A→B)∧(B→A) A→B??B→?A A?B??A??B 矛盾律 蕴涵等值式 等价等值式 假言易位 等价否定等值律 (A→B) ∧(A→?B) ??A 归缪论 根据已知的等值式，推演出另外一些等值式的过程称为等值演算。

置换定理：设?(A)是含命题公式A的命题公式，?(B)是用命题公式B置换了?(A)中的A之后得到的命题公式。如果A?B，则?(A)??(B)。

等值演算的用途： （1） 验证两个公式等值 （2） 判别命题公式的类型 （3） 解决实际问题

例6：用途1

p→(q→r)?(p∧q) →r 解：p→(q→r)

??p∨(q→r) （蕴涵等值式） ??p∨(?q∨r) （蕴涵等值式） ?(?p∨?q)∨r (结合律) ??(p∧q)∨r (德·摩根律) ?(p∧q) →r （蕴涵等值式）

例7：用途2

(1) q∨?((?p∨q) ∧p) (2) (p∨?p) →((q∧?q) ∧r) (3) (p→q) ∧?p

例8：用途3

A,B,C,D 4人做百米竞赛，观众甲、乙、丙预报比赛的名次为： 甲：C第一，B第二； 乙：C第二，D第三； 丙：A第二，D第四

比赛结束后发现甲、乙、丙每人报告的情况都是各对一半，试问实际名次如何（无并列者）？

解：pi,qi,ri,si表示A,B,C,D第i名，i=1,2,3,4

① (r1∧?q2) ∨(?r1∧q2) ?1 ② (r2∧?s3) ∨(?r2∧s3) ?1 ③ (p2∧?s4) ∨(?p2∧s4) ?1

①∧②?1 C不能既第一又第二，B和C不能都第二，所以

④ (r1∧?q2∧?r2∧s3) ∨(?r1∧q2?r2∧s3) ?1

③∧④?1 A，B不能同时第二，D不能第三又第四，所以

1? p2∧?s4 ∧r1∧?q2∧?r2∧s3

所以C第一，A第二，D第三，B第四。 作业：

p30-32 1.4 1.5 1.6 1.7 1.8 1.10(4)

1.4 联结词全功能集 p,q为两个命题 题 …式 记作 联结词 为真的条件iff 等值式 复合命