search
Log In
3 votes
560 views

How many different Boolean functions of degree $n$ are the

  1. $2^{2^n}$
  2. $(2^2)^n$
  3. $2^{2^n} -1$
  4. $2^n$ 
in Set Theory & Algebra
edited by
560 views
0
Answer $1)$

If we do $2$ to $n$ mapping, n boolean element can make set of $2^{n}$ elements.

Now for mapping of $2$ to $2^{n}$, boolean function would be $2^{2^{n}}$

1 Answer

3 votes
$A$ $B$ $f_0$ $f_1$ $f_2$ $f_3$ $f_4$ $f_5$ $f_6$ $f_7$ $f_8$ $f_9$ $f_{10}$ $f_{11}$ $f_{12}$ $f_{13}$ $f_{14}$ $f_{15}$
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

As we can see from the above table ,

Using $n$ boolean variables (here $n=2$ $A,B$ are boolean variables),

We can create $2^n$ combinations ($00,01,10,11$)

and using those $2^n$ combinations we can create $2^{2^n}$ functions ($16$ functions = $f_0,f_1,....f_{15}$)

$\therefore$ Option $1.$ is correct.


edited by

Related questions

8 votes
3 answers
1
2.6k views
Consider the poset $( \{3,5,9,15,24,45 \}, \mid).$ Which of the following is correct for the given poset ? There exist a greatest element and a least element There exist a greatest element but not a least element There exist a least element but not a greatest element There does not exist a greatest element and a least element
asked Jul 2, 2019 in Set Theory & Algebra Arjun 2.6k views
1 vote
2 answers
2
1.8k views
Find the zero-one matrix of the transitive closure of the relation given by the matrix $A$ : $A =\begin{bmatrix} 1 & 0& 1\\ 0 & 1 & 0\\ 1& 1& 0 \end{bmatrix}$ $\begin{bmatrix} 1 & 1& 1\\ 0 & 1 & 0\\ 1& 1& 1 \end{bmatrix}$ ... $\begin{bmatrix} 1 & 1& 1\\ 0 & 1 & 0\\ 1& 0& 1 \end{bmatrix}$
asked Jul 2, 2019 in Set Theory & Algebra Arjun 1.8k views
2 votes
1 answer
3
544 views
Consider the following statements: $S_1$: For any integer $n>1, \: a^{\phi(n)} \equiv 1(mod \: n)$ for all $a \in Z_n^*$ , where $\phi(n)$ is Euler’s phi function. $S_2$: If $p$ is prime, then $a^p \equiv 1(mod \: p)$ for all $a \in Z_p^*$. Which one of the following is/are correct? Only $S_1$ Only $S_2$ Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$
asked Jul 2, 2019 in Set Theory & Algebra Arjun 544 views
2 votes
2 answers
4
2.1k views
How many ways are there to place $8$ indistinguishable balls into four distinguishable bins? $70$ $165$ $^8C_4$ $^8P_4$
asked Jul 2, 2019 in Combinatory Arjun 2.1k views
...