Project: Optimal Circuit Synthesis with SAT · Exact Circuit Synthesis

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Before searching for circuits, we need a reliable evaluator. Truth-table rows are ordered lexicographically: \[00… 0, 00… 1, \dotsc, 11… 1.\] For every row, evaluate the gates in their listed order. The four-bit operation string can be indexed by the pair of predecessor values.

Programming problem. Compute the truth tables of all circuit outputs.

  • Input format.  The first line contains \(n\), \(m\), and \(r\) (\(1\le n\le 8\), \(0\le m\le 100\), \(1\le r\le 20\)): the numbers of inputs, gates, and outputs. Each of the next \(m\) lines contains two predecessor indices \(a_{i},b_{i}\) and a four-bit operation string. Gate \(i\) has index \(n+i\), and \(0\le a_{i},b_{i}<n+i\). The last line contains \(r\) source indices used as outputs.

  • Output format.  Print \(r\) lines. Line \(j\) must be the \(2^{n}\)-bit truth table of output \(j\), in lexicographic order of input assignments.

5 points
Public samples
Public sample 1
Input
2 2 2
0 1 0110
0 1 0001
2 3
Expected output
0110
0001
Public sample 2
Input
3 0 3
0 1 2
Expected output
00001111
00110011
01010101