Project: Optimal Circuit Synthesis with SAT · Exact Circuit Synthesis

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Sources are numbered consecutively. For a circuit with \(n\) inputs, sources \(0,\dotsc,n-1\) are the inputs. Gate \(i\) has source number \(n+i\) and may use only sources smaller than \(n+i\).

Consider two inputs and the gates

Sources 2 and 3 are the sum and carry bits of a half-adder. The two gates share both inputs.

Problem. What is the minimum number of fan-in-two gates needed to compute both the sum and the carry of two bits?

5 points