Skip to main content

logicaffeine_proof/
grounding.rs

1//! Finite-domain grounding.
2//!
3//! A logic grid — and any finite, domain-closed problem — becomes DECIDABLE by
4//! expanding bounded quantifiers over the finite set of individuals named in the
5//! premises:
6//!
7//! ```text
8//! ∀x. φ(x)   over {a, b, c, d}   →   φ(a) ∧ φ(b) ∧ φ(c) ∧ φ(d)
9//! ∃x. φ(x)   over {a, b, c, d}   →   φ(a) ∨ φ(b) ∨ φ(c) ∨ φ(d)
10//! ```
11//!
12//! The result is QUANTIFIER-FREE, so our kernel proves it (certified, explainable)
13//! and Z3 decides it in milliseconds — no e-matching, no search blowup, guaranteed
14//! to terminate. This is general and reusable: it knows nothing about any specific
15//! puzzle, only about quantifiers and the finite domain the premises declare.
16
17use crate::{ProofExpr, ProofTerm};
18
19/// Ground every quantifier in `e` over `domain` (Herbrand expansion): a universal
20/// becomes the conjunction of its instances, an existential the disjunction. The
21/// returned expression is quantifier-free when `domain` covers the universe.
22///
23/// Sound AND complete for a domain-CLOSED finite problem (every individual named):
24/// `∀x.φ ≡ ⋀_c φ[x:=c]` and `∃x.φ ≡ ⋁_c φ[x:=c]` exactly when the witness/
25/// counter-example is guaranteed to be one of the `c`.
26pub fn ground(e: &ProofExpr, domain: &[ProofTerm]) -> ProofExpr {
27    match e {
28        ProofExpr::ForAll { variable, body } => fold_conj(
29            domain
30                .iter()
31                .map(|c| ground(&subst(body, variable, c), domain)),
32        ),
33        ProofExpr::Exists { variable, body } => fold_disj(
34            domain
35                .iter()
36                .map(|c| ground(&subst(body, variable, c), domain)),
37        ),
38        ProofExpr::And(l, r) => {
39            ProofExpr::And(Box::new(ground(l, domain)), Box::new(ground(r, domain)))
40        }
41        ProofExpr::Or(l, r) => {
42            ProofExpr::Or(Box::new(ground(l, domain)), Box::new(ground(r, domain)))
43        }
44        ProofExpr::Implies(l, r) => {
45            ProofExpr::Implies(Box::new(ground(l, domain)), Box::new(ground(r, domain)))
46        }
47        ProofExpr::Iff(l, r) => {
48            ProofExpr::Iff(Box::new(ground(l, domain)), Box::new(ground(r, domain)))
49        }
50        ProofExpr::Not(x) => ProofExpr::Not(Box::new(ground(x, domain))),
51        ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
52            operator: operator.clone(),
53            body: Box::new(ground(body, domain)),
54        },
55        // Quantifier-free leaves (Predicate, Identity, Atom, Term, …) are unchanged.
56        leaf => leaf.clone(),
57    }
58}
59
60/// Left-fold instances into a conjunction; an empty domain makes `∀` vacuously true.
61fn fold_conj(mut it: impl Iterator<Item = ProofExpr>) -> ProofExpr {
62    match it.next() {
63        None => ProofExpr::Atom("True".to_string()),
64        Some(first) => it.fold(first, |acc, e| ProofExpr::And(Box::new(acc), Box::new(e))),
65    }
66}
67
68/// Left-fold instances into a disjunction; an empty domain makes `∃` false.
69fn fold_disj(mut it: impl Iterator<Item = ProofExpr>) -> ProofExpr {
70    match it.next() {
71        None => ProofExpr::Atom("False".to_string()),
72        Some(first) => it.fold(first, |acc, e| ProofExpr::Or(Box::new(acc), Box::new(e))),
73    }
74}
75
76/// Substitute the bound variable `var` with the term `to` throughout `e`, stopping
77/// at any quantifier that re-binds `var` (capture avoidance).
78fn subst(e: &ProofExpr, var: &str, to: &ProofTerm) -> ProofExpr {
79    match e {
80        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
81            name: name.clone(),
82            args: args.iter().map(|a| subst_term(a, var, to)).collect(),
83            world: world.clone(),
84        },
85        ProofExpr::Identity(a, b) => {
86            ProofExpr::Identity(subst_term(a, var, to), subst_term(b, var, to))
87        }
88        ProofExpr::And(l, r) => {
89            ProofExpr::And(Box::new(subst(l, var, to)), Box::new(subst(r, var, to)))
90        }
91        ProofExpr::Or(l, r) => {
92            ProofExpr::Or(Box::new(subst(l, var, to)), Box::new(subst(r, var, to)))
93        }
94        ProofExpr::Implies(l, r) => {
95            ProofExpr::Implies(Box::new(subst(l, var, to)), Box::new(subst(r, var, to)))
96        }
97        ProofExpr::Iff(l, r) => {
98            ProofExpr::Iff(Box::new(subst(l, var, to)), Box::new(subst(r, var, to)))
99        }
100        ProofExpr::Not(x) => ProofExpr::Not(Box::new(subst(x, var, to))),
101        ProofExpr::ForAll { variable, body } if variable != var => ProofExpr::ForAll {
102            variable: variable.clone(),
103            body: Box::new(subst(body, var, to)),
104        },
105        ProofExpr::Exists { variable, body } if variable != var => ProofExpr::Exists {
106            variable: variable.clone(),
107            body: Box::new(subst(body, var, to)),
108        },
109        ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
110            operator: operator.clone(),
111            body: Box::new(subst(body, var, to)),
112        },
113        ProofExpr::Term(t) => ProofExpr::Term(subst_term(t, var, to)),
114        // Re-bound quantifiers, Atom, etc. — left as-is.
115        other => other.clone(),
116    }
117}
118
119/// The DOMAIN of a problem: every constant named across `exprs`. For a
120/// domain-closed finite problem this is the universe of individuals to ground over.
121pub fn domain_constants(exprs: &[ProofExpr]) -> Vec<ProofTerm> {
122    let mut out: Vec<String> = Vec::new();
123    for e in exprs {
124        collect_constants(e, &mut out);
125    }
126    out.sort();
127    out.dedup();
128    out.into_iter().map(ProofTerm::Constant).collect()
129}
130
131fn collect_constants(e: &ProofExpr, out: &mut Vec<String>) {
132    fn term(t: &ProofTerm, out: &mut Vec<String>) {
133        match t {
134            ProofTerm::Constant(s) => out.push(s.clone()),
135            ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
136                args.iter().for_each(|a| term(a, out))
137            }
138            _ => {}
139        }
140    }
141    match e {
142        ProofExpr::Predicate { args, .. } => args.iter().for_each(|a| term(a, out)),
143        ProofExpr::Identity(a, b) => {
144            term(a, out);
145            term(b, out);
146        }
147        ProofExpr::And(l, r)
148        | ProofExpr::Or(l, r)
149        | ProofExpr::Implies(l, r)
150        | ProofExpr::Iff(l, r) => {
151            collect_constants(l, out);
152            collect_constants(r, out);
153        }
154        ProofExpr::Not(x) => collect_constants(x, out),
155        ProofExpr::ForAll { body, .. }
156        | ProofExpr::Exists { body, .. }
157        | ProofExpr::Temporal { body, .. } => collect_constants(body, out),
158        ProofExpr::Term(t) => term(t, out),
159        _ => {}
160    }
161}
162
163use std::collections::HashMap;
164
165/// Per-sort domains: for each UNARY predicate used as a sort guard (`Trip`,
166/// `Year`, …), the constants asserted to have it. Built from the ground facts the
167/// declarations produce (`Trip(Alpha)`, `Trip(Beta)`, …). This is what lets
168/// grounding expand `∀x(Trip(x)→…)` over the 4 trips, not the whole universe.
169pub fn sort_domains(premises: &[ProofExpr]) -> HashMap<String, Vec<ProofTerm>> {
170    fn collect(e: &ProofExpr, m: &mut HashMap<String, Vec<ProofTerm>>) {
171        match e {
172            ProofExpr::Predicate { name, args, .. } if args.len() == 1 => {
173                if let ProofTerm::Constant(_) = &args[0] {
174                    let dom = m.entry(name.clone()).or_default();
175                    if !dom.contains(&args[0]) {
176                        dom.push(args[0].clone());
177                    }
178                }
179            }
180            // Sort facts are ground premises, possibly under top-level conjunction;
181            // do NOT descend into quantifiers (those are rules, not facts).
182            ProofExpr::And(l, r) => {
183                collect(l, m);
184                collect(r, m);
185            }
186            _ => {}
187        }
188    }
189    let mut m = HashMap::new();
190    for p in premises {
191        collect(p, &mut m);
192    }
193    m
194}
195
196/// The unary-predicate SORT guarding `var` in `e` (e.g. `Trip` in `Trip(x) → …` or
197/// `Trip(x) ∧ …`), if any — used to pick the right finite domain to ground over.
198fn guard_sort(e: &ProofExpr, var: &str) -> Option<String> {
199    match e {
200        ProofExpr::Predicate { name, args, .. }
201            if args.len() == 1
202                && matches!(&args[0], ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == var) =>
203        {
204            Some(name.clone())
205        }
206        ProofExpr::And(l, r)
207        | ProofExpr::Or(l, r)
208        | ProofExpr::Implies(l, r)
209        | ProofExpr::Iff(l, r) => guard_sort(l, var).or_else(|| guard_sort(r, var)),
210        ProofExpr::Not(x) | ProofExpr::Temporal { body: x, .. } => guard_sort(x, var),
211        // Recurse through a nested quantifier (that does not re-bind `var`) so an
212        // of-pair "∃x(∃y(Trip(x) ∧ … ))" still finds x's guard `Trip` and grounds x
213        // over the 4 trips, not the whole universe (where a phantom non-trip could
214        // satisfy it).
215        ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body }
216            if variable != var =>
217        {
218            guard_sort(body, var)
219        }
220        _ => None,
221    }
222}
223
224/// SORT-AWARE grounding: a guarded quantifier expands only over its sort's domain
225/// (`∀x(Trip(x)→…)` over the trips), falling back to `fallback` (the full universe)
226/// for an unsorted quantifier. Sound for a domain-closed problem and dramatically
227/// smaller than universe-grounding — the optimization the larger puzzles need.
228pub fn ground_sorted(
229    e: &ProofExpr,
230    sorts: &HashMap<String, Vec<ProofTerm>>,
231    fallback: &[ProofTerm],
232) -> ProofExpr {
233    let domain_for = |body: &ProofExpr, var: &str| -> Vec<ProofTerm> {
234        guard_sort(body, var)
235            .and_then(|s| sorts.get(&s).cloned())
236            .unwrap_or_else(|| fallback.to_vec())
237    };
238    match e {
239        ProofExpr::ForAll { variable, body } => {
240            let dom = domain_for(body, variable);
241            fold_conj(
242                dom.iter()
243                    .map(|c| ground_sorted(&subst(body, variable, c), sorts, fallback)),
244            )
245        }
246        ProofExpr::Exists { variable, body } => {
247            let dom = domain_for(body, variable);
248            fold_disj(
249                dom.iter()
250                    .map(|c| ground_sorted(&subst(body, variable, c), sorts, fallback)),
251            )
252        }
253        ProofExpr::And(l, r) => ProofExpr::And(
254            Box::new(ground_sorted(l, sorts, fallback)),
255            Box::new(ground_sorted(r, sorts, fallback)),
256        ),
257        ProofExpr::Or(l, r) => ProofExpr::Or(
258            Box::new(ground_sorted(l, sorts, fallback)),
259            Box::new(ground_sorted(r, sorts, fallback)),
260        ),
261        ProofExpr::Implies(l, r) => ProofExpr::Implies(
262            Box::new(ground_sorted(l, sorts, fallback)),
263            Box::new(ground_sorted(r, sorts, fallback)),
264        ),
265        ProofExpr::Iff(l, r) => ProofExpr::Iff(
266            Box::new(ground_sorted(l, sorts, fallback)),
267            Box::new(ground_sorted(r, sorts, fallback)),
268        ),
269        ProofExpr::Not(x) => ProofExpr::Not(Box::new(ground_sorted(x, sorts, fallback))),
270        ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
271            operator: operator.clone(),
272            body: Box::new(ground_sorted(body, sorts, fallback)),
273        },
274        leaf => leaf.clone(),
275    }
276}
277
278/// [`ground_problem`] but sort-aware (each quantifier grounds over its guard
279/// sort). The default entry point for finite-domain solving.
280pub fn ground_problem_sorted(
281    premises: &[ProofExpr],
282    goal: &ProofExpr,
283) -> (Vec<ProofExpr>, ProofExpr) {
284    let mut all: Vec<ProofExpr> = premises.to_vec();
285    all.push(goal.clone());
286    let fallback = domain_constants(&all);
287    let sorts = sort_domains(premises);
288    let gp = premises
289        .iter()
290        .map(|p| ground_sorted(p, &sorts, &fallback))
291        .collect();
292    let gg = ground_sorted(goal, &sorts, &fallback);
293    (gp, gg)
294}
295
296/// Ground a whole problem — premises AND goal — over the domain of constants they
297/// name. The returned premises and goal are quantifier-free (so the kernel proves
298/// them, certified, and Z3 decides them instantly).
299pub fn ground_problem(premises: &[ProofExpr], goal: &ProofExpr) -> (Vec<ProofExpr>, ProofExpr) {
300    let mut all: Vec<ProofExpr> = premises.to_vec();
301    all.push(goal.clone());
302    let domain = domain_constants(&all);
303    let grounded_premises = premises.iter().map(|p| ground(p, &domain)).collect();
304    let grounded_goal = ground(goal, &domain);
305    (grounded_premises, grounded_goal)
306}
307
308/// "Exactly one φ" entails "at most one φ" — for every premise of the form
309/// `∃x(φ(x) ∧ ∀y(φ(y) → y = x))` (what `Cardinal(1)` produces), emit the PAIRWISE
310/// uniqueness `∀x∀y((φ(x) ∧ φ(y)) → x = y)`.
311///
312/// Why: the existence form grounds to a DISJUNCTION whose disjuncts nest the
313/// uniqueness rule, which the certified backward-chainer cannot use directly; the
314/// pairwise form grounds to plain conjunctive implications it discharges by forward
315/// chaining (the shape `grounded_two_value_grid_proves_with_our_kernel` proves). The
316/// lemma is logically ENTAILED by the original, so adding it is sound, and it is
317/// GENERAL over any "exactly one" statement — never tied to a particular puzzle.
318pub fn at_most_one_lemmas(premises: &[ProofExpr]) -> Vec<ProofExpr> {
319    premises.iter().filter_map(at_most_one_of).collect()
320}
321
322/// FUNCTIONALITY — the missing half of a grid's bijection. Each closure
323/// `∀x(guard(x) → L1 ∨ L2 ∨ … ∨ Ln)` says a row takes AT LEAST one value; this emits
324/// the AT MOST ONE companion `∀x(Li → ¬Lj)` for every ordered pair of distinct
325/// disjuncts. A trip is in exactly one state (one year, …), so a value assigned to a
326/// row EXCLUDES the row's other values — the propagation that, together with
327/// value-uniqueness, determines the whole grid. Sound: for a square grid functionality
328/// is entailed by closure + value-uniqueness + counting, and it is in any case the
329/// inherent single-valuedness of the attribute. Each `Li` must be an atom mentioning
330/// the bound variable (a genuine closure), so unrelated `∀→∨` premises are skipped.
331pub fn functionality_lemmas(premises: &[ProofExpr]) -> Vec<ProofExpr> {
332    let mut out = Vec::new();
333    for p in premises {
334        let ProofExpr::ForAll { variable, body } = p else {
335            continue;
336        };
337        let ProofExpr::Implies(_guard, cons) = body.as_ref() else {
338            continue;
339        };
340        let lits = flatten_or(cons);
341        let all_atoms_on_var = lits.len() >= 2
342            && lits.iter().all(|l| {
343                matches!(l, ProofExpr::Predicate { args, .. }
344                    if args.iter().any(|a| matches!(a, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == variable)))
345            });
346        if !all_atoms_on_var {
347            continue;
348        }
349        for (i, li) in lits.iter().enumerate() {
350            for (j, lj) in lits.iter().enumerate() {
351                if i == j {
352                    continue;
353                }
354                out.push(ProofExpr::ForAll {
355                    variable: variable.clone(),
356                    body: Box::new(ProofExpr::Implies(
357                        Box::new(li.clone()),
358                        Box::new(ProofExpr::Not(Box::new(lj.clone()))),
359                    )),
360                });
361            }
362        }
363    }
364    out
365}
366
367/// HIDDEN SINGLE — the COLUMN closure, dual of the row closure. Each `Exactly one φ`
368/// premise (`∃x(φ(x) ∧ ∀y(φ(y) → y = x))`, e.g. "exactly one trip is in Florida")
369/// entails that AT LEAST ONE row holds the value: `⋁_{r∈dom} value(r)`. The row closure
370/// says a row takes SOME value; this says a value is taken by SOME row. Together with
371/// functionality (a row takes at most one value), it is the deduction a human calls a
372/// "hidden single" — once every other row is excluded from a value, the remaining row
373/// MUST hold it, and the EXISTING literal unit-propagation forces it.
374///
375/// Grounded over the guard sort's finite domain into a pure value-literal disjunction
376/// (the sort guard `Trip(r)` is dropped — every `r` in the domain is a trip). Sound:
377/// `∃x φ(x)` is just the existence half of "exactly one", here merely grounded — `compile`
378/// otherwise SKIPS the `∃`, so the solver never sees the column closure without this.
379/// Structural over any declared square bijection; never keyed to a particular puzzle.
380pub fn column_closure_lemmas(premises: &[ProofExpr]) -> Vec<ProofExpr> {
381    let domains = sort_domains(premises);
382    let mut flat: Vec<ProofExpr> = Vec::new();
383    for p in premises {
384        flatten_and_into(p, &mut flat);
385    }
386    let mut out = Vec::new();
387    for p in &flat {
388        // Only the bare "exactly one" existentials — `at_most_one_of` recognises exactly
389        // that shape (nested ∃∃ of-pairs and definite descriptions are NOT it).
390        if at_most_one_of(p).is_none() {
391            continue;
392        }
393        let ProofExpr::Exists { variable: x, body } = p else {
394            continue;
395        };
396        let ProofExpr::And(phi_x, _uniq) = body.as_ref() else {
397            continue;
398        };
399        let Some(sort) = guard_sort(phi_x, x) else {
400            continue;
401        };
402        let Some(domain) = domains.get(&sort) else {
403            continue;
404        };
405        if domain.len() < 2 {
406            continue;
407        }
408        // The VALUE part of φ (φ with the sort guard `sort(x)` stripped), grounded at
409        // each row of the domain and OR-folded: `value(r1) ∨ … ∨ value(rn)`.
410        let value = strip_sort_guard(phi_x, &sort, x);
411        let mut disj: Option<ProofExpr> = None;
412        for r in domain {
413            let lit_r = subst(&value, x, r);
414            disj = Some(match disj {
415                None => lit_r,
416                Some(acc) => ProofExpr::Or(Box::new(acc), Box::new(lit_r)),
417            });
418        }
419        if let Some(d) = disj {
420            out.push(d);
421        }
422    }
423    out
424}
425
426/// Drop the unary sort-guard conjunct `sort(var)` from a (conjunctive) property `phi`,
427/// leaving the value literal(s). `Trip(x) ∧ In(x, Florida) ↦ In(x, Florida)`.
428fn strip_sort_guard(phi: &ProofExpr, sort: &str, var: &str) -> ProofExpr {
429    let is_guard = |e: &ProofExpr| {
430        matches!(e, ProofExpr::Predicate { name, args, .. }
431            if name == sort && args.len() == 1
432                && matches!(&args[0], ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == var))
433    };
434    if let ProofExpr::And(l, r) = phi {
435        if is_guard(l) {
436            return strip_sort_guard(r, sort, var);
437        }
438        if is_guard(r) {
439            return strip_sort_guard(l, sort, var);
440        }
441        return ProofExpr::And(
442            Box::new(strip_sort_guard(l, sort, var)),
443            Box::new(strip_sort_guard(r, sort, var)),
444        );
445    }
446    phi.clone()
447}
448
449fn flatten_or(e: &ProofExpr) -> Vec<ProofExpr> {
450    match e {
451        ProofExpr::Or(l, r) => {
452            let mut v = flatten_or(l);
453            v.extend(flatten_or(r));
454            v
455        }
456        _ => vec![e.clone()],
457    }
458}
459
460/// Discharge known ground UNARY facts (`Trip(Alpha)`, …) throughout the premises:
461/// each is true, so replace it with `True` and simplify `True ∧ X ↦ X`,
462/// `True → X ↦ X`. Unit propagation on the sort facts — it strips the sort guards out
463/// of every grounded clause (`(Trip(x) ∧ In(x,FL)) ∧ … ↦ In(x,FL) ∧ …`, and a closure
464/// `Trip(t) → D ↦ D` becomes a bare disjunction fact), leaving the pure value-literal
465/// clauses propagation runs on in ONE step. Sound: a true conjunct/antecedent carries
466/// no information.
467pub fn discharge_unary_facts(premises: &[ProofExpr]) -> Vec<ProofExpr> {
468    // Collect ground unary facts from FLATTENED premises — a multi-entity declaration
469    // ("Alpha, Beta, Gamma, Delta are four different trips") arrives as one conjunction,
470    // so `Trip(Alpha)…` live nested inside it, not as top-level premises.
471    let mut flat: Vec<ProofExpr> = Vec::new();
472    for p in premises {
473        flatten_and_into(p, &mut flat);
474    }
475    let mut facts: Vec<(String, String)> = Vec::new();
476    for p in &flat {
477        if let ProofExpr::Predicate { name, args, .. } = p {
478            if let [ProofTerm::Constant(c)] = args.as_slice() {
479                let key = (name.clone(), c.clone());
480                if !facts.contains(&key) {
481                    facts.push(key);
482                }
483            }
484        }
485    }
486    premises.iter().map(|p| discharge(p, &facts)).collect()
487}
488
489fn is_true(e: &ProofExpr) -> bool {
490    matches!(e, ProofExpr::Atom(s) if s == "True")
491}
492
493fn is_false(e: &ProofExpr) -> bool {
494    matches!(e, ProofExpr::Atom(s) if s == "False")
495}
496
497/// Fold away trivial (reflexive) identities and the boolean constants they create: a
498/// grounded `∃x∃y` of-pair has a DIAGONAL instance (`x = y = c`) carrying `¬(c = c)`,
499/// which is `False`, so that disjunct must drop. Without it the solver would face an
500/// unsatisfiable disjunct it cannot refute (the kernel has no reflexivity rule to prove
501/// `c = c`). `Identity(c,c) ↦ True`, `¬True ↦ False`, then `∧`/`∨`/`→` constant-fold.
502pub fn simplify_trivial_identities(premises: &[ProofExpr]) -> Vec<ProofExpr> {
503    premises.iter().map(simplify_ident).collect()
504}
505
506fn simplify_ident(e: &ProofExpr) -> ProofExpr {
507    match e {
508        ProofExpr::Identity(a, b) if a == b => ProofExpr::Atom("True".to_string()),
509        ProofExpr::Not(inner) => {
510            let s = simplify_ident(inner);
511            if is_true(&s) {
512                ProofExpr::Atom("False".to_string())
513            } else if is_false(&s) {
514                ProofExpr::Atom("True".to_string())
515            } else {
516                ProofExpr::Not(Box::new(s))
517            }
518        }
519        ProofExpr::And(l, r) => {
520            let (l, r) = (simplify_ident(l), simplify_ident(r));
521            if is_false(&l) || is_false(&r) {
522                ProofExpr::Atom("False".to_string())
523            } else if is_true(&l) {
524                r
525            } else if is_true(&r) {
526                l
527            } else {
528                ProofExpr::And(Box::new(l), Box::new(r))
529            }
530        }
531        ProofExpr::Or(l, r) => {
532            let (l, r) = (simplify_ident(l), simplify_ident(r));
533            if is_true(&l) || is_true(&r) {
534                ProofExpr::Atom("True".to_string())
535            } else if is_false(&l) {
536                r
537            } else if is_false(&r) {
538                l
539            } else {
540                ProofExpr::Or(Box::new(l), Box::new(r))
541            }
542        }
543        ProofExpr::Implies(l, r) => {
544            let (l, r) = (simplify_ident(l), simplify_ident(r));
545            if is_false(&l) || is_true(&r) {
546                ProofExpr::Atom("True".to_string())
547            } else if is_true(&l) {
548                r
549            } else {
550                ProofExpr::Implies(Box::new(l), Box::new(r))
551            }
552        }
553        ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
554            variable: variable.clone(),
555            body: Box::new(simplify_ident(body)),
556        },
557        ProofExpr::Exists { variable, body } => ProofExpr::Exists {
558            variable: variable.clone(),
559            body: Box::new(simplify_ident(body)),
560        },
561        other => other.clone(),
562    }
563}
564
565fn discharge(e: &ProofExpr, facts: &[(String, String)]) -> ProofExpr {
566    match e {
567        ProofExpr::Predicate { name, args, .. } => {
568            if let [ProofTerm::Constant(c)] = args.as_slice() {
569                if facts.iter().any(|(n, k)| n == name && k == c) {
570                    return ProofExpr::Atom("True".to_string());
571                }
572            }
573            e.clone()
574        }
575        ProofExpr::And(l, r) => {
576            let (l, r) = (discharge(l, facts), discharge(r, facts));
577            match (is_true(&l), is_true(&r)) {
578                (true, _) => r,
579                (_, true) => l,
580                _ => ProofExpr::And(Box::new(l), Box::new(r)),
581            }
582        }
583        ProofExpr::Implies(l, r) => {
584            let (l, r) = (discharge(l, facts), discharge(r, facts));
585            if is_true(&l) {
586                r
587            } else {
588                ProofExpr::Implies(Box::new(l), Box::new(r))
589            }
590        }
591        ProofExpr::Or(l, r) => {
592            ProofExpr::Or(Box::new(discharge(l, facts)), Box::new(discharge(r, facts)))
593        }
594        ProofExpr::Not(x) => ProofExpr::Not(Box::new(discharge(x, facts))),
595        ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
596            variable: variable.clone(),
597            body: Box::new(discharge(body, facts)),
598        },
599        ProofExpr::Exists { variable, body } => ProofExpr::Exists {
600            variable: variable.clone(),
601            body: Box::new(discharge(body, facts)),
602        },
603        ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
604            operator: operator.clone(),
605            body: Box::new(discharge(body, facts)),
606        },
607        other => other.clone(),
608    }
609}
610
611fn at_most_one_of(e: &ProofExpr) -> Option<ProofExpr> {
612    let ProofExpr::Exists { variable: x, body } = e else {
613        return None;
614    };
615    let ProofExpr::And(phi_x, uniq) = body.as_ref() else {
616        return None;
617    };
618    let ProofExpr::ForAll {
619        variable: y,
620        body: uniq_body,
621    } = uniq.as_ref()
622    else {
623        return None;
624    };
625    // The inner ∀ must be the uniqueness clause `φ(y) → y = x` (either order).
626    let ProofExpr::Implies(_phi_y, ident) = uniq_body.as_ref() else {
627        return None;
628    };
629    let ProofExpr::Identity(l, r) = ident.as_ref() else {
630        return None;
631    };
632    let is_var = |t: &ProofTerm, name: &str| matches!(t, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == name);
633    if !((is_var(l, y) && is_var(r, x)) || (is_var(l, x) && is_var(r, y))) {
634        return None;
635    }
636    // ∀x∀y'((φ(x) ∧ φ(y')) → x = y'), with a fresh y' so it never collides with x.
637    let y2 = format!("{x}_amo");
638    let phi_x = phi_x.as_ref().clone();
639    let phi_y2 = subst(&phi_x, x, &ProofTerm::Variable(y2.clone()));
640    let body = ProofExpr::Implies(
641        Box::new(ProofExpr::And(Box::new(phi_x), Box::new(phi_y2))),
642        Box::new(ProofExpr::Identity(
643            ProofTerm::Variable(x.clone()),
644            ProofTerm::Variable(y2.clone()),
645        )),
646    );
647    Some(ProofExpr::ForAll {
648        variable: x.clone(),
649        body: Box::new(ProofExpr::ForAll {
650            variable: y2,
651            body: Box::new(body),
652        }),
653    })
654}
655
656/// "The unique D-trip has property P." Each single-`∃` definite-description clue
657/// `∃x(D(x) ∧ … ∧ P(x))` whose anchor `D` is a SINGLETON grid value (it carries an
658/// `Exactly one …` premise, so the description denotes a unique row) entails the
659/// propagatable rule `∀t(D(t) → P(t))`; when `P` is ALSO a singleton value the
660/// biconditional `∀t(P(t) → D(t))` too — e.g. "the Florida trip is the hunting trip"
661/// ⇒ `In(t,Florida) ↔ Hunt(t)`. Sound: a singleton value names a unique row, so any row
662/// holding it IS that row and therefore carries the clue's property. This replaces the
663/// existential (whose sort-aware grounding still explodes to a row-disjunction) with
664/// row-indexed implications the incremental solver propagates.
665///
666/// Structural only — singleton-ness is read from the `Exactly one` premises, never the
667/// literal value names — so it is not specific to any one puzzle. Nested `∃x∃y`
668/// of-pair clues are left untouched (they ground to compound clauses the DPLL decides).
669pub fn definite_property_implications(premises: &[ProofExpr]) -> Vec<ProofExpr> {
670    let row_sorts = row_sort_predicates(premises);
671    let singletons = singleton_value_signatures(premises, &row_sorts);
672    let mut flat: Vec<ProofExpr> = Vec::new();
673    for p in premises {
674        flatten_and_into(p, &mut flat);
675    }
676    let mut out = Vec::new();
677    for p in &flat {
678        let ProofExpr::Exists { variable: x, body } = p else {
679            continue;
680        };
681        // Nested ∃∃ (of-pair) and the bare `Exactly one` premises are not definite
682        // descriptions of a property — leave them to grounding / at-most-one.
683        if matches!(body.as_ref(), ProofExpr::Exists { .. }) || at_most_one_of(p).is_some() {
684            continue;
685        }
686        let lits = clue_literals_on(body, x, &row_sorts);
687        for (i, anchor) in lits.iter().enumerate() {
688            let Some(sig) = positive_signature(anchor) else {
689                continue;
690            };
691            if !singletons.contains(&sig) {
692                continue;
693            }
694            for (j, other) in lits.iter().enumerate() {
695                if i == j {
696                    continue;
697                }
698                out.push(ProofExpr::ForAll {
699                    variable: x.clone(),
700                    body: Box::new(ProofExpr::Implies(
701                        Box::new(anchor.clone()),
702                        Box::new(other.clone()),
703                    )),
704                });
705            }
706        }
707    }
708    out
709}
710
711fn flatten_and_into(e: &ProofExpr, out: &mut Vec<ProofExpr>) {
712    match e {
713        ProofExpr::And(l, r) => {
714            flatten_and_into(l, out);
715            flatten_and_into(r, out);
716        }
717        _ => out.push(e.clone()),
718    }
719}
720
721/// Unary predicate names that appear as a ground fact (`Trip(Alpha)`): the row sort
722/// guard, dropped from clue bodies so only the value/property literals remain.
723fn row_sort_predicates(premises: &[ProofExpr]) -> std::collections::HashSet<String> {
724    let mut flat: Vec<ProofExpr> = Vec::new();
725    for p in premises {
726        flatten_and_into(p, &mut flat);
727    }
728    let mut s = std::collections::HashSet::new();
729    for p in &flat {
730        if let ProofExpr::Predicate { name, args, .. } = p {
731            if matches!(args.as_slice(), [ProofTerm::Constant(_)]) {
732                s.insert(name.clone());
733            }
734        }
735    }
736    s
737}
738
739/// `(predicate, value)` signatures of the singleton grid values — the value literal of
740/// every `Exactly one …` (`∃x((guard(x) ∧ φ(x)) ∧ ∀y(φ(y) → y = x))`) premise.
741fn singleton_value_signatures(
742    premises: &[ProofExpr],
743    row_sorts: &std::collections::HashSet<String>,
744) -> std::collections::HashSet<(String, String)> {
745    let mut s = std::collections::HashSet::new();
746    for p in premises {
747        let ProofExpr::Exists { variable: x, body } = p else {
748            continue;
749        };
750        let ProofExpr::And(phi, uniq) = body.as_ref() else {
751            continue;
752        };
753        if !matches!(uniq.as_ref(), ProofExpr::ForAll { .. }) {
754            continue;
755        }
756        for lit in clue_literals_on(phi, x, row_sorts) {
757            if let Some(sig) = positive_signature(&lit) {
758                s.insert(sig);
759            }
760        }
761    }
762    s
763}
764
765/// `(name, value)` for a positive value literal (`In(x,Florida)` → `("In","Florida")`,
766/// the unary `Hunt(x)` → `("Hunt","")`); `None` for negatives / non-value atoms.
767fn positive_signature(e: &ProofExpr) -> Option<(String, String)> {
768    let ProofExpr::Predicate { name, args, .. } = e else {
769        return None;
770    };
771    match args.as_slice() {
772        [_, ProofTerm::Constant(v)] => Some((name.clone(), v.clone())),
773        [_] => Some((name.clone(), String::new())),
774        _ => None,
775    }
776}
777
778fn term_is_var(t: &ProofTerm, x: &str) -> bool {
779    matches!(t, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == x)
780}
781
782fn mentions_var(args: &[ProofTerm], x: &str) -> bool {
783    args.iter().any(|a| term_is_var(a, x))
784}
785
786/// The literal value/property conjuncts of a clue body that mention `x`: a conjunction
787/// is split, the row-sort guard is dropped, uniqueness `∀` clauses are ignored, and a
788/// negated conjunction `¬(guard(x) ∧ L(x))` collapses to `¬L(x)`.
789fn clue_literals_on(
790    e: &ProofExpr,
791    x: &str,
792    row_sorts: &std::collections::HashSet<String>,
793) -> Vec<ProofExpr> {
794    match e {
795        ProofExpr::And(l, r) => {
796            let mut v = clue_literals_on(l, x, row_sorts);
797            v.extend(clue_literals_on(r, x, row_sorts));
798            v
799        }
800        ProofExpr::Predicate { name, args, .. } => {
801            if mentions_var(args, x) && !row_sorts.contains(name) {
802                vec![e.clone()]
803            } else {
804                vec![]
805            }
806        }
807        ProofExpr::Not(inner) => match drop_row_guards(inner, x, row_sorts) {
808            Some(lit) => vec![ProofExpr::Not(Box::new(lit))],
809            None => vec![],
810        },
811        _ => vec![],
812    }
813}
814
815/// Strip row-sort guards from a (possibly conjunctive) expression, returning the single
816/// remaining value literal on `x` (or `None` if it is not a clean single literal).
817fn drop_row_guards(
818    e: &ProofExpr,
819    x: &str,
820    row_sorts: &std::collections::HashSet<String>,
821) -> Option<ProofExpr> {
822    let mut lits = clue_literals_on(e, x, row_sorts);
823    if lits.len() == 1 {
824        Some(lits.pop().unwrap())
825    } else {
826        None
827    }
828}
829
830fn subst_term(t: &ProofTerm, var: &str, to: &ProofTerm) -> ProofTerm {
831    match t {
832        ProofTerm::Variable(x) if x == var => to.clone(),
833        ProofTerm::BoundVarRef(x) if x == var => to.clone(),
834        ProofTerm::Function(name, args) => ProofTerm::Function(
835            name.clone(),
836            args.iter().map(|a| subst_term(a, var, to)).collect(),
837        ),
838        ProofTerm::Group(args) => {
839            ProofTerm::Group(args.iter().map(|a| subst_term(a, var, to)).collect())
840        }
841        other => other.clone(),
842    }
843}
844
845#[cfg(test)]
846#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/grounding/tests.rs"]
847mod tests;