Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean Functions

  1. Oct 23, 2004 #1

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm trying to understand why, in two-valued boolean algebra, for n variables, it is possible to form 22n different boolean functions. The textbook explanation is not quite clear.

    Thanks
     
  2. jcsd
  3. Oct 24, 2004 #2

    selfAdjoint

    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    Since the variables can only take on two values, 0 and 1 (or F and T), every function of them can be completely specified by a table with a cell for each distinct combination of input values. How many cells will there be? The first variable can be 0 or 1, so can the second,... what does this come out to be (you figure it), so call this number of cells N_C. Each of the N_C cells can be in one of two output states. How many states is that? (Another calculation). As a function of N_C; then plug your value for N_C into this formula. Does your answer match the one given in the textbook? If not you made a mistake somewhere, go back and find it. If still stuck post your work here and ask again.
     
  4. Oct 24, 2004 #3

    uart

    User Avatar
    Science Advisor

    I don't think it's 2^(2n) but rather 2^(2^n). Perhaps this was just a latex typo or formatting problem.

    Anyway the easiest way to see why it's 2^(2^n) is to consider the function to be defined by a truth-table, that is, all 2^n possible combinations of the input variables listed on the left and the function output (which is either zero or one in any given position) listed on the right.

    The question of how many different functions are possible is indentical to the question of how many unique ways can you fill out the truth-table output. Clearly a function differs from another function if it is different in even just one of the 2^n positions. So the number of such function is therefore precisely the same as the number of binary combinations that can be formed in the 2^n posistions of the truth-table, which of course is 2^(2^n)
     
  5. Oct 24, 2004 #4

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    selfAdjoint: I'll think it out...

    if n = 2, (i.e. we have F(x,y)), then there are 4 possible inputs to the function, namely 00, 01, 10, 11. Are there 22n possible functions because each one of these inputs could result in either a zero or a one, so we have (2n)2 = 16 outcomes? i.e. it is possible to have all of the inputs produce a one, all produce a zero, and any combination in between?

    Another way of looking at it: These inputs that I listed correspond to minterms: m0, m1, m2, and m3. So the question is reduced to how many possible ways are there to sum these minterms together:

    [1] m0

    [2] m0 + m1

    [3]m0 + m1 + m2

    [4]m0 + m1 + m2 + m3

    plus three more (m1 by itself and the sum of it and each of the remaining two (2&3))

    plus two more (m2 by itself and the sum of it and the remaining one (3))

    plus one more (m3)

    plus two more (the sum of m0 and each of 2 and 3)

    Hmm...that's twelve...missing four. Wait...I got it:

    0 + 2 + 3
    0 + 1 + 3
    1 + 2 + 3

    arrrggghhh...that's only 15. Took me forever to realise that the last one I was missing was a sum of none of the terms:

    F = 0. :redface:

    Surely threre must be some easier way of arriving at this using permutations or something?
     
  6. Oct 24, 2004 #5

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    uart: sorry dude, I'm going with the book on this one....
     
  7. Oct 24, 2004 #6

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    selfAdjoint:

    Ok...I also read the section on K-maps (slowly reviewing for my midterm tomorrow in digital logic design...I guess I should have known all about those 16 functions, because some are quite important: NAND, NOR, XOR XNOR, etc. Thankfully I've studied now.). It seems trivial now that for a two by two array of cells representing the minterms, each of which will be filled in with either 0 or 1, there will be 4 x 4 = 16 possible ways to fill in the K-map.

    Three variable map: 2 X 4 cells....8 X 8 = 64 = (23)2.

    But I'm still wondering about my first reply post and whether there is some easier way of doing it using n permute something....
     
    Last edited: Oct 24, 2004
  8. Oct 25, 2004 #7

    uart

    User Avatar
    Science Advisor

    Code (Text):

    abc f0  f1  f2  f3  f4  f5  f6  f7  ....
    --- --  --  --  --  --  --  --  --
    000 0   0   0   0   0   0   0   0
    001 0   0   0   0   0   0   0   0
    010 0   0   0   0   0   0   0   0
    011     0   0   0   0   0   0   0   0
    100 0   0   0   0   0   0   0   0
    101 0   0   0   0   1   1   1   1
    110 0   0   1   1   0   0   1   1
    111 0   1   0   1   0   1   0   1
     
    I hope you can see that this series of functions can be extended to 2^(2^3)) =256 unique truth-tables and that it is not limited to 2^(2*3) = 64 as you are claiming. Not unless you are placing some form of un-stated restriction on the characteristics of the functions under consideration.
     
    Last edited: Oct 25, 2004
  9. Oct 26, 2004 #8

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I do see it! From your table it is obvious that the number of ways to fill eight different spots each with one of two possible values is

    [tex] 2^8 = 2^{2^3} [/tex].

    I apologize for being so blase about it before. I was blinded to this because I was considering the [itex] n = 2 [/itex] case, where it just so happens that

    [tex] 2^{(2 \times 2)} = 2^{2^2} [/tex].

    Still, no matter how I look at it, all my methods...(the "reasoning out" method at the beginning of post #4 and the minterm method that made up the rest of the post, as well as the K-map method in post #6...all seem to point to 256 possible functions for [itex] n = 3 [/itex].

    About the minterm method, if somebody would kindly answer the question I posed in #4 about whether there is an easier method of finding out how many different ways to sum up [itex] 2^n [/itex] minterms (using permutations, I think?), then that will probably clinch it. Still, I wasn't lying about the textbook:

    (Now you see what I meant about the text book explanation being crappy in the first place!) If this statement is truly a mistake (and I'm more and more convinced it is), then they commit it at least twice, once again on pg. 48.

    :grumpy:
     
  10. Oct 26, 2004 #9

    uart

    User Avatar
    Science Advisor

    Yeah I've seen that book by Mano, I never thought it was a particularly good text. In this case though I think it is simply a text setting error that has slipped through the proof reading. Actually double indexes, such as this case of an exponent of an exponent, is something that can get messed-up fairly easily during text setting. I'll bet it was 2^(2^n) in the original manuscript and that it got broken somewhere in the text setting and printing of the book.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Boolean Functions
  1. Boolean functions (Replies: 13)

Loading...