03 第三次课(范式与推理).ppt

* Hongzhi Qiao, Xidian Univ. * 构造下面推理的证明：如果小张追小李并且小李对小张有意思，则他们能成为朋友。或者他们不成为朋友，或者他们成为一对恋人。他们没有成为一对恋人。小张追小李。因此，小李对小张没有意思。　　解：先将简单命题符号化。　　P：小张追小李；　Q：小李对小张有意思；R：他们成为朋友；　　S：他们成为一对恋人。　　前提：(P∧Q)→R， R∨S， S，P 结论： Q 第一章 --- 数理逻辑 * Hongzhi Qiao, Xidian Univ. * 证明：用归谬法　 (1) Q 结论的否定引入　　(2) R∨S 前提引入　　(3) S 前提引入　　 (4) R (2)(3)析取三段论　　 (5) (P∧Q)→R 前提引入　　 (6) (P∧Q) (4)(5)拒取式　　 (7) P∨ Q (6)置换　　 (8) P 前提引入　　(9) Q (7)(8)析取三段论　　(10) Q∧ Q (1)(9)合取　　由于最后一步Q∧ Q = F，即(((P∧Q)→R)∧( R∨S)∧ S∧P)∧Q = F，所以推理正确。 第一章 --- 数理逻辑 Hongzhi Qiao, Xidian Univ. Propositional Equivalences 命题演算 Hongzhi Qiao, Xidian Univ. * Hongzhi Qiao, Xidian Univ. * 作业问题： 真值表 顺序000 001 010 011 100 101 110 111 步骤过于省略。 公式复杂时不细心。 　 第一章 --- 数理逻辑 * Hongzhi Qiao, Xidian Univ. * n 个命题变项所能组成的具有不同真值的命题公式仅有 2 个, 然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个。这样，首先就要问凡与命题公式A等值的公式能否都可以化为某一个统一的标准形式希望这种标准形能为我们的讨论带来些方便，如借助于标准形对任意两个形式上不同的公式，可判断它们的是否等值。借助于标准形容易判断任一公式是否为重言式或矛盾式。　 第一章 --- 数理逻辑 n * Hongzhi Qiao, Xidian Univ. * 标准形或范式这类术语数学上是常见的，如几何学中 ， 分别是圆和椭圆的范式。  第一章 --- 数理逻辑 * Hongzhi Qiao, Xidian Univ. * 合取称为积, 析取称为和。 由一些简单命题或其否定的合取组成的公式称为基本积。 由一些简单命题或其否定的析取组成的公式称基本和。 如 P, P, P∧Q, P∧ Q∧ P都是合取式， 而 P, P, P∨Q, P∨Q∨ Q都是析取式。  第一章 --- 数理逻辑 * Hongzhi Qiao, Xidian Univ. * 范式存在定理　 任一命题公式都存在有与之等值的合取范式和析取范式。 第一章 --- 数理逻辑 * Hongzhi Qiao, Xidian Univ. * 求范式的步骤 对一个已给的公式, 可按下述步骤求得该公式的合取范式和析取范式。　　(1) 消去已给公式中的联结词→和 。　 (2) 重复使用摩根律和双重否定律, 把否定词内移到直接作用于命题变项上。　　(3) 重复使用分配律。 第一章 --- 数理逻辑 * Hongzhi Qiao, Xidian Univ. * 求 (P∨Q) (P∧Q)的析取范式。解： (P∨Q) (P∧Q)= ( (P∨Q)∧(P ∧Q))∨( (P∨Q)∧ (P∧Q))= ( P∧ Q∧P∧Q)∨((P∨Q)∧( P∨ Q)) (摩根律、双重否定)= ( P∧ Q∧P∧Q)∨(P∧ P)∨(P∧ Q)∨(Q∧ P)∨(Q∧ Q) (分配律)这已是析取范式了。又因P∧ P, Q∧ Q,