Discrete Mathematics

profilew350500

Note that "iff" stands for "if and only if". Also, to show "whether or not" means to give a proof for it if it is true and to give a counter example if it is false. Finally a R b means "a is related to b", i.e. (a,b)R.

  1. Let R be the relation on socks in your drawer defined by the following property: 
    a R b iff a and b have the same number of stripes 
    1. Show whether or not R is reflexive.
    2. Show whether or not R is symmetric.
    3. Show whether or not R is transitive.
    4. Is R an equivalent relation? If it is, how may equivalence classes does it have?
  2. Let R be the relation on natural numbers defined by the following property: 
    a R b iff a+b is even 
    1. Show whether or not R is reflexive.
    2. Show whether or not R is symmetric.
    3. Show whether or not R is transitive.
    4. Is R an equivalent relation? If it is, how many equivalence classes does it have?
  3. Let R be the relation on natural numbers defined by the following property: 
    a R b iff f(a)=f(b), where f(n) is the number of 1's in the binary representation of n 
    1. Show whether or not R is reflexive.
    2. Show whether or not R is symmetric.
    3. Show whether or not R is transitive.
    4. Is R an equivalent relation? If it is, how many equivalence classes does it have?
  4. Let R be the relation on functions that map natural numbers to natural numbers defined by the following property: 
    fRg iff for all natural numbers nf(n)g(n) 
    1. Show whether or not R is reflexive.
    2. Show whether or not R is symmetric.
    3. Show whether or not R is transitive.
    4. Is R an equivalent relation? If it is, how many equivalence classes does it have?
  5. Let R be the relation on natural numbers defined by the following property: 
    a R b iff a%7=b%7 (where % is the C++ remainder operation) 
    1. Show whether or not R is reflexive.
    2. Show whether or not R is symmetric.
    3. Show whether or not R is transitive.
    4. Is R an equivalent relation? If it is, how many equivalence classes does it have?
  • 9 years ago
  • 50
Answer(1)

Purchase the answer to view it

blurred-text
NOT RATED
  • attachment
    w350500.docx