in Set Theory & Algebra retagged by
9,342 views
56 votes
56 votes

Let ܵ$S$ denote the set of all functions $f:\{0,1\}^4 \to \{0,1\}$. Denote by $N$ the number of functions from S to the set $\{0,1\}$. The value of $ \log_2 \log_2N $ is _______.

in Set Theory & Algebra retagged by
by
2699 3558 3939
9.3k views

3 Comments

The beauty of the question hovers around the set $S$.
3
3

………………..

1
1
If anyone is wondering what {0,1}^4 means, it is actually the cartesian product {0,1}x{0,1}x{0,1}x{0,1}.={0000,0001…..}
2
2

Subscribe to GO Classes for GATE CSE 2022

5 Answers

85 votes
85 votes
 
Best answer
For a function from set $A$ to set $B$, we need to have a mapping for all elements of $A$ and mapping must be unique.
Let number of elements in $A$ be $m$ and that in $B$ be $n$

So, if we consider an element from $A,$ it can be mapped to any of the element from $B.$ i.e., it has $n$ possibilities when a function is formed. Similarly, for all other members also there are $n$ possibilities as one element from $A$ can be mapped to  only a single element in $B$ (though reverse need not true). So, for $m$ elements in $A,$ we totally have $\underbrace{n \times \dots \times n}_{m \text{ times}} = n^m$ possible functions.

In the question Number of elements (functions) in $f$ is $2^{2^4}$ as $\{0,1\}^4$ contains $2^4$ elements. So, number of functions from $S$ to $\{0,1\}$ will be $2^{2^{2^4}}$. So, $\log_2 \log_2 N = 2^4 = 16.$
edited by
by
2437 3623 5535

5 Comments

How this 2^2^4 came ?? Also what does {0,1}4   Denotes? Please explain

1
1

{0, 1}4 = {0000, 0001, 0010, .... , 1111} set of all 4 length strings over {0, 1}. So, 16 elements in it. 

51
51
what does {0,1}^4 mean?
0
0
4 places, each place can be filled with 0 or 1 , total possible combinations, 2 choices at each places, 2*2*2*2, 4-bit binary numbers,0000 to 1111.
19
19

Great explanation about boolean functions of n variables.

https://cs.fit.edu/~wds/classes/adm/Lectures/BooleanFunctions.pdf

1
1
64 votes
64 votes

Answer : 16

by
8 24 35

1 comment

good explanation :)
1
1
15 votes
15 votes

If anybody wondering why it is 2^2^16 and not just 2^16, here is explanation.

From above two answer number of functions are 2^16 .{f1 , f2 , f3 , f4, ...............f2^16}

And if you read question carefully they asking number of functions from S to the set {0,1}

and set S is .{f1 , f2 , f3 , f4, ...............f2^16} which has to mapped to set {0, 1}

Therefore answer is 2^2^16.

I have written this answer according to my understanding , please correct me if i am wrong

by
14 62 115
14 votes
14 votes

Number of functions in S is 2^16 so in N is (2^(2^16)), and value of  loglog n will be 16.

by
163 309 512
4 votes
4 votes
$f:\{{0,1}\}^4→\{0,1\} $

$\{0,1\}^4$ contains total $24$ elements  

so $16$ elements and S will be $[co-domain]^{domain}  = 216$

$\text{N is S to } \{0,1\} \text { so } 2^{216}$

$log_2log_2N  = 16$
edited by
by
11 61 134

1 comment

Great explanation about boolean functions of n variables.

https://cs.fit.edu/~wds/classes/adm/Lectures/BooleanFunctions.pdf

0
0
Answer:

Related questions

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