# The NAND primitive is minimal

KL-FCS-023 · Circuit minimization · version 1.0.0

## Problem

Minimize the gate count for the declared two-input truth-table signature.

## Context

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.

## Checked result

Minimum gates: 1.

A single NAND gate supplies the target. Neither available input wire has the same signature, so no zero-gate implementation exists.

## Checker reasoning

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.

## Dataset construction

{
  "family": "circuits",
  "task": "Minimize the gate count for the declared two-input truth-table signature.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Complete truth table + zero-gate lower bound",
  "acceptance": [
    "Evaluate the witness circuit in topological signal order.",
    "Compare its complete truth table with the target function.",
    "Enumerate all smaller acyclic circuits, identifying symmetric NAND inputs.",
    "Reject minimality if any smaller circuit implements the target."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "truth_table": 7,
    "row_order": "00, 01, 10, 11; row i is bit i",
    "gate_basis": "two-input NAND; repeated inputs allowed; no constants"
  },
  "claim": {
    "minimum_gates": 1
  },
  "witness": {
    "gates": [
      [
        0,
        1
      ]
    ]
  }
}
```

## Complexity

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

## Limits

The lower bound applies only to the specified two-input NAND basis.

## Common error and further work

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

Add independently checked lower bounds and additional gate libraries.

## Verification

Complete truth table + zero-gate lower bound. 1 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11.
No external dataset or model-generation experiment. Reuse-license selection
remains pending.

- [Conceptual reference](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)