Skip to main content

logicaffeine_proof/
hornsat.rs

1//! Horn-SAT in linear time via unit propagation (forward chaining).
2//!
3//! A Horn clause has at most one positive literal, so it reads as a definite implication
4//! `(body₁ ∧ … ∧ bodyₖ) → head` (or, with no positive literal, a goal `(body₁ ∧ …) → false`).
5//! Such a system has a unique **least model**, computed by O(n+m) forward chaining: start all-false
6//! and fire each implication whose body is fully established. The system is satisfiable iff the
7//! least model violates no goal clause. Both verdicts are certified — the least model is
8//! re-checkable, and an unsatisfiable system yields the derivation (the clauses that force a goal's
9//! body true) which [`is_refutation`] replays independently.
10
11use std::collections::VecDeque;
12
13/// A Horn clause `(body ⇒ head)`: the conjunction of the `body` variables implies `head`, or — when
14/// `head` is `None` — implies false (a goal/integrity clause).
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct HornClause {
17    /// Positive body variables (the antecedent conjunction).
18    pub body: Vec<usize>,
19    /// The implied variable, or `None` for a goal clause `body ⇒ false`.
20    pub head: Option<usize>,
21}
22
23impl HornClause {
24    /// A definite rule `body ⇒ head`.
25    pub fn rule(body: impl Into<Vec<usize>>, head: usize) -> Self {
26        HornClause {
27            body: body.into(),
28            head: Some(head),
29        }
30    }
31    /// A fact `⇒ head` (empty body).
32    pub fn fact(head: usize) -> Self {
33        HornClause {
34            body: Vec::new(),
35            head: Some(head),
36        }
37    }
38    /// A goal `body ⇒ false`.
39    pub fn goal(body: impl Into<Vec<usize>>) -> Self {
40        HornClause {
41            body: body.into(),
42            head: None,
43        }
44    }
45}
46
47/// The outcome of solving a Horn system.
48#[derive(Clone, Debug, PartialEq, Eq)]
49pub enum HornOutcome {
50    /// Satisfiable, with the **least** model (re-checkable via [`satisfies`]).
51    Sat(Vec<bool>),
52    /// Unsatisfiable, witnessed by the clause indices whose forward-chaining forces a goal's body
53    /// fully true (re-checkable via [`is_refutation`]).
54    Unsat(Vec<usize>),
55}
56
57/// Solve a Horn system over `0..num_vars` by forward chaining. Returns the least model, or — if a
58/// goal clause is forced — a certified derivation. Linear in the total clause size.
59pub fn solve(clauses: &[HornClause], num_vars: usize) -> HornOutcome {
60    let mut val = vec![false; num_vars];
61    let mut forced_by = vec![usize::MAX; num_vars]; // the clause that first set each variable true
62                                                    // Count of not-yet-true body variables per clause; a clause is ready to fire at count 0.
63    let mut remaining: Vec<usize> = clauses
64        .iter()
65        .map(|c| c.body.iter().filter(|&&b| b < num_vars).count())
66        .collect();
67    let mut in_body: Vec<Vec<usize>> = vec![Vec::new(); num_vars];
68    for (i, c) in clauses.iter().enumerate() {
69        for &b in &c.body {
70            if b < num_vars {
71                in_body[b].push(i);
72            }
73        }
74    }
75    let mut ready: VecDeque<usize> = (0..clauses.len()).filter(|&i| remaining[i] == 0).collect();
76    while let Some(ci) = ready.pop_front() {
77        match clauses[ci].head {
78            None => {
79                // A goal clause with a fully-established body — the system is unsatisfiable.
80                return HornOutcome::Unsat(derivation(clauses, ci, &forced_by));
81            }
82            Some(h) => {
83                if h < num_vars && !val[h] {
84                    val[h] = true;
85                    forced_by[h] = ci;
86                    for &cj in &in_body[h] {
87                        remaining[cj] -= 1;
88                        if remaining[cj] == 0 {
89                            ready.push_back(cj);
90                        }
91                    }
92                }
93            }
94        }
95    }
96    HornOutcome::Sat(val)
97}
98
99/// The transitive set of clauses supporting the conflict at goal clause `goal_ci`: the goal plus,
100/// recursively, the clause that forced each body variable.
101fn derivation(clauses: &[HornClause], goal_ci: usize, forced_by: &[usize]) -> Vec<usize> {
102    let mut used = vec![goal_ci];
103    let mut seen_clause: std::collections::HashSet<usize> = std::iter::once(goal_ci).collect();
104    let mut seen_var: std::collections::HashSet<usize> = std::collections::HashSet::new();
105    let mut stack: Vec<usize> = clauses[goal_ci].body.clone();
106    while let Some(v) = stack.pop() {
107        if !seen_var.insert(v) {
108            continue;
109        }
110        let fc = forced_by.get(v).copied().unwrap_or(usize::MAX);
111        if fc != usize::MAX && seen_clause.insert(fc) {
112            used.push(fc);
113            stack.extend(clauses[fc].body.iter().copied());
114        }
115    }
116    used
117}
118
119/// Re-check a satisfying model: every clause holds (a rule with a true body has a true head; a goal
120/// has a false body).
121pub fn satisfies(clauses: &[HornClause], assignment: &[bool]) -> bool {
122    clauses.iter().all(|c| {
123        let body_true = c
124            .body
125            .iter()
126            .all(|&b| b < assignment.len() && assignment[b]);
127        match c.head {
128            Some(h) => !body_true || (h < assignment.len() && assignment[h]),
129            None => !body_true,
130        }
131    })
132}
133
134/// Re-check a refutation: replaying *only* the listed clauses by forward chaining forces some goal
135/// clause's body fully true (a contradiction). A solver-free certificate of unsatisfiability.
136pub fn is_refutation(clauses: &[HornClause], num_vars: usize, refutation: &[usize]) -> bool {
137    let mut val = vec![false; num_vars];
138    loop {
139        let mut changed = false;
140        for &ci in refutation {
141            let Some(c) = clauses.get(ci) else {
142                return false;
143            };
144            if let Some(h) = c.head {
145                let body_true = c.body.iter().all(|&b| b < num_vars && val[b]);
146                if body_true && h < num_vars && !val[h] {
147                    val[h] = true;
148                    changed = true;
149                }
150            }
151        }
152        if !changed {
153            break;
154        }
155    }
156    refutation.iter().any(|&ci| {
157        clauses
158            .get(ci)
159            .is_some_and(|c| c.head.is_none() && c.body.iter().all(|&b| b < num_vars && val[b]))
160    })
161}
162
163#[cfg(test)]
164#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/hornsat/tests.rs"]
165mod tests;