Logical Equivalents

Date: 03/03/97 at 06:11:37
From: Lewis Columber
Subject: Logical equivalents

Prove or disprove: existential x P(x) and existential x Q(x) is 
logically equivalent to existential x (P(x) and Q(x)).

We are to prove this using logical equivalences.

Thanks, Lewis 

Date: 03/04/97 at 17:31:55
From: Doctor Daniel
Subject: Re: Logical equivalents

Hi Lewis,

I'm going to use this notation for the backwards capital e: _E, 
and ^ for and. We're to prove or disprove for any proposition P and Q 
that:

(_Ex P(x)) ^ (_Ex Q(x)) <=> (_Ex (P(x)^Q(x)))

Well, let's see what both of these say: The first says that some x 
makes P true, and some x makes Q true.  The second says that some x 
makes both P and Q true.  So it seems unlikely that one directly is 
equivalent to the other.

And here's a simple counterexample: Suppose P(x) is the proposition 
that x is even, and Q(x) is the proposition that x is odd.  Then, 
clearly, _Ex P(x); that just says there are even numbers.  And also, 
_Ex Q(x); that just says there are odd numbers.  But it's not true 
that _Ex(P(x)^Q(x)); that would mean there were a number x that is 
both odd and even; we know that this is false.

So the question is false.

-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/