一阶逻辑等值演算与推理课件.ppt

1、第五章 一阶逻辑等值演算与推理主要内容：重要的等值式 在有限个体域内消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式基本规则 置换规则 换名规则 代替规则前束范式与公式的前束范式自然推理系统F要求：深刻理解并记住重要等值式，并能熟练地应用它们熟练地使用置换规则、换名规则、代替规则准确地求出给定公式的前束范式正确地使用UI, UG, EG, EI规则，特别要注意它们之间的关系对给定的推理，正确地构造出它的证明 一、量词否定等值式例：设例：设P(x)P(x)：X X今天去过操场今天去过操场（1 1）不是所有人今天去过操场）不是所有人今天去过操场 存在一些人今天没有去过操场存

2、在一些人今天没有去过操场 （2 2）不存在一些人今天去过操场）不存在一些人今天去过操场 所有人今天都没有去过操场。所有人今天都没有去过操场。 )()()()(XPXXPX)()()()(XPXXPX5.1 一阶逻辑等值式与置换规则n证：设个体域中的客体变元为证：设个体域中的客体变元为A A( (x x) )x x) )( () )A A( (a a. . . .) )A A( (a a) )A A( (a a) ) )A A( (a a. . . .) )A A( (a a) )( (A A( (a ax x) )A A( (x x) )( (n n2 21 1n n2 21 1A(x)A(x

3、)x) x)( () )A(aA(a. .) )A(aA(a) )A(aA(a) )A(aA(a. .) )A(aA(a) )(A(a(A(ax)A(x)x)A(x)( (n n2 21 1n n2 21 1naaa,21二、量词辖域的扩张与收缩等值式B B) )x xA A( (x x) )( (B B) )x x( (A A( (x x) )B B) )x xA A( (x x) )( (B B) )x x( (A A( (x x) )B B) )x xA A( (x x) )( (B B) )x x( (A A( (x x) )B B) )x xA A( (x x) )( (B B) )

4、x x( (A A( (x x) )例：证明：例：证明：)B)x(A(x)B)x(xA(B)x(A)x()B)x(A)x()B)x(A(x)B)x(A(xB)x(A(x证：证：类似的可以推出类似的可以推出：A A( (x x) ) )x x( (B Bx xA A( (x x) ) )( (B BA A( (x x) ) )x x( (B Bx xA A( (x x) ) )( (B BB B) )x x( (A A( (x x) )B B) )x xA A( (x x) )( (B B) )x x( (A A( (x x) )B B) )x xA A( (x x) )( ( 例如例如Q Q(

5、 (z z) ) )y y) )y yP P( (x x, ,x x) )( ( ( (Q Q( (z z) ) )y y) )y y) )P P( (x x, ,x x) )( ( ( (Q Q( (y y) ) )x x) )P P( (x x) )( ( (Q Q( (y y) ) )x x) )( (P P( (x x) )( (三、量词分配等值式n例如例如 联欢会上所有人既唱歌又跳舞和所有人唱联欢会上所有人既唱歌又跳舞和所有人唱歌且所有人跳舞。这两个语句意义相同。歌且所有人跳舞。这两个语句意义相同。)x(B(x)x(A(x)x(B)x(A(x)x(x)x(xA()x(B)x(A(xB

6、根据上式亦有：根据上式亦有：xB(x)xB(x)xA(x)xA(x)B(x)B(x)x(A(x)x(A(x)x(x)x(xA)x(B)x(A(xB四、多个量词的使用y y) )x xA A( (x x, ,y yy y) )y yA A( (x x, ,x xy y) )x xA A( (x x, ,y yy y) )y yA A( (x x, ,x x对于甲村所有的人，乙村都有人和他同姓。存在一个乙村的人，甲村的人和他同姓。），（）（yxAyx），（）（yxAxy全称量词与存在量词在公式中出现的次序，不能随意更换。具有两个量词的谓词公式，有如下一些蕴含关系。），（）（），（）（），（）（），

7、（）（），（）（），（）（），（）（），（）（），（）（），（）（），（）（），（）（yxAyxyxAxyyxAxyyxAyxyxAxyyxAyxyxAyxyxAxyyxAyxyxAxyyxAxyyxAyx存在一个甲村的人，乙村的人都和他同姓。对于乙村的人，甲村都有人和他同姓。），（）（yxAyx），（）（yxAxy五、量词分配中的一些推理关系式这些学生都聪明或这些学生都努力这些学生都聪明或这些学生都努力 这些学生都聪明或努力。这些学生都聪明或努力。这些学生都聪明或努力这些学生都聪明或努力 这些学生都聪明或这些学生都努力。这些学生都聪明或这些学生都努力。故有：即）（）（由上式得)x(B)x(A

8、)(x()x(B)x()x(A)x( (x)A(x)x)(x)x)(A(x)x)(BB(x)x)(A(x)(x)x)(x)A(x)(BB(x)Bxx)A(x)(x)A(x)x)(）（）（B说明: 以上五种单个量词的谓词演算式可类似推以上五种单个量词的谓词演算式可类似推 广到多个量词的情况。广到多个量词的情况。)x(xB)x(xA)x(B)x(A(x)x(xB)x(xA)x(B)x(A(x类似的有：类似的有：(x)x)(A(x)(x)x)(x)A(x)(BB(x)Bxx)A(x)(x)A(x)x)(）（）（B5.2 一阶逻辑前束范式前束范式：前束范式：谓词公式具有形式：谓词公式具有形式：则该公式

9、叫前束范式。其中则该公式叫前束范式。其中 i i是量词是量词 或或 ，A A 是是不含不含量词的谓词公式。量词的谓词公式。AxQxQxQkk2211)(),()()(),(),()()()(yRyxQxyzRyxQzyx 例例：方法：利用换名规则及代替规则求前束范式例例:求下列公式的前束范式求下列公式的前束范式.)()()()(xQxxPx xQ(x)xQ(x)P(x)P(x)x x解：解：原式u u) ) )y y, ,Q Q( (x x, ,z z) ) )P P( (y y, ,z z) )u u( ( (P P( (x x, ,z zy yx x、u u) ) )y y, ,u u)

10、)Q Q( (x x, ,( (z z) ) )P P( (y y, ,z z) )z z) )( (P P( (x x, ,y y) )( ( (x x) )( ( (2 2、原式Q Q( (x x) ) )P P( (x x) )x x( (z z) ) ) B B( (u u, ,u u) )( (A A( (z z, ,R R) )B B( (u u, , y y) )z z A A( (x x, ,R Ru uy yx xy)y)B(x,B(x,x) x)y(A(y,y(A(y,y) y)yB(x,yB(x,x xy) y)yA(x,yA(x,xx3、3、解：第一步：否定深入解：第一

11、步：否定深入y)y)B(x,B(x,x) x)y(A(y,y(A(y,y) y)yB(x,yB(x,x xy) y)yA(x,yA(x, x xy)y)B(x,B(x,x) x)(A(y,(A(y,y yy) y)B(x,B(x,y yx xy) y)yA(x,yA(x,xx提到前面提到前面第二步：改名以便把量第二步：改名以便把量词z)z)B(u,B(u,u) u)(A(z,(A(z,z zr) r)B(u,B(u, u uy) y)yA(x,yA(x,xxrz)z)B(u,B(u,u) u)z(A(z,z(A(z,r) r)B(u,B(u, u uy) y)yA(x,yA(x,xxrz)z)

12、B(u,B(u,u) u)(A(z,(A(z,r) r)B(u,B(u, y) y)zA(x,zA(x,u uy yx xr、)x(xG)x(xF()x(G)x(F(x)x(xG)x(xF()x(G)x(F(x)x(xG)x(xF()x(G)x(F(x)x(xG)x(Fx()x(G)x(F(x)x(Fx)x(G)x(G)x(F(x)x(Fx)x(G)x(F(x)y(Fy)x(G)x(F(x)y(F)x(G)x(F(yx、全称量词消去规则（全称量词消去规则（U U）A A( (c c) )x xA A( (x x) )A A( (y y) )x xA A( (x x) )5.3 一阶逻辑推理理论

13、x 是(x)中自由出现的个体变项；y 为任意不在(x)中约束出现的个体变项；c 为任意的个体常项。2、全称量词引入规则（全称量词引入规则（UGUG）xA(x)xA(x)A(y)A(y)y 在(y)中自由出现，且y取任何值时均为真；取代y 的x不能在(y)中约束出现，否则会产生错误。例：证明苏格拉底的三段论M(s)M(s)A(s)A(s)M(x)M(x)x(A(x)x(A(x)X(M)X(A(X（2）) s (M) s (A (1) (1) （3）A（S）（4）M（S）证明：证明：A(x):xA(x):x是一个人是一个人 M(x)M(x)：x x是要死的是要死的 S:S:苏格拉底苏格拉底 （1）

14、前提引入前提引入（2)(3)2)(3)假言推理假言推理 （3）存在量词引入规则（）存在量词引入规则（）xA(x)xA(x)A(c)A(c)（4）存在量词消去规则（存在量词消去规则（E E）A A( (c c) )x xA A( (x x) )c 是特定的个体常项；取代c 的x不能已在(c)中出现过。c 是使为真的特定的个体常项；c 不曾在(x)中出现过；(x)中除x外还有其他自由出现的个体变项时,不能用此规则。证明：)x(R)x(W)x(C(x)1()x(Q)x(C(x)2()a (Q)a (C)3()a (R)a (W)a (C)4()a (C)5()a (R)a (W)6()a (Q)7(

15、)a (R)8()a (R)a (Q)9()x(R)x(Q(x)10(2)EI(3)化简(1)UI(4)(5)假言推理(7)(8)合取引入(9)EG例：证明R(x)R(x)x(Q(x)x(Q(x)Q(x)Q(x)x(C(x)x(C(x)R(x)R(x)W(x)W(x)x(C(x)x(C(x)前提引入前提引入(3)化简(6)化简)()()()()()()(xQxxPxxQxPx例 证明)()()()(xQxxPx 证明：用反证法：设为附加前提)()()()(xQxxPx （1）P)()()()(xQxxPx （2）T（1）E)()(xPx （3）T（2）I)()(xPx （4）T（3）E)()(

16、xQx （5）T（2）I)()(xQx （6）T（5）E)(cP （7）ES（4）)(cQ （8）US（6）)()(cQcP （9）T（7）（8）I)()(cQcP （10）)()()(xQxPx（11）)()(cQcP（12）)()()()(cQcPcQcP （13）T（9）EPUS T（10）（12）I矛盾原命题成立证法证法2：用CP规则)()()()(附附加加假假设设PxPx 1)()(xPx （2）T（1）E)(cP （3）ES（2）PxQxPx)()()()( 4)()()()()()()(xQxxPxxQxPx)()()()(67EGxQx )()()()(45UScQcP ITc

17、Q)()()(536CPxQxxPx)()()()()( 8)y(M)y, x(S(yx) z(zP:C)z, x(R) z(P( z)y(M)y, x(S(y(x:H)()()()()()()()()()()(),()()()(),()()(),()()()(),()()()(45343121USaPETzPzPzPzUSzbRzPzyMybSyPzxRzPzyMyxSyx 附附加加前前提提）下列推理是否严密？例：任何人违反交通规则，则要受到罚款，因此，例：任何人违反交通规则，则要受到罚款，因此，如果没有罚款，则没有人违反交通规则。如果没有罚款，则没有人违反交通规则。zx:)z,x(Rz)z

18、(Py)y(Mx,yx:)y,x(S:受到是罚款。：是交通规则：的论域为人。违反设解CPyMyxSyxzPzUGyMyxSyxETyMybSyETyMybSyITyMybSyETzbRzPzUGzbRzPzITabRaP)(),()()()()()()()(),()()()()()(),()()()()(),()()()()(),()()()(),()()()()(),()()()()(),()()( 1311121011210829786756分析分析 带量词的谓词公式，在进行逻辑推证时，必须正带量词的谓词公式，在进行逻辑推证时，必须正确使用确使用US,UG,ES,EG这几个消去量词和扩张量

19、词的规这几个消去量词和扩张量词的规则。在推理过程中，谓词公式只能应用表则。在推理过程中，谓词公式只能应用表2-1所列的蕴所列的蕴含式和等价式，除表中所列的代量词公式外，一般的含式和等价式，除表中所列的代量词公式外，一般的不能在量词后面的辖域内进行蕴含推导或等价变换。不能在量词后面的辖域内进行蕴含推导或等价变换。如：如：),()()(),()()(zbRzPzzbRzPz 但在推理中不能作为公式引用，因为它未列入公式推但在推理中不能作为公式引用，因为它未列入公式推理表中。根据以上分析：理表中。根据以上分析：的错误。的错误。还包括了“省略“步骤还包括了“省略“步骤其中其中都是错误步骤。都是错误步骤

20、。)()(),()()()(),()(),()(10987111010987ETyMybSyUGzbRzPzETzbRzPzITabRaP)()(),()()()(),()()()()(),()()()()(),()()(829786756 CPyMyxSyxzPzUGyMyxSyxETyMybSyETyMybSy)(),()()()()()()()(),()()()()()(),()()()()(),()()( 1311121011210)()()()()()()()()()()(),()()()(),()()(),()()()(),()()()(45343121USaPETzPzPzPzU

21、SzbRzPzyMybSyPzxRzPzyMyxSyx 附附加加前前提提）正正确确做做法法为为：ETzbRzPzUGzbRzPzETabRaPITabRaP)(),()()()()(),()()()()(),()()()(),()()(89786756 CPyMyxSyxzPzUGyMyxSyxUGyMybSyETcMcbSETcMcbSUScMcbSITyMybSyITyMybSy)(),()()()()()()()(),()()()()()(),()()()()(),()()()(),()()()(),()()()(),()()()()(),()()( 171516141513141213111210119210