The Gateway to Computer Science Excellence
+3 votes
204 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 by Veteran (431k points)
edited by | 204 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.

by Boss (24k points)
edited by
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
50,737 questions
57,312 answers
198,343 comments
105,038 users