Dual-rail Horn MaxSAT correctness, exact threshold and score cap
ProvedHornMaxSAT.DualRail.semantic_correctnessLet be any finite CNF formula with declared variables, and let be the specified dual-rail partial MaxSAT instance from §5.2. Assignments range over all rail variables, hard feasibility means satisfying every clause of , and counts satisfied soft-clause occurrences with unit weight.
- Every clause of and is Horn.
- The exact decision threshold is :
- Every feasible assignment obeys the universal cap
The statement applies without a feasibility assumption, including , empty clauses, duplicate clauses or literals, tautologies, contradictory units, and unused declared variables. Hornness counts distinct positive literals. This is the semantic correctness component of the paper's specific SAT-to-Horn-MaxSAT transformation and can be reused independently of its machine implementation.
Formalization Note. This is the exact semantic conjunct of the mission's existing root statement. All published definitions, the dual-rail clauses and the threshold are unchanged.
import Definitions.Def_HornMaxSAT_DualRail_HEnc set_option autoImplicit false open WordRAM.Conjectures open HornMaxSAT.DualRail
theorem HornMaxSAT.DualRail.semantic_correctness : ∀ F : SATInstance,
(HEnc F).IsHorn ∧
(F.Satisfiable ↔ ∃ b : Fin (HEnc F).numVars → Bool,
(HEnc F).Feasible b ∧ F.variables ≤ (HEnc F).score b) ∧
(∀ b : Fin (HEnc F).numVars → Bool,
(HEnc F).Feasible b → (HEnc F).score b ≤ F.variables) := by sorry