NOTE: “Tautology" & “Valid" are Different Concepts in First Order Logic. Tautology & Valid are Same Concepts in Propositional Logic.
Watch the following Detailed Lecture on “Tautology Vs Valid” in First Order Logic:
$\color{red}{\text{Tautology Vs Valid in First Order Logic:}}$ "Tautology" in Predicate Logic(Click Here)
Note 1 :
When no information is given about Domain of variables for a First Order Logic (FOL) formula, then consider that domain for all variables in the given FOL formula is same. Unless otherwise explicitly stated, domain should be taken same for all variables of a given FOL formula.
Note 2 :
For propositional logic(PL) / Sentential logic, “Tautology” of an expression means same thing as “Validity” of that expression. But this is Not true in FOL.
Tautology/Validity in Propositional Logic :
Tautologies are 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.
Given propositional logic expression (PLE) $G$ is said to be Valid or Tautology iff $G$ is ALWAYS True, regardless of which valuation is used for the propositional variables.
Some examples of Tautologies in PL :
$A \vee \neg A$
$(A \vee B) \rightarrow (A \vee B)$
$(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A) $
In propositional logic, there is no distinction between a tautology and a logically valid formula. So,
In Propositional logic $: \text{Valid} \equiv \text{Tautology} \equiv \text{True}$
Tautology/Validity in First Order Logic(FOL) :
From Wikipedia :
The definition of tautology can be extended to sentences in predicate logic, which may contain quantifiers—a feature absent from sentences of propositional logic. Indeed, in propositional logic, there is no distinction between a tautology and a logically valid formula. In the context of predicate logic, many authors define a tautology to be a sentence that can be obtained by taking a tautology of propositional logic, and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). The set of such formulas is a proper subset of the set of logically valid sentences of predicate logic (i.e., sentences that are true in every model).
The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences in first-order logic. These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained between logical validities, sentences that are true in every model, and tautologies, which are a proper subset of the first-order logical validities. In the context of propositional logic, these two terms coincide.
A tautology in first-order logic is a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). (Note that Propositional logic manipulations can be done on the given formula, but No FOL manipulation should be done.)
For example, because $A \vee \neg A$ is a tautology of propositional logic, $( \forall x (x=x) ) \vee \neg ( \forall x (x=x) ) $ is a tautology in first order logic.
Example $2 :$
$[(\forall y \neg Py \rightarrow \neg Px) \rightarrow (Px \rightarrow \neg \forall y \neg Py)]$ is a FOL Tautology.
because it can be obtained from a contraposition tautology $(A \rightarrow \neg B) \rightarrow (B \rightarrow \neg A) $ by replacing $A$ by $\forall y \neg Py$ and $B$ by $Px$.
Example $3 :$
$ \forall x \forall y P(x,y) \rightarrow \forall x \forall y P(x,y) $ is a FOL tautology because it can be obtained from a PL Tautology $A \rightarrow A $ by replacing $A$ with $\forall x \forall y P(x,y).$
Not all logical validities are tautologies in first-order logic.
For example, the sentence $ {\displaystyle (\forall xRx)\to \lnot \exists x\lnot Rx} $
is true/valid in any first-order interpretation BUT it is Not a FOL Tautology, because it corresponds to the propositional sentence ${\displaystyle A\to B} $ which is not a tautology of propositional logic.
Example $2 :$
$\forall x(Px \rightarrow Px)$ is NOT a FOL Tautology because it corresponds to the propositional sentence $A$ which is not a tautology of propositional logic. Note that $\forall x(Px \rightarrow Px)$ is FOL Valid formula But Not Tautology.
Example $3 :$
$ (\forall x Px) \rightarrow Pc $ is NOT a FOL Tautology because it corresponds to the propositional sentence $A \rightarrow B$ (By replacing $ (\forall x Px)$ with $A$ and $Pc$ with $B$) which is not a tautology of propositional logic. NOTE that $ (\forall x Px) \rightarrow Pc $ is FOL Valid formula But Not Tautology.
Example $4:$
The following is an example of a logical truth that is not a tautology: $ \exists x \text{Cube}(x) \vee \exists x \neg \text{Cube}(x) $. Because the validity of the argument depends on the meaning of the existential quantifier $\exists $ , and not just on the meaning of the connective $\vee$.
A sentence containing quantifiers that is a tautology is this: $ \forall x \text{Cube}(x) \vee \neg \forall x \text{Cube}(x) $ which is just an instance of the tautologous form $ A \vee \neg A $.
So that's that.
NOTE : Every FOL Tautology is FOL validity BUT Not vice versa.
So, If a given FOL formula is Not valid, then it is Not a FOL Tautology.
Now coming back to the given question :
Option A :
Option A is NOT at all valid in FOL.
$ \forall x \exists yR(x,y) \leftarrow \exists y \forall xR(x,y) $ is FOL Validity. But it is Not FOL Tautology.
$ \forall x \exists y R(x,y) \rightarrow \exists y \forall x R(x,y) $ is NOT FOL Validity. So, it is Not FOL Tautology as well.
Option B :
$ (\forall x[ \exists yR(x,y)\rightarrow S(x,y)])\rightarrow \forall x \exists y S(x,y) $ is NOT at all valid.
For example, Let $A$ be a set $\{a,b \}$ and let relation $R$ on $A$ be $ \{ (a,a) \}$ and let relation $S$ on $A$ be $ \{ (a,a) \}$ then clearly $\forall x \exists y S(x,y) $ is false. Also $ (\forall x[ \exists y R(x,y)\rightarrow S(x,y)]) $ is true. So, we can say that option B is NOT Valid. So, it is Not a Tautology.
Option C :
$ [\forall x \exists y(P(x,y)\rightarrow R(x,y))]\leftrightarrow [\forall x \exists y(\neg P(x,y)\vee R(x,y))] $ is a FOL Tautology.
Note that we can do Propositional logic manipulations, so, $A \rightarrow B $ can be written $A' \vee B.$
So,
$ [\forall x \exists y(P(x,y)\rightarrow R(x,y))] \leftrightarrow [\forall x \exists y(\neg P(x,y)\vee R(x,y))] $ is same as $ [\forall x \exists y( \neg P(x,y) \vee R(x,y))]\leftrightarrow[\forall x \exists y(\neg P(x,y)\vee R(x,y))] $
under only propositional logic manipulation.
Now, we can take $A = [\forall x \exists y( \neg P(x,y) \vee R(x,y))]$ and so $A \leftrightarrow A$ is tautology in PL.
Option D :
$ \forall x \forall yP(x,y) \rightarrow \forall x \forall y P(y,x)$ is FOL Valid But Not FOL Tautology. NOTE that if we replace $\forall x \forall y P(x,y)$ by $A$ then $ \forall x \forall y P(y,x)$ is some B. But $A \rightarrow B$ is Not tautology in PL.
References :
Page number $115$ in the below book :
Watch the following Detailed Lecture on “Tautology Vs Valid” in First Order Logic:
$\color{red}{\text{Tautology Vs Valid in First Order Logic:}}$ "Tautology" in Predicate Logic (Click HERE)
