logicaffeine_proof/lib.rs
1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3
4// Number-theory / cryptanalysis substrate — factoring, elliptic/isogeny, lattice, order-finding.
5// These are prover tools (the hardness lens behind isogeny/ait/oracle), not runtime crypto; they
6// depend only on `logicaffeine_base::numeric`.
7pub mod cyclotomic;
8pub mod elliptic;
9pub mod factor;
10pub mod fp2;
11pub mod hyperelliptic;
12pub mod lattice;
13pub mod period;
14
15pub mod arith;
16// Independent replay checker for the analog lane's range-safety certificates (the PR/RUP-checker
17// pattern applied to voltage bounds): dependency-free, fail-closed, trusted over the producer.
18pub mod affine;
19pub mod affine_gfp;
20pub mod aig;
21pub mod ait;
22pub mod bmc;
23pub mod cardinality;
24pub mod cdcl;
25pub mod certifier;
26pub mod cnf;
27pub mod coalgebra;
28pub mod complexity;
29pub mod counterexample;
30pub mod counting_principle;
31pub mod crush;
32pub mod cubical;
33pub mod cycle_ratio;
34pub mod decide;
35pub mod development;
36pub mod dimacs;
37pub mod discrimination;
38pub mod eilenberg_maclane;
39pub mod engine;
40pub mod error;
41pub mod families;
42pub mod formula;
43pub mod fraig;
44pub mod gf2;
45pub mod grid_solver;
46pub mod grounding;
47pub mod groupoid;
48pub mod hints;
49pub mod hornsat;
50pub mod hypercube;
51pub mod inprocess;
52pub mod interval_replay;
53pub mod interval_sched;
54pub mod isogeny;
55pub mod kan_complex;
56pub mod lemma_index;
57pub mod linalg;
58pub mod linalg_certify;
59pub mod linarith_solve;
60pub mod lll;
61pub mod lrat;
62pub mod lyapunov;
63pub mod macaulay;
64pub mod matching;
65pub mod min_cost_flow;
66pub mod modm;
67pub mod modp;
68mod numeral;
69pub mod omega_solve;
70pub mod optimize;
71pub mod ordering;
72pub mod parity_cardinality;
73pub mod permgroup;
74pub mod pigeonhole;
75pub mod polycalc;
76pub mod postnikov;
77pub mod pr;
78pub mod progress_complex;
79pub mod proof;
80pub mod proof_emit;
81pub mod proof_rewrite;
82pub mod pseudo_boolean;
83pub mod rainbow;
84pub mod register_alloc;
85pub mod relax_replay;
86pub mod revgate;
87pub mod rule_search;
88pub mod rup;
89pub mod sat;
90pub mod satcli;
91pub mod sdcl;
92pub mod seq_equiv;
93pub mod simp;
94pub mod solve;
95pub mod sos;
96pub mod steenrod;
97pub mod sweep;
98pub mod sym_break;
99pub mod sym_certify;
100pub mod sym_dynamic;
101mod symbols;
102pub mod symmetry;
103pub mod symmetry_detect;
104pub mod tactic;
105pub mod tactic_cert;
106pub mod tactic_script;
107pub mod thermal_replay;
108pub mod trace_determinism;
109pub mod two_group;
110pub mod two_type;
111pub mod twosat;
112pub mod unify;
113pub mod units;
114pub mod streams;
115pub mod verify;
116pub mod xl;
117pub mod xor_drat;
118pub mod xor_engine;
119pub mod xorsat;
120
121#[cfg(feature = "verification")]
122mod modal_translation;
123#[cfg(feature = "verification")]
124pub mod oracle;
125
126pub use engine::{BackwardChainer, PremiseVariables};
127pub use error::ProofError;
128pub use hints::{suggest_hint, SocraticHint, SuggestedTactic};
129pub use unify::Substitution;
130
131use std::fmt;
132
133// =============================================================================
134// PROOF TERM - Owned representation of logical terms
135// =============================================================================
136
137/// Owned term representation for proof manipulation.
138///
139/// Decoupled from arena-allocated `Term<'a>` to allow proof trees to persist
140/// beyond the lifetime of the parsing arena.
141///
142/// # See Also
143///
144/// * [`ProofExpr`] - Expression-level representation containing `ProofTerm`s
145/// * [`unify::unify_terms`] - Unification algorithm for terms
146/// * [`unify::Substitution`] - Maps variables to terms
147/// * [`certifier::certify`] - Converts proof trees to kernel terms
148#[derive(Debug, Clone, PartialEq, Eq, Hash)]
149pub enum ProofTerm {
150 /// A constant symbol (e.g., "Socrates", "42")
151 Constant(String),
152
153 /// A variable symbol (e.g., "x", "y")
154 Variable(String),
155
156 /// A function application (e.g., "father(x)", "add(1, 2)")
157 Function(String, Vec<ProofTerm>),
158
159 /// A group/tuple of terms (e.g., "(x, y)")
160 Group(Vec<ProofTerm>),
161
162 /// Reference to a bound variable in a pattern context.
163 /// Distinct from Variable (unification var) and Constant (global name).
164 /// Prevents variable capture bugs during alpha-conversion.
165 BoundVarRef(String),
166}
167
168impl fmt::Display for ProofTerm {
169 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
170 match self {
171 ProofTerm::Constant(s) => write!(f, "{}", s),
172 ProofTerm::Variable(s) => write!(f, "{}", s),
173 ProofTerm::Function(name, args) => {
174 write!(f, "{}(", name)?;
175 for (i, arg) in args.iter().enumerate() {
176 if i > 0 {
177 write!(f, ", ")?;
178 }
179 write!(f, "{}", arg)?;
180 }
181 write!(f, ")")
182 }
183 ProofTerm::Group(terms) => {
184 write!(f, "(")?;
185 for (i, t) in terms.iter().enumerate() {
186 if i > 0 {
187 write!(f, ", ")?;
188 }
189 write!(f, "{}", t)?;
190 }
191 write!(f, ")")
192 }
193 ProofTerm::BoundVarRef(s) => write!(f, "#{}", s),
194 }
195 }
196}
197
198// =============================================================================
199// PROOF EXPRESSION - Owned representation of logical expressions
200// =============================================================================
201
202/// Owned expression representation for proof manipulation.
203///
204/// Supports all `LogicExpr` variants to enable full language coverage.
205/// This is the "proposition" side of the Curry-Howard correspondence.
206///
207/// # See Also
208///
209/// * [`ProofTerm`] - Terms embedded within expressions (predicate arguments)
210/// * [`unify::unify_exprs`] - Expression-level unification with alpha-equivalence
211/// * [`unify::beta_reduce`] - Normalizes lambda applications
212/// * [`certifier::certify`] - Converts expressions to kernel types
213/// * [`DerivationTree`] - Proof trees conclude with a `ProofExpr`
214#[derive(Debug, Clone, PartialEq)]
215pub enum ProofExpr {
216 // --- Core FOL ---
217 /// Atomic predicate: P(t1, t2, ...)
218 Predicate {
219 name: String,
220 args: Vec<ProofTerm>,
221 world: Option<String>,
222 },
223
224 /// Identity: t1 = t2
225 Identity(ProofTerm, ProofTerm),
226
227 /// Propositional atom
228 Atom(String),
229
230 // --- Logical Connectives ---
231 /// Conjunction: P ∧ Q
232 And(Box<ProofExpr>, Box<ProofExpr>),
233
234 /// Disjunction: P ∨ Q
235 Or(Box<ProofExpr>, Box<ProofExpr>),
236
237 /// Implication: P → Q
238 Implies(Box<ProofExpr>, Box<ProofExpr>),
239
240 /// Biconditional: P ↔ Q
241 Iff(Box<ProofExpr>, Box<ProofExpr>),
242
243 /// Negation: ¬P
244 Not(Box<ProofExpr>),
245
246 // --- Quantifiers ---
247 /// Universal quantification: ∀x P(x)
248 ForAll {
249 variable: String,
250 body: Box<ProofExpr>,
251 },
252
253 /// Existential quantification: ∃x P(x)
254 Exists {
255 variable: String,
256 body: Box<ProofExpr>,
257 },
258
259 // --- Modal Logic ---
260 /// Modal operator: □P or ◇P (with world semantics)
261 Modal {
262 domain: String,
263 force: f32,
264 flavor: String,
265 body: Box<ProofExpr>,
266 },
267
268 /// Counterfactual conditional: P □→ Q. Quantifies the consequent over the
269 /// closest antecedent-worlds (a similarity ordering), so it is strictly
270 /// distinct from material implication in both directions.
271 Counterfactual {
272 antecedent: Box<ProofExpr>,
273 consequent: Box<ProofExpr>,
274 },
275
276 // --- Temporal Logic ---
277 /// Temporal operator: Past(P), Future(P), Always(P), Eventually(P), Next(P)
278 Temporal {
279 operator: String,
280 body: Box<ProofExpr>,
281 },
282
283 /// Binary temporal operator: Until(P,Q), Release(P,Q), WeakUntil(P,Q)
284 TemporalBinary {
285 operator: String,
286 left: Box<ProofExpr>,
287 right: Box<ProofExpr>,
288 },
289
290 // --- Lambda Calculus (CIC extension) ---
291 /// Lambda abstraction: λx.P
292 Lambda {
293 variable: String,
294 body: Box<ProofExpr>,
295 },
296
297 /// Function application: (f x)
298 App(Box<ProofExpr>, Box<ProofExpr>),
299
300 // --- Event Semantics ---
301 /// Neo-Davidsonian event: ∃e(Verb(e) ∧ Agent(e,x) ∧ ...)
302 NeoEvent {
303 event_var: String,
304 verb: String,
305 roles: Vec<(String, ProofTerm)>,
306 },
307
308 // --- Peano / Inductive Types (CIC Extension) ---
309 /// Data Constructor: Zero, Succ(n), Cons(h, t), etc.
310 /// The building blocks of inductive types.
311 Ctor { name: String, args: Vec<ProofExpr> },
312
313 /// Pattern Matching: match n { Zero => A, Succ(k) => B }
314 /// Eliminates inductive types by case analysis.
315 Match {
316 scrutinee: Box<ProofExpr>,
317 arms: Vec<MatchArm>,
318 },
319
320 /// Recursive Function (Fixpoint): fix f. λn. ...
321 /// Defines recursive functions over inductive types.
322 Fixpoint { name: String, body: Box<ProofExpr> },
323
324 /// Typed Variable: n : Nat
325 /// Signals to the prover that induction may be applicable.
326 TypedVar { name: String, typename: String },
327
328 // --- Higher-Order Pattern Unification ---
329 /// Meta-variable (unification hole) to be solved during proof search.
330 /// Represents an unknown expression, typically a function or predicate.
331 /// Example: Hole("P") in ?P(x) = Body, to be solved as P = λx.Body
332 Hole(String),
333
334 /// Embedded term (lifts ProofTerm into ProofExpr context).
335 /// Used when a term appears where an expression is expected.
336 /// Example: App(Hole("P"), Term(BoundVarRef("x")))
337 Term(ProofTerm),
338
339 // --- Fallback ---
340 /// Unsupported construct (with description for debugging)
341 Unsupported(String),
342}
343
344// =============================================================================
345// MATCH ARM - A single case in pattern matching
346// =============================================================================
347
348/// A single arm in a match expression.
349/// Example: Succ(k) => Add(k, m)
350#[derive(Debug, Clone, PartialEq)]
351pub struct MatchArm {
352 /// The constructor being matched: "Zero", "Succ", "Cons", etc.
353 pub ctor: String,
354
355 /// Variable bindings for constructor arguments: ["k"] for Succ(k)
356 pub bindings: Vec<String>,
357
358 /// The expression to evaluate when this arm matches
359 pub body: ProofExpr,
360}
361
362impl fmt::Display for ProofExpr {
363 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
364 match self {
365 ProofExpr::Predicate { name, args, world } => {
366 write!(f, "{}", name)?;
367 if !args.is_empty() {
368 write!(f, "(")?;
369 for (i, arg) in args.iter().enumerate() {
370 if i > 0 {
371 write!(f, ", ")?;
372 }
373 write!(f, "{}", arg)?;
374 }
375 write!(f, ")")?;
376 }
377 if let Some(w) = world {
378 write!(f, " @{}", w)?;
379 }
380 Ok(())
381 }
382 ProofExpr::Identity(left, right) => write!(f, "{} = {}", left, right),
383 ProofExpr::Atom(s) => write!(f, "{}", s),
384 ProofExpr::And(left, right) => write!(f, "({} ∧ {})", left, right),
385 ProofExpr::Or(left, right) => write!(f, "({} ∨ {})", left, right),
386 ProofExpr::Implies(left, right) => write!(f, "({} → {})", left, right),
387 ProofExpr::Iff(left, right) => write!(f, "({} ↔ {})", left, right),
388 ProofExpr::Not(inner) => write!(f, "¬{}", inner),
389 ProofExpr::ForAll { variable, body } => write!(f, "∀{} {}", variable, body),
390 ProofExpr::Exists { variable, body } => write!(f, "∃{} {}", variable, body),
391 ProofExpr::Modal {
392 domain,
393 force,
394 flavor,
395 body,
396 } => {
397 write!(f, "□[{}/{}/{}]{}", domain, force, flavor, body)
398 }
399 ProofExpr::Counterfactual {
400 antecedent,
401 consequent,
402 } => {
403 write!(f, "({} □→ {})", antecedent, consequent)
404 }
405 ProofExpr::Temporal { operator, body } => write!(f, "{}({})", operator, body),
406 ProofExpr::TemporalBinary {
407 operator,
408 left,
409 right,
410 } => {
411 write!(f, "TemporalBinary({}, {}, {})", operator, left, right)
412 }
413 ProofExpr::Lambda { variable, body } => write!(f, "λ{}.{}", variable, body),
414 ProofExpr::App(func, arg) => write!(f, "({} {})", func, arg),
415 ProofExpr::NeoEvent {
416 event_var,
417 verb,
418 roles,
419 } => {
420 write!(f, "∃{}({}({})", event_var, verb, event_var)?;
421 for (role, term) in roles {
422 write!(f, " ∧ {}({}, {})", role, event_var, term)?;
423 }
424 write!(f, ")")
425 }
426 ProofExpr::Ctor { name, args } => {
427 write!(f, "{}", name)?;
428 if !args.is_empty() {
429 write!(f, "(")?;
430 for (i, arg) in args.iter().enumerate() {
431 if i > 0 {
432 write!(f, ", ")?;
433 }
434 write!(f, "{}", arg)?;
435 }
436 write!(f, ")")?;
437 }
438 Ok(())
439 }
440 ProofExpr::Match { scrutinee, arms } => {
441 write!(f, "match {} {{ ", scrutinee)?;
442 for (i, arm) in arms.iter().enumerate() {
443 if i > 0 {
444 write!(f, ", ")?;
445 }
446 write!(f, "{}", arm.ctor)?;
447 if !arm.bindings.is_empty() {
448 write!(f, "({})", arm.bindings.join(", "))?;
449 }
450 write!(f, " => {}", arm.body)?;
451 }
452 write!(f, " }}")
453 }
454 ProofExpr::Fixpoint { name, body } => write!(f, "fix {}.{}", name, body),
455 ProofExpr::TypedVar { name, typename } => write!(f, "{}:{}", name, typename),
456 ProofExpr::Unsupported(desc) => write!(f, "⟨unsupported: {}⟩", desc),
457 ProofExpr::Hole(name) => write!(f, "?{}", name),
458 ProofExpr::Term(term) => write!(f, "{}", term),
459 }
460 }
461}
462
463// =============================================================================
464// INFERENCE RULE - The logical moves available to the prover
465// =============================================================================
466
467/// The "Lever" - The specific logical move made at each proof step.
468///
469/// This enum captures HOW we moved from premises to conclusion. Each variant
470/// corresponds to a different proof strategy or logical rule.
471///
472/// # See Also
473///
474/// * [`DerivationTree`] - Each node contains an `InferenceRule`
475/// * [`certifier::certify`] - Maps inference rules to kernel terms
476/// * [`hints::suggest_hint`] - Suggests applicable rules when stuck
477/// * [`BackwardChainer`] - The engine that selects and applies rules
478///
479/// One constructor's case in a generic induction scheme
480/// ([`InferenceRule::InductionScheme`]). The derivation's premises align 1:1 with
481/// the cases, in the inductive's constructor-registration order.
482#[derive(Debug, Clone, PartialEq)]
483pub struct InductionCase {
484 /// The constructor this case eliminates (e.g. `"Succ"`, `"Node"`).
485 pub constructor: String,
486 /// The constructor's arguments, in order — each bound in the case body.
487 pub args: Vec<InductionArg>,
488}
489
490/// One argument of a constructor in an [`InductionCase`].
491#[derive(Debug, Clone, PartialEq)]
492pub struct InductionArg {
493 /// The name bound for this argument in the case body.
494 pub name: String,
495 /// Whether this argument is itself of the inductive type — a recursive
496 /// position, which therefore carries an induction hypothesis.
497 pub recursive: bool,
498}
499
500/// `ModusPonens` → `modus_ponens`. The script spelling of a rule name: a capital starts a new
501/// word, and a run of capitals (`EqualityTransitivity` has none, but a future `LHS` would) stays
502/// one word, so the transformation is a bijection on the names it is applied to.
503fn snake_case(name: &str) -> String {
504 let mut out = String::with_capacity(name.len() + 4);
505 let chars: Vec<char> = name.chars().collect();
506 for (i, c) in chars.iter().enumerate() {
507 if c.is_ascii_uppercase() && i > 0 {
508 let prev_lower = chars[i - 1].is_ascii_lowercase() || chars[i - 1].is_ascii_digit();
509 let next_lower = chars.get(i + 1).is_some_and(|n| n.is_ascii_lowercase());
510 if prev_lower || next_lower {
511 out.push('_');
512 }
513 }
514 out.push(c.to_ascii_lowercase());
515 }
516 out
517}
518
519#[derive(Debug, Clone, PartialEq)]
520pub enum InferenceRule {
521 // --- Basic FOL ---
522 /// Direct match with a known fact in the Context/KnowledgeBase.
523 /// Logic: Γ, P ⊢ P
524 PremiseMatch,
525
526 /// Logic: P → Q, P ⊢ Q
527 ModusPonens,
528
529 /// Logic: ¬Q, P → Q ⊢ ¬P
530 ModusTollens,
531
532 /// Logic: P, Q ⊢ P ∧ Q
533 ConjunctionIntro,
534
535 /// Logic: P ∧ Q ⊢ P (or Q)
536 ConjunctionElim,
537
538 /// Logic: P ⊢ P ∨ Q
539 DisjunctionIntro,
540
541 /// Logic: P ∨ Q, P → R, Q → R ⊢ R
542 DisjunctionElim,
543
544 /// Logic: ⊥ ⊢ anything (ex falso quodlibet). The single premise concludes `False`.
545 ExFalso,
546
547 /// Logic: assume P, derive Q ⊢ P → Q (implication introduction / →I). The
548 /// single premise proves Q with P bound as a local hypothesis.
549 ImpliesIntro,
550
551 /// Logic: prove P → Q and Q → P ⊢ P ↔ Q (biconditional introduction / ↔I).
552 BicondIntro,
553
554 /// Logic: ¬¬P ⊢ P (and P ⊢ ¬¬P)
555 DoubleNegation,
556
557 /// Logic: classical reductio (proof by contradiction) — assume ¬G, derive ⊥ ⊢ G,
558 /// discharged through the `dne` axiom. The single premise concludes `False` with
559 /// ¬G bound as a local hypothesis.
560 ClassicalReductio,
561
562 // --- Quantifiers ---
563 /// Logic: ∀x P(x) ⊢ P(c)
564 /// Stores the specific term 'c' used to instantiate the universal.
565 UniversalInst(String),
566
567 /// Logic: ∀x P(x) ⊢ P(t) at an arbitrary witness TERM (a compound like
568 /// `add(a, Zero)`, not just a name). `UniversalInst` keeps the name-only
569 /// fast path; this carries the full term for instantiations that
570 /// `simp`/`crush` produce by matching.
571 UniversalInstTerm(ProofTerm),
572
573 /// Logic: Γ, x:T ⊢ P(x) implies Γ ⊢ ∀x:T. P(x)
574 /// Stores variable name and type name for Lambda construction.
575 UniversalIntro { variable: String, var_type: String },
576
577 /// Logic: P(w) ⊢ ∃x.P(x)
578 /// Carries the witness and its type for kernel certification.
579 ExistentialIntro {
580 witness: String,
581 witness_type: String,
582 },
583
584 /// Logic: P(t) ⊢ ∃x.P(x) at an arbitrary witness TERM — `use (n + 1)`, `use (f x)`,
585 /// the compound witnesses Lean's `exists`/`use` takes. [`InferenceRule::ExistentialIntro`]
586 /// carries its witness as a `String`, which the certifier can only resolve as one NAME, so
587 /// `add(n, 1)` certified to a global literally called `"add(n, 1)"` that no context
588 /// declares. This carries the term, exactly as [`InferenceRule::UniversalInstTerm`] sits
589 /// beside [`InferenceRule::UniversalInst`] for the dual quantifier.
590 ///
591 /// `witness_type` is the ∃-binder's DOMAIN, not the witness's own type name: it must be
592 /// the domain `certifier::proof_expr_to_type` gives the same `Exists`, or the certified
593 /// term's type and the goal type disagree. Both sides read it from one function,
594 /// `certifier::existential_domain`.
595 ExistentialIntroTerm {
596 witness: ProofTerm,
597 witness_type: String,
598 },
599
600 // --- Modal Logic (World Moves) ---
601 /// Logic: □P (in w0), Accessible(w0, w1) ⊢ P (in w1)
602 /// "Necessity Elimination" / "Distribution"
603 ModalAccess,
604
605 /// Logic: If P is true in ALL accessible worlds ⊢ □P
606 /// "Necessity Introduction"
607 ModalGeneralization,
608
609 // --- Temporal Logic ---
610 /// Logic: t1 < t2, t2 < t3 ⊢ t1 < t3
611 TemporalTransitivity,
612
613 /// Logic: P(s₀), ∀s(P(s) → P(next(s))) ⊢ G(P)
614 /// Standard k-induction for hardware safety properties.
615 TemporalInduction,
616
617 /// Logic: G(P) ⊢ P ∧ X(G(P))
618 /// Fixpoint unfolding of Always.
619 TemporalUnfolding,
620
621 /// Logic: P(w) ⊢ F(P) for witness world w
622 /// Prove Eventually by exhibiting a reachable witness.
623 EventualityProgress,
624
625 /// Logic: Induction on trace length for P U Q
626 UntilInduction,
627
628 // --- Peano / Inductive Reasoning (CIC seed) ---
629 /// Logic: P(0), ∀k(P(k) → P(S(k))) ⊢ ∀n P(n)
630 /// Stores the variable name, its inductive type, and the step variable used.
631 StructuralInduction {
632 variable: String, // "n" - the induction variable
633 ind_type: String, // "Nat" - the inductive type
634 step_var: String, // "k" - the predecessor variable (for IH matching)
635 },
636
637 /// Logic: generic structural induction over ANY inductive type. Generalizes
638 /// [`InferenceRule::StructuralInduction`] (fixed to the nullary-base + unary-step
639 /// Nat shape) to an arbitrary constructor set — one premise per constructor, in
640 /// registration order, each recursive argument carrying its own induction
641 /// hypothesis. Certifies to a `Fix` over an N-ary `Match`: the dependent
642 /// eliminator the kernel re-checks for coverage, case types, and termination.
643 InductionScheme {
644 variable: String, // the induction variable, e.g. "t"
645 ind_type: String, // the inductive type, e.g. "Tree"
646 cases: Vec<InductionCase>, // one per constructor, in registration order
647 },
648
649 // --- Linear arithmetic (order) ---
650 /// `a ≤ b`, `b ≤ c` ⊢ `a ≤ c` over `Int`. The middle term is recovered from
651 /// the first premise's conclusion. Certifies to `le_trans a b c p₀ p₁`.
652 /// Inequalities are encoded as the Prop `Eq Bool (le a b) true`.
653 LeTrans,
654
655 /// `⊢ a ≤ a` over `Int`. Certifies to `le_refl a`.
656 LeRefl,
657
658 /// `a ≤ b`, `c ≤ d` ⊢ `a + c ≤ b + d` over `Int`. The four operands are read
659 /// from the conclusion `le(add a c, add b d) = true`; `premise[0]` proves
660 /// `a ≤ b`, `premise[1]` proves `c ≤ d`. Certifies to `le_add_mono a b c d p₀ p₁`.
661 LeAddMono,
662
663 /// Linear contradiction: `premise[0]` proves `le(m, n) = true` for ground `m > n`
664 /// (so `le m n ⇝ false`, the Prop is `Eq Bool false true`). Concludes `⊥` via the
665 /// `Bool` no-confusion discriminator. Lets contradictory bounds prove anything.
666 LinFalse,
667
668 /// `0 ≤ k`, `a ≤ b` ⊢ `k·a ≤ k·b` — scale an inequality by a non-negative `k`.
669 /// Operands from the conclusion `le(mul k a, mul k b) = true`; `premise[0]` proves
670 /// `0 ≤ k`, `premise[1]` proves `a ≤ b`. Certifies to `le_mul_nonneg k a b p₀ p₁`.
671 /// A Farkas-reconstruction primitive.
672 LeMulNonneg,
673
674 /// `a ≤ b` ⊢ `0 ≤ b - a` — move an inequality to one side. Operands from the
675 /// conclusion `le(0, sub b a) = true`; `premise[0]` proves `a ≤ b`. Certifies to
676 /// `le_sub a b p₀`. The Farkas "collect to a single side" primitive.
677 LeSub,
678
679 /// `a < b` ⊢ `(a + 1) ≤ b` — integer DISCRETENESS. Operands from the conclusion
680 /// `le(add a 1, b) = true`; `premise[0]` proves `a < b` (`lt(a,b) = true`).
681 /// Certifies to `lt_succ_le a b p₀`. This is the one step rational Fourier-Motzkin
682 /// lacks — the `omega` primitive that refutes strict systems the rational solver
683 /// reports satisfiable.
684 LtSuccLe,
685
686 /// `a < (b + 1)` ⊢ `a ≤ b` — the upper-side discreteness companion. Operands
687 /// from the conclusion `le(a, b) = true`; `premise[0]` proves `a < b+1`
688 /// (`lt(a, add b 1) = true`). Certifies to `lt_add1_le a b p₀`. Preferred over
689 /// `LtSuccLe` when the strict bound is already `b+1`, since it cancels the
690 /// constant instead of propagating it into the Farkas reconstruction.
691 LtAdd1Le,
692
693 /// `(a + 1) ≤ b` ⊢ `a < b` — the CONVERSE of [`InferenceRule::LtSuccLe`], and the only
694 /// way to CONCLUDE a strict inequality about symbolic operands. Operands are read from the
695 /// conclusion `lt(a, b) = true`; `premise[0]` proves `le(add a 1, b) = true`. Certifies to
696 /// `le_succ_lt a b p₀`.
697 ///
698 /// **It needs a prelude axiom that is not registered yet.** Of the `Int` order axioms in
699 /// the trusted base, NONE concludes a `lt`: `lt_succ_le` and `lt_add1_le` both take one as
700 /// a PREMISE, so a relation chain can compose a strict step but can only state its result
701 /// in the tightened form `a + 1 ≤ d`. Adding `le_succ_lt : Π a b. (a + 1) ≤ b → a < b`
702 /// closes that, and it is a ledger decision (`tcb_ledger_lock`'s `DEFINABLE_CEILING`), not
703 /// a tactic one — Lean PROVES this, because its `Int` is an inductive.
704 ///
705 /// The strictly better move, which costs no axiom at all and REMOVES two, is to make `lt`
706 /// a DEFINITION (`lt a b := le (add a 1) b`) instead of an opaque primitive: `lt_succ_le`
707 /// and `lt_add1_le` then hold by conversion and leave the ledger, and `a < b` becomes
708 /// definitionally `a + 1 ≤ b`, so this rule is not needed either.
709 ///
710 /// Until one of those lands, nothing CONSTRUCTS this rule: every producer asks
711 /// `engine::strict_conclusions_available` first, so no tree is ever built that the
712 /// kernel would have to refuse.
713 LeSuccLt,
714
715 /// `⊢ (a ≤ b) ∨ (b ≤ a)` over `Int` — LINEAR-ORDER TOTALITY, a leaf (no premises).
716 /// Certifies to `le_total a b`, whose operands are read from the conclusion
717 /// `Or (le(a,b) = true) (le(b,a) = true)`.
718 ///
719 /// This is the GOAL-DIRECTED half of `omega`. A refutation engine only ever proves `⊥`;
720 /// a decision procedure proves the goal, and the way it does that is to assume the goal
721 /// false and refute. Totality is the sound, axiom-free approximation of that assumption
722 /// for a `≤` goal: split on `le_total a b`, take the goal itself in the left branch, and
723 /// refute the hypotheses together with `b ≤ a` in the right. It reaches every goal whose
724 /// negation-by-totality is refutable; the strictly larger fragment (`¬(a ≤ b) ⟹ b+1 ≤ a`)
725 /// needs an axiom the trusted base does not have, and is deliberately NOT assumed here.
726 LeTotal,
727
728 // --- Equality ---
729 /// Leibniz's Law / Substitution of Equals
730 /// Logic: a = b, P(a) ⊢ P(b)
731 /// The equality proof is in `premise\[0\]`, the P(a) proof is in `premise\[1\]`.
732 /// Carries the original term and replacement term for certification.
733 Rewrite { from: ProofTerm, to: ProofTerm },
734
735 /// POSITIONAL Leibniz: like [`InferenceRule::Rewrite`], but abstracting exactly ONE
736 /// occurrence of `to` in the conclusion — the `occurrence`-th, counted left-to-right in
737 /// the same pre-order walk the tactic layer uses.
738 ///
739 /// `Rewrite` carries no position, and the `Eq_rec` motive it builds abstracts EVERY
740 /// occurrence, so `P(a, a)` rewritten by `a = b` could only ever become `P(b, b)`. That
741 /// is why Lean has `conv` and occurrence arguments at all: `P(b, a)` is a different (and
742 /// frequently the only provable) goal. A caller that rewrote one occurrence had nowhere
743 /// to record which, so the trust door could not follow it.
744 ///
745 /// The kernel is the check on the index: `Eq_rec` demands the source premise prove
746 /// `P from`, so an index that abstracted the wrong occurrence yields a motive the source
747 /// subgoal does not inhabit and the proof is REFUSED. A wrong position cannot be unsound,
748 /// only unprovable.
749 RewriteAt {
750 from: ProofTerm,
751 to: ProofTerm,
752 occurrence: usize,
753 },
754
755 /// Symmetry of Equality: a = b ⊢ b = a
756 EqualitySymmetry,
757
758 /// Transitivity of Equality: a = b, b = c ⊢ a = c
759 EqualityTransitivity,
760
761 /// Reflexivity of Equality: a = a (after normalization)
762 /// Used when both sides of an identity reduce to the same normal form.
763 Reflexivity,
764
765 /// Arithmetic decision: an `Int` equality discharged by the proof-producing
766 /// arithmetic oracle ([`crate::arith::prove_int_eq`]) into a kernel-checked
767 /// proof (computation + the ring axioms). The conclusion is the `Identity`.
768 ArithDecision,
769
770 /// Proof by kernel evaluation: a closed decidable proposition (a ground
771 /// comparison or Bool/Nat equality) discharged via `native_decide`. The
772 /// leaf carries only the claim; certification re-runs the evaluator and
773 /// the kernel checks the resulting `of_decide_eq_true`/`ofReduceBool`
774 /// term, so a lying leaf is rejected.
775 NativeDecide,
776
777 /// Proof by ground REFUTATION: the conclusion is `¬P` for a closed `P` that COMPUTES
778 /// FALSE. A leaf — like [`InferenceRule::NativeDecide`], it carries only the claim, and
779 /// certification re-runs the computation, so a lying leaf certifies to nothing.
780 ///
781 /// The dual `NativeDecide` lacks is the reason `decide` had no `ProofExpr::Not` arm at
782 /// all: a `Decidable` instance decides `P` true through `of_decide_eq_true`, and the
783 /// false direction needs `of_decide_eq_false`, which the trusted base does not register.
784 /// No axiom is needed, because `Bool` is an inductive with two constructors and its
785 /// no-confusion discriminator is already how a ground-false inequality becomes `⊥`
786 /// ([`InferenceRule::LinFalse`]): a ground `Int` disequality transports `le a a` (true by
787 /// computation) along the assumed equality into `le a b` (false by computation) with
788 /// `Eq_rec`, and a ground `Bool` disequality is that contradiction already.
789 GroundRefutation,
790
791 // --- Fallbacks ---
792 /// "The User Said So." Used for top-level axioms.
793 Axiom,
794
795 /// "The Machine Said So." (Z3 Oracle)
796 /// The string contains the solver's justification.
797 OracleVerification(String),
798
799 /// Proof by Contradiction (Reductio ad Absurdum)
800 /// Logic: Assume ¬C, derive P ∧ ¬P (contradiction), conclude C
801 /// Or: Assume P, derive Q ∧ ¬Q, conclude ¬P
802 ReductioAdAbsurdum,
803
804 /// Contradiction detected in premises: P and ¬P both hold
805 /// Logic: P, ¬P ⊢ ⊥ (ex falso quodlibet)
806 Contradiction,
807
808 // --- Quantifier Elimination ---
809 /// Existential Elimination (Skolemization in a proof context)
810 /// Logic: ∃x.P(x), [c fresh] P(c) ⊢ Goal implies ∃x.P(x) ⊢ Goal
811 /// The witness c must be fresh (not appearing in Goal).
812 ExistentialElim { witness: String },
813
814 /// Case Analysis on a formula `C` whose two cases both reach absurdity.
815 /// Logic: (C → ⊥), (¬C → ⊥) ⊢ ⊥ — note this is the *intuitionistic* form
816 /// (build `¬C` and `¬¬C`, then apply), so certifying it needs no excluded
817 /// middle. Used for self-referential paradoxes like the Barber Paradox.
818 ///
819 /// `case_formula` carries the actual proposition `C` (not a rendered string)
820 /// so the certifier can build the case lambdas' parameter types and bind `C`
821 /// / `¬C` as local hypotheses in each branch.
822 CaseAnalysis { case_formula: Box<ProofExpr> },
823
824 /// Logic: `A ∨ B`, `A ⊢ C`, `B ⊢ C` ⊢ `C` — disjunction elimination to a common
825 /// conclusion (here always `⊥`, for the grounded-grid contradiction prover).
826 /// Premises: `[A∨B, left-branch (C assuming A), right-branch (C assuming B)]`.
827 /// Unlike `DisjunctionElim` (disjunctive syllogism, which needs a refuted
828 /// disjunct) this eliminates BOTH disjuncts by case analysis — the move a grid's
829 /// of-pair / either-or / closure clause needs. The disjuncts (and, when a disjunct
830 /// is a conjunction, each of its conjuncts) are bound as local hypotheses in the
831 /// respective branch, so a branch may reference them directly.
832 DisjunctionCases,
833}
834
835impl InferenceRule {
836 /// Why [`certifier::certify`] cannot turn this rule into a kernel term —
837 /// `None` when it can.
838 ///
839 /// **This is the list a proof PRODUCER must consult before it emits a tree.**
840 /// A [`DerivationTree`] is an ordinary Rust value: it can be built with any
841 /// variant, it passes every Rust type check, and a rule with no certifier arm
842 /// fails only at [`verify::check_derivation`] — surfacing as a
843 /// `verification_error` that reads like a kernel limitation rather than what
844 /// it is, a tree that was never certifiable. Selecting a rule by NAME is how
845 /// that happens: `TemporalTransitivity` looks exactly right for `t₁ < t₂`,
846 /// `t₂ < t₃` ⊢ `t₁ < t₃`, and it is dead.
847 ///
848 /// Existence in this enum is not evidence of implementation. The match below
849 /// is EXHAUSTIVE and so is `certify`'s — adding a variant without deciding
850 /// both is a compile error, which is the only thing that keeps the enum and
851 /// the certifier from drifting apart.
852 pub fn uncertifiable_reason(&self) -> Option<&'static str> {
853 match self {
854 // --- Modal and temporal: DECLARED, never implemented. -------------
855 // Nothing in any engine constructs these, `certify` has no arm for
856 // any of them, and each names a proof shape with a perfectly good
857 // translation into live rules. Each reason states that translation,
858 // so a producer that reached for the name can rebuild the tree.
859 InferenceRule::ModalAccess => Some(
860 "no certifier arm: modal necessity-elimination is unimplemented. Express \
861 `□P` as `∀v. Accessible(w, v) → P(v)` and use UniversalInst + ModusPonens",
862 ),
863 InferenceRule::ModalGeneralization => Some(
864 "no certifier arm: modal necessity-introduction is unimplemented. Express \
865 `□P` as `∀v. Accessible(w, v) → P(v)` and use UniversalIntro",
866 ),
867 InferenceRule::TemporalTransitivity => Some(
868 "no certifier arm: temporal-order transitivity is unimplemented. A time \
869 order is an ordinary order — use LeTrans on `≤`, or the `<` chain it \
870 tightens to",
871 ),
872 InferenceRule::TemporalInduction => Some(
873 "no certifier arm: k-induction over a trace is unimplemented. Induct on \
874 the trace index with StructuralInduction / InductionScheme",
875 ),
876 InferenceRule::TemporalUnfolding => Some(
877 "no certifier arm: fixpoint unfolding of `Always` is unimplemented. \
878 Express `G P` as `∀n. P n` and use ConjunctionIntro over its \
879 instantiations",
880 ),
881 InferenceRule::EventualityProgress => Some(
882 "no certifier arm: `Eventually` by witness is unimplemented. Express \
883 `F P` as `∃n. P n` and use ExistentialIntro",
884 ),
885 InferenceRule::UntilInduction => Some(
886 "no certifier arm: induction for `P U Q` is unimplemented. Express it as \
887 `∃k. Q k ∧ ∀j < k. P j` and use ExistentialIntro + ConjunctionIntro",
888 ),
889
890 // --- Deliberately outside the trusted base. ----------------------
891 InferenceRule::OracleVerification(_) => Some(
892 "refused by design: an SMT oracle attests satisfiability but hands back no \
893 checkable proof term, so it can never become a kernel certificate. For \
894 arithmetic, ArithDecision is the proof-producing route",
895 ),
896
897 // --- Everything below has a real arm in `certifier::certify`. ----
898 InferenceRule::PremiseMatch
899 | InferenceRule::ModusPonens
900 | InferenceRule::ModusTollens
901 | InferenceRule::ConjunctionIntro
902 | InferenceRule::ConjunctionElim
903 | InferenceRule::DisjunctionIntro
904 | InferenceRule::DisjunctionElim
905 | InferenceRule::ExFalso
906 | InferenceRule::ImpliesIntro
907 | InferenceRule::BicondIntro
908 | InferenceRule::DoubleNegation
909 | InferenceRule::ClassicalReductio
910 | InferenceRule::UniversalInst(_)
911 | InferenceRule::UniversalInstTerm(_)
912 | InferenceRule::UniversalIntro { .. }
913 | InferenceRule::ExistentialIntro { .. }
914 | InferenceRule::ExistentialIntroTerm { .. }
915 | InferenceRule::StructuralInduction { .. }
916 | InferenceRule::InductionScheme { .. }
917 | InferenceRule::LeTrans
918 | InferenceRule::LeRefl
919 | InferenceRule::LeAddMono
920 | InferenceRule::LinFalse
921 | InferenceRule::LeMulNonneg
922 | InferenceRule::LeSub
923 | InferenceRule::LtSuccLe
924 | InferenceRule::LtAdd1Le
925 | InferenceRule::LeSuccLt
926 | InferenceRule::LeTotal
927 | InferenceRule::Rewrite { .. }
928 | InferenceRule::RewriteAt { .. }
929 | InferenceRule::EqualitySymmetry
930 | InferenceRule::EqualityTransitivity
931 | InferenceRule::Reflexivity
932 | InferenceRule::ArithDecision
933 | InferenceRule::NativeDecide
934 | InferenceRule::GroundRefutation
935 | InferenceRule::Axiom
936 | InferenceRule::ReductioAdAbsurdum
937 | InferenceRule::Contradiction
938 | InferenceRule::ExistentialElim { .. }
939 | InferenceRule::CaseAnalysis { .. }
940 | InferenceRule::DisjunctionCases => None,
941 }
942 }
943
944 /// Rewrite every NAME, TERM and PROPOSITION this rule carries in its PAYLOAD.
945 ///
946 /// Two places in this crate rename a rigid eigen-CONSTANT back to the variable it stands
947 /// for, and a renaming that reaches a node's conclusion but not the payload of the rule
948 /// that justifies it produces a tree whose motive, witness or case formula is about a name
949 /// the conclusion no longer mentions — the certifier then computes against one proposition
950 /// and checks another, and refuses a correct proof. Each of the two walkers had its own
951 /// `match` with an `other => other.clone()` catch-all, and each caught a DIFFERENT subset:
952 /// `engine::rewrite_tree_const_to_var` covered `UniversalInst`, `ExistentialIntro`,
953 /// `ExistentialElim`, `Rewrite` and `CaseAnalysis`; `tactic::eigen_to_var_tree` covered
954 /// `Rewrite` alone. NEITHER covered `RewriteAt`, `UniversalInstTerm` or
955 /// `ExistentialIntroTerm` — the three payload-carrying rules added after they were written,
956 /// which is exactly what a catch-all guarantees will happen again.
957 ///
958 /// This is that decision, once, and the match is EXHAUSTIVE: a rule variant added later
959 /// cannot silently keep a stale name in its payload, because adding one without deciding
960 /// its arm here is a compile error.
961 ///
962 /// Binder names a rule INTRODUCES (`UniversalIntro`'s variable, `StructuralInduction`'s
963 /// induction and step variables, `InductionScheme`'s case arguments) are deliberately left
964 /// alone: they are not references to anything outside the node, and renaming one would
965 /// change which variable the eliminator abstracts.
966 pub fn map_payload(
967 &self,
968 name: &dyn Fn(&str) -> String,
969 term: &dyn Fn(&ProofTerm) -> ProofTerm,
970 expr: &dyn Fn(&ProofExpr) -> ProofExpr,
971 ) -> InferenceRule {
972 match self {
973 // --- Payloads that NAME a term the surrounding proof also mentions. ----------
974 InferenceRule::UniversalInst(witness) => InferenceRule::UniversalInst(name(witness)),
975 InferenceRule::ExistentialIntro { witness, witness_type } => {
976 InferenceRule::ExistentialIntro {
977 witness: name(witness),
978 witness_type: witness_type.clone(),
979 }
980 }
981 InferenceRule::ExistentialElim { witness } => {
982 InferenceRule::ExistentialElim { witness: name(witness) }
983 }
984
985 // --- Payloads that ARE terms. ------------------------------------------------
986 InferenceRule::UniversalInstTerm(witness) => {
987 InferenceRule::UniversalInstTerm(term(witness))
988 }
989 InferenceRule::ExistentialIntroTerm { witness, witness_type } => {
990 InferenceRule::ExistentialIntroTerm {
991 witness: term(witness),
992 witness_type: witness_type.clone(),
993 }
994 }
995 InferenceRule::Rewrite { from, to } => {
996 InferenceRule::Rewrite { from: term(from), to: term(to) }
997 }
998 InferenceRule::RewriteAt { from, to, occurrence } => InferenceRule::RewriteAt {
999 from: term(from),
1000 to: term(to),
1001 occurrence: *occurrence,
1002 },
1003
1004 // --- The one payload that is a PROPOSITION. ----------------------------------
1005 InferenceRule::CaseAnalysis { case_formula } => {
1006 InferenceRule::CaseAnalysis { case_formula: Box::new(expr(case_formula)) }
1007 }
1008
1009 // --- Binders the rule introduces, type NAMES, and the oracle's justification
1010 // string: nothing here refers outward, so nothing here is renamed.
1011 InferenceRule::UniversalIntro { .. }
1012 | InferenceRule::StructuralInduction { .. }
1013 | InferenceRule::InductionScheme { .. }
1014 | InferenceRule::OracleVerification(_)
1015 // --- …and every payload-free rule.
1016 | InferenceRule::PremiseMatch
1017 | InferenceRule::ModusPonens
1018 | InferenceRule::ModusTollens
1019 | InferenceRule::ConjunctionIntro
1020 | InferenceRule::ConjunctionElim
1021 | InferenceRule::DisjunctionIntro
1022 | InferenceRule::DisjunctionElim
1023 | InferenceRule::ExFalso
1024 | InferenceRule::ImpliesIntro
1025 | InferenceRule::BicondIntro
1026 | InferenceRule::DoubleNegation
1027 | InferenceRule::ClassicalReductio
1028 | InferenceRule::ModalAccess
1029 | InferenceRule::ModalGeneralization
1030 | InferenceRule::TemporalTransitivity
1031 | InferenceRule::TemporalInduction
1032 | InferenceRule::TemporalUnfolding
1033 | InferenceRule::EventualityProgress
1034 | InferenceRule::UntilInduction
1035 | InferenceRule::LeTrans
1036 | InferenceRule::LeRefl
1037 | InferenceRule::LeAddMono
1038 | InferenceRule::LinFalse
1039 | InferenceRule::LeMulNonneg
1040 | InferenceRule::LeSub
1041 | InferenceRule::LtSuccLe
1042 | InferenceRule::LtAdd1Le
1043 | InferenceRule::LeSuccLt
1044 | InferenceRule::LeTotal
1045 | InferenceRule::EqualitySymmetry
1046 | InferenceRule::EqualityTransitivity
1047 | InferenceRule::Reflexivity
1048 | InferenceRule::ArithDecision
1049 | InferenceRule::NativeDecide
1050 | InferenceRule::GroundRefutation
1051 | InferenceRule::Axiom
1052 | InferenceRule::ReductioAdAbsurdum
1053 | InferenceRule::Contradiction
1054 | InferenceRule::DisjunctionCases => self.clone(),
1055 }
1056 }
1057
1058 /// Every rule that can be applied from a NAME alone — the payload-free variants, whose
1059 /// application is fixed by the goal and the facts in scope.
1060 ///
1061 /// A rule carrying an argument is deliberately absent: `Rewrite` needs its equation,
1062 /// `UniversalInstTerm` its witness, `StructuralInduction` its variable, and a name cannot
1063 /// supply any of them. Those have their own tactics (`rewrite`, `exists`, `induction`),
1064 /// and reporting the absence is more useful than guessing the argument.
1065 ///
1066 /// The seven declared-but-unimplemented rules ARE here. `by_rule` looks them up, finds
1067 /// [`InferenceRule::uncertifiable_reason`] and reports that reason — which is the whole
1068 /// point of the list: a producer that reached for a dead name learns it is dead, instead
1069 /// of watching a search fail for no stated cause.
1070 pub const NAMEABLE: &'static [InferenceRule] = &[
1071 InferenceRule::PremiseMatch,
1072 InferenceRule::ModusPonens,
1073 InferenceRule::ModusTollens,
1074 InferenceRule::ConjunctionIntro,
1075 InferenceRule::ConjunctionElim,
1076 InferenceRule::DisjunctionIntro,
1077 InferenceRule::DisjunctionElim,
1078 InferenceRule::DisjunctionCases,
1079 InferenceRule::ExFalso,
1080 InferenceRule::ImpliesIntro,
1081 InferenceRule::BicondIntro,
1082 InferenceRule::DoubleNegation,
1083 InferenceRule::ClassicalReductio,
1084 InferenceRule::ReductioAdAbsurdum,
1085 InferenceRule::Contradiction,
1086 InferenceRule::Axiom,
1087 InferenceRule::EqualitySymmetry,
1088 InferenceRule::EqualityTransitivity,
1089 InferenceRule::Reflexivity,
1090 InferenceRule::LeTrans,
1091 InferenceRule::LeRefl,
1092 InferenceRule::LeAddMono,
1093 InferenceRule::LeMulNonneg,
1094 InferenceRule::LeSub,
1095 InferenceRule::LinFalse,
1096 InferenceRule::LtSuccLe,
1097 InferenceRule::LtAdd1Le,
1098 InferenceRule::LeSuccLt,
1099 InferenceRule::LeTotal,
1100 InferenceRule::ArithDecision,
1101 InferenceRule::NativeDecide,
1102 InferenceRule::GroundRefutation,
1103 InferenceRule::ModalAccess,
1104 InferenceRule::ModalGeneralization,
1105 InferenceRule::TemporalTransitivity,
1106 InferenceRule::TemporalInduction,
1107 InferenceRule::TemporalUnfolding,
1108 InferenceRule::EventualityProgress,
1109 InferenceRule::UntilInduction,
1110 ];
1111
1112 /// Resolve a rule NAME, as a proof script or a translator spells it: the variant's own
1113 /// name (`ModusPonens`) or its snake_case form (`modus_ponens`). Nothing else — a
1114 /// case-insensitive or punctuation-insensitive match would quietly accept `MODUSPONENS`
1115 /// and make a typo indistinguishable from a rule that does not exist.
1116 pub fn from_name(name: &str) -> Option<InferenceRule> {
1117 InferenceRule::NAMEABLE
1118 .iter()
1119 .find(|r| {
1120 let canonical = r.canonical_name();
1121 name == canonical || name == snake_case(&canonical)
1122 })
1123 .cloned()
1124 }
1125
1126 /// This rule's canonical name. A payload-free variant renders as its bare variant name —
1127 /// the spelling [`InferenceRule::from_name`] accepts; a payload-carrying one renders with
1128 /// its payload, which is what a derivation dump wants and what `from_name` deliberately
1129 /// cannot read back.
1130 pub fn canonical_name(&self) -> String {
1131 format!("{self:?}")
1132 }
1133
1134 /// Whether [`certifier::certify`] has an arm that builds a kernel term for
1135 /// this rule. The negation of [`InferenceRule::uncertifiable_reason`].
1136 pub fn is_certifiable(&self) -> bool {
1137 self.uncertifiable_reason().is_none()
1138 }
1139}
1140
1141// =============================================================================
1142// DERIVATION TREE - The recursive proof structure
1143// =============================================================================
1144
1145/// The "Euclidean Structure" - A recursive tree representing the proof.
1146///
1147/// This is the object returned by the Prover. It allows the UI to render
1148/// a step-by-step explanation (Natural Language Generation).
1149///
1150/// # Structure
1151///
1152/// Each node contains:
1153/// - `conclusion`: The proposition proved at this step
1154/// - `rule`: The logical rule applied (how we know the conclusion)
1155/// - `premises`: Sub-proofs justifying the rule's requirements
1156/// - `substitution`: Variable bindings from unification
1157///
1158/// # See Also
1159///
1160/// * [`BackwardChainer::prove`] - Creates derivation trees
1161/// * [`InferenceRule`] - The rules that justify each step
1162/// * [`ProofExpr`] - The conclusion type
1163/// * [`certifier::certify`] - Converts trees to kernel terms
1164/// * [`hints::suggest_hint`] - Suggests next steps when stuck
1165#[derive(Debug, Clone)]
1166pub struct DerivationTree {
1167 /// The logical statement proved at this node.
1168 pub conclusion: ProofExpr,
1169
1170 /// The rule applied to justify this conclusion.
1171 pub rule: InferenceRule,
1172
1173 /// The sub-proofs that validate the requirements of the rule.
1174 /// Example: ModusPonens will have 2 children (The Implication, The Antecedent).
1175 pub premises: Vec<DerivationTree>,
1176
1177 /// The depth of the tree (used for complexity limits).
1178 pub depth: usize,
1179
1180 /// The bindings unification discovered at this step — SEARCH TELEMETRY, not part of the
1181 /// claim.
1182 ///
1183 /// Ten sites in [`BackwardChainer`] write it and NOTHING in the repository reads it: not
1184 /// [`certifier::certify`], not [`verify::check_derivation`], not the derivation-document writer. Only the two
1185 /// eigenconstant-renaming walkers touch it, and they only carry it along. So a rule that
1186 /// recorded a substitution INSTEAD of instantiating its own conclusion would be believed by
1187 /// nobody and checked by nobody — the certified term would prove one proposition while the
1188 /// node claimed another, and every rule that computes from its own conclusion (a motive, a
1189 /// rewrite's endpoints) would compute from the stale one.
1190 ///
1191 /// What keeps that from happening is an invariant, not a checker: **a node's conclusion is a
1192 /// fixed point of its own substitution.** Every writer either applies it to the conclusion
1193 /// first or binds only variables the conclusion does not carry. It is locked by
1194 /// `T_tactics_extra::no_certified_node_records_a_substitution_its_conclusion_has_not_taken`,
1195 /// which sweeps the chainer and checks it directly — keep that green, or give the field a
1196 /// reader.
1197 pub substitution: unify::Substitution,
1198}
1199
1200impl DerivationTree {
1201 /// Constructs a new Proof Node.
1202 /// Automatically calculates depth based on children.
1203 pub fn new(conclusion: ProofExpr, rule: InferenceRule, premises: Vec<DerivationTree>) -> Self {
1204 let max_depth = premises.iter().map(|p| p.depth).max().unwrap_or(0);
1205 Self {
1206 conclusion,
1207 rule,
1208 premises,
1209 depth: max_depth + 1,
1210 substitution: unify::Substitution::new(),
1211 }
1212 }
1213
1214 /// A leaf node (usually a Premise, Axiom, or Oracle result).
1215 pub fn leaf(conclusion: ProofExpr, rule: InferenceRule) -> Self {
1216 Self::new(conclusion, rule, vec![])
1217 }
1218
1219 /// Set the substitution for this derivation step.
1220 pub fn with_substitution(mut self, subst: unify::Substitution) -> Self {
1221 self.substitution = subst;
1222 self
1223 }
1224
1225 /// Every node of this tree whose rule [`certifier::certify`] cannot build, as
1226 /// `(rule, why)` pairs in pre-order — empty when the whole tree is certifiable.
1227 ///
1228 /// **A proof PRODUCER runs this before handing the tree to
1229 /// [`verify::check_derivation`].** A `DerivationTree` is an ordinary Rust value:
1230 /// any rule can be put in any node, the result type-checks, and a dead rule is
1231 /// discovered only when certification reaches it — as a `verification_error`
1232 /// that reads like the kernel refusing a proof. Asking here instead makes the
1233 /// answer structural and keeps it where the producer can act on it: rebuild the
1234 /// node out of live rules, or reject the input.
1235 ///
1236 /// The dead rule is usually not at the root. A root of `ExFalso` over a subtree
1237 /// justified by `TemporalUnfolding` is well-formed everywhere except the one
1238 /// node that matters, which is why this walks the whole tree rather than
1239 /// answering about `self.rule`.
1240 pub fn uncertifiable_rules(&self) -> Vec<(String, &'static str)> {
1241 let mut out = Vec::new();
1242 self.collect_uncertifiable(&mut out);
1243 out
1244 }
1245
1246 fn collect_uncertifiable(&self, out: &mut Vec<(String, &'static str)>) {
1247 if let Some(why) = self.rule.uncertifiable_reason() {
1248 out.push((format!("{:?}", self.rule), why));
1249 }
1250 for premise in &self.premises {
1251 premise.collect_uncertifiable(out);
1252 }
1253 }
1254
1255 /// Renders the proof as a text-based tree (for debugging/CLI).
1256 pub fn display_tree(&self) -> String {
1257 self.display_recursive(0)
1258 }
1259
1260 fn display_recursive(&self, indent: usize) -> String {
1261 let prefix = " ".repeat(indent);
1262
1263 let rule_name = match &self.rule {
1264 InferenceRule::UniversalInst(var) => format!("UniversalInst({})", var),
1265 InferenceRule::UniversalInstTerm(term) => format!("UniversalInst({})", term),
1266 InferenceRule::UniversalIntro { variable, var_type } => {
1267 format!("UniversalIntro({}:{})", variable, var_type)
1268 }
1269 InferenceRule::ExistentialIntro {
1270 witness,
1271 witness_type,
1272 } => {
1273 format!("∃Intro({}:{})", witness, witness_type)
1274 }
1275 InferenceRule::ExistentialIntroTerm {
1276 witness,
1277 witness_type,
1278 } => {
1279 format!("∃Intro({}:{})", witness, witness_type)
1280 }
1281 InferenceRule::StructuralInduction {
1282 variable,
1283 ind_type,
1284 step_var,
1285 } => {
1286 format!("Induction({}:{}, step={})", variable, ind_type, step_var)
1287 }
1288 InferenceRule::OracleVerification(s) => format!("Oracle({})", s),
1289 InferenceRule::Rewrite { from, to } => format!("Rewrite({} → {})", from, to),
1290 InferenceRule::RewriteAt {
1291 from,
1292 to,
1293 occurrence,
1294 } => {
1295 format!("Rewrite({} → {} @{})", from, to, occurrence)
1296 }
1297 InferenceRule::EqualitySymmetry => "EqSymmetry".to_string(),
1298 InferenceRule::EqualityTransitivity => "EqTransitivity".to_string(),
1299 r => format!("{:?}", r),
1300 };
1301
1302 let mut output = format!("{}└─ [{}] {}\n", prefix, rule_name, self.conclusion);
1303
1304 for premise in &self.premises {
1305 output.push_str(&premise.display_recursive(indent + 1));
1306 }
1307 output
1308 }
1309}
1310
1311impl fmt::Display for DerivationTree {
1312 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1313 write!(f, "{}", self.display_tree())
1314 }
1315}
1316
1317// =============================================================================
1318// PROOF GOAL - The target state for backward chaining
1319// =============================================================================
1320
1321/// The Goal State for the Backward Chainer.
1322///
1323/// Represents a "hole" in the proof that needs to be filled. During backward
1324/// chaining, goals are decomposed into subgoals until they match known facts.
1325///
1326/// # Fields
1327///
1328/// * `target` - What we are trying to prove
1329/// * `context` - Local assumptions (e.g., antecedents of implications we've entered)
1330///
1331/// # See Also
1332///
1333/// * [`BackwardChainer::prove`] - Takes a goal and produces a derivation tree
1334/// * [`DerivationTree`] - The result of successfully proving a goal
1335/// * [`ProofExpr`] - The target type
1336#[derive(Debug, Clone)]
1337pub struct ProofGoal {
1338 /// What we are trying to prove right now.
1339 pub target: ProofExpr,
1340
1341 /// The local assumptions available (e.g., inside an implication).
1342 pub context: Vec<ProofExpr>,
1343}
1344
1345impl ProofGoal {
1346 pub fn new(target: ProofExpr) -> Self {
1347 Self {
1348 target,
1349 context: Vec::new(),
1350 }
1351 }
1352
1353 pub fn with_context(target: ProofExpr, context: Vec<ProofExpr>) -> Self {
1354 Self { target, context }
1355 }
1356}