Can someone tell me off the bat if these 2 statements are logically equivalent or not. I am leaning towards "equivalent"

a) x such that (p(x) or q(x))

b) x such that p(x)) or x such that q(x))

Printable View

- October 21st 2010, 07:48 PMDarKLogical Equivalence
Can someone tell me off the bat if these 2 statements are logically equivalent or not. I am leaning towards "equivalent"

a) x such that (p(x) or q(x))

b) x such that p(x)) or x such that q(x)) - October 21st 2010, 11:32 PMPiperAlpha167
Yes, that would be a good way to lean.

But does getting agreement from me, or anyone else for that matter, really mean very much?

Maybe pick some system and establish it for yourself? There are systems that'll make life pretty easy.

In one that I have in mind you could reason informally as follows:

Necessity: (b) is a necessary condition for (a)

Take (a) as premiss. Pick an arbitrary name, say c, drop the existential quantifier and assume p(c) or q(c).

The 'or' (now as a main connective) should suggest "proof by cases". So derive (b) from p(c).

The second case (deriving (b) from q(c)) follows immediately from the first case by simply changing what needs to be changed. Except for tying up some loose ends, you're done (at least in one direction).

Sufficiency: (b) is a sufficient condition for (a)

Take (b) as premiss. I see another 'or' (and it's already the principal connective). Now what? - October 22nd 2010, 02:43 AMemakarov
Informally, existential quantification is similar to a (possibly infinite) disjunction. If the quantified variable ranges over the domain , then is .

Viewed from this angle, is , while is . Both of these big disjunctions have the same disjuncts, and since disjunction is commutative and associative, they are equivalent.

Similarly, universal quantification is similar to conjunction, so distributes over . (Universal quantification is also very similar to implication -- isn't it curious?) On the other hand is , which is not equivalent to . One can see from the distributivity of over that the former formula includes the two disjuncts from the latter formula but also has other disjuncts. This means that the latter formula implies the former one, i.e., implies , as expected.