How do we decide whether the formula in predicate logic is a tautology? Is there some universal way to decide and prove it?
Let's have an example:
$$ \forall x \forall z \exists y\,(P(x,y) \lor P(y,z)) \leftrightarrow \forall x \exists y \forall z\,(P(x,y) \lor P(y,z)) $$
I was adviced to choose some Universum and it's realisation but I don't know how to do that.
Could you help me to solve it?
No, there is (provably) no universal method to determine whether a formula in first-order logic is logically valid. We say that first-order logic is undecidable.
If the formula is logically valid, it will have a formal proof (in each of the various proof systems for first-order logic).
On the other hand, if it is not logically valid, then there will be a structure that does not satisfy the formula -- but there's no guarantee that such a structure will have a definite description from which one can prove that it doesn't satisfy the formula.
If the formula is complex enough it is possible that it can neither be proved valid or proved not-valid.
So in general it's up to cleverness and creativity.
For your concrete example, we first observe that the formulas on the two sides of $\leftrightarrow$ are both closed -- i.e. they have no free variables -- so each of them will simply be true or false about any structure (a set with a relation $P$) we apply it to.
The formula is then logically valid if every possible relation either satisfies both sides or doesn't satisfy either side.
We can further see that the difference between the two sides is that the one to the left has $\forall z \exists y$ where the one on the right has $\exists y \forall z$. This makes the right one harder to satisfy then the left one (because on the left $y$ is allowed to depend on $z$), so if there is a counterexample, it has to be a relation $P$ that satisfies the left-hand side and doesn't satisfy the right-hand side.
What does the right-hand side say, then?
(Rest of answer removed; it was based on a horrible failure to notice what the actual symbols in the formula were)