第二章习题二
1、求证∀x∀y(P(x)→Q(y))⇔∃xP(x)→∀yQ(y)
∀x∀y(P(x)→Q(y))
⇔∀x∀y(¬P(x)∨Q(y)) 条件式的等值式
⇔∀x(¬P(x)∨∀yQ(y)) 辖域的扩充与收缩规律
⇔∀x¬P(x)∨∀yQ(y) 辖域的扩充与收缩规律
⇔¬∃xP(x)∨∀yQ(y) 量词的德摩律
⇔∃xP(x)→∀yQ(y) 条件式的等值式
2、把下列各式转换为前束范式
(1) ∃x(¬(∃yP(x,y)→(∃zQ(z)→R(x))))
⇔∃x(¬(∃yP(x,y)→(¬∃zQ(z)∨R(x)))) 条件式的等值式
⇔∃x(¬(¬∃yP(x,y)∨(¬∃zQ(z)∨R(x)))) 条件式的等值式
⇔∃x((¬¬∃yP(x,y)∧(¬¬∃zQ(z)∧¬R(x)))) 德摩律
⇔∃x((∃yP(x,y)∧(∃zQ(z)∧¬R(x)))) 否定的否定
⇔∃x∃y∃z ((P(x,y)∧(Q(z)∧¬R(x)))) 量词辖域的扩张与收缩
⇔∃x∃y∃z (P(x,y)∧Q(z)∧¬R(x)) 量词辖域的扩张与收缩
(2) ∀x∀y((∃zP(x,y,z)∧∃uQ(x,u))→∃vQ(y,v))
⇔∀x∀y(¬ (∃zP(x,y,z)∧∃uQ(x,u)) ∨∃vQ(y,v)) 条件式的等值式
⇔∀x∀y( (¬∃zP(x,y,z) ∨¬∃uQ(x,u)) ∨∃vQ(y,v)) 德摩律
⇔∀x∀y( (∀z¬P(x,y,z) ∨∀u¬Q(x,u)) ∨∃vQ(y,v)) 德摩律
⇔∀x∀y∀z∀u∃v ( (¬P(x,y,z) ∨¬Q(x,u)) ∨Q(y,v)) 德摩律
⇔∀x∀y∀z∀u∃v ( ¬P(x,y,z) ∨¬Q(x,u)∨Q(y,v)) 德摩律
(3) ∀xF(x) →∀yP(x,y)
⇔∀zF(z) →∀yP(x,y) 约束变元与自由变元同名，故约束变元改名
⇔¬∀zF(z)∨∀yP(x,y) 条件式的等值式
⇔∃z¬F(z)∨∀yP(x,y) 德摩律
⇔∃z∀y(¬F(z)∨P(x,y)) 德摩律
(4) ∀x(P(x,y)→∃yQ(x,y,z))
⇔∀x(P(x,y)→∃sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名
⇔∀x(¬P(x,y) ∨∃sQ(x,s,z)) 条件式的等值式
⇔∀x∃s(¬P(x,y)∨Q(x,s,z)) 辖域的扩充与收缩
(5) ∀x(P(x,y)↔∃yQ(x,y,z))
⇔∀x(P(x,y)↔∃sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名
⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃sQ(x,s,z)→P(x,y))) 双条件的等值式
⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃tQ(x,t,z)→P(x,y))) 后面约束变元与前面同则后面换名⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(¬∃tQ(x,t,z)∨P(x,y))) 条件式的等值式
⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(∀t¬Q(x,t,z)∨P(x,y))) 德摩律
⇔∀x∃s∀t((¬P(x,y)∨Q(x,s,z))∧(¬Q(x,t,z)∨P(x,y))) 辖域的扩充与收缩
(6) ∀x(F(x) →G(x,y)) →(∃yH(y) →∃zL(y,z))
⇔∀x(F(x) →G(x,y)) →(∃sH(s) →∃zL(y,z)) 约束变元改名
⇔¬∀x(F(x) →G(x,y)) ∨(∃sH(s) →∃zL(y,z)) 条件式的等值式
⇔¬∀x(¬F(x) ∨G(x,y)) ∨(¬∃sH(s) ∨∃zL(y,z)) 条件式的等值式
⇔∃x¬ (¬F(x) ∨G(x,y)) ∨(¬∃sH(s) ∨∃zL(y,z)) 德摩律
⇔∃x¬(¬F(x) ∨G(x,y)) ∨(∀s¬H(s) ∨∃zL(y,z)) 德摩律
⇔∃x(¬¬F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 德摩律
⇔∃x(F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 否定的否定
⇔∃x∀s∃z(F(x)∧¬G(x,y))∨(¬H(s)∨L(y,z)) 辖域的扩充与收缩
(7) ∃xF(x,y) →(F(x) →¬∀yG(x,y))
⇔∃sF(s,y) →(F(x) →¬∀yG(x,y)) 约束变元改名
⇔∃sF(s,y)→(F(x)→¬∀tG(x,t)) 约束变元改名
⇔¬∃sF(s,y)∨(¬F(x)∨¬∀tG(x,t)) 条件式的等值式
⇔∀s¬F(s,y)∨(¬F(x)∨∃t¬G(x,t)) 德摩律
⇔∀s∃t¬F(s,y)∨(¬F(x)∨¬G(x,t)) 辖域的扩充与收缩
⇔∀s∃t¬F(s,y)∨¬F(x)∨¬G(x,t) 结合律。