Results 1 to 13 of 13

Math Help - Logical identities problem

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    31

    Logical identities problem

    I've just started a course in logics and set theory with no background whatsoever in this field, and for some reason I'm having problems with proving stuff with identities.

    I'll try and give the first problem I'm stuck in, which is one of the easier ones I got for homework - hoping that I might get the idea and be able to continue on my own.

    here it is then :

    (pΛ~q)→~(pVr) ≡ p→q
    so I did :
    ~(pΛ~q) V ~(pVr) ≡ p→q
    and...I'm stuck I tried several other formulas and got nowhere.
    I think that one of my biggest problems is that I'm not completely sure how to treat the variables and think of it as an equation instead of whatever it is .

    If anybody could show me the way to prove it, maybe with a some commentary as well - I would highly appreciate it, cause I'm pretty lost.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Laban View Post
    I've just started a course in logics and set theory with no background whatsoever in this field, and for some reason I'm having problems with proving stuff with identities.

    I'll try and give the first problem I'm stuck in, which is one of the easier ones I got for homework - hoping that I might get the idea and be able to continue on my own.

    here it is then :

    (pΛ~q)→~(pVr) ≡ p→q
    so I did :
    ~(pΛ~q) V ~(pVr) ≡ p→q
    and...I'm stuck I tried several other formulas and got nowhere.
    I think that one of my biggest problems is that I'm not completely sure how to treat the variables and think of it as an equation instead of whatever it is .

    If anybody could show me the way to prove it, maybe with a some commentary as well - I would highly appreciate it, cause I'm pretty lost.

    Thanks

    I don't understand how come you changed the --> in the original formula with V in the second....why?!

    Anyway, to show logical equivalence you've to build truth tables for both sides and prove that for ANY

    given values for p,q you get the same truth value in both tables.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by Laban View Post
    I've just started a course in logics and set theory with no background whatsoever in this field, and for some reason I'm having problems with proving stuff with identities.

    I'll try and give the first problem I'm stuck in, which is one of the easier ones I got for homework - hoping that I might get the idea and be able to continue on my own.

    here it is then :

    (pΛ~q)→~(pVr) ≡ p→q
    so I did :
    ~(pΛ~q) V ~(pVr) ≡ p→q
    and...I'm stuck I tried several other formulas and got nowhere.
    I think that one of my biggest problems is that I'm not completely sure how to treat the variables and think of it as an equation instead of whatever it is .

    If anybody could show me the way to prove it, maybe with a some commentary as well - I would highly appreciate it, cause I'm pretty lost.

    Thanks
    Your first step is correct. You have to proceed as follows :

    ≡ ~(pΛ~q) V ~(pVr)

    ≡ (~pVq)V(~pΛ~r)

    ≡ (~pV(~pΛ~r)) V(qV(~pΛ~r))

    ≡ ~pV((qV~p)Λ(qV~r))

    ≡ (~pVq)Λ(~pVqV~r)

    ≡ ~pVq

    Some steps as well as the reasoning are not shown. Can you complete the details ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    I think I got this part (~pV(~pΛ~r)) V(qV(~pΛ~r)) , though I still find it hard to match it with any of the basic formulas - which is quite important to me here, since obviously, I can't seem to think an inch beyond them - which is really bad.

    The part after ~pV((qV~p)Λ(qV~r)) is completely beyond me - so I'd love some details.

    Anywise, Thank you.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by Laban View Post
    I think I got this part (~pV(~pΛ~r)) V(qV(~pΛ~r)) , though I still find it hard to match it with any of the basic formulas - which is quite important to me here, since obviously, I can't seem to think an inch beyond them - which is really bad.

    The part after ~pV((qV~p)Λ(qV~r)) is completely beyond me - so I'd love some details.

    Anywise, Thank you.
    (~pV(~pΛ~r)) V(qV(~pΛ~r)) ≡ ~pV((qV~p)Λ(qV~r)) :

    (~pV(~pΛ~r)) ≡ ~p because AV(AΛB) = A, since (AΛB) is a subset of A.

    (qV(~pΛ~r)) ≡ (qV~p)Λ(qV~r)) by the distributive laws.


    ~pV((qV~p)Λ(qV~r)) ≡ (~pVq)Λ(~pVqV~r) :

    ~pV((qV~p)Λ(qV~r))≡(~pVqV~p) Λ(~pVqV~r)) again, by the distributive laws.

    Notice that the first clause becomes (~pVq). Now consider (~pVq) as A and ~r to be B. the expression becomes AΛ(AVB). What does this work out to be ?

    Also, I leave it to you to write down the whole thing more formally.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    Ok thanks, finally got it

    but while working on it alone (meaning with friends xD) I got this - I'd like it if you could check to see if it makes sense :
    starting here :

    ≡ (~pVq) V (~pΛ~r) ≡ (now I just change the appearance a bit, adding brackets to make it look more organized)

    ≡ q V [~p V (~pΛr)] ≡ (now using this formula p V (pΛq) ≡ p; just that the p is ~p in this case)

    ≡ q V ~p

    is it good?
    Last edited by Laban; October 15th 2010 at 07:59 AM. Reason: wrongly pressing replay
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Excellent !

    I prefer your solution to mine.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    I really can't take much credit for this since I didn't came up with it by myself but thank you.
    It is really important for me at this stage to get the "playability" of the formulas and identities, which is still a bit awkward to me.

    I'd like to ask another question, if you don't mind :

    a,b and c are 3 different numbers.
    arrange them by size if you know that :
    if a is not the biggest then b is the biggest and if b is not the smallest then c is the biggest.

    I don't even know where to start.

    p.s - excuse my bad wording - it's freely translated
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by Laban View Post

    a,b and c are 3 different numbers.
    arrange them by size if you know that :
    if a is not the biggest then b is the biggest and if b is not the smallest then c is the biggest.
    Case 1: a is not the biggest .

    b is the biggest. So b is not the smallest. So c should be the biggest which is a contradiction.

    Case 2: a is the biggest.

    c is not the biggest. Therefore b is the smallest. So we have b<c<a.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    aww...you make it look super easy though I still don't quite get it :/

    is it possible to display it in identities as well?

    thanks a lot for your crazy fast replys as well bb
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Laban View Post
    I still don't quite get it
    There are two possible cases: One possible case is where A is not the biggest, and the other possible case is where A is the biggest.

    So let's check what happens in either case:

    If case one holds, then A is not the biggest, so B is the biggest, so B is not the smallest, so C is the biggest. But it can't be that both B and C are the biggest. So case one is not actually possible. So we can eliminate case one.

    So case two holds, so A is the biggest, so C is not the biggest, so B is the smallest (by "modus tollens", since we were told that if B is NOT the smallest then C IS the biggest). So we have B is the smallest and A is the biggest, so C is in between, so we have B, C, A in order from smallest to biggest.

    And that's the answer - B, C, A from smallest to biggest - since case one does not hold (it would be a contradiction if it did hold) so only case two can hold.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Quote Originally Posted by Laban View Post
    aww...you make it look super easy though I still don't quite get it :/

    is it possible to display it in identities as well?

    thanks a lot for your crazy fast replys as well bb
    It can work like this:

    a is the smallest = a1
    a is in the middle = a2
    a is the biggest = a3

    b is the smallest = b1
    b is in the middle = b2
    b is the biggest = b3

    c is the smallest = c1
    c is in the middle = c2
    c is the biggest = c3

    Observe that a1→~a2Λ~a3Λ~b1Λ~c1. Similar conditions hold true for other variables.

    Now the given conditions are :

    ~a3 → b3
    ~b1 → c3

    Now, any variable is either true or false. So we will have the following cases :

    1) ~a3

    → b3
    → ~b1
    → c3

    But b3 → ~c3 which is a contradiction.

    2) a3

    → ~c3
    → b1
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Oct 2010
    Posts
    31
    thanks all.

    Traveller - thanks for putting out with me, I'll probably be back soon with some more problems.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Logical Problem
    Posted in the Math Puzzles Forum
    Replies: 2
    Last Post: March 18th 2011, 12:39 PM
  2. Replies: 6
    Last Post: June 22nd 2010, 11:59 PM
  3. Prove/disprove using logical using logical arguments
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 24th 2010, 06:29 AM
  4. Replies: 3
    Last Post: January 21st 2010, 07:45 AM
  5. logical math problem?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 28th 2009, 05:47 PM

Search Tags


/mathhelpforum @mathhelpforum