# Math Help - Logic

1. ## Logic

My teacher told me these things :

There exist x belongs to R , ( p(x) ^ q(x) ) iff ( there exist x belongs R , p(x) ) ^ ( there exist x belongs R , q(x) ) is not logically correct.

But

There exist x belongs to R ( p(x) V q(x) ) iff ( there exist x belongs R , p(x) ) V ( there exist x belongs R , q(x) ) is right.

For my knowledge I guess in the first statement,

There exist x belongs to R , ( p(x) ^ q(x) ) implies ( there exist x belongs R , p(x) ) ^ ( there exist x belongs R , q(x) ) is logically correct.

But the other way that means , ( there exist x belongs R , p(x) ) ^ ( there exist x belongs R , q(x) ) implies There exist x belongs to R , ( p(x) ^ q(x) ) is wrong. Am I right with this?

In the second one both the implies parts are correct.

But is there a standard method of proving such things? If so can someone please explain.

2. ## Re: Logic

Originally Posted by Kristen111111111111111111
For my knowledge I guess in the first statement,

There exist x belongs to R , ( p(x) ^ q(x) ) implies ( there exist x belongs R , p(x) ) ^ ( there exist x belongs R , q(x) ) is logically correct.

But the other way that means , ( there exist x belongs R , p(x) ) ^ ( there exist x belongs R , q(x) ) implies There exist x belongs to R , ( p(x) ^ q(x) ) is wrong. Am I right with this?

In the second one both the implies parts are correct.
You are right. If you have a witness x that makes both p(x) and q(x) true, then it makes p(x) true and it makes q(x) true separately. In contrast, if you have two witnesses: one for p(x) and one for q(x), they may be different, and so there may not be a single witness for p(x) /\ q(x). With respect to universal quantification, verifying p(x) /\ q(x) for all x is the same as verifying p(x) for all x and then verifying q(x) for all x.

Another way to look at this is to note that existential quantification is essentially a potentially infinite disjunction: ∃x P(x) is true in (an interpretation with domain) {x1, x2, ...} iff P(x1) \/ P(x2) \/ ... is true. Similarly, universal quantification is analogous to conjunction: ∀x P(x) is true in {x1, x2, ...} iff P(x1) /\ P(x2) /\ ... is true. (It is fascinating that in another sense existential quantification is very similar to conjunction and universal quantification to implication, but this is another story.) Viewed this way, the commutativity of existential quantification and disjunction is basically the commutativity of disjunction:

∃x (P(x) \/ Q(x)) iff
[P(x1) \/ Q(x1)] \/ [P(x2) \/ Q(x2)] \/ ... iff
[P(x1) \/ P(x2) \/ ...] \/ [Q(x1) \/ Q(x2) \/ ...]

If we try to replace dusjunction with conjunction above, we get an infinite disjunction of conjunctions, and then we need to use distributivity of disjunction over conjunction, which creates a complicated formula. It is possible to see, though, that one implication does work, and the other does not.

You should similarly check that ∀x (P(x) /\ Q(x)) is equivalent to (∀x P(x)) /\ (∀x Q(x)) and that (∀x P(x)) \/ (∀x Q(x)) implies ∀x (P(x) \/ Q(x)), but not the other way around. The picture is dual to that of existential quantification.

Originally Posted by Kristen111111111111111111
But is there a standard method of proving such things? If so can someone please explain.
If you have other similar formulas in mind, feel free to post them.

It is recommended to post questions about logic in the Discrete Math university subforum, whose full name is: "Discrete Math Help Forum: Discrete mathematics, logic, set theory".