《交大数理逻辑课件5-2谓词逻辑的等值和推理演算.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件5-2谓词逻辑的等值和推理演算.ppt（29页珍藏版）》请在三一办公上搜索。
1、作业讲评2,P37:4(1)证明：AB与B*A*同永真、同可满足,定理：(A*)*=A,(A)=A定理：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)求析取范式、主析取范式,(
2、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=m0 x mx1=m00 m01 m01 m11=(0,1,3),AB=(AB)(AB),结合律:(AB)C=A(BC),补充题：（主析取范式的应用）,某勘探队有3名队员，有一天取得一块矿样，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
4、(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)
5、,量词分配等值式,量词 对的分配律(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
6、(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
7、)(v2)(vn)A 其中：是或 vi是个体变项，i=1,n A是不含量词的谓词公式,公式的前束范式,定理（前束范式存在定理）谓词逻辑中的任何公式都存在与之等值的前束范式。注意:公式的前束范式不惟一例：(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
8、)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)
9、(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)
10、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 推理演算,推理演算利用谓词公式间的各种等价关系和蕴涵关系，通过一些推理规则，推出另一些谓词演算公式来，这就是谓词演算的推演过程。在推理过程中，除了可以
11、使用命题逻辑中的推理规则外，还增加了下面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)中约束出现的个体变项.在右式中，
12、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)中出现过.规则说明对于论域
13、中的任意个体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是
14、要死的,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(y)置换 G(y)F(y)假言三段论 x(G(x)F(x)UG,作业7,P84:3(1)(4)P85:4(1)(2)P85:5(1),有关命题逻辑的思考题,有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门。为协助你脱逃，今派两名战士负责解答你所提出的任何问题。惟可虑者，此两战士中一名天性诚实，一名说慌成性，今后生死由你自己选择。”逻辑学家深思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？,
