离散数学：第一章第3节 等值演算201009final [兼容模式].pdfVIP

第一章命题逻辑 §1.3 等值演算 定义1.9 设A , B 是公式。如果对于每个真值赋值v ， §1.1 命题和联结词 v(A) = v(B) ，则称A 和B 等值，也称A 与B 逻辑等 §1.2 公式和真值赋值 价，记为A ⇔B 。 §1.3 等值演算 AA ⇔⇔BB 的意思是的意思是：：AA 和和BB 恒等恒等，，即不管其中出现即不管其中出现 §1.4 对偶定理 的命题变元取什么值，A 和B 的值都是一样的。 §1.5 联结词的完全集 §1.6 范式 §1.7 逻辑推论 A ⇔B 当且仅当A ↔B 是永真式。（等值定理） 逻辑等价关系⇔和双条件联接词↔的区别： 证明：（充分性）如果A和B等值，那么根据定义 1. ↔是联接词，代表逻辑运算，A ↔B 的结果仍 1.9，所以对于每个真值赋值v ，v(A) ＝v(B) ， 然是一个命题公式；而⇔描述两个公式之间的 也就是也就是AA和和BB 的真值总是相同的真值总是相同，，所以所以AA ↔↔BB 是永是永 逻辑等价关系逻辑等价关系，，AA ⇔⇔BB 的结果是非命题公式的结果是非命题公式 真式 2. 如果要求计算机来判断公式A 、B是否逻辑等价， （必要性）如果A ↔B 是永真式，那么对于任何一 即A ⇔B 那是办不到的，但是计算机却可以计 个真值赋值v ，二者的真值要么都真，要么都假， 算公式A ↔B 是否是永真式 即他们的真值总是相同的，则A ⇔B 用真值表判断两公式是否等值 ⇔等价关系的性质： p q p q (p q) p q p q ∨ ¬ ∨ ¬ ¬ ¬ ∧¬ 1. 自反性：对于任意公式A ，A ⇔A 。 0 0 0 1 1 1 1 2.对称性：若A ⇔B ，则B ⇔A 。 33.传递性传递性：若若AA ⇔BB 且且BB ⇔CC，则则AA ⇔CC 。 00 11 11 00 11 00 00 1 0 1 0 0 1 0 1 1 1 0 0 0 0 ¬(p ∨q) ⇔¬p ∧¬q 1 常用的等值式模式 常用的等值式模式 交换律 A ∨B ⇔B ∨A A ∧B ⇔B ∧A 双重否定律 A ⇔¬¬A