Figure 1.1, Truth table, number of Boolean functions

[gs99]

At bottom of page 9, I read: ”An inspection of figure 1.1 reveals that the number of Boolean functions that can be defined over n binary variables is 2^2^n.”

The truth table in Figure 1.1 has three variables. The results indicate f(x, y, z) = (x + y)z’, as mentioned on page 8.  

How does a close inspection of figure 1.1 reveal the formula 2^2^n?

[cadet1620]

For a function with n inputs there are 2ⁿ rows in the truth table.

The output value for each row can be one of two values, 0 or 1, so the number of unique truth tables is 2²ⁿ.

--Mark

[gs99]

Thanks for that explanation.

IMO, it would be easier to recognize these relationships if Figure 1.1 had shown a few examples of simpler two-input functions. See image.

[gs99]

“For a function with n inputs there are 2n rows in the truth table.”

I assume ‘2’ represents binary base 2. Is that what you’re referring to by “two values, 0 or 1”?
For binary two-variable functions, 2^2 = 4 combinations (00, 01, 10, 11)
For binary three-variable functions, 2^3 = 8    (000, 001, 010, 011, 100, 101, 110, 111)

The formula (base^n) works for other number bases.
For ternary two-variable functions, 3^2 = 9    (e.g. 00, 01, 02, 10, 11, 12, 20, 21, 22)
For decimal two-variable functions, 10^2 = 100    (00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11 … 97, 98, 99)

Getting the combinations in truth tables is normally done first. The book first explains truth tables as one of the ways to specify a Boolean function, providing an example of a three-variable format with eight combinations in Figure 1.1.

It then refers to the question of how many unique Boolean functions can be expressed on a given truth table format.
What’s the relationship between the combinations and the number of functions? Can the result of the first calculation (2^n) be input to the second? By looking at Figure 1.2, we see there are 16 functions on a binary, two-variable format that has 4 combinations.

In this example, the relationship appears to be: combinations^2 = number of functions (4^2 = 16). This agrees with the book formula (2^2^n) = 2^2^2 = 16. The 4-bit matrix in Figure 1.2 confirms 16 unique binary values representing 16 Boolean functions.  

A binary three-variable format has 8 combinations^2 = 64, which also agrees with the book formula. 2^2^3 = 64.

However, when I make an 8-bit matrix, there are 256 unique results, starting with:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
and ending with:
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1
(11111111 = 255)

How many Boolean functions can be used with a three variable format, 64 or 256?
This site indicates 256: http://www.sdmath.com/math/boolean.html

[cadet1620]

gs99 wrote

“For a function with n inputs there are 2n rows in the truth table.”

You misquote what I wrote by loosing the typography that n is superscripted.

“For a function with n inputs there are 2ⁿ rows in the truth table.”

How many Boolean functions can be used with a three variable format, 64 or 256?
This site indicates 256: http://www.sdmath.com/math/boolean.html

As I wrote, "... the number of unique truth tables is 2²ⁿ."

So in the case of n=3, there are 2²³=2⁸=256 possible Boolean functions.

Note that sequential exponentiation when written using typographic superscripting evaluates from right to left. a^bc is a^(b^c). Left to right evaluation must be written as (a^b)^c.

One should always use parentheses when writing sequential exponentiation when using "^". Use (a^b)^c when you mean left to right evaluation.

--Mark

[gs99]

I apologize for the typo (2n), but in all my examples, I demonstrate the concept of exponent.

You mention two terms new to me: “sequential exponentiation” and “typographic superscripting”.
I assume sequential exponentiation is equal to “nested exponents”. And typographic superscripting is when exponents appear as superscripts, not using the ^ character.

There is considerable confusion about evaluating nested exponents.
Disagreement on operator precedence for 2^3^4
http://www.walkingrandomly.com/?p=4154

Exponential Powers - GMAT Math Study Guide
http://www.platinumgmat.com/gmat_study_guide/exponential_powers
This statement appears near the bottom: “A recursive exponential expression is one in which multiple exponents are nested within each other." Their example:

appears the same as what’s in the book.
But they say:  “It would be wrong to first compute 2^3 = 8 and then compute 2^8 = 256.”

However, I’ve come to learn that “right-to left” evaluation of nested exponents is perhaps the authoritative choice.

Personally, I prefer simpler ways of learning. The first “formula” provided is 2^n.

The ‘2’ here represents base two, the actual values of 0 and 1 in the table. So it’s also the base of exponent n, the number of variables/input, and not the reverse: n^2.
 
This could be stated b^n (base^number of variables).

The same formula can be used to find both:
…the number of combinations in a truth table
…the number of Boolean functions  
for any base and variable quantity.

Our focus is on binary; for a three-variable format:
2^3 = 8 combinations
2^8 = 256 Boolean functions
or 2^(2^3) = 256. (This works in Excel: =A2^(B2^C2) where numbers 2, 2, 3 are in A, B, C.

[cadet1620]

Time to put on my math teacher hat...

A nice concise statement of the rule for evaluating exponential expressions involving multiple exponents can be found in the textbook Basic Mathematics for Engineers, 8th Ed., Stephen A. Fenner.

The reason for this is the the exponent in an exponential is it itself an expression consisting of all of the superscripted text. For example, a very common expression that you will find in textbooks is x²ⁿ⁺¹, related to series expansions of trigonometric functions. Because the 2n+1 is set in the same size type and at the same superscript level it must be evaluated before the exponentiation—there are implied parentheses surrounding the superscripted expression.

This example shows how the right-to-left association for the exponential operator follows from the evaluation order of x²ⁿ⁺¹.

x2n+1	=	x(2n+1)
x2n+1	=	x(2n+1)
x2n	=	x(2n)

We always had confusion about this order of evaluation in my classes because different brands of calculators evaluate 2^3^4 differently, as do different calculator apps, spreadsheet programs, and programming languages.

Always use parentheses when writing anything but the most basic exponential using the "^" or "**" operators. Use (2^3)^4 or 2^(3^4) so that your meaning will be clear.

---

Regarding "An inspection of figure 1.1 reveals that..."

I have always disliked that structure in textbooks. If it is important that students know the derivation of a formula used in the text, then the derivation should be given. Otherwise, the formula should simple be used.

The 2²ⁿ formula is not used anywhere else in this chapter, so the derivation is not needed.

--Mark