Skip to main content

Crate logicaffeine_proof

Crate logicaffeine_proof 

Source
Expand description

§logicaffeine-proof

Proof search for Logicaffeine: a backward-chaining prover over an owned IR (ProofExpr / ProofTerm), a tactic language, certified SAT/CDCL solvers that emit DRAT/LRAT refutations, and a number-theory and cryptanalysis substrate. Finding a proof is hard and checking one is easy, so this crate does the finding and something smaller does the checking: a derivation becomes a term logicaffeine_kernel type-checks, and an UNSAT verdict carries a refutation the RUP checker replays. The search itself is never trusted: a wrong one yields verified == false, never a false claim.

Part of the Logicaffeine workspace, tier 2. It depends on logicaffeine_base and logicaffeine_kernel and never on the language crate (the Liskov invariant), so any front-end can reuse it. The default build has no Z3 and no external crates, which keeps the SAT and model-checking stack browser-ready.

§Role in the workspace

This crate owns proof representation, search and certification; logicaffeine_language and logicaffeine_compile both use it without a dependency cycle. The LogicExpr → ProofExpr lowering lives in the language crate, not here, so the engine stays independent of any one front-end.

A proof is verified iff the chainer found a derivation, certifier::certify turned it into a kernel Term, and the kernel type-checked that term against the goal. This is Curry-Howard made concrete: each inference rule maps to a kernel term (ModusPonens is application), so the proof is a program and checking it is type checking. An externally built DerivationTree (e.g. from the grid solver) is re-checked the same way, so untrusted search sits outside the trusted base. Trust levels run fast → strong: untrusted CDCL/SMT (cnf::cdcl_entails, oracle), then RUP-certified (rup::entails_certified, sat::prove_unsat), then kernel-certified (verify). See proof-and-verification.md.

§Example

Socrates is a man and every man is mortal, so Socrates is mortal, and the kernel agrees:

use logicaffeine_kernel::infer_type;
use logicaffeine_proof::verify::prove_certify_check;
use logicaffeine_proof::{ProofExpr, ProofTerm};

let pred = |name: &str, arg: ProofTerm| ProofExpr::Predicate {
    name: name.to_string(),
    args: vec![arg],
    world: None,
};
let socrates = ProofTerm::Constant("Socrates".to_string());
let x = ProofTerm::Variable("x".to_string());

let man = pred("man", socrates.clone());
let every_man_is_mortal = ProofExpr::ForAll {
    variable: "x".to_string(),
    body: Box::new(ProofExpr::Implies(
        Box::new(pred("man", x.clone())),
        Box::new(pred("mortal", x)),
    )),
};
let result = prove_certify_check(&[man, every_man_is_mortal], &pred("mortal", socrates));

assert!(result.verified);
let term = result.proof_term.expect("a verified proof carries its term");
assert!(infer_type(&result.kernel_ctx, &term).is_ok());

§Public API

Re-exported at the crate root: BackwardChainer, PremiseVariables, ProofError, suggest_hint, SocraticHint, SuggestedTactic, Substitution; plus ProofTerm, ProofExpr, MatchArm, InferenceRule, DerivationTree, ProofGoal defined directly in lib.rs.

Search (engine::BackwardChainer):

let mut prover = BackwardChainer::new();
prover.set_max_depth(depth: usize);
prover.set_premise_variables(reading: PremiseVariables);  // Schematic (default) | Local
prover.add_axiom(expr: ProofExpr);
prover.knowledge_base() -> &[ProofExpr];
prover.prove(goal: ProofExpr) -> ProofResult<DerivationTree>;
prover.prove_with_goal(goal: ProofGoal) -> ProofResult<DerivationTree>;

PremiseVariables says how a knowledge-base equation’s free variables read: Schematic (a rewrite schema standing for all its instances, the default for a standalone chainer) or Local (a hypothesis about fixed values, so only the equation as stated is available). The verify entry points and the tactic layer run Local, so the search never builds an instance the certificate cannot cite.

Verification (verify):

verify::prove_certify_check(premises: &[ProofExpr], goal: &ProofExpr) -> VerifiedProof;
verify::prove_certify_check_bounded(premises, goal, max_depth: usize) -> VerifiedProof;
verify::prove_certify_check_with_defs(..) / prove_certify_check_bounded_with_defs(..);
verify::check_derivation(premises, goal, tree: DerivationTree) -> VerifiedProof;
verify::detect_conflict(premises: &[ProofExpr]) -> ConflictReport;
verify::ScopedChecker::new(premises, goal).certifies(tree: DerivationTree) -> bool;
verify::close_over_context_locals(ctx: &Context, term: &Term) -> Term;
verify::prove_library(theorems: &[LibraryTheorem]) -> Vec<LibraryResult>;
VerifiedProof::axiom_footprint(&self) -> AxiomFootprint;  // { trusted, introduced }

VerifiedProof { derivation, proof_term, kernel_ctx, verified, verification_error } carries the re-checkable kernel term; detect_conflict returns a kernel proof of False plus the indices of the clashing premises. A theorem’s free variables become kernel locals typed by use (Int in arithmetic, the inductive a premise’s unary predicate names, otherwise Entity), and the finished term is closed over them. The _with_defs variants register Definitions as δ-unfoldable kernel definitions after every atom their bodies mention. ScopedChecker prepares a scope once and certifies many candidate derivations against it. axiom_footprint is #print axioms for the certified term, read transitively through definitions: trusted holds the prelude declarations the proof cites (checked against a freshly registered StandardLibrary), introduced everything else: premises, symbols, and any smuggled sorryAx.

IR: ProofTerm (Constant, Variable, Function, Group, BoundVarRef) and ProofExpr cover full FOL plus extensions: connectives, quantifiers, Modal / Counterfactual / Temporal / TemporalBinary, Lambda / App, Neo-Davidsonian NeoEvent, inductive Ctor / Match / Fixpoint / TypedVar, and unification Holes. InferenceRule names the move at each step: ModusPonens / ModusTollens, ∧/∨ intro and elim, ∀/∃ intro and elim (ExistentialIntroTerm carries a ProofTerm witness), ModalAccess, StructuralInduction, Leibniz Rewrite and positional RewriteAt { from, to, occurrence }, the order rules (LeTrans, LeRefl, LeTotal, LtSuccLe, …), ArithDecision, GroundRefutation (¬P for a closed P that computes false), ReductioAdAbsurdum, CaseAnalysis, DisjunctionCases, and more. Rule introspection: InferenceRule::{NAMEABLE, from_name, canonical_name, is_certifiable, uncertifiable_reason, map_payload} and DerivationTree::uncertifiable_rules; certifier::certify refuses a rule with no certifier arm with that reason. A DerivationTree { conclusion, rule, premises, depth, substitution } is the prover’s result; ProofGoal { target, context } is consumed.

Hints (hints):

hints::suggest_hint(goal: &ProofExpr, kb: &[ProofExpr], failed: &[SuggestedTactic]) -> SocraticHint;

SocraticHint { text, suggested_tactic, priority } proposes a SuggestedTactic as a leading question rather than giving the answer outright.

SAT and model checking (Z3-free, browser-ready; sat and bmc):

sat::find_model(e: &ProofExpr) -> ModelOutcome;            // Sat(model) | Unsat | Unsupported
sat::prove_equivalence(a, b: &ProofExpr) -> EquivOutcome;  // Equivalent | Differ(cex) | Unsupported
sat::prove_unsat(e: &ProofExpr) -> UnsatOutcome;           // Refuted (RUP) | Sat(model) | Unsupported
bmc::find_counterexample(init, trans, property, max_k) -> BmcOutcome;
bmc::prove_invariant(init, trans, property, k) -> InductionOutcome;  // k-induction, unbounded
bmc::check_vacuity(antecedent: &ProofExpr) -> VacuityOutcome;

UNSAT verdicts from sat are independently RUP-certified (a refutation the trusted checker cannot replay yields Unsupported, never a false Refuted); bmc reduces BMC, k-induction, and vacuity to prove_unsat.

Core modules:

  • certifier: certify, DerivationTree → kernel Term.
  • unify: Robinson unification with occurs check, capture-avoiding beta_reduce, Miller patterns.
  • grounding: expands bounded quantifiers over a finite domain.
  • grid_solver: the certified logic-grid solver (watched-literal unit propagation + DPLL).
  • cdcl: the CDCL(T) core: two watched literals, 1-UIP, VSIDS, Luby restarts, a Theory trait, and a DRAT/LRAT log. Incremental: solves under assumptions within a conflict budget, variables and decision variables added between solves, and LRAT hints recorded as each clause is learned (a level-0 fact named by its unit clause, derived once), so a caller keeps one derivation across every solve.
  • cnf: Tseitin clausification of a ProofExpr, plus a gate-level builder (Cnf::{atom_lit, add_clause, encode_and, encode_or, encode_implies, encode_iff}) for a producer holding a shared gate DAG; sat::prove_unsat_certified_cnf returns the same checked refutation steps sat::prove_unsat_certified gives for a ProofExpr.
  • rup: the RUP checker.
  • arith: the proof-producing Int ring oracle. BigInt coefficients, closed goals by checked kernel normalization at any literal width, ring proofs whose laws are proved in the prelude, and None in a context whose add/mul/sub are not the checked integer operations.
  • interval_replay: the independent range-safety checker for analog netlist claims. It replays claimed voltage bounds by directed-outward-rounded interval arithmetic with no dependencies: the RUP-checker trust pattern applied to clipping and noise-floor safety.
  • relax_replay: the residual judge for physics-solved linear systems. It re-multiplies A·x̂ − b in exact ℚ and checks the declared ∞-norm bound, so the physical solver is untrusted by construction; it also judges settled minimization and Ising readouts.
  • thermal_replay: the same judge for thermal maps. It reassembles the thermal Laplacian from a neutral edge/ground/injection list and demands G·ΔT = P as an exact equality, plus connectivity and positivity.
  • error: ProofError / ProofResult.

§Module map

Beyond the core, the crate is a library of certified reasoners and proof systems. Every entry is a pub mod:

  • SAT engines and interchange: dimacs (DIMACS CNF I/O), satcli (the SAT command-line driver shared by the logos-sat binary and largo sat: competition output, certificate export, injected streams), twosat (2-SAT via implication-graph SCC), hornsat (Horn-SAT unit propagation), sdcl (Satisfaction-Driven Clause Learning), inprocess (certified inprocessing simplifications), discrimination (the first-order discrimination-tree index under simp).
  • Certified proof output: proof (shared proof-step vocabulary), proof_emit (DRAT/LRAT/DPR trace emission, replayable by the SAT community’s independent checkers), lrat (LRAT hint chains found by watched-literal propagation over a solver’s learned clauses, trimmed backward to the clauses the refutation uses, or to any target clauses a log derives, and a structured checker that replays them), proof_rewrite (the commutation of independent refutation steps, as proof-rewrite 2-cells), pr (propagation-redundancy checker), complexity (a refutation that carries a checkable bound on its own size).
  • Circuit equivalence: aig (and-inverter graphs: structural hashing, the AIGER ASCII and binary formats, bit-parallel simulation), sweep (two circuits paired by port name and decided by SAT sweeping, every equality a lemma with an LRAT proof and every difference an input assignment that replays), fraig (the same decision on one incremental solver over the reduced graph: nodes merged by structure without a call, the rest by budgeted solves under assumptions on the cones they ask about, every clause logged with its hints as it is made, and every equality carried by one LRAT derivation from the miter’s formula), units (two circuits decided over units proven apart, each cut out as a function nothing is known of: in rounds, applications of one function whose operands are proven equal identified, on either side or across, a unit’s latency matched, each side unrolled with its inputs bound per clock and its outputs claimed at their own clocks, and every round’s derivation and identification re-checked), streams (two valid-ready stream circuits at their own widths and paces decided token for token under an arrival pattern: each side’s handshakes proven constants with the data free, so a schedule that depends on the data is refused by name, then the k-th tokens claimed equal over the units), seq_equiv (a pipeline unrolled to its latency against its combinational reference, decided by either engine, and two sequential circuits equal for all time by an inductive correspondence of their registers, with the certificate a checker replays), cycle_ratio (the maximum delay-per-register over a graph’s cycles, the clock no retiming can beat: Howard’s policy iteration on each strongly connected component, the bound certified by its cycle and an integer potential no edge violates), min_cost_flow (the network simplex on a strongly feasible tree, every optimum certified by complementary slackness, every infeasibility by a cut, every unbounded problem by a negative cycle: the dual of a least-area register cut at a target clock).
  • Algebraic proof systems: gf2 (GL(n,2)), xorsat / xor_engine / xor_drat (GF(2) parity: Gaussian XOR-SAT, DPLL(XOR), and the CNF→DRAT bridge), modp (GF(p) linear algebra), modm (ℤ/m by CRT), polycalc (Polynomial Calculus / Nullstellensatz over GF(2)), pseudo_boolean (cutting planes), affine / affine_gfp (the AGL(n,2) / AGL(n,p) affine symmetry a permutation break cannot see), sos (exact Sum-of-Squares / Positivstellensatz), lll (Lovász Local Lemma certificate), macaulay / xl (the Macaulay matrix and XL linearization that solve multivariate-quadratic systems over GF(2)/GF(2⁸), the algebraic cryptanalysis Ding formalized via the degree of regularity), rainbow (a Ding–Schmidt Oil-and-Vinegar signature reference, the multivariate scheme xl attacks).
  • Symmetry: symmetry / symmetry_detect (detection), sym_break (lex-leader breaking), sym_certify (certified breaking), sym_dynamic (Symmetric Explanation Learning), permgroup (Schreier–Sims BSGS, the non-abelian coset decision), families (parametric generators for symmetry-rich hard instances).
  • Combinatorial reasoners: pigeonhole / matching (bipartite-matching infeasibility), cardinality (cardinality constraints over boolean atoms), counting_principle (the modular counting principle Count_q(n): O(clauses) recognition, q ∤ n certificate), parity_cardinality (the coupled exactly-one + parity obstruction, decided by GF(2) augmentation), interval_sched (sweep-line scheduling), register_alloc (linear-scan allocation as a Hall reasoner), hypercube (Boolean-hypercube subcube cover), ordering (a polynomial-time recognizer and certified refuter for the GT(n) no-maximum ordering principle, which the general cascade decides only by super-polynomial search), lyapunov (Lyapunov-measure synthesis).
  • Homotopy of symmetry and concurrency: groupoid (symmetry breaking as keeping one assignment per orbit of the action groupoid), coalgebra (a certified refutation as a coalgebra, and a Lyapunov measure as a morphism to the countdown), cubical (cubical homology in any dimension over GF(2)), kan_complex (the nerve of a group, with the Kan condition checked in degrees 2 and 3), two_group / two_type / eilenberg_maclane / postnikov (crossed modules, K(A, n) spaces and the Postnikov k-invariant), steenrod (Steenrod squares on Z/2[x]), progress_complex / trace_determinism (the space of schedules of concurrent operations: mutual exclusion leaves a hole in it, and pairwise-independent operations, which reach the same state on every schedule, leave it contractible).
  • Tactics, developments and simplification: tactic / tactic_script (interactive goal-state proving), tactic_cert (the certificate producers and independent checkers shared with the kernel’s second checker: a tactic hands back a certificate that checker replays, so it trusts the certificate rather than the tactic that found it), formula (formal-FOL surface-text parser), development (## Theory block bodies), simp (oriented rewrite-rule sets).
  • Silicon reversibility: revgate certifies a reversible logic gate as a bijection. An n-bit unit is reversible iff its truth table is a permutation of {0..2ⁿ}, and a linear CNOT/XOR block iff its GF(2) transfer matrix is invertible.
  • Arithmetic, optimization and dispatch: linarith_solve (Fourier–Motzkin LIA core), optimize (certified SAT-based minimization), solve (the structure-detecting dispatcher: cheap recognizers first, each claiming a verdict only with a re-checked certificate, then CDCL for the rest), ait (certified algorithmic-information / description-length objects), isogeny (certified SIDH/SIKE torsion-image witnesses), linalg (exact linear algebra over ℚ: A·x = b decided as an exact identity with an independently re-multiplied residual_is_zero certificate, det A ≠ 0 certifying nonsingularity outright), linalg_certify (each row identity cleared to an integer identity, proven by the arith ring oracle, and re-checked by the kernel’s own infer_type).
  • Number theory and cryptanalysis: factor (structural factoring and RSA attacks: trial division, Fermat, Pollard p−1 and rho, Wiener, Coppersmith, each returning factors verify_factorization re-checks), elliptic (Montgomery x-only ECM), period (order-finding, the classical shell of Shor’s algorithm), lattice (exact LLL / Coppersmith over Rational), fp2 (𝔽_{p²} arithmetic and the supersingular 2-isogeny graph), hyperelliptic (genus-2 Richelot (2,2)-isogeny, the Castryck–Decru mechanism), cyclotomic (the power-of-two Module-LWE ring ℤ[X]/(Xⁿ+1)). This is pure number theory over logicaffeine_base::numeric, and the hardness lens isogeny, ait and solve build on.

§Tactics and decision procedures

Beyond the certified SAT/BMC core, the crate ships a tactic layer and algebraic solvers:

  • engine: the backward-chaining proof engine. Order chains mix = and ≤ (an equality is a two-way edge through positional Leibniz).
  • rule_search: aesop-style rule-set search, turning auto’s fixed cascade into a searchable rule database.
  • crush: the grind-style closer. It E-matches quantified equality lemmas into the goal.
  • decide: proof by evaluation for closed decidable goals. div/mod are Euclidean, total and arbitrary-precision (a zero divisor gives quotient 0, remainder the dividend); integer literals past i64 are integers; a goal that evaluates false is reported false, not undecided, and a negated ground goal is proved by GroundRefutation.
  • omega_solve: omega, linear integer arithmetic. It refutes the hypotheses (a strict a < b becomes a + 1 ≤ b through lt_succ_le, then a Farkas refutation), proves the goal directly (a ground comparison by computation, a ≤ by chaining in-scope facts, an Int equality through the ring oracle), or splits on le_total and refutes the other side. It reaches every goal whose negation-by-totality is refutable, not all of Presburger arithmetic, and adds no axiom.
  • linarith_solve: the rational Fourier–Motzkin core with Farkas certificates behind linarith, which declines any goal that needs integrality.
  • lemma_index: exact? / apply? premise selection over a named, certified lemma index.
  • counterexample: when a goal is false, exhibits a model instead of just failing.
  • simp: oriented rewrite-rule sets; SimpSet::register_context_lemmas(&Context) compiles the @[simp] rules a kernel context registers.

§The tactic language

tactic::ProofState holds the open goals; a tactic replaces the focused goal with zero or more subgoals and records the rule it used, and ProofState::qed assembles the steps into one DerivationTree and sends it through verify::check_derivation. A tactic builds the derivation; the kernel checks it. tactic::Tactic is Box<dyn Fn(&mut ProofState) -> Result<(), TacticError>>, and tactic::combinators builds one per primitive plus seq, first, try_, repeat, then_all, all_goals, any_goals and focus (an error when its block leaves the goal open). tactic::PTerm is a script term: one syntax read as a proof or as a value by its position.

tactic_script::parse_script compiles proof text to a Tactic; ProofState::run_script runs it, and logicaffeine_language::compile::run_proof_sketch runs a theorem’s Proof: line through it, discharging what the sketch leaves open with auto. Sentence punctuation (., ,) separates steps like ;.

script  := seq
seq     := chain (';' chain)*                  run in order
chain   := atom ('<;>' atom)*                  t2 on every goal t1 spawned
atom    := '(' script ')' | 'first' '[' script ('|' script)* ']'
         | 'try' atom | 'repeat' atom | 'all_goals' atom | 'any_goals' atom
         | 'focus' atom | NAME ARG*
term    := factor (('+'|'-') factor)*          the argument of exact/exists/have/refine
factor  := app ('*' app)*
app     := primary primary*                    application by juxtaposition
primary := NAME | '?' NAME? | '(' term (',' term)* ')'

Primitive steps: intro a b, exact <term>, apply h, rfl, cases h [with a b], rewrite h [at <k> | at <hyp> [<k>]] (position, location, or both), exists <term>, assumption, simp, simp only [h₁, h₂], simp [h], decide, omega, linarith, ring, crush, calc h₁ h₂ …, by_rule <Rule> (certified before it reports success), split, left, right, auto, induction [n], by_contra h, have h from <term>, refine <term> (one subgoal per ?_ hole). Each has English synonyms (use/witness for exists, assume/suppose for intro, arithmetic/integers for omega, rationals for linarith, grind for crush, …). tactic_script::TacticEnv names user-defined tactics as scripts (expansion is depth-bounded, so a recursive definition is refused), and prove_scripted_library proves a dependency-ordered library of ScriptedTheorems, each proved conclusion citable by later ones.

§Feature flags

FeatureDefaultEnables
verificationofflogicaffeine-verify, and with it oracle (the Z3 SMT fallback) and the private modal_translation (modal/temporal → world-indexed FOL). Z3 verdicts are never kernel-certified.

Without it the crate is kernel-certified search plus SAT/RUP/BMC, with no Z3 and no external runtime dependency.

§Dependencies

Internal: logicaffeine-base, logicaffeine-kernel; logicaffeine-verify (optional, gated behind verification). No dependency on the language crate (Liskov invariant), and no external (non-workspace) crates: the default build is pure Rust with no Z3 and no runtime dependency, which is what keeps the SAT/BMC stack browser-ready.

§License

MIT License — see LICENSE.md.


Docs index · Root README · Changelog

Re-exports§

pub use engine::BackwardChainer;
pub use engine::PremiseVariables;
pub use error::ProofError;
pub use hints::suggest_hint;
pub use hints::SocraticHint;
pub use hints::SuggestedTactic;
pub use unify::Substitution;

Modules§

affine
The affine group AGL(n,2) — the symmetry a permutation break cannot see.
affine_gfp
The affine group AGL(n,p) over GF(p) — the mod-p generalization of the affine break.
aig
And-inverter graphs: a circuit as two-input AND gates over complemented edges, read and written in the AIGER format (Biere, The AIGER And-Inverter Graph Format, Version 20071012, and its 1.9 extension).
ait
Algorithmic information theory — certified description-length objects
arith
Proof-PRODUCING arithmetic oracle (untrusted search, kernel-checked proof).
bmc
Bounded model checking, k-induction, and vacuity over ProofExpr — pure-Rust, certified, Z3-free, browser-ready.
cardinality
Cardinality constraints over boolean ProofExpr atoms — the missing primitive that lets the certified solver answer “at most / at least / exactly k of these are true”. Encoded with Sinz’s sequential counter (linear in n·k, fresh auxiliary atoms under a caller-chosen prefix), so the result is an ordinary boolean obligation the existing CNF/CDCL/RUP pipeline discharges. This is the building block for SAT-based optimization (crate::optimize).
cdcl
A conflict-driven clause-learning (CDCL) SAT core — the modern competition-grade engine, built to the lineage that made SAT practical: two-watched-literal unit propagation (Moskewicz et al., Chaff, 2001), first-UIP conflict analysis with learned clauses and non-chronological backtracking (Marques-Silva & Sakallah, GRASP, 1996), VSIDS-style activity decisions, and Luby restarts (Luby et al., 1993). The clean reference implementation it follows is Eén & Sörensson’s MiniSat (2003).
certifier
The Certifier: Converts DerivationTrees to Kernel Terms.
cnf
Tseitin clausification: a grounded, quantifier-free ProofExpr → CNF over the CDCL core’s Lits (Tseitin, 1968 — the standard linear-size equisatisfiable transform that introduces one auxiliary variable per compound subformula). This is the bridge from the logic-grid encoding (closures, at-most-one, of-pair, clue clauses) to the crate::cdcl SAT engine, giving the Untrusted trust tier: solve premises ∧ ¬goal; UNSAT ⇒ the goal is entailed. The same CNF feeds the RUP checker (the fast trust tier) and is the input an AllDifferent GAC propagator filters.
coalgebra
The coalgebraic / Poly view, made into checked code rather than narration.
complexity
Certified complexity bounds — a refutation that carries a checkable proof of its own size.
counterexample
Counterexamples — when a goal is FALSE, exhibit a model instead of failing silently. Lean ships no built-in counterexample finder with its automation; this closes that gap.
counting_principle
Fast refuter for the modular counting principle Count_q(n): partition an n-element set into blocks of size q. Encoded as: one Boolean per q-subset (block); a coverage clause per element (the incident blocks, at least one chosen); and a disjointness clause for every pair of overlapping blocks. It is unsatisfiable exactly when q ∤ n.
crush
crush — the grind-style closer: E-match quantified equality lemmas into the ground e-graph, then discharge the goal by certified congruence closure.
cubical
A general d-dimensional cubical-homology engine — one engine, every rung of the ladder.
cycle_ratio
The maximum cycle ratio of a weighted digraph, exact and certified: the bound a loop puts on a clock period.
cyclotomic
Power-of-two cyclotomic ring R = ℤ[X]/(Xⁿ + 1), n = 2ᵏ
decide
decide — proof by evaluation for closed decidable goals.
development
A formal-development parser: the body of a ## Theory block — a sequence of Axiom and Theorem declarations in formal notation — into the axioms and LibraryTheorems the multi-theorem driver consumes.
dimacs
DIMACS CNF parsing and printing — the SAT-competition interchange format, and the front door for running arbitrary instances through the solver.
discrimination
First-order discrimination tree: the shared pattern index under simp rule lookup, exact?/apply? library search, and crush’s E-matching.
eilenberg_maclane
The general Eilenberg–MacLane construction K(A, n) — one engine, every rung of the tower.
elliptic
Elliptic-curve primitives over ℤ/N — the additive→multiplicative lift
engine
Backward chaining proof engine.
error
Error types for proof search and unification.
factor
Structural factoring: the AIT thesis applied to public-key crypto.
families
Parametric generators for symmetry-rich SAT families — the canonical hard cases where symmetry breaking earns its keep. They are programmatic (reproducible, offline, parametric) rather than vendored .cnf files, and each is pinned to its known verdict so the solver and the certified pipeline can be tested against ground truth.
formula
A self-contained parser from formal first-order-logic surface text to ProofExpr.
fp2
𝔽_{p²} arithmetic and the supersingular isogeny graph
fraig
Combinational equivalence by incremental SAT sweeping, certified by one derivation.
gf2
The general linear group GL(n,2) and the invertibility constant — where the reciprocal SAT-threshold sum comes home.
grid_solver
A fast, certified finite-domain (logic-grid) solver.
grounding
Finite-domain grounding.
groupoid
The action groupoid — what symmetry breaking means, categorically, as checked code.
hints
Socratic Hint Engine - Generates pedagogical hints for proof guidance.
hornsat
Horn-SAT in linear time via unit propagation (forward chaining).
hypercube
The Boolean hypercube {0,1}ⁿ and its subcube cover — the geometric substrate beneath SAT, and the executable form of the Lean formalization’s HypercubeSAT.
hyperelliptic
Genus-2 curves and the Richelot (2,2)-isogeny — the abelian-surface mechanism
inprocess
Certified inprocessing: clause-database simplifications that emit a machine-checkable proof.
interval_replay
Independent range-safety checker for analog netlist claims — the trust core of the analog lane’s RangeCertificate, in the same spirit as this crate’s PR/RUP checker: a small, dependency-free replay the certificate producer cannot influence.
interval_sched
Interval scheduling in O(n log n) via a sweep line — the matching/Hall reasoner reaching into resource allocation over time.
isogeny
Certified isogeny torsion-image witnesses — the SIDH/SIKE public-data structure, in the prover
kan_complex
Actually having an ∞-groupoid — not its invariants, the object itself, with its defining property machine-verified.
lattice
LLL lattice reduction — the geometric lens of the compression campaign.
lemma_index
exact? / apply? and premise selection: search over a NAMED, certified lemma library.
linalg
Exact linear algebra over ℚ — the certified core of the LOGOS numerical stack.
linalg_certify
Kernel-certified linear algebra: turn an exact solve into a KERNEL-CHECKED PROOF TERM.
linarith_solve
The decision core for linear integer arithmetic: Fourier-Motzkin elimination that tracks the non-negative combination it eliminates with, so an unsatisfiable system yields its Farkas certificate — the multipliers λᵢ ≥ 0 on the original constraints such that Σ λᵢ·constraintᵢ is a positive constant ≤ 0 (a contradiction). The proof engine reconstructs a kernel proof from those multipliers via le_mul_nonneg/le_add_mono + the Bool no-confusion discriminator. Pure and self-contained — no kernel, no certificates here.
lll
Satisfiability from sparsity — the Lovász Local Lemma certificate and its constructive Moser–Tardos witness. The lower bookend to the first-moment bound.
lrat
LRAT refutations at scale: hint chains found by watched-literal propagation, trimmed to the clauses a refutation uses, and replayed by a checker that trusts nothing the search did.
lyapunov
Lyapunov-function synthesis — don’t search for the proof, discover the measure that collapses the problem, and let the proof fall out as a corollary.
macaulay
Monomials and the Macaulay matrix — the combinatorial skeleton of the XL algorithm.
matching
Certified bipartite-matching infeasibility — the polynomial reasoner for pigeonhole-shaped problems that are exponential for resolution (and therefore for any CDCL SAT solver, ours included).
min_cost_flow
Minimum-cost flow, exact and certified: the dual of every scheduling and retiming problem whose constraints are differences of two variables, which is how a register cut of least area at a target clock is found.
modm
Linear algebra over ℤ/m for composite m, by the Chinese Remainder Theorem — the multiplicative symmetry break. A system Σ aᵢ·xᵢ ≡ c (mod m) over a squarefree modulus m = p₁·…·p_t factors, through the ring isomorphism ℤ/m ≅ GF(p₁) × … × GF(p_t), into one independent system over each prime field — each decided by crate::modp::solve — and the per-field solutions are recombined by CRT. The factorization of the modulus is the symmetry that splits the problem; the prime fields are the irreducible pieces:
modp
Linear algebra over GF(p) — the mod-p generalization of the GF(2) parity cut (crate::xorsat).
omega_solve
omega — linear INTEGER arithmetic, the discreteness-aware layer over the rational Farkas core.
optimize
Certified SAT-based optimization. We have no native MaxSAT/ILP solver, so we minimise an integer cost the honest way: binary-search the smallest feasible cost bound, where each query is a certified decision (prove_unsat → Sat witness or RUP-Refuted). The result is a certified optimum — a witness at the optimum and a refutation at optimum−1 — not merely a value we happened to find.
ordering
The ordering-principle specialist — a polynomial-time recognizer + refuter for GT(n), the linear-ordering contradiction. GT(n) asserts a strict total order (totality + antisymmetry + transitivity) in which every element has a strictly greater one (“no maximum”). That is impossible: a finite strict total order always has a maximum. So a complete GT(n) core is unsatisfiable, and any formula containing it (a superset of an UNSAT core) is UNSAT.
parity_cardinality
Fast refuter for the coupled exactly-one + parity family. An exactly-one group (an at-least-one clause plus the full at-most-one clique over its variables) forces EXACTLY one of its selectors true, so their XOR is 1 (odd). If the formula’s parity substructure forces that same XOR to 0 (even), the two are inconsistent and the formula is UNSAT — the mixed obstruction neither theory sees alone.
period
The period / order seam — the classical shell of Shor’s algorithm
permgroup
Schreier–Sims: a base and strong generating set (BSGS) for a permutation group — the non-abelian generalization of Gaussian elimination, and the last rung of the algebra ladder (GF(2)→GF(p)→ℤ/m linear; this is the group level).
pigeonhole
Pigeonhole / bipartite-matching detection for the general solver — the cardinality reasoning that lets prove_unsat win on pigeonhole-shaped formulas in POLYNOMIAL time.
polycalc
Polynomial Calculus / Nullstellensatz over GF(2) — the algebraic proof system that subsumes the linear cuts (parity is its degree-1 fragment) and, at higher degree, refutes strictly more.
postnikov
The Postnikov k-invariant — the gluing data of a 2-type, and the obstruction to breaking it into a product.
pr
The PR (propagation-redundancy) checker — the trust tier for model-removing clause additions, and the keystone that makes certified symmetry breaking possible.
progress_complex
Genuine higher homotopy, at last — π₁ ≠ 0 from real concurrency, the hole is the deadlock.
proof
Shared proof-step vocabulary for the certified checkers.
proof_emit
Standard proof-trace emission — DRAT, LRAT, and DPR text from our in-memory ProofStep stream, so the certified refutations this crate produces are not merely self-checked but replayable by the SAT community’s independent (and in cake_lpr’s case formally verified) checkers.
proof_rewrite
The proof-rewrite 2-cells — independent refutation steps commute, and the commutation squares make the space of proof-orderings a contractible CAT(0) cube complex. This is the honest higher structure the symmetry tower pointed at, and it is genuine 2-dimensional homotopy: not a faked π₂, but the coherence theorem for proofs — every way of reordering independent steps is coherently the same, up to all higher homotopies.
pseudo_boolean
Pseudo-Boolean constraints + cutting planes — a proof system STRICTLY STRONGER than resolution.
rainbow
Rainbow — Jintai Ding & Dieter Schmidt’s multilayer Oil-and-Vinegar signature (ACNS 2005), the multivariate scheme our XL engine is built to attack. This is a faithful reference over GF(2^8): a two-layer central map F, invertible affine transforms S and T, public key P = S ∘ F ∘ T, and the Oil-and-Vinegar trapdoor that inverts F at signing time.
register_alloc
Certified linear-scan register allocation — the matching/Hall reasoner as a compiler back-end.
relax_replay
Settled-answer replay — the residual certificate for physics-solved linear systems.
revgate
Certify reversible logic gates as bijections.
rule_search
aesop-style rule-set search: turn auto’s fixed cascade into an extensible, best-first search over registered rules.
rup
The RUP (Reverse Unit Propagation) linear checker — the fast default trust tier.
sat
Propositional SAT-discharge of a ProofExpr obligation — the engine behind in-browser, Z3-free hardware proving.
satcli
The SAT command-line driver shared by logos-sat and largo sat.
sdcl
Satisfaction-Driven Clause Learning (Heule, Kiesl & Seidl) — the engine that reasons at the Extended-Frege level by discovering propagation-redundant clauses, not just learning implied ones. It is symmetry breaking taken to its limit: where certified symmetry breaking needs an automorphism to supply a witness, SDCL finds the witness by solving the positive reduct — a smaller SAT problem — so it works on any structure, symmetric or not.
seq_equiv
Sequential equivalence by unrolling: a pipelined circuit proven equal to its combinational reference at its latency, or two pipelines of different depths proven to compute the same transaction.
simp
simp rule sets: oriented rewrite rules compiled from proved lemmas, indexed for fast lookup, instantiated by matching.
solve
Structure-detecting solve front-end — the auto-dispatcher that puts our whole arsenal behind a single entry point.
sos
Sum-of-Squares / Positivstellensatz refutation over ℚ — kept EXACT (no SDP, no floating point) by the LP slice of the cone. True SoS is a semidefinite program over the reals; that would forfeit our certified guarantee. Instead we take the diagonal (fixed-square-basis) Positivstellensatz, which is an exact rational linear program: a CNF is lifted to degree-2 pseudo-Boolean inequalities and the lift is refuted by exact Fourier–Motzkin / Farkas elimination.
steenrod
The Steenrod algebra acting on H*(BZ/2; Z/2) = Z/2[x] — the deepest layer of cohomology operations, and a place where homotopy theory turns out to be number theory.
streams
Stream equivalence over units proven apart: two circuits that take a stream of tokens through a valid-ready handshake and give a stream back, each at its own width and its own pace, decided equal token for token under an arrival pattern.
sweep
Combinational equivalence: two circuits’ outputs proven equal, or told apart by an input assignment that replays, every equality carried by a lemma whose LRAT proof a small checker re-validates.
sym_break
Complete lex-leader symmetry breaking, driven by the Schreier–Sims backend.
sym_certify
Certified symmetry breaking — the centerpiece. Given a formula and a set of verified symmetry generators, add lex-leader symmetry-breaking predicates as PR steps (each self-checked, fail-closed), solve the augmented formula, and emit a single composed refutation that an independent checker accepts against the original formula alone.
sym_dynamic
Dynamic symmetry breaking — Symmetric Explanation Learning (SEL), the in-search tier.
symmetry
Symmetry breaking for the general solver — the second pillar (with crate::pigeonhole cardinality reasoning) for winning on pigeonhole.
symmetry_detect
General symmetry detection for CNF — the engine behind certified symmetry breaking.
tactic
A tactic framework with a first-class goal state — the interactive proof interface (ROOT R5 of the Lean-competitive architecture).
tactic_cert
Certificate producers and independent checkers shared with the kernel rechecker.
tactic_script
A tiny proof-script language over the crate::tactic combinators — proofs as TEXT, the way a Lean/Coq proof reads. This is the self-contained seam toward a full English vernacular: it has no dependency on the surface language, so it compiles a script string straight into a composed Tactic.
thermal_replay
Thermal-map replay — the independent judge of a claimed steady-state temperature map.
trace_determinism
The concurrency tie made literal: determinism = contractibility, on a real machine.
two_group
The 2-group frontier — climbing past K(G,1) to genuine 2-types, honestly.
two_type
A genuinely 2-truncated ∞-groupoid, had as an object: the minimal K(A, 2).
twosat
2-SAT in linear time via the implication graph + strongly-connected components.
unify
First-order unification for proof search.
units
Equivalence over units proven apart: two circuits built of units (adders, multipliers, any module already proven equal to its counterpart), each unit cut out of its circuit — its results free inputs, its operands outputs — and the two decided over the units as functions they know nothing of, a unit’s own proof standing for what it computes.
verify
Unified theorem verification — the single door.
xl
XL — algebraic cryptanalysis of multivariate quadratic (MQ) systems by linearization.
xor_drat
The CNF→GF(2) bridge: compile a Gaussian (XOR linear-dependency) refutation into a strict DRAT proof that an external checker (drat-trim) accepts.
xor_engine
DPLL(XOR) — the live GF(2) reasoning engine.
xorsat
XOR-SAT via Gaussian elimination over GF(2) — the parity analog of the pigeonhole/matching supercrush.

Structs§

DerivationTree
The “Euclidean Structure” - A recursive tree representing the proof.
InductionArg
One argument of a constructor in an InductionCase.
InductionCase
The “Lever” - The specific logical move made at each proof step.
MatchArm
A single arm in a match expression. Example: Succ(k) => Add(k, m)
ProofGoal
The Goal State for the Backward Chainer.

Enums§

InferenceRule
ProofExpr
Owned expression representation for proof manipulation.
ProofTerm
Owned term representation for proof manipulation.