Solved Examples on Logical Equivalences: Predicate Logic

Samuel Dominic Chukwuemeka (SamDom For Peace) Solve all questions.
Show all work.
You may use any of the Laws of Logical Equivalences and/or Logical Equivalences for Propositional Logic and Predicate Logic.
For any law of logical equivalence that you use, please indicate the law or the logical equivalence number.

(1.) Prove the equivalence: $\neg[\forall x (p(x) \lor q(x))] \equiv \exists x(\neg p(x) \land \neg q(x))$


$ LHS \\[3ex] \neg[\forall x (p(x) \lor q(x))] \\[3ex] \equiv \neg \forall x \; \neg(p(x) \lor q(x)) \\[3ex] *** \\[3ex] \neg \forall x \equiv \exists x ...No.(11.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(p(x) \lor q(x)) \equiv \neg p(x) \land \neg q(x) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] *** \\[3ex] \equiv \exists x(\neg p(x) \land \neg q(x)) \\[3ex] = RHS $

(2.) Prove the equivalence: $\neg[\forall x (p(x) \land q(x))] \equiv \exists x(\neg p(x) \lor \neg q(x))$


$ LHS \\[3ex] \neg[\forall x (p(x) \land q(x))] \\[3ex] \equiv \neg \forall x \; \neg(p(x) \land q(x)) \\[3ex] *** \\[3ex] \neg \forall x \equiv \exists x ...No.(11.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(p(x) \land q(x)) \equiv \neg p(x) \lor \neg q(x) ...No.(2.)\;De\:\:Morgan's\:\:Law \\[3ex] *** \\[3ex] \equiv \exists x(\neg p(x) \lor \neg q(x)) \\[3ex] = RHS $

(3.) Prove the equivalence: $\neg[\exists x (p(x) \lor q(x))] \equiv \forall x(\neg p(x) \land \neg q(x))$


$ LHS \\[3ex] \neg[\exists x (p(x) \lor q(x))] \\[3ex] \equiv \neg \exists x \; \neg(p(x) \lor q(x)) \\[3ex] *** \\[3ex] \neg \exists x \equiv \forall x ...No.(12.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(p(x) \lor q(x)) \equiv \neg p(x) \land \neg q(x) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] *** \\[3ex] \equiv \forall x(\neg p(x) \land \neg q(x)) \\[3ex] = RHS $

(4.) Prove the equivalence: $\neg[\exists x (p(x) \land q(x))] \equiv \forall x(\neg p(x) \lor \neg q(x))$


$ LHS \\[3ex] \neg[\exists x (p(x) \land q(x))] \\[3ex] \equiv \neg \exists x \; \neg(p(x) \land q(x)) \\[3ex] *** \\[3ex] \neg \exists x \equiv \forall x ...No.(12.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(p(x) \land q(x)) \equiv \neg p(x) \lor \neg q(x) ...No.(2.)\;De\:\:Morgan's\:\:Law \\[3ex] *** \\[3ex] \equiv \forall x(\neg p(x) \lor \neg q(x)) \\[3ex] = RHS $

(5.) Prove the equivalence: $\forall x(\neg p(x) \land q(x)) \equiv \neg[\exists x (p(x) \lor \neg q(x))]$


$ RHS \\[3ex] \neg[\exists x (p(x) \lor \neg q(x))] \\[3ex] \equiv \neg \exists x \; \neg(p(x) \lor \neg q(x)) \\[3ex] *** \\[3ex] \neg \exists x \equiv \forall x ...No.(12.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(p(x) \lor \neg q(x)) \equiv \neg p(x) \land \neg \neg q(x) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg \neg q(x) \equiv q(x) ...No.(15.)...Double\:\:Negation\:\:Law \\[3ex] *** \\[3ex] \equiv \forall x(\neg p(x) \land q(x)) \\[3ex] = LHS $

(6.) Prove the equivalence: $\exists x(p(x) \lor \neg q(x)) \equiv \neg[\forall x (\neg p(x) \land q(x))]$


$ RHS \\[3ex] \neg[\forall x (\neg p(x) \land q(x))] \\[3ex] \equiv \neg \forall x \; \neg(\neg p(x) \land q(x)) \\[3ex] *** \\[3ex] \neg \forall x \equiv \exists x ...No.(11.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(\neg p(x) \land q(x)) \equiv \neg \neg p(x) \lor \neg q(x) ...No.(2.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg \neg p(x) \equiv p(x) ...No.(15.)...Double\:\:Negation\:\:Law \\[3ex] *** \\[3ex] \equiv \exists x(p(x) \lor \neg q(x)) \\[3ex] = LHS $

(7.) Prove the equivalence: $\forall x(\neg p(x) \land \neg q(x)) \equiv \neg[\exists x (\neg p(x) \rightarrow q(x))]$


$ RHS \\[3ex] \neg[\exists x (\neg p(x) \rightarrow q(x))] \\[3ex] \equiv \neg \exists x \; \neg(\neg p(x) \rightarrow q(x)) \\[3ex] *** \\[3ex] \neg \exists x \equiv \forall x ...No.(12.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg p(x) \rightarrow q(x) \equiv p(x) \lor q(x) ...No.(4.) \\[3ex] \therefore \neg(\neg p(x) \rightarrow q(x)) \equiv \neg (p(x) \lor q(x)) \\[3ex] \neg (p(x) \lor q(x)) \equiv \neg p(x) \land \neg q(x) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] *** \\[3ex] \equiv \forall x(\neg p(x) \land \neg q(x)) \\[3ex] = LHS $

(8.) Prove the equivalence: $\neg[\forall x (p(x) \rightarrow \neg q(x))] \equiv \exists x(p(x) \land q(x))$


$ LHS \\[3ex] \neg[\forall x (p(x) \rightarrow \neg q(x))] \\[3ex] \equiv \neg \forall x \; \neg(p(x) \rightarrow \neg q(x)) \\[3ex] *** \\[3ex] \neg \forall x \equiv \exists x ...No.(11.)\;De\:\:Morgan's\:\:Law \\[3ex] p(x) \rightarrow \neg q(x) \equiv \neg p(x) \lor \neg q(x) ...No.(5.) \\[3ex] \therefore \neg(p(x) \rightarrow \neg q(x)) \equiv \neg(\neg p(x) \lor \neg q(x)) \\[3ex] \neg(\neg p(x) \lor \neg q(x)) \equiv \neg \neg p(x) \land \neg \neg q(x) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg \neg p(x) \equiv p(x) ...Number(15.)...Double\:\:Negation\:\:Law \\[3ex] \therefore \neg \neg p(x) \land \neg \neg q(x) \equiv p(x) \land q(x) \\[3ex] *** \\[3ex] \equiv \exists x(p(x) \land q(x)) \\[3ex] = RHS $

(9.) Prove the equivalence: $\neg[\forall x (p(x) \lor (q(x) \lor r(x)))] \equiv \exists x(\neg p(x) \land (\neg q(x) \land \neg r(x)))$


$ LHS \\[3ex] \neg[\forall x (p(x) \lor (q(x) \lor r(x)))] \\[3ex] \equiv \neg \forall x \; \neg(p(x) \lor (q(x) \lor r(x))) \\[3ex] *** \\[3ex] \neg \forall x \equiv \exists x ...No.(11.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(p(x) \lor (q(x) \lor r(x))) \equiv \neg p(x) \land \neg(q(x) \lor r(x)) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(q(x) \lor r(x)) \equiv \neg q(x) \land \neg r(x) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] \therefore \neg(p(x) \lor (q(x) \lor r(x))) \equiv \neg p(x) \land \neg q(x) \land \neg r(x) \\[3ex] *** \\[3ex] \equiv \exists x(\neg p(x) \land \neg q(x) \land \neg r(x)) \\[3ex] \equiv \exists x(\neg p(x) \land (\neg q(x) \land \neg r(x))) \\[3ex] = RHS $

(10.)


(11.) Prove the equivalence: $\neg[\exists x (\neg p(x) \lor (\neg q(x) \lor \neg r(x)))] \equiv \forall x(p(x) \land (q(x) \land r(x)))$


$ LHS \\[3ex] \neg[\exists x (\neg p(x) \lor (\neg q(x) \lor \neg r(x)))] \\[3ex] \equiv \neg \exists x \; \neg(\neg p(x) \lor (\neg q(x) \lor \neg r(x))) \\[3ex] *** \\[3ex] \neg \exists x \equiv \forall x ...No.(12.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(\neg p(x) \lor (\neg q(x) \lor \neg r(x))) \equiv \neg \neg p(x) \land \neg(\neg q(x) \lor \neg r(x)) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg(\neg q(x) \lor \neg r(x)) \equiv \neg \neg q(x) \land \neg \neg r(x) ...No.(1.)\;De\:\:Morgan's\:\:Law \\[3ex] \neg \neg p(x) \equiv p(x) ...Number(15.)...Double\:\:Negation\:\:Law \\[3ex] \neg \neg q(x) \equiv q(x) \\[3ex] \neg \neg r(x) \equiv r(x) \\[3ex] \therefore \neg(\neg q(x) \lor \neg r(x)) \equiv q(x) \land r(x) \\[3ex] \therefore \neg \neg p(x) \land \neg(\neg q(x) \lor \neg r(x)) \equiv p(x) \land q(x) \land r(x) \\[3ex] *** \\[3ex] \equiv \forall x(p(x) \land q(x) \land r(x)) \\[3ex] \equiv \forall x(p(x) \land (q(x) \land r(x))) \\[3ex] = RHS $

(12.)