交大数理逻辑课件5-2谓词逻辑的等值和推理演算.ppt

作业讲评2,P37: 4(1) 证明： AB与B*A*同永真、同可满足,定理2.5.2： (A*)*=A, (A)= A 定理2.5.3： A = A* 证明： 若AB永真，则 B A 永真 由 A = A*， B = B*，得 B*A* 永真 即： B*A* 永真 反之，若B*A* 永真，则(A*)* (B*)*永真 由 A=(A*)*，B=(B*)*，得 AB 永真 AB与B* A*同永真 显然， A B与B* A*同可满足,P37：5(3)求析取范式、主析取范式,(PQ) (PQ) = ( P Q) (P Q)( P Q) =( P Q)(P Q)( P Q) = (P Q)(P Q)( P Q) = (1,2,3),AB = (AB)(AB),P37：5(8)求析取范式、主析取范式,(PQ)(Q P) (Q P) = (P Q)(QP) Q) P) = (P Q)(Q P)Q)(QP) Q) P) = (P Q)(Q P)Q) P) = (P Q)(PQ) P) = (P Q)(PQ) P)(P Q) P) =(PQ)(PQ) = PQ = m0x mx1 = m00 m01 m01 m11 = (0,1,3),AB = (AB)(AB),结合律: (AB)C = A(BC),补充题：（主析取范式的应用）,某勘探队有3名队员，有一天取得一块矿样，3人的判断如下： 甲说：这不是铁，也不是铜； 乙说：这不是铁，是锡； 丙说：这不是锡，是铁。 经实验室鉴定后发现，其中一个人两个判断都正确，一个人判对一半，另一个人全错了。根据以上情况判断矿样种类。 解：设P：矿样为铁， Q：矿样为铜， R：矿样为锡。 则：甲： P Q 乙： P R 丙： P R,补充题,设P: 矿样是铁,Q : 矿样是铜, R : 矿样是锡 “”：全对，“&”：对一半，“”：全错 以甲为例， “”：全对 P Q “&”：对一半 ( P Q)( P Q) “”：全错 P Q 例:甲全对，乙对一半，丙全错 (PQ)(PR)(P R)(PR) =(PQ)(P R) (PR) (PQ)(PR)(P R),甲： P Q 乙： P R 丙： P R,第5章 谓词逻辑的等值和推理演算,5.1 否定型等值式 5.2 量词分配等值式 5.3 范式 5.4 基本的推理公式 5.5 推理演算 5.6 谓词逻辑的归结推理法,量词分配等值式,量词对、 的分配律 (x)(P(x)q) = (x)P(x)q (x)(P(x)q) = (x)P(x)q (x)(P(x)q) = (x)P(x)q (x)(P(x)q) = (x)P(x)q 量词对的分配律 (x)(P(x) q) = (x)P(x) q (x)(P(x) q) = (x)P(x) q (x)(q P(x) = q (x)P(x) (x)(q P(x) = q (x)P(x),量词分配等值式,量词对的分配律 (x)(P(x)Q(x) = (x)P(x)(x)Q(x) 注意：对无分配律 (x)P(x) (x)Q(x) (x)(P(x) Q(x) 量词 对的分配律 (x)(P(x)Q(x) = (x)P(x)(x)Q(x) 注意：对无分配律 (x)(P(x)Q(x)(x)P(x)(x)Q(x),量词分配等值式,量词 对的分配律 (x)(P(x)Q(x) = (x)P(x)(x)Q(x) 注意：对无分配律 由前面证明得： (x)P(x)(x)Q(x)(x)(P(x)Q(x) 而 (x)P(x)(x)Q(x) = (x)P(x)(x) Q(x) = (x)P(x)(x) Q(x) (x)P(x)(x)Q(x)(x)(P(x)Q(x) 由双条件否定等价式有 (x)(P(x)Q(x)(x)P(x)(x)Q(x),(x)(P(x)Q(x) = (x) (P(x)Q(x) = (x)(P(x)Q(x),例 将下面命题用两种形式符号化,(1) 没有不犯错误的人 解： 设 F(x)：x是人，G(x)：x犯错误. x(F(x)G(x) = x (F(x) G(x) = x( F(x) G(x) = x(F(x)G(x) (2) 不是所有的人都爱看电影 解：令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x) = x (F(x) G(x) = x ( F(x)G(x) = x(F(x)G(x),(x)P(x) = (x)P(x),(x)P(x) = (x)P(x),只要的人，他就会犯错误,有的人不爱看电影,5.3 前束范式,如下列公式是前束范式： xy(F(x)(G(y)H(x,y) ， x(F(x)G(x) 下列公式不是前束范式： x(F(x)y(G(y)H(x,y)， x(F(x)G(x),定义 如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则称为前束范式。 前束范式有如下形式： (v1)(v2) (vn)A 其中：是或 vi是个体变项，i=1, ,n A是不含量词的谓词公式,公式的前束范式,定理5.3.1（前束范式存在定理） 谓词逻辑中的任何公式都存在与之等值的前束范式。 注意: 公式的前束范式不惟一 例： (x)(M(x)F(x) = (x) (M(x)F(x) = (x)(M(x)F(x) （量词否定等值式） = (x)(M(x)F(x) 求公式的前束范式的方法: 利用重要等值式、置换规则、换名规则、代替规则进行等值演算.,例 求下列公式的前束范式,(x)F(x)(x)G(x) 解: (x)F(x)(x)G(x) = (x)F(x)(x)G(x) （量词否定等值式） = (x)(F(x)G(x) （量词分配等值式） 另有一种形式 (x)F(x)(x)G(x) = (x)F(x)(x)G(x) = (x)F(x)(y)G(y) ( 代替规则 ) = (x)(y) (F(x)G(y) ( 量词辖域扩张 ) 两种形式是等值的,例 求下列公式的前束范式,(x)F(x)(y) (G(x,y)H(y) 解 (x)F(x)(y)(G(x,y)H(y) =(z)F(z)(y)(G(x,y)H(y)（换名规则） =(z)(y)(F(z)(G(x,y)H(y),(x)(A(x)B) = (x)A(x)B,(x)(q P(x) = q (x)P(x),5.4 基本的推理公式,基本的推理公式 (x)P(x)(x)Q(x) (x)(P(x)Q(x) (x)(P(x)Q(x) (x)P(x)(x)Q(x) (x)(P(x)Q(x) (x)P(x)(x)Q(x) (x)(P(x)Q(x) (x)P(x)(x)Q(x) (x)(P(x) Q(x) (x)P(x) (x)Q(x) (x)(P(x) Q(x) (x)P(x) (x)Q(x) (x)(P(x)Q(x) (x)(Q(x)R(x) (x)P(x)(x)R(x) (x)(P(x)Q(x) P(a) Q(a),(x)(P(x)Q(x) (x)P(x)(x)Q(x),解释性的证明 设解释I下有 (x)(P(x)Q(x) =T 则有x0个体域D，使 (P(x0)Q(x0) =T 从而有 P(x0)=T， Q(x0)=T， 也即 (x)P(x)(x)Q(x)=T 在解释I下 (x)(P(x)Q(x) (x)P(x)(x)Q(x) 但反之，不成立,基本的推理公式,基本的推理公式 (x)(y)P(x, y) (x)(y)(P(x,y) (x)(y)P(x, y) (y) (x)(P(x,y) 解释性的证明 设一解释I下有 (x)(y)P(x, y) =T 于是有x0个体域D，使对一切的y D,都有 P(x0,y) =T 从而有对一切的yD, 都有一个x（均选为x0）,使 P(x, y)=T， 也即 (y) (x)P(x,y)=T (x)(y)P(x, y) (y) (x)(P(x,y),5.5 推理演算,推理演算 利用谓词公式间的各种等价关系和蕴涵关系，通过一些推理规则，推出另一些谓词演算公式来，这就是谓词演算的推演过程。 在推理过程中，除了可以使用命题逻辑中的推理规则外，还增加了下面4条关于量词的推理规则。 UI 规则 UG规则 EI 规则 EG规则,推理规则,(1)前提引入规则 (2)结论引入规则 (3)置换规则 (4)假言推理规则 (AB)A B (5)附加规则 A (AB) (6)化简规则 (AB) A (7)拒取式规则 (AB)B A,(8)假言三段论规则 (AB)(BC) (AC) (9)析取三段论规则 (AB)B A (10)构造性二难推理规则 (AB)(CD)(AC) (BD) (11)合取引入规则 A, B AB,有关量词的推理规则,(12) 全称量词消去规则（UI规则） 两式成立的条件是： 在左式中，取代x的y应为任意的不在A(x)中约束出现的个体变项. 在右式中，c为任意个体常项. 用y或c去取代A(x)中的自由出现的x时，一定要在x自由出现的一切地方进行取代. 规则说明： 若个体域中的所有个体都满足谓词A，则个体域中任一个体c也满足谓词A。,有关量词的推理规则,(13) 全称量词引入规则（UG规则） 该式成立的条件是： 无论A(y)中自由出现的个体变项y取何值，A(y)应该均为真. 取代自由出现的y的x，也不能在A(y)中约束出现. 规则说明 如果能够证明对论域中任一个体x断言A(x)都成立，则有结论xA(x)成立。,有关量词的推理规则,(14) 存在量词引入规则（EG规则） 该式成立的条件是： c是使A为真的特定个体常项. 取代c的x不能在A(c)中出现过. 规则说明 对于论域中的任意个体c，如果A(c)为真，则必定可以得到结论xA(x)为真。,有关量词的推理规则,(15) 存在量词消去规则（EI规则） 该式成立的条件是： c是使A为真的特定的个体常项. c不在A(x)中出现. 若A(x)中除自由出现的x外，还有其他自由出现的个体变项，此规则不能使用. 规则说明 对于论域中的某些个体，若xA(x)和xB(x)都是真，则对于某些c和d， 可以断定A(c)B(d)必定为真， 但是不能断定A(c)B(c)为真,注意: 这些个体不是任意的。这点非常重要,使用推理规则的推演算举例,例1 证明苏格拉底三段论: “人都是要死的, 苏格拉 底是人，所以苏格拉底是要死的.” 令 F(x): x是人, G(x): x是要死的, a: 苏格拉底 前提：x(F(x)G(x)，F(a) 结论：G(a) 证明： F(a) 前提引入 x(F(x)G(x) 前提引入 F(a)G(a) UI G(a) 假言推理 注意：使用UI时，用a取代x .,使用推理规则的推演算举例,例2 乌鸦都不是白色的. 北京鸭是白色的. 因此，北京鸭不是乌鸦. 解：令F(x): x是乌鸦, G(x): x是北京鸭, H(x): x是白色的 前提：x(F(x)H(x)， x(G(x)H(x) 结论：x(G(x)F(x),使用推理规则的推演算举例,前提：x(F(x)H(x)， x(G(x)H(x) 结论：x(G(x)F(x) 证明： x(F(x)H(x) 前提引入 F(y)H(y) UI x(G(x)H(x) 前提引入 G(y)H(y) UI H(y)F(