1.2命题逻辑等值演算.ppt

离散数学 本节的主要内容 等值式与基本的等值式 等值演算与置换规则 联结词全功能集 若A与B有相同的真值表，则说明在2n个赋 值下，A与B的真值都相同,于是等价式A?B应 为重言式。 定义1.10 设A,B是两个命题公式，若等价式 A ? B为重言式，则称A与B是等值的，记作A?B。 例2.1 判断下面两个公式是否等值 ┐(p∨q) 与 ┐p∧┐q 例题2.2 判断下列各组公式是否等值(1)p→(q→r)与(p∧q)→r (2)(p→q)→r与(p∧q)→r （1）双重否定律 A ? ┐┐A （2）幂等律 A ? A∨A ，A ? A∧A （3）交换律 A∨B ? B∨A，A∧B ? B∧A （4）结合律 (A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) （5）分配律???????? A∨(B∧C) ? (A∨B)∧(A∨C)  （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律） （6）德·摩根律????? ┐(A∨B) ? ┐A∧┐B ┐(A∧B) ? ┐A∨┐B （7）吸收律?????? ?A∨(A∧B) ? A，A∧(A∨B) ? A （8）零律 ??? A∨1 ? 1 ， A∧0 ? 0 （9） 同一律??????? A∨0 ? A 。A∧1 ? A （10）排中律??? A∨┐A ? 1 （11）矛盾律? A∧┐A ? 0 （12）蕴涵等值式?? ? A→B ? ┐A∨B （13）等价等值式??? A?B ? (A→B)∧(B→A) （14）假言易位???? ? A→B ? ┐B→┐A （15）等价否定等值式?????A?B ? ┐A?┐B （16）归谬论?????? (A→B)∧(A→┐B) ? ┐A 其中A,B,C可以代表任意的公式，称这样的等值式为等值式模式。 每个等值式模式都给出了无穷多个同类型的具体的等值式。 例如，在蕴涵等值式 A→B?┐A∨B 中， 取A=p，B=q时，得等值式 p→q?┐p∨q  取A=p∨q∨r，B=p∧q时，得等值式 (p∨q∨r)→(p∧q) ? ┐(p∨q∨r)∨(p∧q) 这些具体的等值式都被称为原来的等值式模式的一个实例。 由已知的等值式推演出另外一些等值式 的过程为等值演算。 置换规则 :设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若B?A，则Φ(B)?Φ(A)。 等值演算的基础 等值关系的性质：自反性：A?A。对称性：若A?B，则B?A。传递性：若A?B且B?C，则A?C。 基本的等值式 置换规则 等值演算的应用 证明两个公式等值 判断公式类型 解判定问题 证明两个公式等值(p→q)→r ? (p∨r)∧(┐q∨r) 例2.3 用等值演算法验证等值式 (p∨q)→r ? (p→r)∧(q→r) 方法三、通过等值演算化成容易观察真值的情况， 再进行判断。 A=(p→q)→r ? (┐p∨q)→r （蕴涵等值式） ? ┐(┐p∨q)∨r （蕴涵等值式） ? (p∧┐q)∨r ? （德摩根律） B=p→(q→r) ? ┐p∨(┐q∨r) （蕴涵等值式） ? ┐p∨┐q∨r ? （结合律） 000，010是A的成假赋值，而它们是B的成真赋值。 例1.13 若已知{┐，→｝是全功能集，证明{┐， ∨} 也是全功能集。 证明：由于{┐，→｝是全功能集，因而任一真值函数均可仅有 含 {┐，→｝中的联结词的命题公式表示。而对于任意的命题形 式A,B有 (A→B)?┐A∨B 因而任一真值函数均可仅有含{┐， ∨} 中的联结词的命 题公式表示，所以它是全功能集。 定理 都是联结词完备集 证：已知 为联结词完备集，因而只需证明其中的每个联结词都可以由 定义即可 类似可证明 是联结词完备集。 * * 等值演算 联结词全功能集 2.1 等值式 两公式什么时候代表了同一个命题呢？ 抽象地看，它们的真假取值完全相同时 即代表了相同的命题。 1.等值的定义及说明 用真值表可以验证两个公式是否等值。 判断A,B是否等值(A?B ) ?判断A ? B为重言式 ?A ? B的真值表最后一列全为1 ?在各种