

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

In this problem we describe the boolean functions of $n$ variables like a vectors with lenght $2^n$ with standard assumption that $k$-th component of the vector $0\leq k \leq 2^n -1$ is thе value of the function on this boolean assessment, which is the record of k in binary positional system.

The problem :

Let $f=(0, 1, 0, 1, 0, 0, 0, 1), g=(0, 1, 1, 1)$ and $h=(0, 0, 0, 1)$.

Write the composition of :

1.$$f(g(u, v), y, z)$$ 2.$$ g(h(u, z), z)$$ 3.$$f(g(u, v), g(u, v), g(h(u, z), h(u, z)) )$$

Can you help me with the first one...than I will try to do the other two myself. Thanks.

share|cite|improve this question
up vote 2 down vote accepted

$f(g(u,v),y,z)$: Treat the input to this composition as a $4$-tuple $\langle u,v,y,z\rangle$. Let’s look at a few sample inputs. The $0$-th input is $u=v=y=z=0$, and for that input we get


The $5$-th input is $u=y=0,v=z=1$, and for that input we get


More generally, we can make a table:

$$\begin{array}{c|c|c} u&v&g(u,v)&y&z&f(g(u,v),y,z)\\ \hline 0&0&0&0&0&0\\ 0&0&0&0&1&1\\ 0&0&0&1&0&0\\ 0&0&0&1&1&1\\ \hline 0&1&1&0&0&0\\ 0&1&1&0&1&0\\ 0&1&1&1&0&0\\ 0&1&1&1&1&1\\ \hline 1&0&1&0&0&0\\ 1&0&1&0&1&0\\ 1&0&1&1&0&0\\ 1&0&1&1&1&1\\ \hline 1&1&1&0&0&0\\ 1&1&1&0&1&0\\ 1&1&1&1&0&0\\ 1&1&1&1&1&1 \end{array}$$

The composition is therefore described by the $2^4$-place vector

$$\langle 0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1\rangle\;.$$

share|cite|improve this answer
A very big thank you! – DiscreteMath'sFan Jan 17 '13 at 20:05
@DiscreteMath'sFan: You’re very welcome! – Brian M. Scott Jan 17 '13 at 20:07

Your Answer


