Playground Documentation Challenges Full Docs

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 first
expression
The expression whose value to compute — of an enumerated type: 𝔹, or any type(T = c1 | … | cn) (X, not X -> ✔). 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

Produces
X -> v, where v is the value X takes under every assignment of its atoms consistent with the facts
Delivery & Label
Like a proof: into the current block, a label before decide catches the result, and as a proof in an argument of a call its statement is that proof. Facts about X itself are not used, so contradict[| decide(X)] refutes an assumption about X.
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 = c is true, c = d false). Atoms of the problem are maximal subexpressions that are no such function — P, p(x), ∀{x | …}, k: Color; each has an enumerated type. A cell f(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 statements F -> c with a value on the right: from the labels if given, otherwise the visible ones that share atoms with X (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 the decide node (as import parses 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.

▶ Run

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.

▶ Run

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).

▶ Run

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).

▶ Run

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: X and every atom are of a type(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) and p(d) are unrelated even if c = d is a fact. No quantifiers: ∀{x | p(x)} and p(c) are unrelated. No arithmetic.
  • Facts are statements F -> c with a value c of F's type on the right: those of the labels if labels are given and, if they do not determine X and the list is not closed by ;, the visible ones that share atoms with X, transitively, while the total stays within 10 atoms — a needed fact beyond that is not taken, and the answer is «not determined». Rewritings a -> b whose right side is not a value are not facts. Facts about X itself are skipped on purpose (so that contradict[| decide(X)] refutes an assumption about X).
  • 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 X needs, 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:

  1. Split an atom by the values of its enumeration: a branch if(A -> c) B1: … per value, each proving the goal X -> v under 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.
  2. Close every branch as soon as the values chosen so far make a fact or X itself 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 fact F(A, B) -> w found at the point), or the injectivity schema of two cells with one value; X computed is the goal itself; a branch whose hypothesis is the goal is that hypothesis (B2: if(X -> v) {}).
  3. The branch labels and the lemma's own label are internal names (𝓑1, decide.…); below they are written as a program could, through the label Bool of 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.

▶ Run

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.

▶ Run

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.

▶ Run

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.

A hint and an argument

▶ Run
ℹ
If the facts do not determine the value, decide reports assignments that give different values; if the facts contradict each other, it lists them. Pass the facts as labels and close the list with ; to make the search exact.