Notices
Results 1 to 5 of 5

Thread: relations problem

  1. #1 relations problem 
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Hello! Merry Christmas and a Happy New Year.

    I got one problem.

    Alpha is relation on A x A, where A is set.

    I need to prove:

    alpha is symmetric and antisymmetric if and only if alpha is subset of {(x,x)|x is in A}

    I tried to prove it this way.

    Let x,y is in the set A.

    Alpha is symetric:

    If (x,y) is in alpha then (y,x) is in alpha.

    Alpha is antisymetric:

    If (x,y) is in alpha and (y,x) is in alpha then x=y

    So I need to prove:

    (P -> Q) ^ ((P ^ Q) -> S) <=> (P -> S)

    where p denotes - (x,y) is in alpha
    q denotes - (y,x) is in alpha
    s denotes - x=y

    But when I construct truth table (it is not tautology) it falls on:
    P- true
    Q-false
    S-true

    Is the theorem not correct or I did some mistake?

    Thanks in advance.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I would skip the logic problem and just use a proof by contradiction. Assume that (x,y), for some x not queal to y, is in A.


    Reply With Quote  
     

  4. #3  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Quote Originally Posted by MagiMaster
    I would skip the logic problem and just use a proof by contradiction. Assume that (x,y), for some x not queal to y, is in A.
    Thank you.

    Yes, I know that I could solve it that way.

    I solved it that way, but I am interested in this way (because it is straightforward).

    Could you possibly tell me what is the error?

    P.S I also tried several other problems using that method but nothing, always false cases.

    Thanks in advance.
    Reply With Quote  
     

  5. #4  
    Forum Bachelors Degree
    Join Date
    Apr 2007
    Location
    Veles,Macedonia
    Posts
    473
    Magi, anybody?
    Reply With Quote  
     

  6. #5  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Implication and truth tables always throws me a bit. The truth table for implication is a bit misleading. One of the true entries should really read something more like N/A, but since it's supposed to be either true or false, we say it's vacuously true.

    In this particular case, you have P->Q is false but P and S are both true. I'm not sure this is particularly instructive.

    In generaly, when you're using implications, I think you should either get rid of the implications (transform them in to something else), or use some method of proof other than a truth table. (You can still use boolean logic, but skip the truth table.)
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •