东北农业大学《离散数学》课件-第一部分4-6讲（金老师）.pdfVIP

离散数学 东北农业大学 第 4 讲 等值演算 导 入 用真值表法判断两个公式是否等 值在命题变项较多时，工作量是 很大的。 导 入 一个有效的方法是等值演算。 等 值 演 算 由已知的等值式推演出另外 一些等值式的过程。 等 值 演 算 置换规则 设Φ(A)是含公式A的命题公式 , Φ(B) 是用公式B置换了Φ(A)中所有(或部分） 的A后得到的命题公式，则 若B  A ，则Φ(B)  Φ(A)。 等 值 演 算 的 用 途 例4.1 验证p(qr)  (p∧q)  r 右边   (p ∧ q) ∨ r (蕴涵等值式)  ( p ∨  q) ∨ r (德摩根律)   p ∨ ( q ∨ r) (结合律)   p ∨ (q  r) (蕴涵等值式)  p  (q  r) (蕴涵等值式) 等 值 演 算 的 用 途 例4.2 判断公式 (p  q) ∧ p  q的类型 原式  ((pq) ∧ p) ∨ q   ((p ∨ q) ∧ p) ∨ q   (p ∨ q) ∨  p ∨ q  (p ∧  q) ∨  p ∨ q  (p ∨  p) ∧ ( q ∨  p) ∨ q  1 ∧ ( q ∨  p) ∨ q  ( q ∨  p) ∨ q   p ∨ ( q ∨ q)   p ∨ 1  1 所以为永真式。 等 值 演 算 的 用 途 文字断案问题 例4. 3 某勘探队有3名队员 ，有一天取得一块矿样 ，3人判断如下： 甲说：这不是铁，也不是铜。 乙说：这不是铁，是锡。 丙说：这不是锡，是铁。 经实验室鉴定发现 ，其中一人的两个判断全对 ，一人判对一 半 ，另一人全错。试根据以上情况 ，判断矿样的种类。 等 值 演 算 的 用 途 解: 设 p:矿样是铁。q:矿样是铜。r:矿样是锡。根据题设知有六种情况： ①甲正确，乙对一半，丙全错； ②甲正确，乙全错，丙对一半； ③甲对一半，乙正确，丙全错； ④甲对一半，乙全错，丙正确； ⑤甲全错，乙正确，丙对一半； ⑥甲全错，乙对一半，丙正确。 等 值 演 算 的 用 途 以上六种情况对应公式分别为： ①(p∧q)∧((p∧r)∨(p∧r)) ∧(p∧r) 0 ② (p∧q)∧(p∧r)∧((p∧r)∨(p∧r)) 0 ③((p∧q)∨(p∧q))∧(p∧r)∧(p∧r)p∧q∧r ④ ((p∧q)∨(p∧q))∧(p∧r)∧(p∧r)p∧q∧r ⑤ (p∧q)∧( p∧r)∧((p∧r)∨(p∧r)) 0 ⑥ (p∧q)∧ ((p∧r) ∨(p∧r) ) ∧ (p∧r) 0 等 值 演 算 的 用 途 六种情况对应公式 ①甲正确，乙对一半，丙全错； ①(p∧q) ∧((p∧r)∨(p∧r)) ∧(p∧r) 0 ②甲正确，乙全错，丙对一半； ② (p∧q) ∧(p∧r)∧((p∧r) ∨(p∧ r)) 0 ③甲对一半，乙正确，丙全错； ③((p∧q) ∨(p∧q)) ∧(p∧r) ∧(p∧r)p∧q ∧r ④甲对一半，乙全错，丙正确； ④ ((p∧q) ∨(p∧q)) ∧(p∧r)∧(p∧ r)p∧ q∧  r ⑤甲全错，乙正确，丙对一半；