Boolean minimisation

The minimiser reduces the set of sufficient truth-table rows to the smallest equivalent Boolean expression. setqca solves this exactly: the result is a proven minimum, not a good-enough approximation.

The public engine

The engine is public so it can be tested and reused independently of the QCA layer.

from setqca.minimize import minimize

# AB~C + ABC -> AB
solutions = minimize({6, 7}, width=3)
print(solutions[0].as_expression(("A", "B", "C")))
# A*B

Logical remainders are supplied as explicit don't-cares:

solutions = minimize({6, 7}, dont_cares={4, 5}, width=3)
print(solutions[0].as_expression(("A", "B", "C")))
# A

The algorithm

1. Cube generation. Each minterm in the on-set and don't-care set becomes a fully specified cube.
2. Iterative combination. Cubes differing in exactly one fixed literal merge, replacing that literal with a don't-care. Cubes that never merge are prime.
3. Pruning. Primes built only from don't-cares are discarded: they cannot cover any row that actually needs covering.
4. Chart solving. The prime-implicant chart is solved by branch and bound, always branching on the hardest uncovered minterm first.
5. Lexicographic optimisation. Covers are ranked first by number of prime implicants, then by total literal count.

Steps 1–3 are classical Quine-McCluskey. Step 4 is what makes the result exact: the greedy "pick the largest prime" heuristic used by many implementations can miss the true minimum.

Model ambiguity

A minimisation problem often has several distinct covers of identical minimal cost. This is model ambiguity, and it is a property of the data, not a defect.

minimize returns all tied minimal covers, up to max_solutions:

solutions = minimize(on_set, dont_cares=remainders, width=4, max_solutions=256)
for solution in solutions:
    print(solution.as_expression(conditions))

Reporting only the first solution when several exist misrepresents the evidence. QCAResult.summary_frame() returns one row per solution precisely so ambiguity stays visible.

Complexity

Exact minimisation is worst-case exponential in the number of conditions, and no implementation escapes that. What matters in practice is not the number of conditions alone but the shape of the chart: how many prime implicants there are, and how much they overlap.

The figures below come from benchmarks/profile_phases.py on ordinary hardware, for a typical QCA design: 40 observed cases, an outcome that genuinely depends on the conditions, and every unobserved row treated as a logical remainder — that is, the parsimonious solution, which is the more expensive of the two standard families because it hands the solver a large don't-care set.

Conditions	Truth-table rows	Remainders	Parsimonious solution
6	64	36	0.004 s
7	128	95	0.009 s
8	256	218	0.034 s
9	512	473	0.113 s
10	1 024	984	0.448 s

Roughly a trebling per additional condition in this regime, where the cost is carried by prime generation and chart construction rather than by the exponential search. Conservative solutions are cheaper still at the same width, since they use no don't-cares.

Dense tables — where a large fraction of all minterms is sufficient — are the worst case, because they are the regime where the exact search itself dominates. At seven conditions, timing the cover phase alone:

Sufficient share	Positives	Primes	Cover solving
0.10	11	10	<0.0001 s
0.25	33	26	0.0001 s
0.50	65	53	0.0024 s
0.75	91	78	0.60 s

Do not extrapolate from either table to your own data; the chart shape matters more than the width. If a run does not finish, the practical levers are reducing the number of conditions — which is good QCA practice anyway — or lowering max_solutions when the model is highly ambiguous.

This cost is the price of exactness. A faster minimiser (CCubes/eQMC-style) is a roadmap item, but it will be added as an alternative engine rather than by weakening the guarantee of the current one.

Being told before it gets slow

Exact minimisation is worst-case exponential, and that cost is not negotiable here: no heuristic is substituted when a problem gets hard, because a silently approximate answer is worse than a slow one. What is negotiable is finding out in advance.

Once the primes are generated — which is fast — the chart's shape is known, and minimize warns before entering the exponential phase:

>>> minimize(large_on_set, width=12)
MinimizationComplexityWarning: Exact minimisation of 400 configurations over 12
conditions produced 180 prime implicants (72000 chart cells). Solving the chart
exactly is worst-case exponential and may take a long time. The result will
still be exact. To reduce the cost, use fewer conditions, tighten the
consistency cutoff so fewer configurations qualify, or lower max_solutions if
the model is highly ambiguous.

The run still completes, and still returns an exact answer. Silence it with warnings.simplefilter, or switch the check off with complexity_guard=False.

The trigger is the number of prime implicants, not the number of conditions: the density table above is the evidence, and the threshold sits either side of the climb between 53 and 78 primes. That climb is driven by how much the primes overlap, which is why this is a warning rather than a prediction — a chart with many primes and little overlap solves instantly.

Where the time goes

benchmarks/profile_phases.py times each phase separately across four dimensions — cases, conditions, sufficient configurations and remainders:

python benchmarks/profile_phases.py
python benchmarks/profile_phases.py --max-width 9 --markdown

Two different phases dominate in two different regimes:

• Remainder-heavy problems — the parsimonious case, where most of the property space is unobserved — are dominated by prime generation.
• Dense on-sets are dominated by solving the chart.

Truth-table construction barely moves with the number of cases — 25× the cases costs under 2× the time, because the work is proportional to the property space, not to the sample. Adding cases is cheap; adding conditions is not.

Measure before optimising

Prime generation was originally the bottleneck at eight conditions, taking 1.4 s. Rewriting it over integer masks rather than tuples of optional bits brought that to 0.010 s — the same algorithm, a different representation. The exactness and R-parity tests passed unchanged, which is what made the rewrite safe to keep.

How the search stays tractable

Three reductions cut the search space without ever changing the answer:

1. Essential prime implicants. If a minterm is covered by exactly one prime, every possible cover must contain that prime. Essentials are selected up front instead of being rediscovered on every branch.
2. An independent-set lower bound. If several uncovered minterms have pairwise disjoint sets of candidate primes, each needs its own further prime. That count bounds the cost of any completion from below, so branches that cannot possibly reach the incumbent cost are abandoned early.
3. State memoisation. The covers reachable from a partial solution depend only on which minterms remain uncovered. Reaching the same remaining set at a strictly worse cost can therefore never produce a better or tied result.

Each is a standard result about prime-implicant charts, and each preserves both minimality and the completeness of the returned tie set.

Inspecting the chart

minimize reports its answer. minimize_chart reports its reasoning:

from setqca import minimize_chart

result = minimize_chart(on_set, dont_cares=remainders, width=3)
print(result.summary(("A", "B", "C")))

Configurations to cover: 6
Prime implicants: 6
Essential primes: 0
Dominated primes: 0
Minimum cost: 3 implicants, 6 literals
Minimum covers: 2
  ~A*~B + ~A*C + A*B
  ~A*~C + B*C + A*~B

Three questions the chart answers that a bare solution cannot:

Why is this term in the solution?

print(result.covers[0].explain(("A", "B", "C")))

Each term is labelled either essential — the only prime covering some configuration, so every possible solution contains it — or selected among interchangeable alternatives.

How could this configuration have been covered?

result.chart.explain(6, ("A", "B", "C"))
# 'Row 6 can be covered by any of: A*B, B*C.'

Why did a plausible-looking term never appear?

result.chart.dominated lists primes that another prime covers entirely at no greater literal cost. They cannot appear in any minimum cover, which is usually the answer to "why isn't A*B in my solution?".

The chart also exports as a table, one row per configuration and one column per prime:

result.chart.to_frame()

The chart changes nothing

minimize_chart returns exactly the covers minimize returns — a parametrised test asserts the two agree. The extra structure is explanation, not a different algorithm.

result.truncated reports whether max_solutions cut the list of tied covers short, so a capped result is never mistaken for an unambiguous one.

Fitting solutions back to cases

A Boolean cover is a statement about truth-table rows. To evaluate it against the original fuzzy cases, each implicant is re-evaluated as a conjunction under the minimum t-norm and the cover as their disjunction under the maximum s-norm. That is what produces the consistency, coverage and PRI reported for each solution, and the per-term fits in FittedSolution.term_fits.

setqca.minimize.qmc

Exact classical Quine-McCluskey minimisation.

BooleanSolution dataclass

BooleanSolution(implicants: tuple[Implicant, ...])

Exact minimal Boolean cover expressed as a set of prime implicants.

literal_count property

literal_count: int

Return the total number of literals across all implicants.

as_expression

as_expression(conditions: tuple[str, ...]) -> str

Render the cover in standard QCA notation, e.g. A*~B + C.

Source code in src/setqca/minimize/qmc.py

def as_expression(self, conditions: tuple[str, ...]) -> str:
    """Render the cover in standard QCA notation, e.g. ``A*~B + C``."""
    return " + ".join(item.as_expression(conditions) for item in self.implicants)

prime_implicants

prime_implicants(
    on_set: set[int], dont_cares: set[int], width: int
) -> tuple[Implicant, ...]

Generate all prime implicants exactly using classical QMC.

Internally a cube is a pair of integers — a mask of the fixed positions and the values at those positions — rather than a tuple of optional bits. Benchmarking showed this phase dominating on remainder-heavy problems, which is exactly the parsimonious case, and integer masks make combining a few machine operations instead of a tuple walk. The algorithm is unchanged; only the representation is.

Parameters:

Name	Type	Description	Default
on_set	set of int	Minterms that must be covered.	required
dont_cares	set of int	Minterms usable but not required.	required
width	int	Number of conditions.	required

Returns:

Type	Description
tuple of Implicant	Primes covering at least one required minterm, ordered by literal count then bit pattern.

Raises:

Type	Description
ValueError	If the two sets overlap.

Source code in src/setqca/minimize/qmc.py

def prime_implicants(on_set: set[int], dont_cares: set[int], width: int) -> tuple[Implicant, ...]:
    """Generate all prime implicants exactly using classical QMC.

    Internally a cube is a pair of integers — a mask of the fixed positions and
    the values at those positions — rather than a tuple of optional bits.
    Benchmarking showed this phase dominating on remainder-heavy problems,
    which is exactly the parsimonious case, and integer masks make combining
    a few machine operations instead of a tuple walk. The algorithm is
    unchanged; only the representation is.

    Parameters
    ----------
    on_set : set of int
        Minterms that must be covered.
    dont_cares : set of int
        Minterms usable but not required.
    width : int
        Number of conditions.

    Returns
    -------
    tuple of Implicant
        Primes covering at least one required minterm, ordered by literal
        count then bit pattern.

    Raises
    ------
    ValueError
        If the two sets overlap.
    """
    if on_set & dont_cares:
        raise ValueError("on_set and dont_cares must be disjoint.")
    universe = on_set | dont_cares
    if not universe:
        return ()

    full_mask = (1 << width) - 1
    # A cube is (mask, value): `mask` marks the fixed positions, `value` holds
    # the bits there. A minterm m is covered when `m & mask == value`.
    current: set[tuple[int, int]] = {(full_mask, minterm) for minterm in universe}
    primes: set[tuple[int, int]] = set()

    while current:
        grouped: dict[tuple[int, int], list[int]] = defaultdict(list)
        for mask, value in current:
            grouped[(mask, value.bit_count())].append(value)

        used: set[tuple[int, int]] = set()
        next_round: set[tuple[int, int]] = set()
        for (mask, ones), values in grouped.items():
            neighbours = grouped.get((mask, ones + 1))
            if not neighbours:
                continue
            for left in values:
                for right in neighbours:
                    difference = left ^ right
                    # Exactly one differing fixed position, and both cubes fix
                    # it, is the classical combination rule.
                    if difference & (difference - 1) or not difference & mask:
                        continue
                    used.add((mask, left))
                    used.add((mask, right))
                    reduced = mask & ~difference
                    next_round.add((reduced, left & reduced))

        primes.update(cube for cube in current if cube not in used)
        current = next_round

    def covers(cube: tuple[int, int], minterm: int) -> bool:
        mask, value = cube
        return minterm & mask == value

    # A prime built only from don't-cares cannot cover any required minterm.
    useful = [cube for cube in primes if any(covers(cube, m) for m in on_set)]
    return tuple(
        sorted(
            (_to_implicant(cube, width, on_set | dont_cares) for cube in useful),
            key=lambda item: (
                item.literals,
                tuple(2 if bit is None else bit for bit in item.pattern),
            ),
        )
    )

exact_minimum_covers

exact_minimum_covers(
    primes: tuple[Implicant, ...],
    on_set: set[int],
    *,
    max_solutions: int = 256,
) -> tuple[BooleanSolution, ...]

Solve the prime-implicant chart exactly by branch-and-bound.

Optimisation is lexicographic: first minimise the number of implicants, then the total number of literals. All tied minimal covers are returned up to max_solutions.

Three exactness-preserving reductions keep the search tractable:

1. Essential primes. A minterm covered by exactly one prime forces that prime into every cover, so essentials are selected up front rather than rediscovered on every branch.
2. Independent-set lower bound. Uncovered minterms whose candidate primes are pairwise disjoint each require a distinct further prime, which bounds the cost of any completion from below.
3. State memoisation. Reaching the same set of uncovered minterms at a strictly worse cost can never yield a better or tied cover, because the completions available from a state depend only on that state.

Parameters:

Name	Type	Description	Default
primes	tuple of Implicant	Candidate prime implicants, as produced by :func:prime_implicants.	required
on_set	set of int	Minterms that must be covered.	required
max_solutions	int	Upper bound on the number of tied minimal covers returned.	256

Returns:

Type	Description
tuple of BooleanSolution	Every returned cover has identical, provably minimal cost.

Raises:

Type	Description
RuntimeError	If some minterm of on_set is covered by no supplied prime.

Source code in src/setqca/minimize/qmc.py

def exact_minimum_covers(
    primes: tuple[Implicant, ...],
    on_set: set[int],
    *,
    max_solutions: int = 256,
) -> tuple[BooleanSolution, ...]:
    """Solve the prime-implicant chart exactly by branch-and-bound.

    Optimisation is lexicographic: first minimise the number of implicants,
    then the total number of literals. All tied minimal covers are returned up
    to ``max_solutions``.

    Three exactness-preserving reductions keep the search tractable:

    1. **Essential primes.** A minterm covered by exactly one prime forces that
       prime into every cover, so essentials are selected up front rather than
       rediscovered on every branch.
    2. **Independent-set lower bound.** Uncovered minterms whose candidate
       primes are pairwise disjoint each require a distinct further prime, which
       bounds the cost of any completion from below.
    3. **State memoisation.** Reaching the same set of uncovered minterms at a
       strictly worse cost can never yield a better or tied cover, because the
       completions available from a state depend only on that state.

    Parameters
    ----------
    primes : tuple of Implicant
        Candidate prime implicants, as produced by :func:`prime_implicants`.
    on_set : set of int
        Minterms that must be covered.
    max_solutions : int, default 256
        Upper bound on the number of tied minimal covers returned.

    Returns
    -------
    tuple of BooleanSolution
        Every returned cover has identical, provably minimal cost.

    Raises
    ------
    RuntimeError
        If some minterm of ``on_set`` is covered by no supplied prime.
    """
    if not on_set:
        return (BooleanSolution(()),)
    covered = [frozenset(m for m in on_set if prime.covers(m)) for prime in primes]
    literals = [prime.literals for prime in primes]
    choices = solve_minimum_cover(covered, literals, on_set, max_solutions=max_solutions)
    return tuple(BooleanSolution(tuple(primes[i] for i in indices)) for indices in choices)

solve_minimum_cover

solve_minimum_cover(
    covered: Sequence[frozenset[int]],
    literals: Sequence[int],
    on_set: set[int],
    *,
    max_solutions: int = 256,
) -> tuple[tuple[int, ...], ...]

Solve a covering problem exactly, independently of what is being covered.

The exactness guarantee lives here, so every minimiser in the package — binary and multi-value alike — shares one verified implementation rather than repeating the search.

Parameters:

Name	Type	Description	Default
covered	sequence of frozenset of int	For each candidate, the elements of on_set it covers.	required
literals	sequence of int	Cost of each candidate, used as the secondary objective.	required
on_set	set of int	Elements that must be covered.	required
max_solutions	int	Upper bound on the number of tied minimum covers returned.	256

Returns:

Type	Description
tuple of tuple of int	Candidate indices, one tuple per tied minimum cover.

Raises:

Type	Description
RuntimeError	If some element is covered by no candidate.

Source code in src/setqca/minimize/qmc.py

def solve_minimum_cover(
    covered: Sequence[frozenset[int]],
    literals: Sequence[int],
    on_set: set[int],
    *,
    max_solutions: int = 256,
) -> tuple[tuple[int, ...], ...]:
    """Solve a covering problem exactly, independently of what is being covered.

    The exactness guarantee lives here, so every minimiser in the package —
    binary and multi-value alike — shares one verified implementation rather
    than repeating the search.

    Parameters
    ----------
    covered : sequence of frozenset of int
        For each candidate, the elements of ``on_set`` it covers.
    literals : sequence of int
        Cost of each candidate, used as the secondary objective.
    on_set : set of int
        Elements that must be covered.
    max_solutions : int, default 256
        Upper bound on the number of tied minimum covers returned.

    Returns
    -------
    tuple of tuple of int
        Candidate indices, one tuple per tied minimum cover.

    Raises
    ------
    RuntimeError
        If some element is covered by no candidate.
    """
    cover_map = {m: tuple(i for i, reach in enumerate(covered) if m in reach) for m in on_set}
    if any(not options for options in cover_map.values()):
        raise RuntimeError("Prime-implicant chart cannot cover every positive row.")

    # A minterm with a single candidate forces that candidate into every cover.
    essential = frozenset(options[0] for options in cover_map.values() if len(options) == 1)
    start_uncovered = (
        frozenset(on_set).difference(*(covered[i] for i in essential))
        if essential
        else frozenset(on_set)
    )

    def lower_bound(uncovered: frozenset[int]) -> int:
        """Return a lower bound on the number of further candidates required."""
        blocked: set[int] = set()
        bound = 0
        for minterm in sorted(uncovered, key=lambda m: len(cover_map[m])):
            options = cover_map[minterm]
            if blocked.isdisjoint(options):
                bound += 1
                blocked.update(options)
        return bound

    best_cost: tuple[int, int] | None = None
    best: set[tuple[int, ...]] = set()
    seen: dict[frozenset[int], tuple[int, int]] = {}

    def search(chosen: frozenset[int], uncovered: frozenset[int]) -> None:
        nonlocal best_cost
        current_cost = (len(chosen), sum(literals[i] for i in chosen))
        if not uncovered:
            if best_cost is None or current_cost < best_cost:
                best_cost = current_cost
                best.clear()
            if current_cost == best_cost and len(best) < max_solutions:
                best.add(tuple(sorted(chosen)))
            return
        if best_cost is not None:
            if current_cost >= best_cost:
                return
            # Any completion needs at least `lower_bound` further candidates,
            # and candidates never reduce the cost.
            if (current_cost[0] + lower_bound(uncovered), current_cost[1]) > best_cost:
                return
        previous = seen.get(uncovered)
        if previous is not None and current_cost > previous:
            return
        if previous is None or current_cost < previous:
            seen[uncovered] = current_cost

        # Branch on the element with the fewest candidates: every cover must
        # contain one of them, so this is a complete and narrow branching rule.
        target = min(uncovered, key=lambda m: len(cover_map[m]))
        ordered = sorted(
            cover_map[target],
            key=lambda i: (-len(covered[i] & uncovered), literals[i], i),
        )
        for index in ordered:
            search(chosen | {index}, uncovered - covered[index])

    search(essential, start_uncovered)
    return tuple(sorted(best))

minimize

minimize(
    on_set: set[int],
    *,
    dont_cares: set[int] | None = None,
    width: int,
    max_solutions: int = 256,
    complexity_guard: bool = True,
) -> tuple[BooleanSolution, ...]

Return all exact minimum Boolean covers for the specified truth table.

Parameters:

Name	Type	Description	Default
on_set	set of int	Minterms that must be covered.	required
dont_cares	set of int	Logical remainders, usable but not required.	None
width	int	Number of conditions.	required
max_solutions	int	Upper bound on the number of tied minimum covers returned.	256
complexity_guard	bool	Warn with :class:~setqca.minimize.MinimizationComplexityWarning when the chart looks likely to be slow. The result is exact either way; the warning arrives before the expensive phase rather than after it.	True

Returns:

Type	Description
tuple of BooleanSolution	Every cover of provably minimal cost.

Source code in src/setqca/minimize/qmc.py

def minimize(
    on_set: set[int],
    *,
    dont_cares: set[int] | None = None,
    width: int,
    max_solutions: int = 256,
    complexity_guard: bool = True,
) -> tuple[BooleanSolution, ...]:
    """Return all exact minimum Boolean covers for the specified truth table.

    Parameters
    ----------
    on_set : set of int
        Minterms that must be covered.
    dont_cares : set of int, optional
        Logical remainders, usable but not required.
    width : int
        Number of conditions.
    max_solutions : int, default 256
        Upper bound on the number of tied minimum covers returned.
    complexity_guard : bool, default True
        Warn with :class:`~setqca.minimize.MinimizationComplexityWarning` when
        the chart looks likely to be slow. The result is exact either way; the
        warning arrives before the expensive phase rather than after it.

    Returns
    -------
    tuple of BooleanSolution
        Every cover of provably minimal cost.
    """
    dc = set() if dont_cares is None else set(dont_cares)
    required = set(on_set)
    primes = prime_implicants(required, dc, width)
    if complexity_guard:
        warn_if_complex(
            estimate_complexity(
                width=width,
                required=len(required),
                dont_cares=len(dc),
                primes=len(primes),
            )
        )
    return exact_minimum_covers(primes, required, max_solutions=max_solutions)

setqca.minimize.implicant

Boolean implicant representation used by exact QMC minimisation.

Implicant dataclass

Implicant(
    pattern: tuple[Bit, ...], origins: frozenset[int]
)

A Boolean cube and the minterms from which it was derived.

literals property

literals: int

Number of non-minimised literals.

covers

covers(minterm: int) -> bool

Return whether this cube covers a binary minterm.

Source code in src/setqca/minimize/implicant.py

def covers(self, minterm: int) -> bool:
    """Return whether this cube covers a binary minterm."""
    width = len(self.pattern)
    bits = tuple((minterm >> shift) & 1 for shift in reversed(range(width)))
    return all(p is None or p == b for p, b in zip(self.pattern, bits, strict=True))

combine

combine(other: Implicant) -> Implicant | None

Combine cubes that differ in exactly one fixed literal.

Source code in src/setqca/minimize/implicant.py

def combine(self, other: Implicant) -> Implicant | None:
    """Combine cubes that differ in exactly one fixed literal."""
    if len(self.pattern) != len(other.pattern):
        return None
    differences: list[int] = []
    for idx, (left, right) in enumerate(zip(self.pattern, other.pattern, strict=True)):
        if left == right:
            continue
        if left is None or right is None:
            return None
        differences.append(idx)
    if len(differences) != 1:
        return None
    pattern = list(self.pattern)
    pattern[differences[0]] = None
    return Implicant(tuple(pattern), self.origins | other.origins)

as_expression

as_expression(conditions: tuple[str, ...]) -> str

Render using standard QCA notation, e.g. A*~B.

Source code in src/setqca/minimize/implicant.py

def as_expression(self, conditions: tuple[str, ...]) -> str:
    """Render using standard QCA notation, e.g. ``A*~B``."""
    if len(conditions) != len(self.pattern):
        raise ValueError("condition count does not match implicant width.")
    literals = [
        condition if bit == 1 else f"~{condition}"
        for condition, bit in zip(conditions, self.pattern, strict=True)
        if bit is not None
    ]
    return "1" if not literals else "*".join(literals)

minterm_to_implicant

minterm_to_implicant(minterm: int, width: int) -> Implicant

Create a fully specified implicant from a minterm integer.

Source code in src/setqca/minimize/implicant.py

def minterm_to_implicant(minterm: int, width: int) -> Implicant:
    """Create a fully specified implicant from a minterm integer."""
    if minterm < 0 or minterm >= 2**width:
        raise ValueError("minterm is outside the truth-table domain.")
    pattern = tuple((minterm >> shift) & 1 for shift in reversed(range(width)))
    return Implicant(pattern, frozenset({minterm}))