3.5 已知公式?xA(x)??y(B(x,y)?P(y)).ppt

已知公式?xA(x)??y(B(x,y)?P(y)) (1)试对公式中的自由变元x代以y3+2;(2)试对公式中的谓词变元B(e1,e2)代以式子?xC(e1,e2,x,y)。解:(1) 改名为?xA(x)??u(B(x,u)?P(u))代入得到:?xA(x)??u(B(y3+2,u)?P(u)) (2) 改名为?xA(x)??u(B(x,u)?P(u))代入式子改名?xC(e1,e2,x,y)=?tC(e1, e2, t, y)代入得到:?xA(x)??u(?tC(x,u,t,y)?P(u)) 试求下列公式的前束范式和SKOLEM标准形。 (1) ?x(?(?yX(x,y))?(?zY(z)?Z(x)))解: 先求前束范式原式= ?x(?(?(?yX(x,y))) ∨(?zY(z)?Z(x))) 消去蕴涵词= ?x((?yX(x,y))∨(?zY(z)?Z(x))) = ?x ?y ?z(X(x,y)∨(Y(z)?Z(x))) 前移量词消去存在量词,求SKOLEM标准形原式=?y ?z(X(a,y)∨(Y(z)?Z(a))) 引入Skolem常量a =?y (X(a,y)∨(Y(f(y))?Z(a))) 引入Skolem函数f(y) 试求下列公式的前束范式和SKOLEM标准形。 (2) ?x?y?z(X(x,y,z)?(?uY(u,x)??xW(y,x)))解: 先求前束范式原式= ?x?y?z(X(x,y,z)∧(??uY(u,x)∨?vW(y,v))) 消去蕴涵词= ?x?y?z(X(x,y,z)∧(?u?Y(u,x)∨?vW(y,v))) 否定深入= ?x?y ?z?u ?v(X(x,y, z) ∧(?Y(u,x)∨W(y, v))) 前移量词消去存在量词,求SKOLEM标准形原式=?y ?z?u ?v(X(a,y,z) ∧(?Y(u,a)∨W(y, v))) 引入Skolem常量a = ?y?z?u(X(a,y, z) ∧(?Y(u,a)∨W(y, f(y,z,u))))引入Skolem函数f(y,z,u)?u与?v的次序?补1试把下列语句翻译为谓词演算公式(1)某些人喜欢所有明星;(3分)解记P(e)表示e为人; S(e)表示e为明星; L(e1,e2)表示e1喜欢e2。原话可以翻译为:?x (B(x) ??y(S(y)?L(x,y)))补1(2)并非所有人均喜欢电脑游戏。解记P(e)表示e为人; G(e)表示e为电脑游戏; L(e1,e2)表示e1喜欢e2。原话可以翻译为:??x(P(x) ??y(G(y) ?L(x,y)))??x(P(x) ??y(G(y) ∧L(x,y)))或补1(3)任何人均不喜欢杂草;解记P(e)表示e为人; A(e)表示e为杂草; L(e1,e2)表示e1喜欢e2。原话