Annotated Logic: Intervals, Lattices, and Confidence

📍 Where we are: Part VI · Annotated and Temporal Logic — Chapter 19. Provenance Semirings labeled every derived fact with where it came from; now we keep that machinery bolt for bolt and swap the label for a single number that says how sure we are.

Classical logic hands every fact one of two verdicts: it holds, or it does not. That is exactly right for a hand-curated ontology and exactly wrong for the messy knowledge bases the rest of this series cares about — the ones filled by an information-extraction pipeline reading noisy text, or merged from sources of uneven trust. There, a fact is rarely certainly true; it is true to a degree. This chapter attaches that degree to each fact as a number, shows that the arithmetic of combining such numbers is a lattice we have already met, and — the punchline — that the lattice is the very same semiring from the previous chapter, so the annotated reasoner needs not one new line of code.

The simple version

Imagine planning a trip with connecting flights. A single itinerary is only as dependable as its shakiest leg — one flight with a 50 percent chance of delay drags the whole trip down to 50 percent, no matter how reliable the other legs are. That is a conjunction: you need every leg to work, so the itinerary inherits its weakest link. But suppose two different itineraries both get you there. Now you take the better of the two and ignore the worse — that is a disjunction: only one option has to work, so you keep the best case. Annotated logic is this arithmetic of confidence made precise: a conjunction takes the minimum, a disjunction takes the maximum, and a fact's final confidence is the best route that reaches it.

What this chapter covers

• From yes-or-no to a degree — why real knowledge bases need graded truth, and the interval $[0,1]$ as the set of truth values in place of the crisp $\{0, 1\}$.
• The confidence lattice — meet $\sqcap = \min$ (a conjunction is only as strong as its weakest link) and join $\sqcup = \max$ (a disjunction takes the best alternative), read straight off conf_meet and conf_join.
• The same idea as a semiring — $([0,1], \max, \min)$ is the Confidence semiring, so last chapter's provenance_lfp computes graded truth with no new machinery at all.
• The Gödel t-norm — min-and-max is one of the three standard fuzzy connectives; where it sits among its cousins, in one table and no detour.
• The committed run — reach(p3, p1) earns confidence 0.8, computed as $\max(\min(0.9, 0.8), 0.5)$: a strong two-hop path outvotes a weak direct edge.
• Annotated logic programs — the general shape behind the demo: a rule body multiplies, a fact's alternatives add, and the head takes the join over all its derivations.
• The unsolved part — confidence and provenance annotate what and how sure; neither says when, the exact gap the next chapter fills with temporal intervals.

From yes-or-no to a degree

Start with what a truth value is. In classical logic an interpretation is a function $\nu$ (read "nu") that sends each ground atom to one of two values, and we write that set of values as $\{0, 1\}$ — 0 for false, 1 for true. A graded, or annotated, interpretation makes one change: it lets the value be anything in the whole closed interval between them,

$$\nu : \text{atoms} \to [0, 1],$$

where $[0,1]$ is the set of all real numbers from 0 to 1 inclusive. Read $\nu(\text{cites}(p3, p1)) = 0.5$ as "we are 50 percent confident that p3 cites p1"; a 1 is certainty, a 0 is certain falsehood or plain absence, and the numbers in between are the graded truths a crisp logic cannot express [1]. Nothing about the facts changed — the same p3, p2, p1 — only the label each carries. This is the minimal move from "does it hold?" to "how sure are we?", and everything below is the arithmetic that move forces on us.

The running example for the whole chapter is a three-edge citation graph, a directed acyclic graph (DAG) in which each edge carries both a provenance token and a confidence (annotated.py lines 151–155):

EDGES = [
    ("p3", "p2", "r", 0.9),
    ("p2", "p1", "s", 0.8),
    ("p3", "p1", "t", 0.5),
]

There is a strong two-hop path p3 → p2 → p1 (edges $r$ at 0.9 and $s$ at 0.8) and a weak direct edge p3 → p1 (edge $t$ at 0.5). By the chapter's end those five numbers will decide, with no hand-waving, exactly how confident we should be that p3 reaches p1.

The confidence lattice: meet is min, join is max

The interval $[0,1]$, ordered by the usual $\le$, is a lattice: any two values have a greatest lower bound and a least upper bound, and here those are just the smaller and the larger of the two. The greatest lower bound is the meet, written $\sqcap$, and it is $\min$; the least upper bound is the join, written $\sqcup$, and it is $\max$:

$$x \sqcap y \;=\; \min(x, y), \qquad x \sqcup y \;=\; \max(x, y).$$

Decode the two symbols before trusting them. The meet $\sqcap$ combines the parts of a conjunction — an "and" — and it takes the minimum, because a conjunction is only as true as its weakest conjunct: a chain of claims cannot be more certain than its shakiest link. The join $\sqcup$ combines the alternatives of a disjunction — an "or" — and it takes the maximum, because a disjunction is satisfied by its best alternative: if any one route works, you keep that one and forget the rest. In the companion file these are two one-liners, and each docstring states the reading (annotated.py lines 189–197):

def conf_meet(*xs) -> float:
    """Lattice meet ⊓ — the confidence of a *conjunction* (weakest link)."""
    return min(xs)


def conf_join(*xs) -> float:
    """Lattice join ⊔ — the confidence of a *disjunction* / best alternative."""
    return max(xs)

On the three edge confidences the two operations give opposite answers, and the gap between them is the whole point: $\sqcap(0.9, 0.8, 0.5) = 0.5$ (the weakest link drags the conjunction down to the direct edge's 0.5) while $\sqcup(0.9, 0.8, 0.5) = 0.9$ (the disjunction rises to the strongest edge) [2].

Graded reachability on the citation DAG: min runs along a conjunctive path (weakest link), max chooses among alternative derivations (best case), and the strong two-hop 0.8 beats the weak direct 0.5 to give reach(p3, p1) confidence 0.8. Original diagram by the authors, created with AI assistance.

The same idea as a semiring: no new machinery

Here is where the previous chapter pays off. A semiring $(K, \oplus, \otimes, 0, 1)$ is a carrier set $K$ with a "plus" $\oplus$ that combines alternative derivations of a fact and a "times" $\otimes$ that combines the facts inside one derivation's body, plus a $0$ that is the identity for $\oplus$ and a $1$ that is the identity for $\otimes$. Confidence fits this frame exactly — and the companion file registers it as one line among five semirings (annotated.py line 132):

CONFIDENCE = Semiring(0.0, 1.0, max, min, "Confidence [0,1]")

So the plus is $\max$ (join over alternatives) and the times is $\min$ (meet over a body): the lattice of the previous section is a semiring. The identities line up too, which is the tell that this is no coincidence: $\max(x, 0.0) = x$, so $0.0$ is the plus-identity, and $\min(x, 1.0) = x$, so $1.0$ is the times-identity.

semiring part	symbol	Confidence value	logical reading
carrier $K$	—	the interval $[0,1]$	a truth degree
plus $\oplus$	$\max$	best of the alternatives	disjunction / best derivation
times $\otimes$	$\min$	weakest of the group	conjunction / weakest link
zero $0$	$0.0$	certainly false / absent	identity for $\max$
one $1$	$1.0$	certainly true	identity for $\min$

Because Confidence is a semiring, the previous chapter's annotated fixpoint engine runs on it unchanged — the same provenance_lfp that computed Boolean, Which, Why, and polynomial provenance computes graded truth by swapping in this one row. The load-bearing lines are these (annotated.py lines 86–95):

    ann = dict(edb_annot)
    for _ in range(max_iter):
        new = dict(edb_annot)          # base tokens persist; IDB is recomputed
        for head, body in rules:
            for sub, prod in _match_body(body, ann, sr, {}, sr.one):
                h = _apply(head, sub)
                new[h] = sr.plus(new.get(h, sr.zero), prod)
        if new == ann:
            return ann
        ann = new

Read the inner two lines as the whole recipe. prod arrives from _match_body as the $\otimes$-product (here, the $\min$) over every fact the rule body matched — the conjunction. Then sr.plus(new.get(h, sr.zero), prod) folds that derivation into the head's running annotation with $\oplus$ (here, $\max$) — accumulating over alternative derivations. Every semiring reads the same acyclic derivation as different information; Confidence reads it as "min over the body, max over the derivations," and the loop is Volume 1's least-fixpoint climb with the values relabeled.

The Gödel t-norm: min and max among the fuzzy connectives

Why min for "and," rather than, say, multiplication? Fuzzy logic answers this with the notion of a triangular norm, or t-norm: a function $T : [0,1] \times [0,1] \to [0,1]$ that behaves like a graded conjunction — associative, commutative, monotone in each argument, and with $1$ as identity so that $T(x, 1) = x$. There is not one t-norm but a family, and $\min$ is the specific member called the Gödel t-norm [2]. It is the one the confidence lattice uses, and it has two properties its cousins lack: it is idempotent ($\min(x, x) = x$, so a rule body may cite the same fact twice without paying for it — and because the dual join $\max$ is idempotent too, re-deriving a fact by an identical route likewise adds nothing), and it is the largest possible t-norm, meaning min-based reasoning is the most optimistic graded conjunction on offer.

t-norm	$x \otimes y$	reading of "$x$ and $y$"
Gödel (minimum)	$\min(x, y)$	weakest link; idempotent, the largest t-norm
product	$x \cdot y$	independent evidence multiplies down
Łukasiewicz	$\max(0,\; x + y - 1)$	confidence can bottom out at exactly 0

The three disagree the moment two inputs are both uncertain: $\min(0.8, 0.8) = 0.8$, but the product gives $0.64$ and the Łukasiewicz t-norm gives $0.6$. Which is "right" is a modeling choice, not a fact of nature — a point the unsolved section returns to. This chapter, and its code, commit to the Gödel t-norm because it is the one that coincides with the lattice meet and hence with the Confidence semiring; that coincidence is precisely what let us reuse the fixpoint engine.

The committed run: reach(p3, p1) earns 0.8

Now put the pieces together on the DAG. Reachability is two Datalog rules — a base case and a recursive step (annotated.py lines 157–160):

REACH_RULES = [
    (("reach", "?x", "?y"), [("edge", "?x", "?y")]),
    (("reach", "?x", "?z"), [("edge", "?x", "?y"), ("reach", "?y", "?z")]),
]

The fact reach(p3, p1) has two derivations, which is exactly what makes the join $\oplus$ do visible work. One is the direct edge $t$, confidence 0.5. The other is the two-hop path: edge(p3, p2) at 0.9 conjoined with reach(p2, p1), and reach(p2, p1) is itself just the edge $s$ at 0.8, so the body's meet is $\min(0.9, 0.8) = 0.8$. The head then takes the join over the two derivations:

$$\mathrm{conf}(\text{reach}(p3, p1)) \;=\; \max\big(\underbrace{\min(0.9,\, 0.8)}_{\text{two-hop } r,\,s},\; \underbrace{0.5}_{\text{direct } t}\big) \;=\; \max(0.8,\, 0.5) \;=\; 0.8.$$

derivation of reach(p3, p1)	body facts and confidences	$\otimes = \min$ over the body
direct edge	edge(p3, p1) = 0.5	0.5
two-hop path	edge(p3, p2) = 0.9, reach(p2, p1) = 0.8	0.8
head: $\oplus = \max$ over derivations		0.8

The moral is that graded reachability follows the best route, not the shortest one: the strong two-hop path (0.8) outvotes the weak direct edge (0.5), so the annotation lands at 0.8. Running the module prints exactly this, alongside the same fact's four other provenance labels and the standalone lattice demo — this is the real, committed output of python3 annotated.py:

reachability of (p3, p1) — direct edge t, plus two-hop path r·s
  Boolean       : True
  Which-prov    : ['r', 's', 't']
  Why-prov      : [['r', 's'], ['t']]
  Polynomial    : t + r·s
  Confidence    : 0.8

confidence lattice [0,1]:
  ⊓(0.9, 0.8, 0.5) = 0.5  (conjunction: weakest link)
  ⊔(0.9, 0.8, 0.5) = 0.9  (disjunction: best case)

Notice the two "0.8"s and one "0.5" tell different stories. The Confidence : 0.8 line is the fixpoint answer — a join of meets, respecting the derivation structure of the two paths. The ⊓(0.9, 0.8, 0.5) = 0.5 line is the lattice demo treating all three edges as one flat conjunction, whose weakest link is the direct edge's 0.5. Same three numbers, different combination shapes, different results: structure is what the semiring buys you over a naive min of everything.

Annotated logic programs: rules that carry a number

The demo is one instance of a general pattern, the generalized annotated logic program [3]. In such a program every fact carries an annotation drawn from a lattice, every rule instance combines its body annotations with the lattice meet ($\otimes$), and a derived atom's annotation is the join ($\oplus$) over all rule instances that conclude it. That is precisely the line new[h] = sr.plus(new.get(h, sr.zero), prod) above: prod is one derivation's meet-over-the-body, and sr.plus accumulates the join-over-derivations into the head. For the Confidence lattice this reads "a rule is only as strong as its weakest premise, and a conclusion is as strong as its best rule instance" — which is why the two-hop path could lift reach(p3, p1) even though a single edge in it was no stronger than 0.8. Swap the lattice and the same program computes provenance, or plain Boolean entailment, or shortest-path cost; the annotation is a parameter, the engine is fixed.

The unsolved part

Graded confidence is genuinely useful, but two honest limits sit right at its edge. The first is inside the choice of t-norm. The Gödel min ignores independence: two independent sources that each vouch for a fact at 0.8 arguably justify more confidence than one alone, yet $\min$ — and indeed $\max$ over derivations — leaves the answer pinned at 0.8, where a probabilistic plus (the product t-conorm $x + y - xy$, the disjunctive dual of the product t-norm) would push two independent 0.8's up toward 0.96. Min/max confidence is therefore a coarse, deliberately optimistic bookkeeping, not a probability; treating a lattice degree as if it were a probability is a category error that quietly overstates what the number means.

The second limit is what the annotation cannot say at all. Confidence answers how sure; the previous chapter's provenance answers where from. Neither answers when. The fact faculty(alice) is not true-at-0.8 in some timeless way — it is true over an interval, say the years 2012 to 2025, and false outside it. A single number from $[0,1]$ has no room to carry a start and an end, so an entire dimension of real knowledge — validity over time — falls outside the whole apparatus of this chapter. That missing dimension is exactly the annotation the next chapter adds.

Why it matters

Annotated logic is the cleanest bridge from crisp symbolic reasoning toward the neural half of the series. A learned extractor or a neural link-predictor does not emit "true"; it emits a score in $[0,1]$ — which is to say, an annotation. Grounding those soft scores in a lattice and a semiring gives you a principled way to propagate them through a rule set instead of an ad-hoc one: min for a rule body, max over derivations, computed by the identical fixpoint climb that runs crisp reasoning. This is the seam Volume 4 widens, where min and max soften into differentiable operators so that a reasoner's confidence can be trained end to end; the crisp $\max(\min(\cdot))$ target computed here is the exact fixpoint that soft, learnable reasoners are trying to approximate. Knowing what the exact graded answer is — 0.8, and why — is what lets you check whether a learned system reached the right degree or merely a plausible-looking one.

Key terms

• Annotated (fuzzy) interpretation — a function sending each atom to a truth degree in $[0,1]$ instead of the crisp $\{0, 1\}$; the label changes, the facts do not.
• Confidence lattice — the interval $[0,1]$ ordered by $\le$, with meet $\sqcap = \min$ (weakest link) and join $\sqcup = \max$ (best case).
• Meet / join — the greatest lower bound $\min$ combining a conjunction, and the least upper bound $\max$ combining a disjunction's alternatives.
• Confidence semiring — $([0,1], \max, \min, 0.0, 1.0)$: plus is $\max$, times is $\min$, so the lattice is a semiring and the annotated fixpoint engine runs on it unchanged.
• t-norm (triangular norm) — a graded conjunction on $[0,1]$; $\min$ is the Gödel t-norm, idempotent and the largest, alongside the product and Łukasiewicz t-norms.
• Generalized annotated logic program — a program whose facts carry lattice annotations; each rule instance meets its body and each head joins over its derivations.
• The graded reachability answer — reach(p3, p1) has confidence $\max(\min(0.9, 0.8), 0.5) = 0.8$: the strong two-hop path beats the weak direct edge.

Where this leads

Confidence and provenance have told us how sure a fact is and where it came from, and both did so by hanging a single label on each fact and combining labels with a semiring. The next chapter, Temporal Reasoning, changes the kind of label from a number to an interval of time and asks the question this chapter could not: when does a fact hold, and how do two time-spans relate? It answers with Allen's interval algebra — the thirteen ways two intervals can sit relative to each other, with a composition table the companion file computes rather than hand-types — turning faculty(alice) from a timeless 0.8 into a fact that begins, ends, and lines up against every other fact in the academic world's timeline.