FPRD LabShare an approach

← Claims

Corollary · trace preservation

CRD-SAT-12c

Absorbed additions preserve a fixed DPLL trace

Exact statement

For a fixed variable order and polarity, exhaustive unit propagation, and stopping when every stored clause is syntactically satisfied, the equivalent conditions of CRD-SAT-12a imply that FF and F∪AF\cup A have identical complete DPLL traces: the same closures, decisions, conflicts, and stopping points.

StatusProved for the stated fixed-policy DPLL interface
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

All-seed UP equality already fixes the propagation and branching states reached by a solver whose branching policy does not inspect the added clause syntax.

Hypotheses and scope

  • Variable order and polarity are fixed independently of the formula representation.
  • Unit propagation is exhaustive and termination occurs when every stored clause is syntactically satisfied.
  • Every addition is UP-absorbed as in CRD-SAT-12a.

Proof or evidence

All-seed UP equality gives identical closures, conflicts, and subsequent fixed decisions. Absorption also gives semantic entailment. If a partial assignment satisfies every base clause, every total extension is a base model and therefore satisfies every added clause; an added clause cannot remain merely unset at the stopping point. The complete traces coincide.

Fixed-policy DPLL corollary →

Verification notes

The stopping argument was checked separately from closure equality. It depends on formula-independent branching and does not extend to reason or metadata-sensitive work.

Limitations

  • Formula-inspecting heuristics, scans, watches, clause activity, provenance, learning, deletion, and proof cost are excluded.
  • CRD-SAT-13 shows that reason-sensitive conflict work can differ even when this trace-level observer agrees.

Open work

Keep the fixed-policy and syntax-insensitive scope explicit when comparing later reason-sensitive results.