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? 
Administrator

For a function with n inputs there are 2^{n} 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^{2n}. Mark 
Thanks for that explanation.
IMO, it would be easier to recognize these relationships if Figure 1.1 had shown a few examples of simpler twoinput functions. See image. 
“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 twovariable functions, 2^2 = 4 combinations (00, 01, 10, 11) For binary threevariable functions, 2^3 = 8 (000, 001, 010, 011, 100, 101, 110, 111) The formula (base^n) works for other number bases. For ternary twovariable functions, 3^2 = 9 (e.g. 00, 01, 02, 10, 11, 12, 20, 21, 22) For decimal twovariable 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 threevariable 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, twovariable 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 4bit matrix in Figure 1.2 confirms 16 unique binary values representing 16 Boolean functions. A binary threevariable format has 8 combinations^2 = 64, which also agrees with the book formula. 2^2^3 = 64. However, when I make an 8bit 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 
Administrator

You misquote what I wrote by loosing the typography that n is superscripted. “For a function with n inputs there are 2^{n} rows in the truth table.” As I wrote, "... the number of unique truth tables is 2^{2n}." So in the case of n=3, there are 2^{23}=2^{8}=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 
This post was updated on .
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 “rightto 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 threevariable 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. 
Administrator

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^{2n+1}, 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 righttoleft association for the exponential operator follows from the evaluation order of x^{2n+1}.
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^{2n} formula is not used anywhere else in this chapter, so the derivation is not needed. Mark 
Free forum by Nabble  Edit this page 