Skip to main content

logicaffeine_proof/
cardinality.rs

1//! Cardinality constraints over boolean [`ProofExpr`] atoms — the missing primitive that lets the
2//! certified solver answer "at most / at least / exactly `k` of these are true". Encoded with
3//! Sinz's sequential counter (linear in `n·k`, fresh auxiliary atoms under a caller-chosen
4//! prefix), so the result is an ordinary boolean obligation the existing CNF/CDCL/RUP pipeline
5//! discharges. This is the building block for SAT-based optimization (`crate::optimize`).
6//!
7//! Correctness is pinned **exhaustively** against a brute-force oracle (every assignment, small n).
8
9use crate::ProofExpr;
10
11fn atom(s: String) -> ProofExpr {
12    ProofExpr::Atom(s)
13}
14fn and(a: ProofExpr, b: ProofExpr) -> ProofExpr {
15    ProofExpr::And(Box::new(a), Box::new(b))
16}
17fn not(a: ProofExpr) -> ProofExpr {
18    ProofExpr::Not(Box::new(a))
19}
20fn implies(a: ProofExpr, b: ProofExpr) -> ProofExpr {
21    ProofExpr::Implies(Box::new(a), Box::new(b))
22}
23fn tautology() -> ProofExpr {
24    let t = atom("__card_true".to_string());
25    ProofExpr::Or(Box::new(t.clone()), Box::new(not(t)))
26}
27fn contradiction() -> ProofExpr {
28    let f = atom("__card_false".to_string());
29    and(f.clone(), not(f))
30}
31fn conj(parts: Vec<ProofExpr>) -> ProofExpr {
32    let mut it = parts.into_iter();
33    match it.next() {
34        None => tautology(),
35        Some(first) => it.fold(first, and),
36    }
37}
38
39/// "At most `k` of `vars` are true." Auxiliary atoms are named `{aux}_{i}_{j}`, so distinct
40/// constraints in one formula must use distinct `aux` prefixes.
41pub fn at_most(vars: &[ProofExpr], k: usize, aux: &str) -> ProofExpr {
42    let n = vars.len();
43    if k >= n {
44        return tautology();
45    }
46    if k == 0 {
47        return conj(vars.iter().map(|v| not(v.clone())).collect());
48    }
49    // s(i, j) ≙ "at least j of x_1..x_i are true" (1-based).
50    let s = |i: usize, j: usize| atom(format!("{aux}_{i}_{j}"));
51    let mut clauses: Vec<ProofExpr> = Vec::new();
52
53    clauses.push(implies(vars[0].clone(), s(1, 1)));
54    for j in 2..=k {
55        clauses.push(not(s(1, j)));
56    }
57    for i in 2..=n {
58        let xi = vars[i - 1].clone();
59        clauses.push(implies(xi.clone(), s(i, 1)));
60        clauses.push(implies(s(i - 1, 1), s(i, 1)));
61        for j in 2..=k {
62            clauses.push(implies(and(xi.clone(), s(i - 1, j - 1)), s(i, j)));
63            clauses.push(implies(s(i - 1, j), s(i, j)));
64        }
65        // Already k counted and another true ⇒ would exceed k: forbidden.
66        clauses.push(not(and(xi, s(i - 1, k))));
67    }
68    conj(clauses)
69}
70
71/// "At least `k` of `vars` are true" — i.e. at most `n−k` are false.
72pub fn at_least(vars: &[ProofExpr], k: usize, aux: &str) -> ProofExpr {
73    let n = vars.len();
74    if k == 0 {
75        return tautology();
76    }
77    if k > n {
78        return contradiction();
79    }
80    let negated: Vec<ProofExpr> = vars.iter().map(|v| not(v.clone())).collect();
81    at_most(&negated, n - k, aux)
82}
83
84/// "Exactly `k` of `vars` are true."
85pub fn exactly(vars: &[ProofExpr], k: usize, aux: &str) -> ProofExpr {
86    and(
87        at_least(vars, k, &format!("{aux}_ge")),
88        at_most(vars, k, &format!("{aux}_le")),
89    )
90}
91
92#[cfg(test)]
93#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/cardinality/tests.rs"]
94mod tests;