Decide ordinary logic
deduxit also decides ordinary propositional logic, in three variants:
- classical logic, where every formula is true or false, so that
a \/ ~aholds; - intuitionistic logic, where a proof of a formula must build it, so
that
a \/ ~aand~~a -> ado not hold in general; - minimal logic, intuitionistic logic in which false is an ordinary atom: nothing follows from it.
Name the logic with --logic and give prove a formula or a sequent:
$ deduxit prove --logic classical '((a -> b) -> a) -> a'
valid (classical logic by the affine translation into affine MALL, focus engine)
──────── ax
a ⊢ b, a
────────── →R ───── ax
⊢ a → b, a a ⊢ a
───────────────────── →L
(a → b) → a ⊢ a
─────────────────── →R
⊢ ((a → b) → a) → a
$ deduxit prove --logic intuitionistic 'a \/ b -> b \/ a'
valid (intuitionistic logic by the SAT solver)
───── ax ───── ax
a ⊢ a b ⊢ b
───────── ∨R₂ ───────── ∨R₁
a ⊢ b ∨ a b ⊢ b ∨ a
───────────────────────── ∨L
a ∨ b ⊢ b ∨ a
─────────────────── →R
⊢ (a ∨ b) → (b ∨ a)
$ 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, 2
world 1: forces a; below 3
world 2: forces nothing; below 3
world 3: forces a
Read the answer
valid: the sequent is a theorem of the logic. deduxit shows its proof in Gentzen's sequent calculus, LK for classical logic and LJ for the other two, and checks it by the rules of the logic before it is shown. The exit status is 0.not valid: no proof exists in LK or LJ, so the sequent is not a theorem of that logic.~~a -> aabove is a classical theorem, but not an intuitionistic one. The exit status is 1. The lines after it are a countermodel (A countermodel).unknown: a limit, such as the time limit, stopped the search before it decided. The exit status is 3, and the line says which limit it was.
The words in brackets name the logic and how deduxit decided the sequent: by LJT, or through a translation into linear logic and the engine that searched there (How a sequent is decided).
The line of a classical sequent that is not valid may name an
assignment of truth values that makes it false. Here a -> b fails
where a is true and b false:
$ deduxit prove --logic classical 'a -> b'; echo "exit $?"
not valid (classical logic by the affine translation into affine MALL, focus engine): the translated sequent is unprovable: the classical reading is false where a is true and every other atom false (! and ? erased, ⊗ and & as and, ⅋ and ⊕ as or, 1 and ⊤ true, ⊥ and 0 false), and every provable sequent reads as a tautology
exit 1
Write a formula
The connectives are ->/→, /\/∧, \//∨, ~/¬, <->/↔,
true/⊤ and false/⊥. ~ binds tightest, then /\, \/, ->,
and last <->. -> and <-> group to the right. A sequent such as
a, a -> b |- b has hypotheses left of |-; a formula alone is the
sequent with nothing on the left.
How a sequent is decided
--method chooses how (the settings key ordinary.method):
satis a SAT solver, for all three logics, and the default for each. Its search always ends. A sequent that is not valid comes with a countermodel, which is checked: a Kripke model in intuitionistic and minimal logic, an assignment of the atoms in classical logic. A valid sequent comes with a derivation of LJ in intuitionistic and minimal logic. By default that derivation is LJT's, which is smaller, and where LJT gives none, the one read off the solver's search;--method satalways reads it off the search. In classical logic a valid sequent comes with the solver's clausal proof: every step follows from the clauses of the sequent's negation and the steps before it by unit propagation, and the last step is the empty clause. A checker of deduxit's own accepts it before the verdict is given. A clausal proof is no derivation, so nothing is drawn.embeddingtranslates the sequent into linear logic, searches the image there and reads the proof back as one of LK or LJ. It decides all three logics, and gives the derivation of LK, the refutation and the certificates that the SAT solver does not give.ljtis Dyckhoff's calculus LJT, for intuitionistic and minimal logic. Its search always ends too.tableandtableau, for classical logic, decide the sequent by its truth table or by a tableau, as a first logic course does, and print the table or the tableau (Truth tables and tableaux).
$ deduxit prove --logic classical --method sat -q '((a -> b) -> a) -> a'
valid (classical logic by the SAT solver): a checked clausal proof of 1 step against the 6 clauses of the sequent's negation
$ deduxit prove --logic intuitionistic --method sat '((a -> b) -> a) -> a'; echo "exit $?"
not valid (intuitionistic logic by the SAT solver): a checked countermodel refutes it
world 0 (the model's world): forces nothing; below 1, 2
world 1: forces a; below 3
world 2: forces nothing; below 3
world 3: forces a
exit 1
On the ILTP library's 274 problems, with 2 seconds each, the SAT solver decides 252 in intuitionistic logic and 253 in minimal logic, LJT 200 and the embedding 188 in each. In classical logic the SAT solver decides 254 and the embedding 157. The SAT solver decides every problem the others decide. The classical default decides the same 254, and gives the embedding's output for the 124 the embedding answers with its evidence within 2 seconds: 123 derivations of LK and one refutation. The 186 problems all three decide in intuitionistic logic take it 26 ms in all, LJT 313 ms and the embedding 11.6 s (the measurement).
In classical logic the default keeps the embedding's output where the
embedding gives it quickly. Once the SAT solver has decided, the
embedding searches for at most 2²⁰ units of work, on an image of at
most 2²⁰ occurrences, which costs a median of 16 ms on ILTP and at most
0.1 s. Where it
proves the sequent, you get its verdict line, its derivation of LK and
its certificate, as --method embedding gives them; where it refutes
the sequent, its refutation. Otherwise the solver's clausal proof or
countermodel stands. A larger --work-limit or --occurrence-limit
does not raise these bounds, and a smaller one lowers them;
--method embedding gives the embedding the whole time limit.
Where the SAT solver stops at a bound other than the time limit, such
as a derivation past --derivation-limit, the default hands the
sequent to the embedding, and the verdict line names the translation.
--method sat reports the bound instead. --translation and --linear
name the embedding, so either of them alone chooses it. Through the
embedding, a not valid says that the translated sequent is
unprovable:
$ deduxit prove --logic intuitionistic --method embedding -q '~~a -> a'
not valid (intuitionistic logic by the cbn translation into ILL, two-sided engine): the translated sequent is unprovable: the search was exhaustive
$ deduxit prove --logic minimal --stats -q 'a, a -> b |- b'
valid (minimal logic by the SAT solver)
solver calls: 1
conflicts: 0
lemmas: 0
worlds: 0
facts derived: 3
clauses: 0
proof steps: 0
derivation by LJT: 2 sequents expanded
time: …
LJT's derivation of LJ uses Gentzen's cut for four of its rules, so its
lambda-term (Read a proof as a program) may hold a redex and
its certificate a let.
The translations
Through the embedding, classical logic goes into affine MALL without
exponentials (negation normal form, ∧ as &, ∨ as ⅋), where the
search needs no copy bound. Intuitionistic logic goes into
intuitionistic linear logic (ILL) by one of three translations, which
--translation names:
cbn, Girard's call-by-name translation, the default;cbv, his call-by-value one;01, Liang and Miller's 0/1 translation.
Minimal logic is the same with false an atom. In ILL the search deepens
its copy bound under the time limit, so an intuitionistic formula may be
answered unknown (exit status 3). seq print shows the image, and
--linear the linear proof of it:
$ deduxit seq print --logic intuitionistic --translation cbv 'a, a -> b |- b'
!a, !(!a ⊸ !b) ⊢ !b
$ deduxit seq print --logic minimal '~a |- a -> b'
!(!a ⊸ false) ⊢ !a ⊸ b
$ deduxit prove --logic intuitionistic --linear 'a, a -> b |- b'
valid (intuitionistic logic by the cbn translation into ILL, two-sided engine)
───── ax
a ⊢ a
────── !L
!a ⊢ a
─────── !R ───── ax
!a ⊢ !a b ⊢ b
────────────────── ⊸L
!a, !a ⊸ b ⊢ b
───────────────── !L
!a, !(!a ⊸ b) ⊢ b
A countermodel
A sequent that is not valid comes with a Kripke model that shows why.
The model has worlds, each forcing some atoms. A world lies below the
worlds its arrows reach, and every world forces what each world below it
forces. A world forces A -> B when every world at or above it that
forces A forces B, and ~A is A -> false. Only in minimal logic
can a world force false; in the other logics a world forces ~A when
no world at or above it forces A.
The model's world forces every formula left of |- and not the one
right of it, so the sequent cannot be a theorem. In the example at the
top, world 0 forces neither a nor ~a, since world 1 above it forces
a; so it forces ~~a and not a.
In classical logic the model has one world: the atoms it forces are
true, the others false. By default the verdict line names those atoms
itself; where it cannot, the model follows it. In minimal logic a world may force false, as
an atom. deduxit checks the model before it gives the verdict, and
check checks it again in a file prove --format json wrote. LJT
(--method ljt) finds no model: its "not valid" says the search was
exhaustive. A model past a size bound is not shown or checked, and the
verdict line says so.
To check a model of your own, write it in JSON and give check the
logic and the sequent. The model holds each world's atoms and its
arrows, by the index of the world above:
$ echo '{"worlds": [{"atoms": [], "arrows": [1]}, {"atoms": ["a"]}]}' > model.json
$ deduxit check --logic intuitionistic --sequent 'a \/ ~a' model.json; echo "exit $?"
the model does not satisfy ⊢ a ∨ ¬a at every world: world 0 forces each formula left of ⊢ and not the one right of it
at world 0: a not forced
at world 0: ¬a not forced
at world 0: a ∨ ¬a not forced
exit 1
$ deduxit check --logic intuitionistic --sequent 'a \/ ~a' --world 1 model.json
the model satisfies ⊢ a ∨ ¬a at world 1
A world gets "falsity": true where it forces false (minimal logic).
check first checks that the file is a model of the logic: its arrows
do not go round, every world forces what each world below it forces,
and only minimal logic has falsity. A key it does not know, such as a
misspelt arrows, is an error. The exit status is 0 where the sequent
holds, 1 where it fails, and 2 for a file that is no model of the logic.
--format svg, png and pdf draw the model: each world a box with
the atoms it forces, its number w₀, w₁, … beside it, an arrow up to
each world directly above it, and the model's world outlined in orange.
The drawing's description, which a screen reader reads, says what each
world forces and why the sequent fails. LaTeX and Typst draw no model.
check draws one too: the countermodel of an outcome, or a model of
your own at the world where it fails.
$ deduxit prove --logic intuitionistic --format svg --output model.svg 'a \/ ~a'
--format rocq writes the model as a certificate for deduxit's Rocq
library (Check a certificate in Rocq): a lemma that LJ, or
minimal logic, does not derive the sequent, proved by the library's
theorem that a Kripke model refutes what it does not satisfy. The model
is written as data: for each world the worlds above it, the atoms it
forces, and the worlds that force false. The library checks it by
computation. check --format rocq writes the same for a countermodel
in an outcome, and for a model of your own at the world where it fails.
$ deduxit prove --logic intuitionistic --format rocq 'a \/ ~a'
(* not valid (intuitionistic logic by the SAT solver): a checked countermodel refutes it *)
Lemma certificate : ~ lj (atom := string) intuitionistic [] (vee (var "a") (neg (var "a"))).
Proof.
apply (kripke_refutation String.eqb String.eqb_spec intuitionistic
{| later := [[1]; []];
atoms := [[]; ["a"]];
absurd := [] |} 0).
vm_compute. reflexivity.
Qed.
Truth tables and tableaux
For classical logic, --method table and --method tableau decide a
sequent the way a first logic course does, and print the table or the
tableau in place of a derivation.
The truth table has a row for every assignment of the atoms, from all
true to all false. A row marked × makes every formula left of |-
true and every formula right of it false, so it falsifies the sequent:
$ deduxit prove --logic classical --method table 'a -> b |- b -> a'; echo "exit $?"
not valid (classical logic by its truth table): 1 of its 4 rows falsifies it, a checked countermodel
a b │ a → b ⊢ b → a
T T │ T T
T F │ F T
F T │ T F ×
F F │ T T
world 0 (the model's world): forces b
exit 1
The rows double with each atom, so --method table refuses a sequent
of more than 10 atoms. --table-atoms N raises the bound (the settings
key limits.table_atoms), and none lifts it. check takes the same
flag to check a table made with a raised bound.
A tableau marks each formula T (true) or F (false). It starts from
the sequent, its hypotheses true and the formulas right of |- false,
and expands one formula at a time: a true p ∨ q splits the branch in
two, one where p is true and one where q is. A branch closes, ×,
where a formula is both true and false, ⊥ true or ⊤ false. Each line
names the rule of LK that made it and the line it expands:
$ deduxit prove --logic classical --method tableau 'p \/ q, p -> r, q -> r |- r'
valid (classical logic by a tableau): every branch closes, a checked derivation of LK
1 T p ∨ q
2 T p → r
3 T q → r
4 F r
├─ 5 T p ∨L 1
│ ├─ 6 F p →L 2
│ │ × 5, 6
│ └─ 7 T r →L 2
│ × 7, 4
└─ 8 T q ∨L 1
├─ 9 F p →L 2
│ ├─ 10 F q →L 3
│ │ × 8, 10
│ └─ 11 T r →L 3
│ × 11, 4
└─ 12 T r →L 2
× 12, 4
A closed tableau is a derivation of LK read upside down: a branch is a
goal, its T formulas left of ⊢ and its F formulas right. deduxit
builds it step by step, checks every step by the rules of LK, and checks
the finished derivation, which --format latex and the other drawn
formats draw. A branch left open, with nothing more to expand, gives an
assignment that falsifies the sequent: its true atoms are those the
countermodel forces.
$ deduxit prove --logic classical --method tableau 'a -> b |- b -> a'
not valid (classical logic by a tableau): an open branch gives a checked countermodel
1 T a → b
2 F b → a
3 T b →R 2
4 F a →R 2
├─ 5 F a →L 1
│ open
└─ 6 T b →L 1
open
world 0 (the model's world): forces b
With --format json, the outcome holds the table or the tableau under
search (wire level 14): the table's rows as a T or F per formula of
its sequent's form, and the tableau's nodes, each before its children,
with its signed lines and either the line it expands or how its branch
ends.
Check a tableau written by hand
deduxit check --tableau reads a signed tableau that a student wrote,
checks it rule by rule, and names the first step that breaks a rule.
The tableau is text, one line per signed formula, as on paper and as in
the forall x and Open Logic Project books:
- a line is its number,
TorF, the formula, and at its end the number of the line it expands. A rule's name may come before that number (F∨ 2,∨R 2orF\/ 2), and is then checked too; - the first lines, which expand no line, are the sequent's: its
hypotheses
Tand its conclusionsF; - a branch starts with
-under the lines it goes on from, its lines indented to the column after the-. The tree thatprove --method tableauprints, with├─and└─, reads as well; ×(orx) under a branch closes it, followed by the two lines of a formula true and false, or by the one line of⊥true or⊤false.openmarks a branch that stays open.
A tableau with every step right and every branch closed proves the sequent valid:
$ deduxit check --tableau; echo "exit $?"
> 1 T p \/ q
> 2 F q \/ p
> 3 F q 2
> 4 F p 2
> - 5 T p 1
> × 4, 5
> - 6 T q 1
> × 3, 6
closed tableau of p ∨ q ⊢ q ∨ p: every step follows the rules and every branch closes, so the sequent is valid in classical logic
exit 0
A wrong step is named with its line, its rule and what the rule gives, and the exit status is 1:
$ deduxit check --tableau; echo "exit $?"
> 1 T p /\ q
> 2 F q
> 3 T p 1
> 4 T r 1
wrong tableau of p ∧ q ⊢ q: line 4: T∧ on line 1 (T p ∧ q) adds T p and T q, not T r
exit 1
The check also says where a branch is marked wrongly (× with nothing
that closes it, open on a branch that closes or has a formula left to
expand) and which branch is not finished yet. A finished open branch
makes the sequent not valid: its true atoms give a countermodel, which
is checked against the sequent and printed. --sequent names the
sequent the tableau must start from, as an exercise sets it:
$ deduxit check --tableau --sequent 'a -> b |- b -> a'
> 1 T a -> b
> 2 F b -> a
> 3 T b 2
> 4 F a 2
> - 5 F a 1
> open
> - 6 T b 1
> open
open tableau of a → b ⊢ b → a: every step follows the rules, every branch is finished, and the branch ending at line 5 is open, so the sequent is not valid in classical logic: a checked countermodel
world 0 (the model's world): forces b
An equivalence expands either way: by its sides' values, as the
textbooks do (T p ↔ q into T p, T q and F p, F q), or into its two
implications, as LK does. A tableau without a fault is checked once more
as a derivation in the built-in calculus tableau (see
Calculi given as data), so a closed tableau is a checked
proof. --format json writes the review: {"version": 14, "standing": "closed"|"open"|"unfinished"|"wrong", "sequent", "text_line", "line", "message", "countermodel"}, where text_line is the line of the text
the message is about and line the tableau's own number for it.
Draw the derivation
The derivation is checked with every weakening and contraction as an
inference of its own. It is drawn with each of them left out where it is
admissible, so that it reads as in G3, whose axiom takes a context
(a ⊢ b, a above) and whose rules contract what they use twice.
--structural explicit draws every one (the key view.structural), and
a certificate names every one whatever the flag says:
$ deduxit prove --logic classical --structural explicit '((a -> b) -> a) -> a'
valid (classical logic by the affine translation into affine MALL, focus engine)
───── ax
a ⊢ a
──────── WR
a ⊢ b, a
────────── →R ───── ax
⊢ a → b, a a ⊢ a
───────────────────── →L
(a → b) → a ⊢ a
─────────────────── →R
⊢ ((a → b) → a) → a
--format latex, typst, svg, png and pdf draw the derivation of
LK or LJ. --format rocq writes a certificate over Prop that needs no
library; a classical one uses the standard library's excluded middle.
For a sequent that is not valid, where its image's refutation or the SAT
solver's model is a classical assignment, the certificate is the lemma
that the formula does not hold for all propositions, proved by
instantiating the atoms with True and False. A Kripke countermodel
of intuitionistic or minimal logic has a certificate of its own
(A countermodel).
$ deduxit prove --logic classical --format rocq 'a \/ ~a'
(* valid (classical logic by the affine translation into affine MALL, focus engine) *)
Lemma certificate : forall a : Prop, (a \/ ~ a).
Proof.
exact (fun (a : Prop) => NNPP (a \/ ~ a) (fun k'1 : ~ (a \/ ~ a) => (let k'2 : ~ a := fun x' => k'1 (or_introl x') in let k'3 : ~ (~ a) := fun x' => k'1 (or_intror x') in (k'3 (fun h'4 : a => (k'2 h'4)))))).
Qed.
$ deduxit prove --logic classical --format rocq 'a -> b, b |- a'
(* not valid (classical logic by the affine translation into affine MALL, focus engine): the translated sequent is unprovable: the classical reading is false where b is true and every other atom false (! and ? erased, ⊗ and & as and, ⅋ and ⊕ as or, 1 and ⊤ true, ⊥ and 0 false), and every provable sequent reads as a tautology *)
Lemma certificate : ~ (forall a b : Prop, (a -> b) -> b -> a).
Proof.
intro H. specialize (H False True). tauto.
Qed.
Read a problem file
A .p file under --logic is a problem in TPTP's syntax, as the ILTP
library writes them (nix build .#iltp fetches its 274 propositional
problems). The batch (Decide many sequents at once) takes a
directory of them.
$ echo 'fof(pel1, conjecture, (p => q) <=> (~ q => ~ p)).' > pel1.p
$ deduxit prove --logic intuitionistic --quiet --file pel1.p
not valid (intuitionistic logic by the SAT solver): a checked countermodel refutes it
$ deduxit prove --logic classical --quiet --file pel1.p
valid (classical logic by the affine translation into affine MALL, focus engine)
JSON output
With --format json every method writes the outcome of the ordinary
sequent: its verdict (valid, not_valid, or unknown with a
reason), its logic, the search that decided it and, for a valid
sequent, its evidence. search says the method in method; LJT and the
SAT solver add their statistics:
$ deduxit prove --logic intuitionistic --format json '~~a -> a'
{"version":12,"deduxit":"0.5.0","verdict":"not_valid","logic":"intuitionistic","search":{"method":"sat","statistics":{"calls":4,"conflicts":0,"lemmas":0,"worlds":4,"facts":0,"clauses":0,"proof_steps":0,"ljt":null}},"countermodel":{"sequent":{"formulas":[{"V":0},{"¬":0},{"¬":1},{"→":[2,0]}],"atoms":["a"],"left":[],"right":[3]},"model":{"worlds":[{"atoms":[],"arrows":[1,2]},{"atoms":["a"],"arrows":[3]},{"atoms":[],"arrows":[3]},{"atoms":["a"]}],"world":0}}}
Through the embedding, search holds the translation and, under
image, the outcome of the search on the image, as prove writes it
without --logic (its proof, or its refutation):
$ deduxit prove --logic classical --method embedding --format json 'a |- b'
{"version":12,"deduxit":"0.5.0","verdict":"not_valid","logic":"classical","search":{"method":"embedding","translation":"affine","image":{"verdict":"unprovable","refutation":{"kind":"classical","assignment":[true,false]},"fragment":"MLL","mode":"affine","engine":"focus","statistics":{"nodes":1,"memo_hits":0,"memo_entries":1,"splits":0,"links":0,"tests":0,"copies":0,"forward_copies":0,"work":16},"sequent":{"terms":[{"D":0},{"V":1}],"roots":[0,1],"atoms":["a","b"],"antecedents":0}}},"countermodel":{"sequent":{"formulas":[{"V":0},{"V":1},"⊥"],"atoms":["a","b"],"left":[0],"right":[1]},"model":{"worlds":[{"atoms":["a"]}],"world":0}}}
A valid sequent has its derivation. One valid by a clausal proof has
clausal_proof in its place, with the counts of its variables, clauses
and steps. Where the embedding proved the image but a bound or the time
limit refused its derivation, neither is there, and the image's proof
is the evidence:
$ deduxit prove --logic classical --method sat --format json 'a \/ ~a'
{"version":12,"deduxit":"0.5.0","verdict":"valid","logic":"classical","search":{"method":"sat","statistics":{"calls":1,"conflicts":1,"lemmas":0,"worlds":0,"facts":0,"clauses":4,"proof_steps":1,"ljt":null}},"clausal_proof":{"variables":3,"clauses":4,"steps":1}}
--linear writes the image's outcome alone, as without --logic.
check reads every outcome prove --logic writes, and a derivation of
LK or LJ. It checks the derivation by the rules of its calculus, and the
image's proof or refutation where the embedding found one:
$ deduxit prove --logic intuitionistic --format json 'a |- a' > valid.json
$ deduxit check --file valid.json
valid derivation in LJ of a ⊢ a (intuitionistic logic)
───── ax
a ⊢ a
A clausal proof is written as its counts, LJT and the SAT solver write
no refutation of a sequent that is not valid, and an unknown holds no
proof: there check says the file holds nothing to check, with exit
status 3.
Step by step
deduxit interact --logic classical, intuitionistic or minimal
proves the sequent step by step by the rules of LK or LJ. The session
has the commands of a linear session (Prove step by
step): goals, rules, apply, undo, close,
show, proof, save, load, help and quit.
- A formula is named by its side and its position there:
L0,L1, … left of⊢andR0,R1, … right of it, asgoalslists them. - A rule is named by its name or an ASCII spelling:
andR,orR1,->LorimpL,~RornotR,iffL1,falseL,WL,CR. - The axiom closes a goal that has its formula on both sides, whatever else it holds.
- A rule with two premises gives both the whole context, as LJ's
→Ldoes in G3. Formulas named after the rule go to the first premise instead, and the rest to the second:apply 1 L1 ->L L0sendsL0to the first. closedecides a goal through the embedding, whose derivations have no cut, by the translation--translationchooses. It grafts the derivation found, whichundotakes back whole.
$ deduxit interact --logic intuitionistic 'a -> b, b -> c |- a -> c'
> goals
goal 0: L0: a → b, L1: b → c ⊢ R0: a → c
> apply 0 R0 ->R
opened goal 1: L0: a → b, L1: b → c, L2: a ⊢ R0: c
> rules 1 L1
WL CL →L (with a split or none)
> apply 1 L1 ->L
opened goal 4: L0: a → b, L1: a ⊢ R0: b
opened goal 5: L0: a → b, L1: c, L2: a ⊢ R0: c
> apply 5 L1 ax
closed
> close 4
goal 4: valid (intuitionistic logic by the cbn translation into ILL, two-sided engine)
no goal is open: `proof` checks the proof
> proof
valid proof in LJ (intuitionistic logic)
───── ax ───── ax
a ⊢ a b ⊢ b
──────────────── →L ─────────────── ax
a → b, a ⊢ b a → b, c, a ⊢ c
─────────────────────────────────── →L
a → b, b → c, a ⊢ c
──────────────────── →R
a → b, b → c ⊢ a → c
In intuitionistic and minimal logic every goal keeps one formula right
of ⊢:
- A sequent with none starts as
Γ ⊢ ⊥. - The rules of LK that would leave a premise with none or two (
WR,CR,⊥R,∨Rwith both disjuncts) are refused with the reason. ¬Rand¬Ltake the form of→Rand→LforA → ⊥.- Minimal logic has no
⊥L.
The goals the search cannot decide stay open with the reason, as prove
gives it. show draws the derivation so far, open goals as bare
sequents. proof checks the finished one and prints it in every format
of prove, --structural choosing how the structural rules are drawn
(proof --rocq names every one). save writes the session as JSON,
which --state FILE resumes:
$ deduxit interact --logic minimal 'a |- ~~a'
> apply 0 R0 ~R
opened goal 1: L0: a, L1: ¬a ⊢ R0: ⊥
> apply 1 R0 falseR
error: the rule ⊥R is not available in minimal logic: its premise would have no formula right of ⊢, and every goal of LJ has exactly one
> apply 1 L1 ~L
opened goal 3: L0: a ⊢ R0: a
opened goal 4: L0: a, L1: ⊥ ⊢ R0: ⊥
> close
goal 3: valid (minimal logic by the cbn translation into ILL, horn engine)
goal 4: valid (minimal logic by the cbn translation into ILL, horn engine)
no goal is open: `proof` checks the proof
> proof --rocq
valid proof in LJ (minimal logic)
Lemma certificate : forall a : Prop, a -> (~ ~ a).
Proof.
exact (fun (a : Prop) (h'1 : a) => (fun h'2 : (~ a) => (let h'3 : False := h'2 (h'1) in h'3))).
Qed.