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 are indicative measurements on ordinary hardware, for a typical QCA design: 40 observed cases, about a third of the observed rows sufficient, and every remaining 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	24	~0.004 s
7	128	88	~0.05 s
8	256	216	~0.6 s
9	512	472	~6 s
10	1 024	984	~36 s

Roughly an order of magnitude per additional condition. Conservative solutions are considerably cheaper 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 for the chart solver and degrade sooner. This is the regime benchmarks/benchmark_qmc.py measures:

python benchmarks/benchmark_qmc.py --max-width 9 --density 0.3

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.

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.

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."""
    if on_set & dont_cares:
        raise ValueError("on_set and dont_cares must be disjoint.")
    universe = on_set | dont_cares
    if not universe:
        return ()

    current = {minterm_to_implicant(value, width) for value in universe}
    primes: set[Implicant] = set()

    while current:
        grouped: dict[int, list[Implicant]] = defaultdict(list)
        for implicant in current:
            grouped[sum(bit == 1 for bit in implicant.pattern)].append(implicant)

        used: set[Implicant] = set()
        next_round: dict[tuple[int | None, ...], Implicant] = {}
        for ones in sorted(grouped):
            for left in grouped[ones]:
                for right in grouped.get(ones + 1, []):
                    combined = left.combine(right)
                    if combined is None:
                        continue
                    used.add(left)
                    used.add(right)
                    previous = next_round.get(combined.pattern)
                    if previous is None:
                        next_round[combined.pattern] = combined
                    else:
                        next_round[combined.pattern] = Implicant(
                            combined.pattern, previous.origins | combined.origins
                        )

        primes.update(item for item in current if item not in used)
        current = set(next_round.values())

    # A prime built only from don't-cares cannot cover any required minterm.
    useful = [item for item in primes if any(item.covers(m) for m in on_set)]
    return tuple(
        sorted(
            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,
) -> tuple[BooleanSolution, ...]

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

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,
) -> tuple[BooleanSolution, ...]:
    """Return all exact minimum Boolean covers for the specified truth table."""
    dc = set() if dont_cares is None else set(dont_cares)
    primes = prime_implicants(set(on_set), dc, width)
    return exact_minimum_covers(primes, set(on_set), 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}))