# Logical Equivalences Involving Quantifiers

I've spent a good 2-3 hours trying to look up examples online on how to do this exactly. I was astonished to find so few examples. I'm still trying to figure it out, so what I think I'm supposed to say is, if we assume $A$ is true. Then we can automatically eliminate the "$A$" from both sides of the equation since a proposition with any true proposition means it depends on whether the other proposition, $P(x)$ in this case is true or false. So then you can write it as $\forall x P(x) \equiv \forall x P(x)$ which is trivially true. I assume, if I am going at this with the right logic, you just do the same thing with the second part of this problem? I am a complete beginner and this is the first week of the semester, so I wouldn't be surprised if I am royally screwing this up.

Establish these logical equivalences, where $x$ does not occur as a free variable in $A$. Assume that the domain is nonempty.

a) $(\forall xP(x)) \land A \equiv \forall x(P (x) \land A)$

b) $(\exists xP(x)) \land A \equiv \exists x(P (x) \land A)$

• Right. There are two cases, and you done the True case. Now do the False case. (Careful. Here's where you use the assumption that the domain is not empty.) Oops. You probably meant part b) when you said "the second part." You've only done the first half of part a). – saulspatz Jan 28 '18 at 1:25
• Do you have to do this using the semantics of the logical operators involved, or could you do a formal (syntactical) proof? – Bram28 Jan 28 '18 at 1:39
• I think only the semantics of the logical operators involved. Not a formal proof. I'm glad I am on the right track, though. I'm still trying to figure out how to the false part, I'm pretty sure that it's so obvious that I'm making it out to be trickier than it is, I think. – Alex Rosenbach Jan 28 '18 at 2:04

Here's how to do a semantical proof. I'll do a) and leave b) to you

Take any interpretation $I$ with domain $D_I$

We have:

$I \models (\forall x P(x)) \land A$ iff (by semantics of $\land$)

$I \models (\forall x P(x))$ and $I \models A$ iff (by semantics of $\forall$)

It is true that for all objects $a$ in $D_I$: $I \models P[a]$ and it is also true that $I \models A$ iff (pure logic)

For all objects $a$ in $D_I$ it is true that $I \models P[a]$ and $I \models A$ iff (by semantics of $\land$)

For all objects $a$ in $D_I$: ($I \models P[a] \land A$) iff (by semantics of $\forall$)

$I \models \forall x (P(x) \land A)$

So, since for all interpretations $I$ we have $I \models (\forall x P(x)) \land A$ iff $I \models \forall x (P(x) \land A)$, we have by definition of logical equivalence proven that:

$(\forall x P(x)) \land A \equiv \forall x (P(x) \land A)$

Note: $I \models P[a]$ means that if we introduce a new constant symbol $c$ and extend interpretation $I$ to $I'$ that interprets $c$ as $a$, then $I' \models P(c)$