0

Either exhibit 333 different boolean functions on the three variables p; q; r, or prove that there aren’t 333 different such functions

$p$ $q$ $r$

$0 0 0$

$001$

$010$

$011$

$100$

$101$

$110$

$111$

$f(0,0,0)$ :

$2^8= 256$

$333 not equalto 256$

Can I ask for a feed back on my answer please? thanks

Kit lai
  • 49

3 Answers3

1

There are $2^{3}$ possible inputs in $B^{3}$, where $B = \{0, 1\}$. Each input can map to an element in $\{0, 1\}$. So there are $2^{8}$ possible boolean functions, as there are $2^{2^{3}}$ possible functions.

ml0105
  • 14,674
  • sorry , Im still in doubt with your solution,can you be more detailed/specific? thanks – Kit lai Mar 17 '14 at 22:48
  • @Kitlai Yes he can. – Shahar Mar 17 '14 at 22:51
  • So for f(p, q, r), p can take on 2 values- true or false. The same can be said of q and r, respectively. Since they are independent, by rule of product, we multiply the quantities: $2 * 2 * 2 = 8$ possible input vectors. Each of these 3-tuples map to a single boolean value, which can take on one of two values. So we have $2^{3}$ possible inputs, each of which can map to one of two values. Again, by rule of product, we get $2^{4}$ possible functions. – ml0105 Mar 17 '14 at 22:57
  • Ohhh so its not actually $2^8$ but $2^3 (variables)$ if thats what you mean? – Kit lai Mar 17 '14 at 23:00
  • No. You have three variables. Each variable is independent of the others and can take on two possible values. In your first post, you wrote out all of the possible input vectors. Clearly, you can see that there are $8$ distinct inputs. – ml0105 Mar 17 '14 at 23:04
  • each variable represents 3 inputs , so what i had calculated was just the values that can be input into the function ($2^8$), but what was missing was the answer towards my question which was the boolean functions? which is $2^4$. – Kit lai Mar 17 '14 at 23:08
  • Yes,rechecked my answer $2^8$ , I finally got what you meant , Thank you so much – Kit lai Mar 17 '14 at 23:13
  • Glad I could help! – ml0105 Mar 17 '14 at 23:14
0

Of course there are 256 of them; your original reasoning is correct. Notice that there are $2 = 2^{2^0}$ functions of 0 variables ($ \equiv 0$ and $\equiv 1$). There are $4 = 2^{2^1}$ functions of 1 variable ($ \equiv 0$, $x$, $ \lnot x$ and $\equiv 1$), $16 = 2^{2^2}$ functions of 2 variables (shall I list them?)...

This gives an inductive base to assume that there are $S_n = 2^{2^n}$ functions of $n$ variables. Since a function of $n+1$ variable is a pair of functions of $n$ variables (one with $x_{n+1} = 0$ and another with $x_{n+1} = 1$ we may conclude that $S_{n+1} = S_n ^2$, which completes the induction.

user58697
  • 2,761
  • Sorry I couldnt get what you mean, im a pretty slow learner, can you please explain more detailed? – Kit lai Mar 19 '14 at 09:06
0

what he's saying is that there are only 256 Boolean functions for the variables p,q,r such that for every variable there is only 2 constants, 0 and 1, which is 2^3, and lets just say for function g:(p,q,r) can only ever return only 0 and 1, therefore g:(p,q,r) is 2:2^3 which is 2^8 = 256!

user131747
  • 1