《离散数学》课件第二章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,“人都是要死的，苏格拉底是人，所以苏格拉底是要死的。”,苏格拉底三段论,第二讲 谓词逻辑,（,Predicate,Qogic,）,1.,个体、谓词和量词,2.,谓词公式,3.,等值演算,4.,范式,5.,推理理论,6.,谓词逻辑在计算机科学中的应用,考虑如下,3,个命题或推理：,1 “,有一个整数大于其他每个整数”,2 “,任给, 0,，存在, 0,，如果,|x-a|,，则,|f(x)-b|y),),),x,(,Z(x),y,(,(,Z(y),N(x,y),),(xy),),),2.1,个体,、谓词和量词,2 “,任给,0,，存在,0,，如果,|x-a|,，则,|f(x)-b|0),(,),(,(,0),(|,x,-,a,|,),(,f,(,x,)-,b,|,x,),y(,y,y),5,推理理论,2 全称量词引入规则（UG规则）,A(y),xA(x),成立的条件是：,(1).y在A(y)中自由出现,，且任意,y,，,A(y,),为真,；,(2).替换y的x要选择在A(y)中不出现的变元符号；,z(z,y,),z,z(,z,z,),5,推理理论,3,存在量词引入规则（,EG,规则）,A(c),xA(x),成立的条件是：,(1).c,是特定的个体常量；,(2).,替换,c,的,x,要选择在,A(c),中不出现的变元符号；,(1).P(,x,),Q(,c,),(2).(,x,)(P(,x,),Q(,x,),在使用存在量词引入规则时，替换个体,c,的变元应选择在公式中没有出现的变元符号，正确的推理是：,(1).P(,x,),Q(,c,),(2).(,y,)(P(,x,),Q(,y,),5,推理理论,4,存在量词消除规则（,ES,规则）,xA(x),A(c),成立的条件是：,(1).c,是特定的个体常量，,c,不能在前面的公式序列中出现；,(2).c,不在,A(x),中出现；,(3).A(x),中自由出现的个体变元只有,x,。,(1),(,x,)(,y,)(,x,y,)/,P,(2).(,y,)(,z,y,),/ US,(3).(,z,c,) / ES,(4).(,x,)(,x,c,),/ UG,(5).,c,c,/ US,由(2)得到(3)不能使用存在量词消除规则，因为(2)中含有除,y,以外的自由变元,z,。,5,推理理论,推理方法,直接法,间接法（反证法、,CP,规则）,5,推理理论,示例,证明,(,x)(C(x)W(x)R(x)(,x,) (,C(x)Q(x,)= (,x) (Q (,x)R(x,),【,分析,】,谓词逻辑的推理演算不能用真值表法，所以证明方法有直接证法、反正法和,CP,规则法。当要推理的结论是蕴含式时才能用,CP,规则法，能用,CP,规则法的尽量用,CP,规则法，因为此方法增加了一个前提条件。该题只能用直接证法、反正法。,5,推理理论,证明方法一（直接证法）：,1) (,x)(C(x)W(x)R(x,) P,2) (,x) (,C(x)Q(x,) P,3) (,C(a)Q(a,) ES, 2),4),C(a)W(a)R(a,) US,1),5),C(a,) T,I,3),6),W(a)R(a,) T,I,4),、,5),7),Q(a,) T,I,3),8),R(a,) T,I,6),9),Q(a)R(a,) T,I,7),、,8),10) (,x) (Q (,x)R(x,) EG,9),3),C(a)W(a)R(a,) US,1),4) (,C(a)Q(a,) ES, 2),(3),、,4),次序不能颠倒,),5,推理理论,示例,将下列推理符号化并给出形式证明,:,晚会上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（个体域为参加晚会的人）,解,设,P(x),：,x,唱歌了，,Q(x),：,x,跳舞了，则,前提：,x(P(x),Q(x),结论,：,xP(x),xQ(x),推理形式：,x(P(x),Q(x),xP(x),xQ(x),5,推理理论,(1),(,xP(x),xQ(x) P(,附加,),(2),x,P(x),x,Q(x) R,E,(1),(3),x,P(x) T,I,(2),(4),P(a) ES,(3),(5),x,Q(x) T,I,(2),(6),Q(a) US,(5),(7),x(P(x),Q(x) P,(8) P(a),Q(a) US,(7),(9) Q(a) T,I,(4),(8),(10) Q(a),Q(a),T,I,(6),(9),矛盾,因此，假设不成立，原推理形式正确。,5,推理理论,示例,所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。,解,个体域为全总域，需要引入的谓词包括：,Q(,x,):,x,是有理数；,R(,x,):,x,是实数；,N(,x,):,x,是无理数；,C(,x,):,x,是虚数。上述推理可符号化为：,前提,：,x,(Q(,x,),R(,x,),、,x,(N(,x,),R(,x,),、,x,(C(,x,),R(,x,),结论,：,x,(C(,x,),(,Q(,x,),N(,x,),，,验证该结论的公式序列如下：,5,推理理论,(1).,x,(Q(,x,),R(,x,) / P,(2). Q(,y,),R(,y,) / US,(3).,x,(N(,x,),R(,x,) / P,(4). N(,y,),R(,y,) / US,(5).,x,(C(,x,),R(,x,) / P,(6). C(,y,),R(,y,) / US,(7). C(,y,) / P(附加),(8).,R(,y,) / 分离规则，(6)和(7),(9).,Q(,y,) / 拒取式，(8)和(2),(10).,N(,y,) / 拒取式，(8)和(4),(11).,Q(,y,),N(,y),/ 合取的引入,(12). C(,y,),(,Q(,y,),N(,y,) / T, I (7)和(11),(13).,x,(C(,x,),(,Q(,x,),N(,x,) /UG,5,推理理论,示例,每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。,解,个体域为全总域，引入下列谓词：,P(,x,):,x,是旅客；,Q(,x,):,x,坐头等舱；,R(,x,):,x,坐二等舱；,S(,x,):,x,是富裕的。,原推理可符号化为：,前提,：,x,(P(,x,),(Q(,x,),R(,x,),、,x,(P(,x,),(Q(,x,),S(,x,),、,x,(P(,x,),S(,x,),、,(,x,(P(,x,),S(,x,),结论,：,x,(P(,x,),R(,x,),，验证该结论的公式序列如下：,5,推理理论,(1).,(,x,(P(,x,),S(,x,) / P,(2).,x,(P(,x,),S(,x,) / T, I (2),(3). P(,c,),S(,c,) / ES,(4). P(,c,) / T, I (3),(5).,S(,c,) / T, I (3),(6).,x,(P(,x,),(Q(,x,),R(,x,) / P,(7). P(,c,),(Q(,c,),R(,c,) / US, (6),(8). Q(,c,),R(,c,) / T, I (4)(7),(9).,x,(P(,x,),(Q(,x,),S(,x,)/P,(10).P(,c,),(Q(,c,),S(,c,)/ US(9),(11).Q(,c,),S(,c,) / T, I (4)(11),(12).Q(,c,),S(,c,)/ T, I(11),(13). ,Q(,c,)/ T, I (12)(5),(14). R(,c,)/ T, I (13)(8),(15). P(,c,) ,R(,c,)/ T, I(4)(14),(16). ,x,(P(,x,),R(,x,) / EG,5,推理理论,练习,每一个大学生不是文科生就是理科生；有的大学生爱好文学；小张不是文科生但他爱好文学。因此，如果小张是大学生，他就是理科生；,解,：个体域取全总域，要引入的谓词包括：,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,),，,验证该结论的公式序列为：,5,推理理论,(1).,Q(,c,),T(,c,)/ P,(2).,x,(P(,x,),(Q(,x,),S(,x,)/ P,(3). P(,c,),(Q(,c,),S(,c,)/ US (2),(4). P(,c,)/ P,（附加）,(5). Q(,c,),S(,c,)/ T, I (3)(4),(6).,Q(,c,)/ T, I (1),(7). S(,c,)/ T, I (5)(6),