Results 1 to 13 of 13

Math Help - ordered or unordered selections

  1. #1
    Junior Member
    Joined
    Apr 2012
    From
    canada
    Posts
    38

    ordered or unordered selections

    Consider the Boolean functions f(x, y, z) in three variables such that the table of values of f contains exactly four 1ís.

    (i) Calculate the total number of such functions.

    I was trying to think of this in a mentality of an injective functions, say A= (1,1,1,1) and B = (1,2,3,...,24)
    So I thought 24P4 (ordered and with without repetition
    )




    (ii) We apply the Karnaugh map method to such a function f. Suppose that the map does not contain any blocks of four 1ís, and all four 1ís are covered by three blocks of two 1ís. Moreover, we find that it is not possible to cover all 1ís by fewer than three blocks. Calculate the number of the functions with this property.

    Here, I tried drawing it, I got 12 different ways.. But still trying to figure out how to put that in equation terms.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: ordered or unordered selections

    Hey cellae.

    Can you clarify with the boolean functions are x,y,z all just bits and what space does this function map to (i.e. x,y,z contains 2^3 = 8 possibilities for 3 independent bits, but f can map these either to a lower or higher dimensional space and this info is not given).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2012
    From
    canada
    Posts
    38

    Re: ordered or unordered selections

    umm. Well, that is exactly the question I was given - but I have made a bit of progress:

    (i) So the are the 2^3 possible functions.. And the from here I ask myself; how can I pick precisely 4 1's out of the 8.. which I did (8C4).. so 70

    Then, for (ii)
    I'm still trying to figure out how to calculate the total possibilities of the 4 grouped 1's - the 4 possible square grouped 1's.. this is painful.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: ordered or unordered selections

    Try treating a group as one outcome and everything else as the opposite outcome.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2012
    From
    canada
    Posts
    38

    Re: ordered or unordered selections

    Ok, what about this..

    There is 8 places to put the first 1... Then, because the second 1 needs to sit next to the other 1 then there is 3 possible spots.. Then again, the third 1 has to sit next to a 1, and again the fourth 1 has to be next to a 1.. and there are 4 possible squares of 4 ones..

    sooo.. (8x3x2x1) - 4..so 44 possibilities?

    Seems like a lot though ..
    Last edited by cellae; October 17th 2012 at 03:06 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2012
    From
    Sydney
    Posts
    5
    a
    Last edited by hazthat1; October 17th 2012 at 03:55 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2012
    From
    Sydney
    Posts
    5

    Re: ordered or unordered selections

    Can you clarify your twelve mine look like the following;

    YZ YZ' Y'Z' Y'Z
    x 0 1 1 0
    x' 1 1 0 0
    YZ YZ' Y'Z' Y'Z
    x 1 1 0 0
    x' 1 0 0 1
    YZ YZ' Y'Z' Y'Z
    x 1 1 0 0
    x' 0 1 1 0
    YZ YZ' Y'Z' Y'Z
    x 1 0 0 1
    x' 1 1 0 0
    YZ YZ' Y'Z' Y'Z
    x 0 0 1 1
    x' 0 1 1 0
    YZ YZ' Y'Z' Y'Z
    x 1 0 0 1
    x' 0 0 1 1
    YZ YZ' Y'Z' Y'Z
    x 0 1 1 0
    x' 0 0 1 1
    YZ YZ' Y'Z' Y'Z
    x 0 0 1 1
    x' 1 0 0 1

    Giving me 8 for 1.b and not 12
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Apr 2012
    From
    canada
    Posts
    38

    Re: ordered or unordered selections

    well, there is definitely more that 8!

    I got 16, and that was without overlapping the walls (if that makes sense, like in your last example)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2012
    From
    Sydney
    Posts
    5

    Re: ordered or unordered selections

    hmmm... can you give me some hints on what I am doing wrong? for example

    Like to have three overlapping of 2 1's mean's to me that the z-shape formed is rotated along....

    Wait did you swap up the columns at all?

    As i think I might be able to get another 8 by doing that?
    Last edited by hazthat1; October 17th 2012 at 03:59 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Apr 2012
    From
    canada
    Posts
    38

    Re: ordered or unordered selections

    I too am trying to figure this out ..

    But how is the rest of your 'HW' going ? figure out the propositions?
    Last edited by cellae; October 17th 2012 at 04:07 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2012
    From
    Sydney
    Posts
    5

    Re: ordered or unordered selections

    not yet - going to revise logic quickly before attempting it
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Apr 2012
    From
    canada
    Posts
    38

    Re: ordered or unordered selections

    Well, I know a definite one is (q<->q)..
    and I'm tossing whether (qv~q) is non equivalent or not..

    hope that saves a bit of time !
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Oct 2012
    From
    Sydney
    Posts
    5

    Re: ordered or unordered selections

    [QUOTE=cellae;744469]Well, I know a definite one is (q<->q)..
    and I'm tossing whether (qv~q) is non equivalent or not..

    hope that saves a bit of time ![/QUOTE

    Ignore this - not sure how to delete
    Last edited by hazthat1; October 17th 2012 at 04:53 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sorting of unordered elements - worst case scenario
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 7th 2012, 08:24 AM
  2. Replies: 0
    Last Post: December 7th 2010, 07:17 AM
  3. No of selections and probability
    Posted in the Statistics Forum
    Replies: 10
    Last Post: September 29th 2010, 03:39 AM
  4. Counting Unordered Selections: Card Selection
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 14th 2010, 02:23 PM
  5. ordered and unordered partitions
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 12th 2009, 11:39 AM

Search Tags


/mathhelpforum @mathhelpforum