工科离散数学课件 第一章 1_5_命题公式的真值与逻辑等价(2) - 命题公式等价.pptx

1.5.2 命题公式等价[命题公式等价]若命题公式 A(p1, p2, …, pn) 和 B(p1, p2, …, pn) 有相同的原子变元，且对 p1, p2, …, pn 的每组赋值，A 和 B 的真值都相同。记做 A?B，或 A≡B。(逻辑)等价 = (逻辑)相等 = 等值。——命题公式等价等同于函数相等（三要素）类比：f(x, y) = (x+y)2 = x2+2xy+y2 = g(x, y)1.5 命题公式的分类与逻辑等价-命题公式等价Try it：若A(p1, p2, …, pn) ? B(p1, p2, …, pn) ，能推出什么结论？答： ┐A(p1, p2, …, pn) ? ┐B(p1, p2, …, pn)A(┐p1, ┐p2, …, ┐pn) ? B(┐p1, ┐p2, …, ┐pn)——p∧q ? q∧p?(A与B真值相同，否定亦然) ┐(p∧q) ? ┐(q∧p) ? (A与B的等值性与变元取值无关) ┐p∧┐q ? ┐q∧┐p 2. 证明 A ? B 的3种方法1.5 命题公式的分类与逻辑等价-命题公式等价(1)真值表法例1-21：证明 p→q ? ┐p∨q 和 pˉ? q ? (p∧┐q)∨(┐p∧q)。pqp→q┐p∨qpˉ? qp∧┐q┐p∧q(p∧┐q)∨(┐p∧q)11110000100011010111101100110000Try it：利用真值表法可验证基本算律：交换律、结合律、分配律，德?摩根律等。 1.5 命题公式的分类与逻辑等价-命题公式等价(2)等价变换法（置换法）例1-22：证明 p→(q→r) ? q→(p→r)。[(等价)置换规则]若 X 是 A 的子公式，且X ? Y。若在 A 中用 Y 部分或全部替换 X 得到 B，则A ? B。问：置换规则的本质含义是什么？答：利用对命题公式本身或其子公式进行等价替换不改变原公式的值。证明：p→(q→r) ?(原公式等价变换) ┐p∨(q→r) ?(置换规则) ┐p∨(┐q∨r) ?(交换律、结合律) ┐q∨(┐p∨r) ?(置换规则、原公式等价变换) q→(p→r)——类比：A(x, y) = (x+1)2+y2 ，(x+1)2= x2+2x+1， B(x, y) = x2+2x+1+y2X X = Y Y 1.5 命题公式的分类与逻辑等价-命题公式等价(3)双条件式永真法定理：对于命题公式 A 和 B，A ? B 当且仅当 A?B 为永真式。——可作为“命题公式等价的判定定理”定理：A ? B 当且仅当 A→B 和 B→A均为永真式。证明：因为 A?B ? (A→B)∧(B→A)。若A ? B，则A?B为永真式，即(A→B)∧(B→A)为永真式，知A→B 和 B→A均为永真式。 此过程可逆。 3. 基本等价关系1.5 命题公式的分类与逻辑等价-命题公式等价序号等价关系含 义E1┐┐p? p对合律（双重否定律）E2p∧q ? q∧p交换律E3p∨q ? q∨pE4(p∧q)∧r ? p∧ (q∧r)结合律E5(p∨q) ∨r ? p∨ (q∨r)E6p∧(q∨r) ? (p∧q)∨(p∧r)分配律E7p∨(q∧r) ? (p∨q)∧(p∨r)E8┐(p∧q) ? ┐p∨┐q德?摩根律E9┐(p∨q) ? ┐p∧┐qE10p∨p ? p等幂律E11p∧p ? pE12q∨(p∧┐p) ? q同一律E13q∧(p∨┐p) ? qTry it：利用真值表法验证。 1.5 命题公式的分类与逻辑等价-命题公式等价序号等价关系含 义E14q∨(p∨┐p) ? 1零律E15q∧(p∧┐p) ? 0E16p?q ? ┐p∨q蕴含等值E17┐(p?q) ? p∧┐qE18p?q ? ┐q?┐p假言易位E19p?(q?r) ? (p∧q)?rE20p?q? (p?q)∧(q?p)等价等值E21p?q ? (p∧q)∨(┐p∧┐q)E22┐(p?q) ? p?┐qE23p?q ? ┐p?┐q等价否定等值E24(p?q)∧(p?┐q) ? ┐p归谬论E25pˉ? q ? ┐(p? q)E26p—? q ? (p∧┐q)∨(┐p∧q) 1.5 命题公式的分类与逻辑等价-命题公式等价1. 命题公式 p?q可用┐、∨表示成？ ——重要的转换关系2. 若s、