deduxit 0.5.0

A collection of logic suites: decides, checks, proves step by step and exports sequents of linear logic and of classical, intuitionistic and minimal propositional logic, with checked proofs, Kripke countermodels and Rocq certificates.
Documentation
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! The classical refuter: it looks for an assignment of truth values to
//! the atoms under which a goal's classical reading is false.
//!
//! The reading erases `!` and `?`, reads `⊗` and `&` as "and", `⅋` and
//! `⊕` as "or", `1` and `⊤` as true, `⊥` and `0` as false and `~a` as
//! "not a", and a sequent as the disjunction of its formulas. Every rule
//! of linear logic, in every mode, derives a tautology from tautologies:
//! Mix and weakening add a disjunct, and contraction repeats one. An
//! intuitionistic sequent's one-sided form reads as its implication. So
//! an assignment that falsifies a goal's reading proves it unprovable.
//!
//! The refuter runs after a search that did not prove the goal. It
//! backtracks over the goal's atoms in the order of their indices, trying
//! false before true. At every step it evaluates the reading in three
//! values, and it backs off where the reading is already true. Its work
//! is bounded, one unit per term evaluated, and so is its memory, by the
//! account.

use super::memory::{Account, Charged};
use super::refutation::Classical;
use crate::limits::{Phase, Progress};
use crate::linear::occurrences::{Forest, OccId};
use crate::linear::sequents::{Term, TermId};

/// A truth value of three: the reading under a partial assignment.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Value {
    /// False under every extension of the assignment.
    False,
    /// True under every extension.
    True,
    /// Not yet decided.
    Open,
}

impl Value {
    /// Returns the value of a conjunction.
    const fn and(self, other: Self) -> Self {
        match (self, other) {
            (Self::False, _) | (_, Self::False) => Self::False,
            (Self::True, Self::True) => Self::True,
            _ => Self::Open,
        }
    }

    /// Returns the value of a disjunction.
    const fn or(self, other: Self) -> Self {
        match (self, other) {
            (Self::True, _) | (_, Self::True) => Self::True,
            (Self::False, Self::False) => Self::False,
            _ => Self::Open,
        }
    }
}

/// Returns an assignment under which the classical reading of the goal
/// (`goal`'s occurrences of `forest`) is false, one value per atom of the
/// sequent by index.
///
/// Returns `None` when the reading is a tautology, when the search would
/// pass `work` units (one per term evaluated, so zero switches it off),
/// when its buffers do not fit `account`, when `stop` says so, or for a
/// forest with a quantifier. `stop` is asked before each evaluation, with
/// the units done.
pub(crate) fn refute(
    forest: &Forest,
    goal: &[OccId],
    work: u64,
    account: &Account,
    stop: &mut dyn FnMut(Progress) -> bool,
) -> Option<Classical> {
    // A first-order countermodel needs a domain, which an assignment of
    // truth values to atoms is not.
    if forest.has_binders() {
        return None;
    }
    let sequent = forest.sequent();
    let terms = sequent.terms();
    let members: Vec<TermId> = goal.iter().map(|&o| forest.term(o)).collect();
    let width = members.iter().map(|t| t.index() + 1).max().unwrap_or(0);
    let atoms = sequent.atom_names().len();
    // The bytes held: per term of the arena below the goal, one for its
    // mark and one for its value, and four for the order of the terms
    // reached; and two per atom.
    let bytes = width * 2 + width * 4 + atoms * 2;
    if !account.fits(bytes) {
        return None;
    }
    let mut held = Charged::new(account);
    held.charge(bytes);
    // The terms the goal reaches, in the arena's order: every term names
    // only terms before it, so this order evaluates operands first.
    let mut reached = vec![false; width];
    for t in &members {
        reached[t.index()] = true;
    }
    let mut order = Vec::new();
    let mut occurs = vec![false; atoms];
    for i in (0..width).rev() {
        if !reached[i] {
            continue;
        }
        let term = terms[i];
        for sub in term.subterms() {
            reached[sub.index()] = true;
        }
        if let Some(atom) = term.atom() {
            occurs[atom.index()] = true;
        }
        order.push(i as u32);
    }
    order.reverse();
    let cost = (order.len() as u64).max(1);
    let decided: Vec<usize> = (0..atoms).filter(|&a| occurs[a]).collect();
    let mut assigned: Vec<Option<bool>> = vec![None; atoms];
    let mut values = vec![Value::Open; width];
    // How many of `decided` have a value, and per depth whether its atom
    // was tried true too.
    let mut depth = 0;
    let mut both = vec![false; decided.len()];
    let mut done: u64 = 0;
    loop {
        // The bound is checked before each evaluation, so `done` never
        // passes `work`, a `u64`, and the addition below cannot overflow.
        if done.saturating_add(cost) > work || stop(Progress::new(Phase::Refute, cost, done)) {
            return None;
        }
        done += cost;
        let value = evaluate(terms, &order, &members, &assigned, &mut values);
        let descend = match value {
            Value::False => {
                let assignment = assigned.iter().map(|v| v.unwrap_or(false)).collect();
                return Some(Classical { assignment });
            }
            Value::Open => true,
            Value::True => false,
        };
        if descend {
            // An open value has an atom without a value below it.
            assigned[decided[depth]] = Some(false);
            both[depth] = false;
            depth += 1;
            continue;
        }
        loop {
            if depth == 0 {
                return None;
            }
            depth -= 1;
            if both[depth] {
                assigned[decided[depth]] = None;
            } else {
                assigned[decided[depth]] = Some(true);
                both[depth] = true;
                depth += 1;
                break;
            }
        }
    }
}

/// Returns the reading of the goal whose terms are `members` under the
/// partial assignment `assigned`, evaluating the terms of `order` (the
/// terms the goal reaches, operands first) into `values`.
fn evaluate(
    terms: &[Term],
    order: &[u32],
    members: &[TermId],
    assigned: &[Option<bool>],
    values: &mut [Value],
) -> Value {
    let of = |v: Option<bool>| match v {
        Some(true) => Value::True,
        Some(false) => Value::False,
        None => Value::Open,
    };
    for &i in order {
        let i = i as usize;
        values[i] = match terms[i] {
            Term::Atom(a) => of(assigned[a.index()]),
            Term::DualAtom(a) => of(assigned[a.index()].map(|v| !v)),
            Term::One | Term::Top => Value::True,
            Term::Bot | Term::Zero => Value::False,
            Term::Tensor(k, l) | Term::With(k, l) => values[k.index()].and(values[l.index()]),
            Term::Par(k, l) | Term::Plus(k, l) => values[k.index()].or(values[l.index()]),
            Term::Bang(k) | Term::Quest(k) => values[k.index()],
            Term::Forall(_) | Term::Exists(_) => {
                unreachable!("the classical refuter refuses a sequent with a binder")
            }
        };
    }
    members
        .iter()
        .fold(Value::False, |reading, t| reading.or(values[t.index()]))
}

#[cfg(all(test, feature = "parse"))]
mod tests {
    use super::*;
    use crate::linear::Sequent;

    /// Returns what the refuter finds for the roots of `input`.
    fn refuted(input: &str, work: u64) -> Option<Vec<bool>> {
        let sequent: Sequent = input.parse().unwrap();
        let forest = Forest::new(&sequent).unwrap();
        let account = Account::new(None);
        refute(&forest, forest.roots(), work, &account, &mut |_| false).map(|c| c.assignment)
    }

    /// A falsifying assignment is found where one exists, false tried
    /// first, a tautology is answered with none, and the bound and the
    /// stop give up.
    #[test]
    fn finds_an_assignment_within_its_bound() {
        assert_eq!(refuted("a |- b", 100), Some(vec![true, false]));
        assert_eq!(refuted("|- a, ~a", 100), None);
        assert_eq!(refuted("|- !(a -o b) -o ?a -o b", 100), None);
        assert_eq!(refuted("|- a * b, bot", 100), Some(vec![false, false]));
        assert_eq!(refuted("|- a * b, bot", 0), None);
        let sequent: Sequent = "a |- b".parse().unwrap();
        let forest = Forest::new(&sequent).unwrap();
        let account = Account::new(None);
        assert!(refute(&forest, forest.roots(), 100, &account, &mut |_| true).is_none());
    }

    /// The reading against checked proofs: every generated sequent the
    /// search proves, its proof checked, in every rule set and mode,
    /// classical, with Mix, affine and intuitionistic, reads as a
    /// tautology, so the refuter finds no assignment; and of the mutants,
    /// every one it refutes passes [`Disproof::check`] and none has a
    /// proof.
    #[test]
    fn checked_proofs_read_as_tautologies() {
        use crate::linear::Mode;
        use crate::linear::search::generate::{self, IllRules, Rng, Rules};
        use crate::linear::search::{Options, Refutation, Verdict, prove};
        let (mut proved, mut refuted) = (0, 0);
        let mut judge = |text: &str, mode: Mode, provable: bool| {
            let sequent: Sequent = text.parse().unwrap();
            let outcome = prove(&sequent, mode, &Options::default()).unwrap();
            let forest = Forest::new(&sequent).unwrap();
            let found = refute(
                &forest,
                forest.roots(),
                1 << 20,
                &Account::new(None),
                &mut |_| false,
            );
            match outcome.verdict {
                Verdict::Proved(_) => {
                    assert!(outcome.checked, "{text}");
                    assert_eq!(found, None, "{text} in {mode}: a checked proof");
                    proved += 1;
                }
                Verdict::Unprovable(disproof) => {
                    assert!(!provable, "{text} in {mode}: built from a proof");
                    if let Refutation::Classical(_) = disproof.refutation() {
                        assert_eq!(disproof.check(), Ok(()), "{text} in {mode}");
                        refuted += 1;
                    }
                }
                Verdict::Unknown(_) => assert_eq!(found, None, "{text} in {mode}"),
            }
        };
        for (i, rules) in Rules::ALL.into_iter().enumerate() {
            let mut rng = Rng::new(3100 + i as u64);
            for _ in 0..12 {
                let budget = 2 + rng.below(10);
                let mut formulas = generate::provable(&mut rng, rules, 3, budget).formulas;
                let base = if rules.mix {
                    Mode::CLASSICAL.with_mix()
                } else {
                    Mode::CLASSICAL
                };
                for mode in [base, base.with_affine()] {
                    judge(&generate::sequent(&formulas), mode, true);
                }
                if generate::mutate(&mut rng, &mut formulas, 3) {
                    judge(&generate::sequent(&formulas), base, false);
                }
            }
        }
        for (i, rules) in IllRules::ALL.into_iter().enumerate() {
            let mut rng = Rng::new(3200 + i as u64);
            for _ in 0..12 {
                let budget = 2 + rng.below(10);
                let ill = generate::ill(&mut rng, rules, 3, budget);
                let text = generate::two_sided(&ill.hypotheses, &ill.goal);
                for mode in [Mode::INTUITIONISTIC, Mode::INTUITIONISTIC.with_affine()] {
                    judge(&text, mode, true);
                }
            }
        }
        assert!(
            proved >= 400 && refuted > 0,
            "{proved} proved, {refuted} refuted"
        );
    }
}