离散数学课件第二章(第3讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,6,谓词逻辑的推理理论,1,、关于量词的四个推理规则,（,1,）全称指定规则（,US,规则）,该规则表示成：,x,A(x),A(c)(x,c,个体域,),如果对个体域中所有客体,x,A(x),成立，则对个体域中某个任意客体,c,，,A(c),成立。,（,2,）全称推广规则（,UG,规则）,如果能够证明对个体域中每一个客体,c,，命题,A(c),都成立，则可得到结论,x,A(x),成立。,该规则表示成：,A(c),x,A(x),（,3,）存在指定规则（,ES,规则）,该规则表示成：,xA(x),A(c),如果对于个体域中某些客体,A(x),成立，则必有某个特定的客体,c,，使,A(c),成立。,（,4,）存在推广规则（,EG,规则）,如果对个体域中某个特定客体,c,，有,A(c),成立，则在个体域中，必存在,x,，使,A(x),成立。,该规则表示成：,A(c),xA(x),2,、规则使用说明,（,3,）推导中既用,ES,，又用,US,，则必须先用,ES,，后用,US,方可取相同变元，反之不行。,xP(x),P(c),x,Q(x),Q(c),（,2,）在使用,ES,US,时,要求谓词公式必须是前束范式,（,1,）,用,US,ES,在推导中去掉量词，用,UG,EG,使结论量化（加上量词）。,（,4,）推导中连续使用,US,规则可用相同变元,x,P(x),P(c),x,Q(x),Q(c),（,5,）推导中连续使用,ES,规则时，使用一次更改一个变元。,x,P(x),P(c),x,Q(x),Q(d),例,指出下列推导中的错误，并加以改正。,(1),xP(x)P,(2)P(c)ES(1),(3),xQ(x)P,(4)Q(c)ES(2),解：,第二次使用存在量词消去规则时，所指定的特定个体应该是证明序列以前公式中没有出现过的，正确的推理是：,(1),xP(x)P,(2)P(c)ES(1),(3),xQ(x)P,(4)Q(d)ES(2),3,、,推理证明,(1),命题逻辑中的,P,规则,T,规则都可以引用到谓词逻辑的推理中。,(2),使用量词的四个推理规则对量词进行适当处理。,(3),推理过程中使用谓词逻辑的等价公式和永真蕴含公式。,(4),推理证明方法包括,直接证法和间接证法，其证明思想与命题逻辑中的类似。间接证法包括,CP,规则证明和反证法证明。,（,1,）直接证法,例,证明苏格拉底三段论：,“,人都是要死的，苏格拉底是人，所以苏格拉底是要死的。,”,4,、,推理证明实例,则翻译为：,x(M(x),D(x),，,M(s),D(s),解：设,M(x),：,x,是人；（特性谓词）,D(x),：,x,是要死的；,M(s),：苏格拉底是人；,D(s),：苏格拉底是要死的。,例,:,证明苏格拉底论证,（,x,）,(M(x),D(x),，,M(s),D(s),(1),x(M(x),D(x)P,(2)M(s)D(s)US(1),(3)M(s)P,(4)D(s),T(2)(3)I,例 证明,:,x(P(x),Q(x),x P(x),xQ(x),(1),x P(x),附加前提,(2),x(P(x),Q(x)P,(3)P(c)Q(c)ES(2),(4)P(c)US(1),(5)Q(c)T(3)(4)I,(6),xQ(x)EG(5),(7),x P(x),xQ(x)CP,（,2,）,CP,规则证明,例,将下列推理符号化并给出形式证明,:,每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。,解：,个体域取全总个体域，设,P(x),：,x,是大学生，,Q(x),：,x,是文科生，,S(x),：,x,是理科生，,T(x),：,x,是优等生，,c,：小张,前提：,x(P(x),(Q(x),S(x),，,x(P(x),T(x),，,Q(c),T(c),结论：,P(c),S(c),x(P(x),(Q(x),S(x),x(P(x),T(x),，,Q(c),T(c),P(c),S(c),推理形式如下：,(1)P(c),附加前提,(2),x(P(x),(Q(x),S(x)P,(3)P(c),(Q(c),S(c)US(2),(4)Q(c),S(c)T(1)(3)I,(5),Q(c),T(c)P,(6),Q(c)T(5)I,(7),Q(c),S(c)T(4)E,(8)S(c)T(6)(7)I,(9)P(c),S(c)CP,例 证明：,x(,P(x),Q(x),x,P(x),x,Q(x),(1),x,Q(x),附加前提,(2),x,Q(x)T(1)E,(3)Q(c)US(2),(4),x,P(x)P,(5)P(c)US(4),(6),P(c),Q(c)T(3)(5)I,(7),x(,P(x),Q(x)UG(6),(8),x(,P(x),Q(x)P,(9),x(,P(x),Q(x),x(,P(x),Q(x)T(7)(8)I,（,3反证法,例,将下列推理符号化并给出形式证明,:,晚会上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（个体域为参加晚会的人）,解：,设,P(x),：,x,唱歌了，,Q(x),：,x,跳舞了。,则：前提：,x(P(x),Q(x),结论：,xP(x),xQ(x),x(P(x),Q(x),xP(x),xQ(x),推理形式如下：,(1),(,xP(x),xQ(x),附加前提,(2),x,P(x),x,Q(x)T(1)E,(3),x,P(x)T(2)I,(4),P(a)ES(3),(5),x,Q(x)T(2)I,(6),Q(a)US(5),(7),x(P(x),Q(x)P,(8)P(a),Q(a)US(7),(9),P(a),Q(a)T(8)E,(10)Q(a)T(4)(9)I,(11)Q(a),Q(a),矛盾,T(6)(10)I,