How do I prove whether the following statement is a tautology or not using substitution?

From what I understood if the expression is of the form A⇒A, then we can substitute values to prove tautology.
But how can I interpret ∃x,P(x) and ∃x,Q(x) on the RHS. Does this mean P∧Q? Where am I going wrong?

  • $\begingroup$ I don't believe this is true. Let P(x) be the statement x is even and Q(x) that x is odd. There certainly exists and even number and an odd number, but no number that is both odd and even. $\endgroup$ – Zach Effman Sep 26 '15 at 4:54
  • $\begingroup$ Yes,this is not true,but I am looking for a proof using substitution and not worrying about the truth value so much $\endgroup$ – bandit_king28 Sep 26 '15 at 4:56
  • $\begingroup$ If you know that the formula is not valid (better than : a tautology), to prove this fact you have to "manufacture" a counterexample, i.e. a domain and an interpretation for $P$ and $Q$ such that the antecedent is true and the consequent is false. $\endgroup$ – Mauro ALLEGRANZA Sep 26 '15 at 8:23

To prove the validity of a first-order formula $\varphi$ by substitution, you have to start from a propositional tautology $\alpha$, like $A \to A$ in your example, and find a suitable uniform substitution such that, when applied to $\alpha$, will produce $\varphi$.

Here the key-word is "uniform", i.e. every instance of a propositional letter $A_i$ occurring in $\alpha$ must be replaced with the same "atom".

Thus, form $A \to A$ we can get :

  • $\exists x P(x) \to \exists x P(x)$, or

  • $(∃x P(x) ∧ ∃x Q(x)) \to (∃x P(x) ∧ ∃x Q(x))$

but never :

$(∃x P(x) ∧ ∃x Q(x)) \to ∃x(P(x) ∧ Q(x))$.


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.