Are these a Tautology?

Question

Are the following two well-formed formulae a tautology ?

1. $ \forall x\forall y P(x,y)\rightarrow \forall x\forall y P(y,x) $

2. $[ \forall x\exists y (P(x,y) \rightarrow R(x,y) ) ] \leftrightarrow [ \forall x\exists y (\lnot P(x,y) \lor R(x,y) ) ]$

According to me both are tautologies. But I had to make a choice between these two in an exam. Am I wrong ?

Answer 1

Strictly speaking, tautology :

is a key concept in propositional logic, where a tautology is defined as a propositional formula that is true under any possible Boolean valuation of its propositional variables.

According to this definition, the formula :

$∀x∀yP(x,y)→∀x∀yP(y,x)$

being a formula of first-order logic, is not a tautology, also if it is an (universally) valid formula of first-order logic indeed.

In another sense, we can say that a formula of first-order logic is a tautology when it is a substitution instance of a propositional formula which is a tautology; for example, the valid f-o formula $\forall xP(x) \to \forall xP(x)$ is obtained from $\varphi \rightarrow \varphi$ replacing $\varphi$ with the formula $\forall xP(x)$.

Neither in this second sense the above formula is a tautology, because it can be seen as an instance of the propositional formula $\varphi \to \psi$, which is not a tautology.

---

Regarding the formula :

$∀x∃y(P(x,y)→R(x,y))↔∀x∃y(¬P(x,y)∨R(x,y))$

with the tautological equivalence : $(p \rightarrow q) \leftrightarrow (\lnot p \lor q)$ we can re-write it as :

$∀x∃y(P(x,y)→R(x,y))↔∀x∃y(P(x,y)→R(x,y))$

and now it is a substitution instance of the tautology : $\varphi \leftrightarrow \varphi$.