0
$\begingroup$

Why are there $2^{2^{n}}$ possible boolean functions of n inputs? How to derive that?

For 3, I can only write down 16 and cannot go further.

8 of

$f(x_{1},x_{2},x_{3})=0$

000 = 0

001 = 0

010 = 0

110 = 0

111 = 0

110 = 0

101 = 0

011 = 0

and

8 of

$f(x_{1},x_{2},x_{3})=1$

000 = 1

001 = 1

010 = 1

110 = 1

111 = 1

110 = 1

101 = 1

011 = 1

That's the maximum I can go. How do I proceed?

$\endgroup$
  • 2
    $\begingroup$ What did you try? Where did you get stuck? Do you know how many functions there are from a generic set $A$ to a generic set $B$? Can you work out what the relevant sets $A$ and $B$ are for the question you're asking? Can you work out how big those sets are? $\endgroup$ – David Richerby Oct 10 '15 at 11:57
  • 1
    $\begingroup$ Once you figure it out, this may also give you an idea why the set of functions from $A$ to $B$ is sometimes written $B^A$. $\endgroup$ – G. Bach Oct 10 '15 at 12:15
  • $\begingroup$ I have confirmed again and again that it should be 2∗2n instead. For 1, 4 functions. For 2, 8 functions, For 3, 16 functions, For 4, 32 functions $\endgroup$ – Ka-Wa Yip Oct 11 '15 at 3:32
  • 3
    $\begingroup$ Then you are wrong, again and again. $\endgroup$ – Raphael Oct 11 '15 at 7:10
4
$\begingroup$

Hint: let $f$ be a boolean function with $n$ inputs i.e $f(b_{1},b_{2},b_{3}...b_{n})$ For example, when $n=3$, $(1,0,1)$ and $(1,1,0)$ are different inputs to $f$. Each input maps to an answer. Also there are limited values that $f(b_{1},b_{2},...,b_{n})$ can take.

Now consider the definition of a function: $f\colon A \to B$

Define the size of both sets $A$ and $B$ and you will arrive at your answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I can only know it is $2*{2^{n}}$ as 2 outputs for each function only. I understand $2^{n}$ part. But do not know why need power again. $\endgroup$ – Ka-Wa Yip Oct 10 '15 at 19:28
  • 1
    $\begingroup$ Think in terms of this : $$(input_{1},input_{2},....,input_{2^{n}}) -> (f(input_{1}),...f(input_{2^{n}}))$$ $\endgroup$ – jjohn Oct 10 '15 at 19:35
  • $\begingroup$ as each $f(input_{1})$ has two outputs. Why isn't it $2*{2^{n}}$ instead? $\endgroup$ – Ka-Wa Yip Oct 10 '15 at 20:14
  • $\begingroup$ With that reasoning, there are only $2n$ binary numbers of length n because $b_{i} =0$ or $1$. I'd suggest you read this pdf about the Product Rule in Combinatorics. math.vanderbilt.edu/~mne/274/post0108.pdf $\endgroup$ – jjohn Oct 10 '15 at 20:28
  • $\begingroup$ @ jjohn The output I intend is only 0 or 1. Is it also what you assume here? $\endgroup$ – Ka-Wa Yip Oct 11 '15 at 1:59
2
$\begingroup$

There are $2^{2^3}=256$ different boolean functions of 3 inputs. The $2^3$ here represents the number of rows in the truth table.

Here is the truth table for one of the functions.

Every different assignment of column $X$ is a different function. There are a total of 256 assignment.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Oh! I see it now. So one function takes all inputs of different values. So even if f(0,0,0) =1 and g(0,0,0) =1, f and g will be different if they have different outputs for other entries? $\endgroup$ – Ka-Wa Yip Oct 11 '15 at 10:12
  • $\begingroup$ This answer doesn't quite match the question. The question asks about a boolean function of $n$ inputs, but this answer talks about a function of 3 inputs. I see that you copy-pasted your answer to another question based on Raphael's suggestion, but in the process of doing that, your answer doesn't actually answer the question that was asked here. It might be more useful to edit this answer so that it responds to the question that was asked (about boolean functions of $n$ inputs). $\endgroup$ – D.W. Oct 11 '15 at 10:28
  • 1
    $\begingroup$ Adding a comment on how the observation extends to arbitrary $n$ is probably sufficient. The OP did not get the "general proof" answers, to the "by example" route is probably advisable. (cc @D.W.) $\endgroup$ – Raphael Oct 11 '15 at 11:06
1
$\begingroup$

For any function f, we are being provided n inputs i.e. f(x1,x2,x3,...,xn). Now, it's not important that that function f uses every input provided to produce an output i.e. f may only use a certain subset of inputs from the set of given inputs. The number of possible ways of selecting distinct subsets from a given set of n elements = 2^n. (common set property). Now another thing is the function is boolean. So for every set of inputs it uses, there can be two functions f1 and f2, one which provide true and other which result out for false. Hence there can be 2^(2^n) possible ways for generating boolean functions given n inputs.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Note that you can use LaTeX to format your post. $\endgroup$ – Tom van der Zanden Oct 10 '15 at 13:21
  • $\begingroup$ "Hence there can be 2^(2^n)". How to see that? $\endgroup$ – Ka-Wa Yip Oct 11 '15 at 3:27
1
$\begingroup$

Three input variables form $8$ distinct combinations and you can freely associate $0$ or $1$ to each of them. That makes $2^8$ distinct functions.

$$000\ 001\ 010\ 011\ 100\ 101\ 110\ 111\\\downarrow\\ f_0:0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\\ f_1:0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\\ f_2: 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\\ f_3: 0\ 0\ 0\ 0\ 0\ 0\ 1\ 1\\ \cdots\\ f_{255}:1\ 1\ 1\ 1\ 1\ 1\ 1\ 1$$

For example,

$$f_\lor=0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\\ f_\land=0\ 0\ 0\ 0\ 0\ 0\ 0\ 1$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Even though it is frequently easy to use a formula in order to represent a Boolean function, Boolean functions are defined by their truth tables. Further, if two Boolean functions differ in at least one row of their corresponding truth tables, then we are really talking about different functions (as the functions return a different value at that point), so your problem really asks how many Boolean functions can be defined in $n$ boolean variables.

Now, pick an arbitrary Boolean function with $n$ boolean attributes; that is $f(x_1, x_2, \ldots, x_n)$. The number of rows of its corresponding truth table is $2^n$ (there are $2^n$ different truth assignments as inputs). However, in every such row (think truth assignment) you can fill in a $0$ or a $1$ which is the actual value of the function at that point. In other words we have two choices per row. Thus, by a counting argument we have $$ \underbrace{2\cdot2\cdot\ldots\cdot2}_{2^n \ \mbox{times}} = 2^{2^n} $$ different Boolean functions that can be defined on $n$ boolean variables.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.