Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Logic

  1. #1
    Junior Member
    Joined
    Aug 2013
    From
    UAE
    Posts
    33

    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.
    Last edited by Kristen111111111111111111; August 17th 2013 at 04:40 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Logic

    Quote Originally Posted by Kristen111111111111111111 View Post
    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.

    Quote Originally Posted by Kristen111111111111111111 View Post
    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".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 5th 2010, 12:05 PM
  2. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 03:30 AM
  3. logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2009, 09:24 AM
  4. logic
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: December 1st 2008, 08:49 AM
  5. logic
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 3rd 2008, 10:30 PM

Search Tags


/mathhelpforum @mathhelpforum