Lesson 5

Using the idea above implement a program for the following problem.

Programming problem. Construct a minimum-size circuit for a Boolean function of four variables. All sixteen fan-in-two operations are allowed.

Input format. The first line contains the number \(n\), which is equal to \(4\). The second line contains the \(16\)-bit target truth table in lexicographic order of input assignments.

Output format. First print the number of gates \(m\). Then print \(m\) gate lines, each containing predecessor indices \(a_{i},b_{i}\) and a four-bit operation string. Gate \(i\) has source index \(n+i\), so \(0\le a_{i},b_{i}<n+i\). Finally, print one source index for the output.

4
0110100110010110

3
0 1 0110
2 3 0110
4 5 0110
6