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. The rows of a truth-table are ordered lexicographically: \[00… 0, 00… 1, \dotsc, 11… 1.\] For every row, evaluate the circuit on this assignment.

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.
This problem can only be submitted at Cogniterra.
Public samples
Public sample 1
Input
2 2 2
0 1 0110
0 1 0001
2 3
Example output
0110
0001
Public sample 2
Input
3 0 3
0 1 2
Example output
00001111
00110011
01010101
Public sample 3
Input
3 2 2
0 1 0110
3 2 0001
3 4
Example output
00111100
00010100