Proving tautology by substitution

How do I prove whether the following statement is a tautology or not using substitution?
∃x,P(x)∧∃x,Q(x)⇒∃x,(P(x)∧Q(x))

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?

• 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. – Zach Effman Sep 26 '15 at 4:54
• Yes,this is not true,but I am looking for a proof using substitution and not worrying about the truth value so much – bandit_king28 Sep 26 '15 at 4:56
• 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. – 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))$.