logicaffeine_proof/
cardinality.rs1use 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
39pub 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 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 clauses.push(not(and(xi, s(i - 1, k))));
67 }
68 conj(clauses)
69}
70
71pub 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
84pub 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;