951等值式与置换规则 豪 口置换规则:给定φ(A) 冷A分B,则中(A)分中(B) 口换名规则: 令XA(x)台x"A(x),x‘不在A中出现 ☆彐XA(x)分3xA(x),x‘不在A中出现 口代替规则 令A(x)兮A(x),x不在A中出现
11 ❑ 置换规则：给定φ(A) ❖ A B ，则φ(A) φ(B) ❑ 换名规则： ❖ x A(x) x’ A(x’)，x’不在A中出现 ❖ x A(x) x’ A(x’)，x’不在A中出现 ❑ 代替规则 ❖ A(x) A(x’)，x’不在A中出现 5.1 等值式与置换规则
实例 豪 例1将下面命题用两种形式符号化,并证明两者等值 (1)没有不犯错误的人 解令F(x):x是人,G(x):x犯错误 3x(F(x)∧_G(x)或Vx(F(x)→>G(x) -=(F(r)A-G(r) 兮Vx-(F(x)∧_G(x)量词否定等值式 冷Vx(F(xvG(x) 置换 冷冷Vx(F(x)->G(x) 置换 12
12 实例 例1 将下面命题用两种形式符号化, 并证明两者等值 (1) 没有不犯错误的人 解 令F(x)：x是人，G(x)：x犯错误. x(F(x)G(x)) 或 x(F(x)→G(x)) x(F(x)G(x)) x(F(x)G(x)) 量词否定等值式 x(F(x)G(x)) 置换 x(F(x)→G(x)) 置换
实例 豪 (2)不是所有的人都爱看电影 解令F(x):x是人,Gx):爱看电影. x(F(x)-Gx)或3x(F(x)入-G(x) Vx(F(x)→>G(x) 兮丑x-(F(x)->G(x)量词否定等值式 台丑x-(P(x)G(x)置换 兮丑x(F(x)∧_G(x)置换 13
13 实例 (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(F(x)G(x)) 置换 x(F(x)G(x)) 置换
例 豪 口例:消除既是约束出现又是自由出现的变项 1. VX F(,y,2> 3y G(,yz) tF(ty,2)→G(x,y,2) VtF(ty,2)→丑WG(X,W,2) 2.VX(F(Xy)→yG(xyz) 台X(F(x,→彐yG(x,yZ) 台XF(x,y)→彐tG(x,t,2) 14
14 ❑ 例：消除既是约束出现又是自由出现的变项 1. x F(x,y,z) → y G(x,y,z) 2. x (F(x,y) → y G(x,y,z)) t F(t,y,z) → y G(x,y,z) t F(t,y,z) → w G(x,w,z) x (F(x,t) → y G(x,y,z)) x F(x,y) → t G(x,t,z) 例
951等值式与置换规则 豪 口证明: VxVy(F(X)∧G(y)→H(Xy))分 X于y(F(X)∧G(y)∧-H(Xy)) 证明:-Vxwy(F(x)∧G(y)→H(xy)) 台3X-Wy(-(F(X)∧G(y))vH(Xy)) 台Xy((F(x)∧G(y)∧-H(Xy) 15
15 ❑ 证明: ¬ x y (F(x) G(y) → H(x,y)) x y (F(x) G(y) ¬ H(x,y)) 证明： ¬ x y (F(x) G(y) → H(x,y)) x ¬ y (¬(F(x) G(y)) H(x,y)) x y ((F(x) G(y)) ¬ H(x,y)) 5.1 等值式与置换规则