search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
28 votes
3.9k views

What is the maximum number of different Boolean functions involving $n$ Boolean variables?

  1. $n^2$
  2. $2^n$
  3. $2^{2^n}$
  4. $2^{n^2}$
in Set Theory & Algebra
retagged by
3.9k views
1
In terms of digital:

n-variables

# of minterms=$2^n$

# of boolean functions=$2^{2^{n}}$

4 Answers

41 votes
 
Best answer
answer - C

size of domain = number of different combinations of inputs  $=2^{n}.$

size of codomain $= 2 ( \{0,1\} ).$

number of functions $= \text{(size of co-domain)}^{\text{(size of domain)}}$

edited by
3
According to u  this is mapping btw domain (n ) to co-domain (2 ) i.e boolean is given so co domain have 2 elements right!!
21

We have n boolean variables

So, we will have total of 2n combination of truth table values

For each of these 2n values, to define a boolean function they may be 0 or 1.

So we have 2 choices each for each 2n combination of truth table values

Hence the total number of boolean functions possible with n variables is $2^{2^{n}}$

1
Nicely explained thnx
15 votes

With n boolean variables total number of rows in the truth table = 2^n

Each row of truth table can be taken or not taken (only 2 choices) .

So, maximum no of different boolean functions possible = 2^(2^n)

The correct answer is,(C) 2^(2^n).

1
Thanks for simplified explanation :)
13 votes
We know that a K-map is used to represent and simplify a boolean function. Given 'n' no. of boolean variables, number of cells in the K-map is 2^n. Now each cell has two options. Either 1(True) or 0(False) [in case of SOP]. Different combinations of cells each having value=1 will give generate different functions (which later can be simplified but that is not our concern here). So in that way total number of functions will be 2^(2^n).

edited by
1
6 votes

The number of m-ary functions in p-valued algebra having n-variables is given by $m^{p^{n}}$

Here, m = 2 (boolean functions), p = 2 (boolean variables) and n = n (number of variables)

So, total functions = $2^{2^{n}}$

 Alternative approach :

With n boolean variables, we can have ${2^{n}}$ combinations for functions. And now since each of these is designed to be a boolean function, it's output value can be either 1 or 0, i.e. 2 choices for each function. So total such functions = $2^{2^{n}}$

0
consider we have 2 boolean variable a and b.--> n variables

They can have 4 diff combinations ab,ab',a'b,a'b'.--> 2^n combinations possible

example of boolean function can be ab+ab' or a'b or ab+ab'+a'b' and so on.

Now to be part of a function each combination have 2 options.--->each of  2^n combinations have 2 options

Therefore total functions are 2*2*2*2.

I hope my approach is correct.
Answer:

Related questions

28 votes
4 answers
1
3.7k views
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$ ... $^{20}\mathrm{C}_{10} - ^{8}\mathrm{C}_{4}\times ^{11}\mathrm{C}_{5}$
asked Apr 23, 2016 in Combinatory jothee 3.7k views
33 votes
6 answers
2
5.7k views
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$. How many distinct paths are there for the robot to reach the point $(10,10)$ starting from the initial position $(0,0)$? $^{20}\mathrm{C}_{10}$ $2^{20}$ $2^{10}$ None of the above
asked Sep 22, 2014 in Combinatory Kathleen 5.7k views
33 votes
2 answers
3
6k views
Consider the set $S =\{ a , b , c , d\}.$ Consider the following $4$ partitions $π_1,π_2,π_3,π_4$ on $S : π_1 =\{\overline{abcd}\},\quad π_2 =\{\overline{ab}, \overline{cd}\},$ ... $S' = \{π_1,π_2,π_3,π_4\}$ defined as follows: $π_i \prec π_j$ if and only if $π_i$ refines $π_j$. The poset diagram for $(S',\prec)$ is:
asked Sep 22, 2014 in Set Theory & Algebra Kathleen 6k views
32 votes
5 answers
4
9.6k views
How many different non-isomorphic Abelian groups of order $4$ are there? $2$ $3$ $4$ $5$
asked Sep 22, 2014 in Set Theory & Algebra Kathleen 9.6k views
...