Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Getting started

dēdūxit [deːˈduːk.sɪt] Latin, verb: "it has derived", the perfect of dēdūcō, to lead down, derive.

deduxit is a collection of logic suites. It decides whether a sequent is provable, and shows the proof or says why there is none. It is a command, deduxit, and a Rust library, the crate deduxit. Its suites are linear logic (classical and intuitionistic, first-order and cyclic, and the Lambek calculus) and propositional logic (classical, intuitionistic and minimal, in Ordinary logic). The web page proves step by step in the browser with the same library. It began as linlog, a linear logic library (up to 0.2.0), and is growing to take in more calculi.

This page is a short tour. It assumes you have installed the command (Install deduxit; nix run github:deduxit/deduxit -- prove "A |- A" runs it without installing). This manual describes the main branch; a release's manual is the docs/ directory of its tag.

Your first proof

A sequent A, A -o B |- B says: from A and "A implies B", using each exactly once, derive B. -o is linear implication. Ask deduxit to prove it:

$ deduxit prove "A, A -o B |- B"
provable (MLL, classical, focus engine)
─────── ax   ─────── ax
⊢ ~A, A      ⊢ ~B, B
──────────────────── ⊗
  ⊢ ~A, A ⊗ ~B, B

The first line is the verdict. In brackets are the fragment of linear logic the sequent uses (MLL: only the multiplicative connectives), the logic (classical linear logic by default) and the engine that searched. Below it is the proof, a derivation tree read from the leaves down. Every proof deduxit reports has passed its proof checker.

The tree is written one-sided, the standard form for classical linear logic: every formula moves to the right of ⊢, and a formula on the left becomes its negation ~. So ⊢ ~A, A is the axiom A ⊢ A. To see the tree with the sides you wrote, add --classical-sides two:

$ deduxit prove --classical-sides two "A, A -o B |- B"
provable (MLL, classical, focus engine)
───── ax   ───── ax
A ⊢ A      B ⊢ B
──────────────── ⊸L
  A, A ⊸ B ⊢ B

Quote the sequent, so that the shell passes it as one word. The ASCII connectives are * (tensor, ⊗), par (⅋), & (with), + (plus, ⊕), -o (⊸), ~ (negation), ! and ?; The syntax lists them all.

Your first unprovable sequent

In linear logic every hypothesis must be used exactly once. So A, B |- A has no proof:

$ deduxit prove "A, B |- A"
unprovable (MLL, classical, focus engine): B on the left has no B on the right to meet in an axiom; with -a (affine), an unused hypothesis is allowed

The reason says what is wrong: B is never used. The note names -a, affine mode, where a hypothesis may go unused:

$ deduxit prove -a "A, B |- A"
provable (MLL, classical affine, focus engine)
  ─────── ax
  ⊢ ~A, A
─────────── wk
⊢ ~A, ~B, A

The wk step (weakening) drops the unused ~B.

The exit status tells a script the verdict: 0 provable, 1 unprovable, 3 unknown, 2 an error.

$ deduxit prove -q "A |- B"; echo "exit $?"
unprovable (MLL, classical, focus engine): A on the left has no A on the right to meet in an axiom
exit 1

-q prints the verdict line alone. A third answer, "unknown", comes when a limit stopped the search first, most often the time limit of two seconds. Its line names the flag that gives the search more room; Decide a sequent says more.

Your first intuitionistic proof

-i reads the sequent in intuitionistic linear logic: hypotheses on the left, exactly one formula on the right. The proof is two-sided:

$ deduxit prove -i "A, A -o B |- B"
provable (IMLL, intuitionistic, two-sided engine)
───── ax   ───── ax
A ⊢ A      B ⊢ B
──────────────── ⊸L
  A, A ⊸ B ⊢ B
$ deduxit prove -i "A |- A * A"
unprovable (IMLL, intuitionistic, two-sided engine): A occurs 1 more time on the right than on the left, so they cannot all meet in axioms (an implication's antecedent counts on the other side)

A * A needs two copies of A, and there is one. With !A, "as many A as you like", the sequent is provable:

$ deduxit prove -q "!A |- A * A"
provable (MELL, classical, horn engine)

Your first countermodel

--logic reads a sequent of ordinary propositional logic instead, with -> for implication, \/ for "or" and ~ for "not". In intuitionistic logic A \/ ~A is not valid, and deduxit shows why with a Kripke countermodel:

$ deduxit prove --logic intuitionistic "|- A \/ ~A"
not valid (intuitionistic logic by the SAT solver): a checked countermodel refutes it
world 0 (the model's world): forces nothing; below 1
world 1: forces A

A Kripke model is a set of worlds, each forcing some atoms, and a world forces what every world below it forces. At world 0, A is not yet true, and ~A fails since A holds at world 1 above it. Ordinary logic has the other logics, the truth table and the tableau of classical logic, and the proofs.

Export the proof

--format writes the proof as LaTeX, Typst, SVG, PNG, PDF, a Rocq certificate or JSON. --output writes it to a file, in the format its extension names:

$ deduxit prove --format latex "A, A -o B |- B"
% provable (MLL, classical, focus engine)
\begin{prooftree}
\infer0[$\mathrm{ax}$]{\vdash A^\bot, A}
\infer0[$\mathrm{ax}$]{\vdash B^\bot, B}
\infer2[$\otimes$]{\vdash A^\bot, A \otimes B^\bot, B}
\end{prooftree}
$ deduxit prove --output proof.svg "A, A -o B |- B"

The LaTeX uses the ebproof package; --standalone writes a whole document. Export a proof covers every format.

Check a proof

The JSON form is a proof file. deduxit check verifies it with the checker alone, without searching:

$ deduxit prove --format json "A, A -o B |- B" > proof.json
$ deduxit check proof.json
valid proof of ⊢ ~A, A ⊗ ~B, B (classical)
─────── ax   ─────── ax
⊢ ~A, A      ⊢ ~B, B
──────────────────── ⊗
  ⊢ ~A, A ⊗ ~B, B

Where to go next