logicaffeine_proof/
hornsat.rs1use std::collections::VecDeque;
12
13#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct HornClause {
17 pub body: Vec<usize>,
19 pub head: Option<usize>,
21}
22
23impl HornClause {
24 pub fn rule(body: impl Into<Vec<usize>>, head: usize) -> Self {
26 HornClause {
27 body: body.into(),
28 head: Some(head),
29 }
30 }
31 pub fn fact(head: usize) -> Self {
33 HornClause {
34 body: Vec::new(),
35 head: Some(head),
36 }
37 }
38 pub fn goal(body: impl Into<Vec<usize>>) -> Self {
40 HornClause {
41 body: body.into(),
42 head: None,
43 }
44 }
45}
46
47#[derive(Clone, Debug, PartialEq, Eq)]
49pub enum HornOutcome {
50 Sat(Vec<bool>),
52 Unsat(Vec<usize>),
55}
56
57pub 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]; 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 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
99fn 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
119pub 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
134pub 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;