pith. machine review for the scientific record. sign in
lemma proved term proof

knownParity_eq_parityOf_known'

show as:
view Lean formalization →

No prose has been written for this declaration yet. The Lean source and graph data below render without it.

generate prose now

formal statement (Lean)

 177private lemma knownParity_eq_parityOf_known' {n} (σ : PartialAssignment n) (a : Assignment n)
 178    (X : XORConstraint n) (hcompat : compatible σ a) :
 179    X.vars.foldl (fun acc w => if (σ w).isSome then Bool.xor acc ((σ w).getD false) else acc) false =
 180    parityOf a (X.vars.filter (fun w => (σ w).isSome)) := by

proof body

Term-mode proof.

 181  suffices h : ∀ init,
 182    X.vars.foldl (fun acc w => if (σ w).isSome then Bool.xor acc ((σ w).getD false) else acc) init =
 183    Bool.xor init (parityOf a (X.vars.filter (fun w => (σ w).isSome))) by
 184    specialize h false; simp at h; exact h
 185  intro init
 186  induction X.vars generalizing init with
 187  | nil => simp [parityOf]
 188  | cons w ws ih =>
 189    simp only [List.foldl_cons]
 190    by_cases hw : (σ w).isSome
 191    · simp only [hw, ↓reduceIte, List.filter_cons_of_pos]
 192      have hgetD : (σ w).getD false = a w := getD_of_compat_isSome' σ a w hcompat hw
 193      rw [hgetD, ih (Bool.xor init (a w)), parityOf_cons, Bool.xor_assoc]
 194    · simp only [hw, Bool.false_eq_true, ↓reduceIte, List.filter_cons_of_neg, not_false_eq_true]
 195      exact ih init
 196

used by (1)

From the project-wide theorem graph. These declarations reference this one in their body.

depends on (9)

Lean names referenced from this declaration's body.