Results 1 to 4 of 4

Math Help - Computer science: Functions help

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    8

    Unhappy Computer science: Functions help

    Hi, I hope I can get some help with this problem. The class is called "Formal models of computation". It's a computer science course where we talk about models of how computers work, Turing machines, automatons, etc. It's kind of like Discrete Math for computer science (which I hated).

    Give functions f: E -> E (where E is the set of even integers) that fulfill the following properties

    a. f is one-to-one, but not onto or total
    b. f is total, but not one-to-one or onto
    c. f is total, one-to-one and onto, but is not the identity function (f(x) = x)
    d. f is not total or one-to-one, but is onto.

    I have part c figured out but can't come up with anything for the other 3. Everytime I come up with a function for one property it doesn't meet the other ones. The professor wants the functions to be in the form f(x) = something. We are not allowed to create subsets of set E either. The functions have to work over the entire set E.

    Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    wil
    wil is offline
    Junior Member wil's Avatar
    Joined
    Apr 2005
    From
    Portland, OR
    Posts
    25

    (b) and (c)

    Quote Originally Posted by AlexH View Post
    Give functions f: E -> E (where E is the set of even integers) that fulfill the following properties

    a. f is one-to-one, but not onto or total
    b. f is total, but not one-to-one or onto
    c. f is total, one-to-one and onto, but is not the identity function (f(x) = x)
    d. f is not total or one-to-one, but is onto.
    I can't help you with all of them, but for (b), try the absolute value function or f(x)=x^2. For (c) try f(x)=x+2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Functions

    Hello AlexH
    Quote Originally Posted by AlexH View Post
    Give functions f: E -> E (where E is the set of even integers) that fulfill the following properties

    a. f is one-to-one, but not onto or total
    b. f is total, but not one-to-one or onto
    c. f is total, one-to-one and onto, but is not the identity function (f(x) = x)
    d. f is not total or one-to-one, but is onto.

    I have part c figured out but can't come up with anything for the other 3. Everytime I come up with a function for one property it doesn't meet the other ones. The professor wants the functions to be in the form f(x) = something. We are not allowed to create subsets of set E either. The functions have to work over the entire set E.
    (a) f(x) = \sqrt{x} works OK. It's not total - only perfect squares, 0, 4, 16, ... work as input values; it's not onto - we're just taking the positive square root; but it is one-to-one.

    wil's suggestions for (b) seem to work OK.

    I'm still thinking about (d) ...

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Functions

    Hello AlexH
    Quote Originally Posted by AlexH View Post
    d. f is not total or one-to-one, but is onto.
    I have got an answer for (d), but it's pretty obscure. I reasoned as follows:

     f is not total, so we must exclude at least one even integer from being a valid input to f. The square root function permits only positive numbers as inputs, so that looks a likely candidate.

     f is onto, so we have to find some way of generating negative as well as positive outputs. So I thought of (-1)^n as a candidate, because, as n goes alternately odd and even, (-1)^n has values -1, 1, -1, 1, ...

     f is not one-one, so there must be at least two different input values that generate the same output value.

    So I played around with these ideas and came up with (wait for it!)

    f(x) = \tfrac{1}{2}(-1)^{\frac{1}{2}\sqrt{x}}(\sqrt{x} - 1 + (-1)^{\frac{1}{2}\sqrt{x}})

    So: x can only take (positive) even perfect squares as values: 0, 4, 16, 36, 64, 100, ... Therefore f is not total.

    For these values of x, then:

    \sqrt{x} = 0, 2, 4, 6, 8, 10, ...

    (-1)^{\frac{1}{2}\sqrt{x}} = 1, -1, 1, -1, 1, -1, ...

    \sqrt{x} - 1 + (-1)^{\frac{1}{2}\sqrt{x}} = 0, 0, 4, 4, 8, 8, ...

    and finally:

    \tfrac{1}{2}(-1)^{\frac{1}{2}\sqrt{x}}(\sqrt{x} - 1 + (-1)^{\frac{1}{2}\sqrt{x}}) = 0, 0, 2, -2, 4, -4, ...

    Note that f(0) = 0 = f(4). So f is not one-one, but it is total, because any even integer (positive or negative) can be generated using a suitable value of x.

    I think you need a twisted mind for this sort of thing!

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Oracles in computer science
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 7th 2011, 04:05 PM
  2. computer science problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 05:16 PM
  3. Help with Computer Science Java
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: October 1st 2009, 05:24 PM
  4. Computer Science
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: August 7th 2009, 05:06 PM
  5. Calculus on science computer
    Posted in the Calculus Forum
    Replies: 2
    Last Post: July 18th 2007, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum