Understanding Boolean Functions & 2-Valued Algebra

[cepheid]

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

Thanks

 

[selfAdjoint]

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.

 

[uart]

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)

 

[cepheid]

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 2²ⁿ possible functions because each one of these inputs could result in either a zero or a one, so we have (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: m₀, m₁, m₂, and m₃. So the question is reduced to how many possible ways are there to sum these minterms together:

[1] m₀

[2] m₀ + m₁

[3]m₀ + m₁ + m₂

[4]m₀ + m₁ + m₂ + m₃

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

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

plus one more (m₃)

plus two more (the sum of m₀ 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 realize that the last one I was missing was a sum of none of the terms:

F = 0.

Surely threre must be some easier way of arriving at this using permutations or something?

 

[cepheid]

uart: sorry dude, I'm going with the book on this one...

 

[cepheid]

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 = (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...

 

[uart]

uart: sorry dude, I'm going with the book on this one...

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.

 

[cepheid]

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

$$2^8 = 2^{2^3}$$.

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

$$2^{(2 \times 2)} = 2^{2^2}$$.

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 $n = 3$.

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 $2^n$ minterms (using permutations, I think?), then that will probably clinch it. Still, I wasn't lying about the textbook:

From Digital Design, Third Edition, by M. Morris Mano, pg. 46:

It was previously stated that for n binary variables, one can obtain 2ⁿ distinct minterms, and that any Boolean function can be expressed as a sum of minterms . The minterms whose sum define the Boolean function are those that give the 1's of a function in a truth table. Since the function can be either 1 or 0 for each minterm, and since there are 2ⁿ minterms, one can calculate the possible functions that can be formed with n variables to be 2²ⁿ.

(Now you see what I meant about the textbook 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:

 

[uart]

and since there are 2^n minterms, one can calculate the possible functions that can be formed with n variables to be 2^(2n)

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.