离散数学与---逻辑等价式 .pptVIP

§1.3逻辑等值式 判别等值的方法 真值表（适用于n=3） 等值演算法 用真值表判别A、B等值 例：求证A∧(A∨B)?A 构造公式A∧(A∨B) 和A的真值表； 判断两个的真值表是否相同。是，则等价。 基本等值式（一） 基本等值式(二） 置换定理 设Φ(A)是含命题公式A的命题公式， Φ(B)是用命题公式B置换了Φ(A)中的A得到的公式。 如果A ? B，则Φ(A) ? Φ(B) ?(A ∧ B) ? ? A ∨ ? B的证明 A ∧(A ∨ B) ? A的证明 A → B? ? A ∨ B的证明 等价演算（等值演算） 作用一：证明两公式等价 例：证明?(p∨(? p∧q)) ?(? p∧ ? q) 等价演算（等值演算） 作用二：判别一公式的类型 等价的传递性 A ?B,B ?C, 则A ?C 化简电路图 A(p,q)= ? (p∧q) ∧(p∨ ? q ) ? (? p∨ ? q) ∧(p∨ ? q ) ? (? p ∧p) ∨( ? q ∧p) ∨ ? q ? 0 ∨ ? q ? ? q §1.4联结词的全功能集 联结词的全功能集：能表达任一命题的联结词集。 例如{?,∨,∧} {?,∨,∧, → } 例1:试证{↑}是全功能集. 证：┐P?┐(P?P)?P↑P P?Q?┐┐(P?Q)?┐(P↑Q)?(P↑Q)↑(P↑Q) P?Q?┐(┐P?┐Q)?┐((P↑P)?(Q↑Q)) ?(P↑P)↑(Q↑Q) 例2.试证{┐，→}是全功能集 证：P?Q?┐(┐P?┐Q)?┐(P→┐Q) P?Q?┐(┐P)?Q?┐P→Q 从{0,1}n到{0,1}的真值函数有22n个 本节小结 1.基本等值式 子公式：公式X是公式A的组成部分，称X为A的子公式。 代入规则:A(p1,p2,…,pi,…,pn),另一公式Bi处处代替pi出现的地方，得到的公式A’＝A (p1,p2,…,Bi,…,pn) ，A’称为A的代入实例。 例 结论：如果A是永真式，则A的任一个代入实例都是永真式。 * 西华大学 定义：若公式A、B构成A ?B为永真式，称A、B逻辑等值，记为A?B A ?B 成为永真式，即是A为0时，B为0；A为1时B为1。 A?B，A、B不一定具有相同变元。例如：P ∧ ?P ? Q ∧ ?Q A?B中,?是联结词， A ?B是公式； A?B中,?是符号 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 A ∧ (A ∨ B) A B A 返回判别等 值的方法 A ∨(A ∧ B) ? A A ∧(A ∨ B) ? A 吸收律 A ∨ 1 ? 1 A ∧ 0 ? 0 零律 A ∨ 0 ? A ?(A ∨ B) ? ? A ∧ ? B (A∨B)∨C?A∨(B∨C) A∨B ?B∨A A∨A ?A 等值式 A ∧ 1 ? A 同一律 ?(A ∧ B) ? ? A ∨ ? B 德·摩根律 (A∧B)∧C?A∧(B∧C) 结合律 A∧B?B∧A 交换律 A ∧A ?A 等幂律 ? ?A ?A 双重否定 名称 (A→B)∧ (A → ?B) ? ? A 归谬律 A ∨ ? A ?1 等值式 (A ∧ B) → C ? A →(B →C) 输出律 A → B? ? B → ? A 逆否律 A? B?（A→B）∧（B→A） 等价等值式 A → B? ? A ∨ B 蕴涵等值式 A ∧ ? A ?0 否定律 名称 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 ?(A ∧ B) ? ? A ∨ ? B B A 1 2 4 5 3 1 1 1 1 6 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 1 A ∧ (A ∨ B) ? A B A 2 1 1 1 1 1 3 1 1 1 1 3 1 1 1 1 1 0 1 0 0 0 0 1 A → B ? ? A ∨ B B A 2 1 3 1 1 0 0 1 1 1 0 证明: ?(p∨ (? p∧q)) ? ?((p∨? p)∧ (p∨q)) 分配律 ? ?(T∧ (p∨q)) 否定律 ? ? (p∨q) 同一律