Results 1 to 3 of 3

Math Help - Logical Equivalence

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    48

    Logical Equivalence

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

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

    b) \existsx such that p(x)) or \existsx such that q(x))
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by DarK View Post
    Can someone tell me off the bat if these 2 statements are logically equivalent or not. I am leaning towards "equivalent"

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

    b) \existsx such that p(x)) or \existsx such that q(x))
    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?
    Last edited by PiperAlpha167; October 21st 2010 at 11:51 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    Informally, existential quantification is similar to a (possibly infinite) disjunction. If the quantified variable ranges over the domain \{a_1,a_2,\dots\}, then \exists x\,P(x) is P(a_1)\lor P(a_2)\lor\dots.

    Viewed from this angle, \exists x\,(P(x)\lor Q(x)) is (P(a_1)\lor Q(a_1))\lor (P(a_2)\lor Q(a_2))\lor\dots, while (\exists x\,P(x))\lor(\exists x\,Q(x)) is (P(a_1)\lor P(a_2)\lor\dots)\lor(Q(a_1)\lor Q(a_2)\lor\dots). 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 \forall distributes over \land. (Universal quantification is also very similar to implication -- isn't it curious?) On the other hand \forall x\,(P(x)\lor Q(x)) is (P(a_1)\lor Q(a_1))\land (P(a_2)\lor Q(a_2))\land\dots, which is not equivalent to (P(a_1)\land P(a_2)\land\dots)\lor(Q(a_1)\land Q(a_2)\land\dots). One can see from the distributivity of \land over \lor 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., (\forall x\, P(x))\lor(\forall x\, Q(x)) implies \forall x\,(P(x)\lor Q(x)), as expected.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logical equivalence
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 12th 2011, 05:22 PM
  2. [SOLVED] need to check logical equivalence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 5th 2011, 10:49 PM
  3. Logical Equivalence Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 2nd 2010, 01:06 PM
  4. Proving Logical equivalence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 25th 2009, 10:35 AM
  5. Logical Equivalence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 23rd 2008, 08:17 PM

Search Tags


/mathhelpforum @mathhelpforum