decide
Evaluation over finite types
Overview
Many steps of a proof are pure propositional logic: from iff(P, Q) -> true and P -> true follows Q -> true; from P -> true follows or(P, Q) -> true. Each such step can be a lemma applied by a call, but then every pattern needs its own lemma and its own name. decide(X) finds the value of X from the facts by the tables of its functions and writes the proof as ordinary commands. The same works over any enumerated type: a value of Color = red | green | blue left when the others are refuted, a law of a group of two elements checked for every value of its variables, the house left for a value in a puzzle.
decide(expression);decide(expression, otherExpression, …); // the same as decide(expression); decide(otherExpression); …decide(expression | factLabel1, factLabel2, …);decide(expression | factLabel1, factLabel2, …;); // only these factscontradict[| decide(expression)] theoremLabel[| decide(expression)] // as a proof in an argument<functionAtom(<expression | decide()>) |> // as a hint: decides its place<functionAtom(<expression | decide(| factLabel1, …)>) |> // its place, from these facts firstexpression- The expression whose value to compute — of an enumerated type: 𝔹, or any
type(T = c1 | … | cn)(X, notX -> ✔). Several, comma-separated, are decided in order; each sees the previous results. factLabel1, …- Optional: the facts to use first — labels or commands that return statements. What they leave undetermined is found among the visible facts sharing atoms with the expression, as a call finds the conditions its proofs do not meet;
;at the end — only these. Each must be needed. Facts about the expression itself are never used.
Command Properties
- Group
- Generators
- Produces
X -> v, wherevis the valueXtakes under every assignment of its atoms consistent with the facts- Delivery & Label
- Like a proof: into the current block, a label before
decidecatches the result, and as a proof in an argument of a call its statement is that proof. Facts aboutXitself are not used, socontradict[| decide(X)]refutes an assumption aboutX. - Mechanism
- Functions with tables are atoms of type
[T1, …, Tk -> T]over enumerated types whose rows are visible as statements (or(false, true) -> true,next(red) -> green);=of a hint on two values of an enumeration is a table too (c = cis true,c = dfalse). Atoms of the problem are maximal subexpressions that are no such function —P,p(x),∀{x | …},k: Color; each has an enumerated type. A cellf(h)of a bijection is an atom bound to the other cells: two cells take no value together, every value stands in a cell. Facts are statementsF -> cwith a value on the right: from the labels if given, otherwise the visible ones that share atoms withX(transitively, up to 10 atoms; the cells of one bijection share). The interpreter checks all assignments and then writes the proof as ordinary commands, parsed inside thedecidenode (asimportparses a file inside its node): a case analysis by the schemas of the enumeration, every branch closed by a fact refuted or by the value computed (below). The result is checked like a hand-written proof by cases, and the kernel does not grow.
Basic examples
Values from facts
The atoms may be any expressions of the type: decide(or(not(p(x)), p(x))), decide(∀{x: nat | q(x)}) from iff(∀{x: nat | q(x)}, R) -> true and R -> true.
Several expressions
A list of expressions is decided in order, exactly as separate commands decide(P); decide(Q);: each expression sees the results of the previous ones, and a label before decide catches all of them. This is how the parts of an assumption are taken out: for(p) if(prime(p) ∧ p ∣ d) decide(prime(p), p ∣ d). Nothing appears by itself: every result is written in the command.
Over an enumeration
The atoms, the functions and X itself may be of any enumerated type. A function over enumerated types with visible rows is evaluated by them, like a connective by its truth table; an atom of three values is split three ways. The cells of a bijection color: [House -> Color] (rule("bijective", color)) are evaluated together: the value left for a house, the house left for a value.
Three colours and three houses
The library proves the group laws of Z2 so: for(a, b, c: Z2) decide(a ⊕ b ⊕ c = a ⊕ (b ⊕ c)) with the table of ⊕ (algebra/z2.fl), and solves the Einstein puzzle from the refutations of values (puzzles/einstein_enum.fl).
Equality of values
An equality is the relation of a hint (notation("hint" | Rewrite, Reflexive); the library declares = so in logic/equality.fl): c = c is true by its Reflexive, c = d of two values false by their distinctness. A refuted value is such a fact: k = red -> false above an assumption if(k -> red) that led to a contradiction is what refute of the library delivers (contradict).
What decide is — and what it is not
decide is not a rule of the logic. It is a proof generator: it searches, writes
text with if, calls of the schemas of the enumeration and proofs, and that text is checked by
the kernel like any hand-written proof. So a mistake in decide can only make it refuse — it can never make a false
statement pass. For the same reason a generator may in principle be as clever as one likes (up to a neural network
that finds proofs by itself): only its output is trusted, after checking.
Today decide is a small and weak piece of automation. It is a brute-force search over
the assignments of a finite abstraction of the formula: every maximal subexpression that is not a function
with a table — P, p(x), a = b over an infinite type, ∀{x | …} — is
an opaque atom with no meaning but its enumerated type. It is complete only in this narrow sense: if the selected
facts determine X when the atoms are treated as independent variables over their types,
decide finds the value. It is far from a general prover: Lean's decide and tauto
cover the same ground, Isabelle's blast and auto go far beyond it.
Limits
- Enumerated types only:
Xand every atom are of atype(T = c1 | … | cn)(𝔹 among them). At most 16 atoms, and at most 216 assignments of their values in the search. - Functions with tables are atoms of type
[T1, …, Tk -> T]over enumerated types, with at most 8 arguments and at least one row visible as a statement (and(false, true) -> false). An application is evaluated by a row when one applies; when the rows are incomplete and none applies, the application is an opaque atom. An atom with no visible row is an ordinary function, and its applications are atoms.=is a table on two values of an enumeration only when a hint with a Reflexive theorem is declared for it. - Atoms are opaque and compared syntactically (up to renaming bound variables). No equality
reasoning between atoms:
p(c)andp(d)are unrelated even ifc = dis a fact. No quantifiers:∀{x | p(x)}andp(c)are unrelated. No arithmetic. - Facts are statements
F -> cwith a valuecofF's type on the right: those of the labels if labels are given and, if they do not determineXand the list is not closed by;, the visible ones that share atoms withX, transitively, while the total stays within 10 atoms — a needed fact beyond that is not taken, and the answer is «not determined». Rewritingsa -> bwhose right side is not a value are not facts. Facts aboutXitself are skipped on purpose (so thatcontradict[| decide(X)]refutes an assumption aboutX). - Closed formulas (only values and known functions) are evaluated with one empty assignment, using the same checked proof generator.
- On failure it reports what it saw: assignments with different values of
X, or the list of contradictory facts. Closing the labels with;makes the search exact; when the closed facts do not determine X but the visible ones would, the error names those visible facts. - Every label passed must be needed: the proof keeps only the facts
Xneeds, preferring the labelled ones, and a label none of whose facts is kept is an error, as in a call.
A case split by hand
A case split needs no command. Under P -> false write the step; after the
branch closes, P -> true holds and the same step is written once more:
if (P -> false) contradict[| <…>]; // the branch P -> false: closed, so P -> true above it
contradict[| <…>]; // now with P -> true
With a block, the block stands in the branch and again after it. For two atoms, the branch holds the split on
the second one. When the branches only check the tables, one line does the same: contradict[| decide(G)]
proves G by the tables and the split on its atoms, and the value found against the assumption on
G closes it (logic/propositional.fl, puzzles/knights.fl). decide builds
the tree itself: it chooses the atoms and their order, closes a branch as soon as a fact is determined by the
atoms already split — P ∧ Q is false once P is false — and makes the determined parts facts
from the bottom up, each by one row of its function's table, so taking one conjunct out of a conjunction of twelve
needs a few branches, not 211. A branch that needs more than the tables (a call, a rewriting by a fact)
is written by hand.
The tree is written once for the shape of the step, not for its atoms. The atoms become variables, the
facts the step needs become conditions, and the tree proves a lemma: P(u) from P(u) ∧ Q(u)
is the lemma «𝓅1 from 𝓅1 ∧ 𝓅2», proved where the enumerations, the functions and their tables are visible
and applied by a call with 𝓅1 := P(u), 𝓅2 := Q(u). Another decide of the same shape —
Q(w) from Q(w) ∧ P(v) in another theorem — applies the same lemma; so does one in a file that
imports it. One row of a table with an unknown argument («𝓆1 -> false gives
𝓆1 ∧ 𝓆2 -> false») is a lemma of its own, shared the same way, and so is c = d -> false of
two values. The cells of a bijection stay themselves in the lemma. The log says for each step whether its
lemma is new or applied again. These lemmas have internal names: a program does not see them.
How automation is added to Formall
- The machine reasons only in a generator command that you write for a goal you name (
decide(X)). Other commands and calls never reason silently: no facts appear by themselves, no condition is accepted without a fact. - A generator's scope is a whole theory that can be stated in one phrase («tables over finite types»), not a list of cases that happened to be needed. Inside the scope it searches exhaustively or refuses with a clear message.
- Stronger automation — equality reasoning (congruence closure), linear arithmetic, rings, propositional logic
modulo such a theory — will come as separate commands with their theories stated,
not as one more special case inside
decide.
What decide writes
decide is not a new rule of the logic. It finds the value by trying all assignments, and then writes a
proof by cases with the commands you already know; that text is parsed inside the decide node and checked
like any other code. The proof always has the same shape:
- Split an atom by the values of its enumeration: a branch
if(A -> c) B1: …per value, each proving the goalX -> vunder its hypothesis, and the cases schema of the enumeration (type generates it) combines the branches:Bool[A, X, v | B1, B2]through the label of the type. A value of a bijection is split by the cells it may stand in, with the column schema of the bijection. Atoms that have a fact of their own (P -> true) have their value from the start and are never split. - Close every branch as soon as the values chosen so far make a fact or
Xitself computable:<F(<A>, <B>)>rewrites each atom to its value in the branch and the functions by their tables. A fact refuted so gives the goal by ex falso — the distinctness schema of two values (Bool[F(A, B), X, v | <F(<A>, <B>)>], the factF(A, B) -> wfound at the point), or the injectivity schema of two cells with one value;Xcomputed is the goal itself; a branch whose hypothesis is the goal is that hypothesis (B2: if(X -> v) {}). - The branch labels and the lemma's own label are internal names (
𝓑1,decide.…); below they are written as a program could, through the labelBoolof the type.
For the first example above, if(iff(P, Q) -> true; P -> true) decide(Q) writes:
What decide(Q) writes
The same text as if(iff(P, Q) -> true, P -> true) decide(Q) generates, the schemas of the enumeration named through the label Bool of the type; the full code declares the connectives by their truth tables. P has a fact of its own, so only Q is split.
Modus tollens, if(imp(P, Q) -> true) if(Q -> false) decide(P):
What decide(P) writes for modus tollens
The text if(imp(P, Q) -> true) if(Q -> false) decide(P) generates.
A tautology with three atoms has no facts, so every branch is closed by X itself: eight branches, each
<imp(<and(<imp(<P>, <Q>)>, …)>, …)> computing
true, combined by the cases of the three atoms. The log shows the size of the generated proof:
[ decide ] … // 0 facts, 3 atoms, 8 branches.
Because the result goes through if, the schemas of the enumeration and proofs, the kernel does not grow:
the certificate of such a proof uses only the kernel's ordinary rules.
Labels first, then the visible facts; ; — only these
After | come the facts decide takes first. What they leave open is found among the visible facts, like the conditions of a call that its proofs do not meet: one rule for every |. A ; at the end of the list says «only these». It is needed where the visible facts must not be used — in a block whose assumptions contradict each other on purpose, or where a reader should see everything the result rests on.
Labels first, then the visible facts
The second decide is closed by ;: the error names the visible fact Q -> true that would decide it.
Expected error: with these visible facts it would be true (pass their labels or remove ';')
decide as a hint
In a proof, <e | decide()> rewrites e to its value decided from the visible facts — the propositional counterpart of a theorem hint. A hint is a proof, and a command whose expression is not written takes the place of the hint, as a call T[] infers what is not written; <e | decide(| H)> decides the place from the facts of H first, <e | decide(| H;)> from them alone (Hints are proofs). Standing alone, decide() has no place and is an error.