Checking the validity of a few FOL formulas How can we tell that the following examples (from my book) are logically valid,

I) $ \exists y \forall x p(x,y) \to \forall x \exists y p(x,y) $
II) $ \exists x \exists y p(x,y) \to \neg \forall x \forall y \neg p(x,y) $
III) $ \forall x \forall y p(x,y) \to \exists x \exists y p(x,y) $

but this one is not. 

IV)  $ \exists x \exists y p(x,y) \to \forall x \exists y p(x,y) $

How can we determine if these examples are valid or not? I tried testing them in a truth table, but that did not work. Is there any idea or hint how to proceed? 
Edit: Assuming that by (IV) a counterexample is provided by taking $p(x,y)$ to be the predicate which is true for all $x$ and $y$. Then the left side of the implication is true, but the right side is false, making the implication logically invalid, but for the other options I could not proof them. 
 A: A quick way to approach deciding whether these are valid or not is to use a tree proof generator. It is like using a truth table generator for propositional logic, but it works for first order logic as well. 
Here is a tree proof for I:

In a tree proof the desired result is negated as you can see from the first line. The branches (if more than one) expand but at the bottom of each branch either there is an "x" or there is not. If there is an "x" then the branch closes because a contradiction to the negation of what we want to show has been found in that branch. If the branch remains open without a contradiction we can use that branch to construct a counterexample showing that our original statement is invalid.
Here is a tree proof for II:

Here is a tree proof for III:

Here is a countermodel for IV:

The countermodel has a domain with two members, $0$ and $1$. The predicate $P$ is true only for the pair $(0,0)$. For all other pairs of members from the domain, $P$ is false. In particular, $P(1,0)$ is false.
That means there exists a pair from the domain for which $P$ is true so the antecedent is true, but $P$ is not true for all members of the domain in the $x$ position, so the consequent is false. This makes the proof invalid.

Tree Proof Generator. https://www.umsu.de/trees/
A: $\newcommand{\strc}{\mathfrak{A}}$
You can not use truth tables for predicate logic. This method is simply not appicable for this langauge.  


*

*To prove the validity ($\vDash$) of a formula in predicate logic, 


*

*either you provide an informal (meta-linguistic) semantic proof in which you argue why the formula must be true in all structures (something along the lines of "Suppose the antecedent of the implication, $ \exists y \forall x p(x,y)$ is true in an arbitrary structure $\strc$. Then there is an element, call it $b$, such that [...] Therefore the succedent $\forall x \exists y p(x,y)$ is true as well, and hence the implication holds in that structure. Since $\strc$ was arbitrary, the formula is true in all structure, and hence valid.").

*or you do a formal proof in some syntactic derivation system like natural deduction or tableaus, that is, you go show $\vdash$ instead, and by soundness you know this is a proof that the formula is indeed semantically valid ($\vDash$).  


*To prove the invalidity ($\nvDash$) of a formula, 


*

*you provide a countermodel in which the formula is false. If you found such a structure, then you know that the formula is not true in all structures, and hence not valid.  




Here are some sketches of meta-linguistic proofs alongside formal natural deduction proofs for the first three formulas, created with this natural deduction proof editor and checker:  

I) $ \exists y \forall x p(x,y) \to \forall x \exists y p(x,y) $

Idea: If we know there is an element $y$ -- give it the name $b$ -- which works for all elements $x$, then for all elements we know we can find at least one element $y$ that makes $P(x,y)$ true, namely that element $b$.


II) $ \exists x \exists y p(x,y) \to \neg \forall x \forall y \neg p(x,y) $

Idea: Proof by contradiction: Suppose $\exists x \exists y p(x,y)$ is true, but $\neg \forall x \forall y \neg p(x,y)$ is false, i.e. assume $\forall x \forall y \neg p(x,y)$. We know that there are at least two elements, call them $a$ and $b$, such that $P(x,y)$ is true. But then the claim that for all elements $x$ and $y$, $P(x,y)$ is false leads to a contradiction, since that would mean that $P(x,y)$ is also false of the pair $\langle a,b \rangle$, so the assumption $\forall x \forall y \neg p(x,y)$ must have been wrong, and we have $\neg \forall x \forall y \neg p(x,y)$ whenever $\exists x \exists y p(x,y)$ is true.


III) $ \forall x \forall y p(x,y) \to \exists x \exists y p(x,y) $

Idea: $\forall x \forall y p(x,y)$ can not become vacuously true because by definition, the domain of a structure is non-empty. So if $P(x,y)$ is true for all $x$ and $y$, then there must be at least two (distinct or identical) elements $x$ and $y$ of which $P(x,y)$ is true.

And here is a proof by countermodel of the invalidity of

IV)  $ \exists x \exists y p(x,y) \to \forall x \exists y p(x,y) $

Let $\strc = \langle A, \mathcal{I} \rangle$ be a structure such that  
$A = \{a, b\}$,
$\mathcal{I}(P) = \{\langle a, a \rangle\}$ 
With $x = a$ and $y = a$ there exist $x$ and $y$ such that $P(x,y)$ is true, so $\exists x \exists y P(x,y)$ is true in the structure. But with $x = b$ there is an $x$ for which there exists no $y$ such that $P(x,y)$ is true, i.e. $\forall x \exists y P(x,y)$ is false in the structure.
Since the antecedent of the implication is true but the succedent is false, the formula does not hold in $\strc$. Since there is a structure in which $ \exists x \exists y p(x,y) \to \forall x \exists y p(x,y) $ is false, the formula is not true in all structures, i.e. not valid.  

This should be enough for you to be able to carry out the sketches of the semantic argumentations in more detail for them to become rigorous meta-linguistic proofs.  
