Expand description
dēdūxit [deːˈduːk.sɪt] Latin, verb: "it has derived", the perfect of dēdūcō, to lead down, derive.
A collection of logic suites: decides sequents of linear logic, and of classical, intuitionistic and minimal propositional logic. Every proof it returns has passed the crate’s checker, unless the caller turns the check off, and every Kripke countermodel its own check. A proof prints as a derivation, or exports to LaTeX, Typst, SVG, PNG, PDF or Rocq.
use deduxit::linear::{Mode, Options, Sequent, Verdict, prove};
let sequent: Sequent = "A, A -o B |- B".parse()?;
let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default())?;
match &outcome.verdict {
Verdict::Proved(proof) => println!("provable\n{}", proof.derivation()?),
Verdict::Unprovable(disproof) => println!("unprovable: {disproof}"),
Verdict::Unknown(reason) => println!("unknown: {reason}"),
}{disproof} prints why the sequent is unprovable, in the words of the
deduxit command; {:?} would print the whole data. The examples
below also use serde_json.
This is the library of deduxit.
A guide to the library and the command for AI models is served beside
this documentation: its summary as
llms.txt and its full
reference as
llms-full.txt.
§What you can do
- Decide a sequent:
linear::prove, as above. AModeis the rules a logic allows: classical or intuitionistic, with weakening (affine) or Mix, commutative or ordered. - Read intuitionistic input: parse it as an
IllSequent(below). - Bound a search’s time, memory and work:
linear::prove_withinwithLimitsand a stop (below). - Get the answer the command gives:
Settings::stop(below). - Check a proof, made here or read from a file:
Proof::check. - Print or export a derivation:
Proof::derivationand the formats underexport. - Work with proof nets:
ProofStructure. - Prove step by step:
linear::Interactive(featureinteractive). - Decide classical, intuitionistic or minimal propositional logic,
with a Kripke countermodel (
kripke::Model) for what is not valid:ordinary. - Translate a classical sequent into intuitionistic or minimal logic,
or find a Craig interpolant, each checked:
ordinary::negativeandordinary::interpolant. - Read a proof as a lambda-term:
lambda. - Check, build and draw a derivation in a calculus you give as a rule
file, natural deduction among the built-in ones, as a tree or as a
Fitch proof:
rules(featureserialize). - List what each suite makes and does, and run it over JSON:
protocol(featureprotocol). - Keep sequents and what was made from them, with undo and redo:
workspace(featureprotocol).
Proofs, nets and errors name the occurrences of a sequent: an
occurrence is one place of a subformula in the sequent, and the
sequent’s Forest numbers them.
§A proof, its fragment and its JSON
Parse a sequent, see which fragment of linear logic it lives in, prove it, print the derivation, then write the proof as JSON, read it back and check it:
use deduxit::linear::{Fragment, Mode, Options, Sequent, Verdict, prove};
// Two-sided input becomes one-sided: ⊢ ~A, A ⊗ ~B, B.
let sequent: Sequent = "A, A -o B |- B".parse()?;
assert_eq!(sequent.fragment(), Fragment::MLL);
let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default())?;
let Verdict::Proved(proof) = &outcome.verdict else {
panic!("the sequent is provable");
};
assert_eq!(
proof.derivation()?.to_string(),
"─────── ax ─────── ax\n\
⊢ ~A, A ⊢ ~B, B\n\
──────────────────── ⊗\n\
\x20 ⊢ ~A, A ⊗ ~B, B"
);
let json = serde_json::to_string(&proof)?;
let back: deduxit::linear::Proof = serde_json::from_str(&json)?;
back.check(Mode::CLASSICAL)?;§Intuitionistic input
An IllSequent reads a sequent of intuitionistic
linear logic as it is written, with its hypotheses left of ⊢. Its
errors are in that logic’s terms: par is refused with a hint to
write A -o B. A Sequent parsed from the same
text and proved in an intuitionistic mode would report a subformula
instead.
use deduxit::linear::{IllSequent, Mode, Options, Verdict, prove};
let ill: IllSequent = "A -o B, B -o C |- A -o C".parse()?;
let outcome = prove(ill.sequent(), Mode::INTUITIONISTIC, &Options::default())?;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));
let Err(error) = "A par B |- B".parse::<IllSequent>() else {
panic!("par is not intuitionistic");
};
assert!(error.to_string().contains("write ~A par B as A -o B"));§Limits and stops
Options are a search’s settings, with their
defaults. Limits are the resources a call may use. The crate reads
no clock, so a long call takes a stop: a closure that the call asks
from time to time and that ends the call when it returns true. The
call tells it the Progress made. |_| false never stops. The
limits module lists every long call with its bounds and how often
it asks its stop.
Where there is no clock, as in a browser, a stop can count the work
done:
use deduxit::{Limits, linear::{Fragment, Mode, Options, Verdict, prove_within}};
let mode = Mode::CLASSICAL.with_mix();
let options = Options::default().with_fragment(Some(Fragment::MALL));
let limits = Limits::default().with_memory_bytes(Some(64 << 20));
let mut budget: u64 = 10_000_000;
let sequent = "|- A par B, ~A, ~B".parse()?;
let outcome = prove_within(&sequent, mode, &options, &limits, |progress| {
budget = budget.saturating_sub(progress.work);
budget == 0
})?;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));
assert_eq!(outcome.fragment, Fragment::MALL);§The command’s answers
Options::default() bounds the copies of a ? formula at three per
branch, so that a call without a stop ends. The deduxit command has
a clock instead. It searches without a copy bound until its time limit
of two seconds, and after a tenth of a second it adds a pool of the
machine’s other threads. So the two can answer differently.
Settings::default() holds the command’s settings. To
decide what the command decides, search with its search options and
the stop that Settings::stop makes from its clock. That stop fires
at the time limit but lets the refutation after the search run, as the
command does. Settings::deterministic keeps the search on one
thread, as the command’s --deterministic does:
use deduxit::{Settings, linear::{Mode, Verdict, prove_within}};
use std::time::Instant;
let settings = Settings::default().deterministic();
let start = Instant::now();
let sequent = "!A |- !A * !A".parse()?;
let stop = settings.stop(|| start.elapsed());
let outcome = prove_within(&sequent, Mode::CLASSICAL, &settings.search, &settings.limits, stop)?;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));§What each suite offers, over JSON
protocol lists each suite’s kinds of values and the operations
between them, and runs an operation on JSON values. Here a classical
sequent is translated into intuitionistic logic, and the translation’s
promise, that both are valid together or not, is checked:
use deduxit::{Settings, protocol};
let settings = Settings::default().deterministic();
let sequent = r#"{"version": 8, "formulas": [{"V": 0}, {"¬": 0}, {"∨": [0, 1]}],
"atoms": ["a"], "left": [], "right": [2], "logic": "classical"}"#;
let glivenko = r#"{"translation": "glivenko"}"#;
let translated =
protocol::run("ordinary.translate", &[sequent], glivenko, &settings, |_| false)?;
let text = protocol::summary("ordinary.sequent", &translated.value, &settings.limits)?;
assert_eq!(text, "⊢ ¬¬(a ∨ ¬a)");
let check = protocol::check(
"ordinary.translate", &[sequent], glivenko, &translated.value, &settings, |_| false,
)?;
assert_eq!(check.status, protocol::Status::Held);§Errors
Every call that can fail returns an Error, or a more specific
error that converts into one without loss:
- a
CheckErrorwhen a proof fails the checker (Invalid) or its check was refused (Refused); - a
NetErrorfor a proof structure; - a
ShapeErrorfor a sequent with no intuitionistic reading; - a
ParseErrorfor text that is no sequent.
Error::kind says what sort of failure it is. A call that a bound or
the stop ended is a refusal (ErrorKind::is_refusal, with the
Refusal), never a fault of its input. Error::code is a stable
name that a program can branch on.
Messages name occurrences by number. describe, given the forest or
other value that the numbers belong to (an Owner), prints them as
formulas (Described).
§Syntax and JSON
Sequent says how a sequent is written: the text
that "…".parse::<Sequent>() reads and its Display writes, and its
JSON. The JSON forms are the interchange format of the command, of
front ends and of files. Those of Proof,
Outcome, ProofStructure
and Interactive are described on those types.
ordinary::Sequent says how a sequent of ordinary logic is written.
§Features
On by default:
parse: the text syntaxes, the LLTP readerlinear::lltp, the reader of coverability problemslinear::mist, the generatedlinear::familiesand the TPTP readerordinary::read_tptp;serialize: the JSON forms, through serde;interactive:Interactive, proving step by step;latex,typst,svgandrocq: the exports underexport;sat: the SAT solver batsat, with whichordinary::satdecides classical, intuitionistic and minimal logic;protocol:protocol, what each suite offers as data, run over JSON withserde_json, andworkspace, values linked by its operations (it needsserialize,parseandinteractive).
Off by default:
parallel: the search on a pool ofOptions::jobsthreads, and a pool kept across searches,linear::search::Pool; never for WebAssembly;pngandpdf: the SVG drawings rendered.
An item that needs a feature says so. Every feature but parallel
builds for wasm32-unknown-unknown: without parallel the crate
starts no thread, it never reads a clock, and it takes its time limits
as a caller’s stop. No feature is removed within a 0.y version.
§Stability
The API follows semantic versioning as Cargo reads it below 1.0: a breaking change raises the second number.
Every public enum, and every struct with public fields that may grow,
is #[non_exhaustive]. The enums of the calculus are closed on
purpose, so that a match over them stops compiling when the calculus
grows: Term, Kind, Node, Rule, Verdict,
Branch, Sign, linear::occurrences::Polarity, Side, those of
ordinary’s derivations, a lambda-term’s nodes and types, and
Visit, the stops of a walk.
The JSON forms are promised by their wire level (the module wire,
feature serialize), not by the crate’s version. Display text, the
defaults’ numbers and the engines’ counters are not promised. The
repository’s changelog lists what each release changed.
Re-exports§
pub use limits::Limits;pub use limits::Phase;pub use limits::Progress;pub use limits::Refusal;pub use settings::Clock;pub use settings::Settings;
Modules§
- export
- Writes sequents and proofs as LaTeX, Typst, SVG, PNG, PDF and Rocq.
- kripke
- Finite Kripke models, the countermodels of the suites: worlds, an order on them, and the atoms each world forces.
- lambda
- A proof as a program: an intuitionistic proof read back as a lambda-term.
- limits
- The resources a call may use, what a long call tells its stop, and why a call was refused without an answer.
- linear
- The linear suite: sequents of classical and intuitionistic linear logic, their fragments and modes, the occurrence forest, proofs and their checker, proof nets, and the search that decides a sequent and returns a checked proof or a refutation. The items a caller starts from are re-exported here.
- ordinary
- Ordinary propositional logic: classical, intuitionistic and minimal.
- protocol
- What each suite offers, as data: the kinds of artifacts it makes, the
operations from artifacts to artifacts with their parameters, the
settings each operation reads and what it promises of its output, and
the functions that read, summarize, run and check them over JSON. A
front end lists the operations a value takes, runs one, and shows its
check beside the result, without code of its own per suite. Needs the
cargo feature
protocol(on by default). - rules
- Calculi given as data: a rule file, a derivation whose nodes name its
rules, and a checker that says whether the derivation is one of that
calculus. Needs the cargo feature
serialize(on by default), since a calculus enters as a document. - settings
- What a front end holds: every value that configures a call, in one
Settings. With the featureserializeit reads and writes JSON. ItsClockholds the time limits, which the front end applies through its stop: the library reads no clock. - wire
- The wire forms: how a value crosses a process boundary, as JSON or any
format serde writes, and the rule that keeps a stored document
readable by later releases. Needs the cargo feature
serialize(on by default). - workspace
- A workspace of linked values: a sequent, its translation, the
translation’s proof, a countermodel, a drawing, each a node, and how
each was made from the others. Change a value upstream, and what was
made from it shows as out of date until it is made again; undo and redo
take whole edits back. Needs the cargo feature
protocol(on by default): the kinds of values and the operations between them are the suites’ (protocol).
Structs§
- Described
- An error displayed with formulas in place of occurrence numbers, read
from the value that owns the occurrences.
describeonError,CheckError,NetErrorandShapeErrorreturns it. Nodes and inferences keep their numbers. - Parse
Error - Where and why parsing failed: the place as a byte range, as a range of UTF-16 code units and as a line and a character, what was found there and what could have stood there. It owns its data, so it outlives the input.
Enums§
- Error
- Everything that can go wrong in a call of this crate.
- Error
Kind - What sort of failure an
Erroris.