💻 computer science

A Foundation for Differentiable Logics using Dependent Type Theory

This paper presents a unified formalization of differentiable and fuzzy logics within the Rocq proof assistant using dependent type theory, systematically comparing their analytic, algebraic, and proof-theoretic properties by interpreting them via residuated lattices, formalizing necessary calculus tools like L'Hôpital's rule, and establishing sound sequent calculi for both existing and new logical systems.

Original authors: Reynald Affeldt, Alessandro Bruni, Ekaterina Komendantskaya, Natalia Ślusarz, Kathrin Stark

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Reynald Affeldt, Alessandro Bruni, Ekaterina Komendantskaya, Natalia Ślusarz, Kathrin Stark

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to drive a car. You want the robot to be safe, but you also want it to learn from its mistakes. In the world of Artificial Intelligence (AI), we use Neural Networks (the robot's "brain") to learn. To teach them, we use a "scorecard" called a Loss Function. If the robot makes a mistake, the score goes up; if it does well, the score goes down. The robot tries to minimize this score to get better.

However, sometimes we want the robot to follow specific rules, like "Always stop at a red light" or "Never drive faster than 30 mph." This is where Differentiable Logics come in. They are a special kind of math that turns logical rules (like "If red, then stop") into a scorecard the robot can understand and optimize.

The Problem: A Tower of Babel

For a long time, researchers have been inventing different versions of these "rule-to-score" translators.

Some teams use Fuzzy Logics (old-school math from the 1920s that handles "maybe" and "sort of").
Other teams use Machine Learning Logics (newer math designed specifically for AI training).

The problem? They all speak different languages.

One team says "True" is the number 1.
Another says "True" is 0.
One uses a specific type of "AND" operation, while another uses a different one.
Some rules work perfectly for algebra, but break when you try to do calculus (the math of change and speed). Others work great for calculus but make no sense algebraically.

It's like trying to build a house where the bricks from the foundation are made of wood, the walls are made of glass, and the roof is made of water. They don't fit together, and you can't be sure the house will stand.

The Solution: A Universal Translator

This paper is like building a Universal Translator and a Master Blueprint for all these different logic systems. The authors used a powerful tool called Rocq (a digital proof assistant, think of it as a super-strict math referee) to translate every different logic system into a single, unified language.

Here is what they did, using some creative analogies:

1. The Algebraic Lens (The Lego Structure)

Imagine logic systems as sets of Lego blocks.

Fuzzy Logics are like a set of Legos that snap together perfectly in a specific way (called a Residuated Lattice). They are sturdy and well-understood.
New AI Logics were like a pile of random blocks that didn't seem to snap together.
The Paper's Discovery: The authors showed that some of the new AI blocks can actually snap together if you look at them from the right angle. They proved that a specific version of the new logic (called STL∞) is just as sturdy as the old Lego sets. However, they also found that if you try to make the blocks snap together perfectly (algebraically), they lose their ability to slide smoothly (calculus-wise). It's a trade-off: you can't have a block that is both perfectly rigid and perfectly slippery at the same time.

2. The Analytic Lens (The Smooth Slide)

In machine learning, the robot needs to "slide" down a hill to find the best solution. This requires the math to be smooth (differentiable).

Some old logic rules were like jagged rocks; if the robot tried to slide on them, it would get stuck.
The authors checked which rules allowed for a smooth slide. They discovered that some new rules (like DL2) are very smooth, while others (like the old Gödel logic) are too jagged.
The Big Win: They had to invent a new mathematical tool (a formal proof of L'Hôpital's Rule, a famous calculus trick) to prove that a complex new logic (STL) was actually smooth enough for the robot to use. It's like proving that a bumpy road is actually smooth enough for a race car if you look at it from a specific distance.

3. The Proof-Theoretic Lens (The Rulebook)

Every logic needs a rulebook (a Sequent Calculus) to ensure that if you start with true premises, you end up with a true conclusion.

The old fuzzy logics had excellent, well-written rulebooks.
The new AI logics were playing by the rules of the road without a written rulebook.
The Paper's Contribution: The authors wrote the first official rulebooks for the new AI logics (DL2 and STL∞). They proved that these new rulebooks are "sound," meaning they won't lead the robot into a logical trap.

Why Does This Matter?

Imagine you are a city planner.

Before this paper: You had different architects using different blueprints. One said "The wall must be 10 feet high," another said "The wall must be 3 meters high," and a third said "The wall must be 'very tall'." You couldn't build a safe building because the measurements didn't match.
After this paper: You have a single, unified blueprint. You can now compare the architects. You can say, "Hey, Architect A's design is great for stability, but Architect B's design is better for speed."

The Takeaway

This paper is a massive step toward Safe AI.
By putting all these different logic systems into one "sandbox" (the Rocq proof assistant), the authors:

Found errors in previous research (like finding a crack in a bridge before anyone drove over it).
Created a common language so mathematicians and AI engineers can finally talk to each other.
Built new tools (like the new rulebooks) that allow us to train AI to follow complex rules safely.

In short, they took a chaotic zoo of different mathematical ideas, organized them into a neat library, and gave us the keys to build smarter, safer, and more reliable AI systems.

1. Problem Statement

Differentiable logics (DLs) are quantitative logics emerging from machine learning (ML) literature, designed to translate logical properties into differentiable loss functions for "property-guided training" of neural networks. While fuzzy logics (e.g., Gödel, Łukasiewicz) have a century-old tradition of algebraic and proof-theoretic study, and new ML-inspired logics (e.g., DL2, STL) offer desirable analytic properties (like smoothness), there is a significant gap in their unification:

Lack of Unified Framework: Existing DLs differ in syntax, semantics domains (e.g., $[0,1]$ vs. $(-\infty, \infty)$ ), and algebraic structures.
Missing Algebraic/Proof-Theoretic Foundations: New ML logics often lack rigorous algebraic characterizations (e.g., residuated lattices) and proof-theoretic semantics (sequent calculi).
Analytic vs. Algebraic Trade-offs: Properties desirable for ML (like shadow-lifting, ensuring gradients exist for training) often conflict with algebraic properties (like associativity or idempotence).
Verification Gaps: Manual proofs in the literature often contain errors or are incomplete (e.g., missing cases in shadow-lifting proofs).

The paper aims to systematically compare, formalize, and unify the algebraic, analytic, and proof-theoretic properties of both fuzzy and differentiable logics to enable reliable formal verification of ML systems.

2. Methodology

The authors employ Interactive Theorem Proving (ITP) using the Rocq (formerly Coq) proof assistant and the MathComp library ecosystem.

Unified Syntax via Dependent Types: They define a generic syntax for differentiable logics using intrinsic typing. By using flags (e.g., neg_def, impl_def), the framework enforces valid formulas for specific logics (e.g., preventing negation in DL2 where it is undefined structurally). This allows multiple logics to be encoded in a single, extensible language.
Three-Axis Analysis: The formalization investigates properties across three dimensions:
1. Algebraic: Interpreting logics via Residuated Lattices (checking axioms like commutativity, associativity, and the residuation property $x \odot y \leq z \iff y \leq x \Rightarrow z$ ).
2. Analytic: Formalizing Shadow-lifting (the property that partial derivatives of logical connectives are positive, ensuring training gradients exist). This required formalizing L'Hôpital's rule within MathComp-Analysis, which was previously missing.
3. Proof-Theoretic: Defining and proving the soundness of Hypersequent Calculi (a generalization of Gentzen sequent calculi) for these logics.
Formal Verification: All definitions, theorems, and proofs are mechanized in Rocq. The authors use this to verify existing literature, find errors, and prove new results.

3. Key Contributions

A. Unified Formalization Framework

Created a generic encoding of differentiable logics (Gödel, Łukasiewicz, Yager, Product, DL2, STL $_\nu$ , STL $_\infty$ ) in Rocq.
Used dependent types to ensure that only well-typed formulas are constructible for each specific logic variant.
Extended the MathComp library with new lemmas, including a formal proof of L'Hôpital's rule and properties of partial derivatives.

B. Algebraic Results (Residuated Lattices)

Characterization: Proved that Gödel, Łukasiewicz, Yager, Product, DL2, and the limit case STL $_\infty$ form residuated lattices.
STL $_\nu$ vs. STL $_\infty$ : Demonstrated that STL $_\nu$ (with finite parameter $\nu$ ) is not a residuated lattice due to non-associativity. However, as $\nu \to \infty$ , STL $_\nu$ converges to STL $_\infty$ , which does satisfy lattice axioms.
Negation: Formalized that negation in Gödel and Product logic is not involutive, while Łukasiewicz and Yager are.

C. Analytic Results (Shadow-Lifting)

Formal Proof of Shadow-Lifting: Provided the first complete formal proof of the shadow-lifting property for STL $_\nu$ . The original paper by Varnai and Dimarogonas provided only a sketch; the authors completed the missing cases (specifically $p_{min} < 0$ ) using L'Hôpital's rule.
Trade-off Confirmation: Verified the theoretical impossibility of a logic satisfying Idempotence, Associativity, and Shadow-lifting simultaneously.
- Example: STL $_\nu$ has shadow-lifting but lacks associativity. STL $_\infty$ has associativity but loses shadow-lifting.

D. Proof-Theoretic Results (Sequent Calculi)

Fuzzy Logics: Formalized soundness for existing hypersequent calculi for Gödel, Łukasiewicz, and Product logics.
New Calculi: Proposed and proved soundness for:
- DL2: A new hypersequent calculus tailored to its specific semantics (involving real number comparisons).
- STL $_\infty$ : A calculus for the limit case of STL, which behaves like Gödel logic but with extended reals.
Weak Completeness: Showed that the new calculi for DL2 and STL $_\infty$ are weakly complete (relevant axioms are provable).

E. Error Correction

Identified and fixed errors in previous pen-and-paper proofs regarding the interval properties of comparison operators in fuzzy logics extended with comparisons.
Corrected incomplete proofs regarding the shadow-lifting of STL $_\nu$ .

4. Results Summary

The paper provides a comprehensive table (Table 6 in the paper) categorizing logics by their properties:

Gödel: Residuated lattice, Idempotent, Sound calculus, No shadow-lifting.
Łukasiewicz: Residuated lattice, Involution, Sound calculus, No shadow-lifting.
Product: Residuated lattice, Sound calculus, Has shadow-lifting, No idempotence.
DL2: Residuated lattice, Has shadow-lifting, No idempotence, No structural negation.
STL $_\nu$ : Has shadow-lifting, No lattice/monoid axioms (non-associative).
STL $_\infty$ : Residuated lattice, No shadow-lifting, Sound calculus.

The formalization confirms that Product logic and DL2 are the most promising candidates for reconciling algebraic, analytic, and proof-theoretic requirements, though they sacrifice idempotence.

5. Significance

Bridging Communities: The work unifies the algebraic tradition of fuzzy logic (substructural logics) with the analytic needs of machine learning, providing a common language for researchers in both fields.
Reliability in AI Verification: By formally verifying the properties of logics used to generate loss functions, the paper lays the groundwork for certified property-guided training. This ensures that the translation from logical specifications to optimization objectives is mathematically sound.
Tooling for AI: The Rocq formalization serves as a reference implementation for future tools (like the Vehicle DSL) that aim to compile high-level specifications into neural network verifiers and training loops.
Mathematical Library Expansion: The addition of L'Hôpital's rule and partial derivative theories to the MathComp library benefits the broader formal mathematics community, not just AI research.

In conclusion, this paper establishes a rigorous, machine-checked foundation for differentiable logics, resolving ambiguities in the literature and providing the necessary theoretical tools to build reliable, formally verified machine learning systems.