Tautology - First Order Logic

1.5k Views Asked by At

I have a question in my exam practice, to determine if the following statement is a tautology, in First Order Logic:

question

I think it is a tautology, but am I correct?

In my course the proffesor told us to "translate" the statement to Propositional Logic, like that:

second

Your help is appriciated, is the statment above a tautology in first order logic?

1

There are 1 best solutions below

2
On

Yes, the first-order formula $\forall x (p(x) \rightarrow p(x))$ is valid and we can obtain it "generalizing" an instance of the tautology : $\varphi \rightarrow \varphi$.

I.e. we can obtain it from the tautology $\varphi \rightarrow \varphi$ replacing $\varphi$ with the formula $p(x)$.

Regarding $\forall x p(x) \lor \lnot \forall y p(y)$, it is obtained from $\varphi \lor \lnot \psi$, which is not a tautology.

But it is also a valid formula of first-order logic; in fact, it is equivalent to $\forall x p(x) \lor \lnot \forall x p(x)$ which is obtained from the tautology $\varphi \lor \lnot \varphi$.