4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you, that's what I thought, I don't know why the answer the proffesor gave me is not the same. $\endgroup$ – Alan Feb 10 '15 at 21:30
  • $\begingroup$ But according to 'A Mathematical Introduction to Logic' by Enderton 2nd edition page 115, there is this sentence 'On the other hand, neither $\forall x (Px \rightarrow Px)$ nor $\forall x Px \rightarrow Px$' is a tautology'. $\endgroup$ – Idonknow Apr 12 '15 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.