# Discrete Mathematics (boolean)

Either exhibit 333 diﬀerent boolean functions on the three variables p; q; r, or prove that there aren’t 333 diﬀerent 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$

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.

• 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

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.

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

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!

• so what I had calculated is wrong? $2^2^3$ = $2^8$ = $333$ – Kit lai Mar 23 '14 at 7:00
• $2^8=256\notequal333$ – Kit lai Mar 27 '14 at 22:30