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→ kernelTerm.unify: Robinson unification with occurs check, capture-avoidingbeta_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, aTheorytrait, 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 aProofExpr, 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_cnfreturns the same checked refutation stepssat::prove_unsat_certifiedgives for aProofExpr.rup: the RUP checker.arith: the proof-producingIntring oracle.BigIntcoefficients, closed goals by checked kernel normalization at any literal width, ring proofs whose laws are proved in the prelude, andNonein a context whoseadd/mul/subare 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-multipliesA·x̂ − bin 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 demandsG·ΔT = Pas 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 thelogos-satbinary andlargo 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 undersimp). - 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 schemexlattacks). - 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 principleCount_q(n):O(clauses)recognition,q ∤ ncertificate),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 Postnikovk-invariant),steenrod(Steenrod squares onZ/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(## Theoryblock bodies),simp(oriented rewrite-rule sets). - Silicon reversibility:
revgatecertifies a reversible logic gate as a bijection. Ann-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 = bdecided as an exact identity with an independently re-multipliedresidual_is_zerocertificate,det A ≠ 0certifying nonsingularity outright),linalg_certify(each row identity cleared to an integer identity, proven by thearithring oracle, and re-checked by the kernel’s owninfer_type). - Number theory and cryptanalysis:
factor(structural factoring and RSA attacks: trial division, Fermat, Pollardp−1and rho, Wiener, Coppersmith, each returning factorsverify_factorizationre-checks),elliptic(Montgomery x-only ECM),period(order-finding, the classical shell of Shor’s algorithm),lattice(exact LLL / Coppersmith overRational),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 overlogicaffeine_base::numeric, and the hardness lensisogeny,aitandsolvebuild 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, turningauto’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/modare Euclidean, total and arbitrary-precision (a zero divisor gives quotient0, remainder the dividend); integer literals pasti64are integers; a goal that evaluates false is reported false, not undecided, and a negated ground goal is proved byGroundRefutation.omega_solve:omega, linear integer arithmetic. It refutes the hypotheses (a stricta < bbecomesa + 1 ≤ bthroughlt_succ_le, then a Farkas refutation), proves the goal directly (a ground comparison by computation, a≤by chaining in-scope facts, anIntequality through the ring oracle), or splits onle_totaland 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 behindlinarith, 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
| Feature | Default | Enables |
|---|---|---|
verification | off | logicaffeine-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.
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)overGF(p)— the mod-pgeneralization 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
ProofExpratoms — the missing primitive that lets the certified solver answer “at most / at least / exactlykof these are true”. Encoded with Sinz’s sequential counter (linear inn·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’sLits (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 thecrate::cdclSAT engine, giving the Untrusted trust tier: solvepremises ∧ ¬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 /
Polyview, 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 ann-element set into blocks of sizeq. Encoded as: one Boolean perq-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 whenq ∤ 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
## Theoryblock — a sequence ofAxiomandTheoremdeclarations in formal notation — into the axioms andLibraryTheorems 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
simprule lookup,exact?/apply?library search, andcrush’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
.cnffiles, 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’sHypercubeSAT. - 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
λᵢ ≥ 0on the original constraints such thatΣ λᵢ·constraintᵢis a positive constant≤ 0(a contradiction). The proof engine reconstructs a kernel proof from those multipliers viale_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
ℤ/mfor compositem, by the Chinese Remainder Theorem — the multiplicative symmetry break. A systemΣ aᵢ·xᵢ ≡ c (mod m)over a squarefree modulusm = p₁·…·p_tfactors, through the ring isomorphismℤ/m ≅ GF(p₁) × … × GF(p_t), into one independent system over each prime field — each decided bycrate::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-pgeneralization 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→Satwitness 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 to0(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_unsatwin 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 —
π₁ ≠ 0from 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
ProofStepstream, so the certified refutations this crate produces are not merely self-checked but replayable by the SAT community’s independent (and incake_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 transformsSandT, public keyP = S ∘ F ∘ T, and the Oil-and-Vinegar trapdoor that invertsFat 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: turnauto’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
ProofExprobligation — the engine behind in-browser, Z3-free hardware proving. - satcli
- The SAT command-line driver shared by
logos-satandlargo 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
simprule 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::pigeonholecardinality 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::tacticcombinators — 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 composedTactic. - 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§
- Derivation
Tree - The “Euclidean Structure” - A recursive tree representing the proof.
- Induction
Arg - One argument of a constructor in an
InductionCase. - Induction
Case - The “Lever” - The specific logical move made at each proof step.
- Match
Arm - A single arm in a match expression. Example: Succ(k) => Add(k, m)
- Proof
Goal - The Goal State for the Backward Chainer.
Enums§
- Inference
Rule - Proof
Expr - Owned expression representation for proof manipulation.
- Proof
Term - Owned term representation for proof manipulation.