Given the domain $S=\{0,1\}$, how to write $\forall x \, \exists y \, P(x, y)$ without quantifiers?

Question

How to write $∀x \thinspace ∃y \thinspace P(x, y)$ without quantifiers (using $\wedge$ and $\vee$)? The domain is $S=\{0,1\}$.

Answer 1

Well, given the finiteness of your domain, you can quantify over it entirely. You know that for each $x\in\{0,1\}$, there's some $y\in\{0,1\}$ where $P(x,y)$ is true. So, since $y$ is either 0 or 1, then either $P(x,0)$ or $P(x,1)$ is true for any given $x$. We can expand similarly over $x$, knowing that $P(0,y)$ and $P(1,y)$ must both be true for some $y$.

All that remains is expanding it out fully using proper notation.

Answer 2

It's $\displaystyle\bigwedge_{x\in S} \bigvee_{y\in S} P(x, y) $.