第30讲 逻辑等值的谓词公式.pptVIP

第30讲 逻辑等值的谓词公式 离散数学 4.4 逻辑等值的谓词公式 第4章 谓词逻辑 本讲内容 4.4 逻辑等值的谓词公式 1. 谓词公式等值的定义 Def 4-3 设A和B是谓词公式, 若A和B在任何解释下的取值都相同, 则称A和B是等值的,记为 A = B. (i) A = B的充要条件是谓词公式A ? B永真. (ii) “=”与“ ?”? 小结与作业 Any Questions 谓词公式等值的定义 1 基本等值式 2 (iii) 根据命题逻辑中的等值式得到一些谓词逻辑中的等值式. 对于命题变元p 和q, 有p ? q = ?p ? q, 因为p ? q ? ?p ? q永真, 所以对于谓词公式A和B, 有A ? B ? ?A ? B永真, 进而有A ? B = ?A ? B. 照这种方式, 可以得到很多的谓词逻辑中的等值式. 2. 基本等值式(remember) 10个与量词有关谓词逻辑中的基本等值式. I. 量词转换 (1) ??xA(x) = ?x?A(x). (2) ??xA(x) = ?x?A(x). 例4-12 举例说明I(1)(2)成立. Solution 令D是全班所有同学组成的集合, A(x): x今天来上课, 则“并非每位同学今天都来上课”逻辑等价于“有同学今天没有来上课”, “并非有同学今天来上课”逻辑等价于“每位同学今天都没有来上课”. II. 量词辖域的收缩与扩张 设B中不含自由变元x, 则有 (1) ?x(A(x) ? B) = ?xA(x) ? B. (2) ?x(A(x) ? B) = ?xA(x) ? B. (3) ?x(A(x) ? B) = ?xA(x) ? B. (4) ?x(A(x) ? B) = ?xA(x) ? B. 首先要说明的是, A(x){单独看A(x)!}含自由变元x, 而B中不含自由变元x,但A(x)和B都可能含其他自由变元. 就(1)来说, 左边?x的辖域为A(x) ? B, 右边?x的辖域为A(x), 从左边到右边量词的辖域收缩了, 而从右边到左边量词的辖域扩张了. 可以粗略地这样理解, 因为B中不含自由变元x, 所以?x及?x对B都不起作用. (1)的证明: 对于任意的个体域D上的解释I,假定?x(A(x) ? B)真,则对于任意d?D, A(d) ? B真,于是A(d)和B都为真, 所以?xA(x)和B取真,因此?xA(x) ? B真. 反过来亦成立. 例4-13 证明下列与蕴涵联结词有关的4个等值式, 其中B中不含自由变元x. (1) ?x(A(x) ? B) = ? xA(x) ? B. (2) ?x(B ? A(x) ) = B ? ?xA(x). (3) ?x(A(x) ? B) = ?xA(x) ? B. (4) ?x(B ? A(x) ) = B ? ?xA(x) . Proof (3) III. 量词分配律(量化算子?) (1) ?x(A(x) ? B(x)) = ?xA(x) ? ?xB(x). (2) ?x(A(x) ? B(x)) = ?xA(x) ? ?xB(x). Remark (1) ?x(A(x) ? B(x)) ? ?xA(x) ? ?xB(x). (2) ?x(A(x) ? B(x)) ? ?xA(x) ? ?xB(x). 在给定解释I: D = Z, A(x): x是偶数, B(x): x是奇数. How to remember? D = {班上同学}, A(x): x会唱歌, B(x): x会跳舞. Proof (2)任意给定个体域D上的解释I, 若?x(A(x) ? B(x))在I下取真, 则存在d?D, 使得A(d) ? B(d), 于是A(d)或B(d)为真,因此?xA(x) 或?xB(x)取真,进而?xA(x) ? ?xB(x)真. 反过来亦成立. IV. 双重量词 (1) ?x?yA(x, y) = ?y?xA(x, y). (2) ?x?yA(x, y) = ?y?xA(x, y). Remark ?x?yA(x, y) ? ?y?xA(x, y). D = R. A(x, y): x y. 例4-14 ?x?y(A(x) ? B(y)) = ?xA(x) ? ?yB(y). Proof 最后要说明的是, 等值置换定理在谓词逻辑中仍然成立. 谓词公式等值的定义 基本谓词公式等值式 习题4.4 5, 8 作业 ? * *