# Circuit minimization

A working circuit proves an upper bound. Minimality additionally requires ruling out every smaller circuit in the stated gate model.

## Definitions

- **Gate basis**: The allowed primitive Boolean operations; this family uses two-input NAND.
- **Truth-table signature**: The complete output function over the four input rows 00, 01, 10, 11.
- **Cost model**: Gate count, with acyclic wiring, reusable signals, and unrestricted fan-out.

## Acceptance procedure

1. Evaluate the witness circuit in topological signal order.
2. Compare its complete truth table with the target function.
3. Enumerate all smaller acyclic circuits, identifying symmetric NAND inputs.
4. Reject minimality if any smaller circuit implements the target.

## Complexity

The circuit search grows rapidly with gate count. This family keeps two inputs and at most four witness gates.

## Common failure

Gate-count minimality does not imply minimum delay, energy, area, or transistor count.

## Extensions

Add independently checked lower bounds and additional gate libraries.

## Instances

- KL-FCS-009: XOR with a minimum NAND count — Minimum gates: 4
- KL-FCS-022: Negation from a repeated NAND input — Minimum gates: 1
- KL-FCS-023: The NAND primitive is minimal — Minimum gates: 1

## References

- https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/