One output for input of $n$-tuples using AND, OR, NOT

40 Views Asked by At

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT.

Help $\rightarrow$ Define a function using all the operations AND, OR, NOT. Which gives only one output for an input of $n$-tuples?

Edit 1: Am a beginner to discrete math. I know I need a function that will take up all strings and give one output to set $B$. I don't understand the hint provided regarding $n$-tuples.

2

There are 2 best solutions below

2
On BEST ANSWER

I could not post above so I am writing here:

The total no. of such functions is $2^{2^n}$ because all functions can be expressed. Say you have an arbitrary $g: B_n \rightarrow \{0, 1\}$. List all strings in $B_n$ on which $g$ takes the value $1$. Then $g$ is simply the disjunction of all characteristic functions of these strings as explained above.

1
On

The wording of your hint doesn't make much sense. The closest thing to it seems to be the following: For any sequence $t_1, t_2, \dots, t_n$ in $\{0, 1\}$, try writing a boolean function $f(x_1, x_2, \dots, x_n)$ using and, or, not such that $f(x_1, x_2, \dots, x_n) = 1$ iff $x_1 = t_1, x_2 = t_2, \dots, x_n = t_n$.