第二章习题二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)结合律
