Question

1. Rewrite the following expressions into equivalent expressions where all negation operators immediately precede predicates. Show all intermediate steps Please!!

2. (a) ¬∃x∀y(P(x)∧Q(y))

3. (b) ¬∀x∃y(∃z(P(x,z)∧¬Q(y,z))→∀w¬R(x,y,w))

Answer 1

• For All becomes There Exists and vice-versa
• AND becomes OR and vice-versa

(a) ¬∃x∀y(P(x)∧Q(y))
∀x¬∀y(P(x)∧Q(y))
∀x∃y¬(P(x)∧Q(y))
Answer = ∀x∃y (¬P(x) v ¬Q(y))

(b) ¬∀x∃y(∃z(P(x,z)∧¬Q(y,z))→∀w¬R(x,y,w))
∃x¬∃y(∃z(P(x,z)∧¬Q(y,z))→∀w¬R(x,y,w))
∃x∀y¬(∃z(P(x,z)∧¬Q(y,z))→∀w¬R(x,y,w))
∃x∀y¬(∃z¬(P(x,z)∧¬Q(y,z)) v ∀w¬R(x,y,w))
∃x∀y(¬(∃z¬(P(x,z)∧¬Q(y,z))) ∧ ¬(∀w¬R(x,y,w)))
∃x∀y((∀z¬¬(P(x,z)∧¬Q(y,z))) ∧ (∃w ¬¬R(x,y,w)))
Answer: ∃x∀y(∀z(P(x,z)∧¬Q(y,z)) ∧ ∃w R(x,y,w))

--------------------------------------
Hit the thumbs up if you are fine with the answer. Happy Learning!