I'm trying to figure out how to decide whether the given (predicate logic) formula is a tautology or not and prove it.
$$ \forall x\exists y\exists z\forall u(R(x,y)\land R(z,u))\leftrightarrow \exists x\forall y\forall z \exists u(R(x,y)\land R(z,u)) $$
I can't figure out how to start. I was thinking about getting rid of Quantificators.
Could you give me some hints or help me to solve it?
You can use the rules $$ \forall a(P\land Q(a)) \leftrightarrow P\land \forall a(Q(a)) \qquad\text{when $a$ is not free in }P \\ \exists a(P\land Q(a)) \leftrightarrow P\land \exists a(Q(a)) \qquad\text{when $a$ is not free in }P $$
to push the quantifiers down below the $\land$ on each side. Once that is done you will find that the two sides are identical up to renaming of bound variables and commutativity of $\land$.