Parity systems and unit propagation
Lax119563.ParitySystems · concepts/Lax119563/ParitySystems.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A parity system consists of a set of variables, each taking values in , a set of homogeneous linear equations, and a set of initial facts. Every equation involves two or three distinct variables; formally, , where an equation states .
Unit propagation infers facts of the form only. For an equation with , the rule infers from . The facts known after round are given by
A conflict occurs when both and have been inferred for some variable . The conflict round is the first round such that contains a conflict, or if no conflict occurs.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Algebra.BigOperators.Group.Finset.Basic |
| 2 | import Mathlib.Data.ENat.Lattice |
| 3 | import Mathlib.Data.ZMod.Defs |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Parity systems and unit propagation |
| 8 | type: definition |
| 9 | --- |
| 10 | A *parity system* consists of a set of variables, each |
| 11 | taking values in , a set of homogeneous linear equations, and a set |
| 12 | of *initial facts*. Every equation involves two or three |
| 13 | distinct variables; formally, , where an |
| 14 | equation states . |
| 15 | |
| 16 | *Unit propagation* infers facts of the form only. For an equation |
| 17 | with , the rule infers |
| 18 | from . The facts known after |
| 19 | round are given by |
| 20 | |
| 21 | |
| 22 | |
| 23 | A *conflict* occurs when both and have been inferred for some variable . |
| 24 | The *conflict round* is the first round |
| 25 | such that contains a conflict, or if no conflict occurs. |
| 26 | -/ |
| 27 | |
| 28 | namespace Lax119563.ParitySystems |
| 29 | |
| 30 | /-- A *parity system* with variables of type `V`: homogeneous equations over `𝔽₂` in two or |
| 31 | three distinct variables, each given by its set of variables, and initial facts. -/ |
| 32 | structure ParitySystem (V : Type*) where |
| 33 | /-- The equations; `h` stands for `∑_{X ∈ h} X = 0`. -/ |
| 34 | equations : Set (Finset V) |
| 35 | /-- Every equation involves two or three variables. -/ |
| 36 | card_equation : ∀ h ∈ equations, h.card = 2 ∨ h.card = 3 |
| 37 | /-- The initial facts `K₀`. -/ |
| 38 | initial : Set (V × ZMod 2) |
| 39 | |
| 40 | namespace ParitySystem |
| 41 | |
| 42 | variable {V : Type*} [DecidableEq V] |
| 43 | |
| 44 | /-- The set `K_r` of facts known after round `r` of unit propagation. In round `r + 1`, an |
| 45 | equation `h` and a variable `X ∈ h` infer `X = ∑_{Y ∈ h \ {X}} b_Y` from known facts |
| 46 | `Y = b_Y` for all other variables `Y ∈ h`. -/ |
| 47 | def known (P : ParitySystem V) : ℕ → Set (V × ZMod 2) |
| 48 | | 0 => P.initial |
| 49 | | r + 1 => P.known r ∪ |
| 50 | {f | ∃ h ∈ P.equations, f.1 ∈ h ∧ ∃ b : V → ZMod 2, |
| 51 | (∀ Y ∈ h, Y ≠ f.1 → (Y, b Y) ∈ P.known r) ∧ f.2 = ∑ Y ∈ h.erase f.1, b Y} |
| 52 | |
| 53 | /-- `K_r` contains a conflict. -/ |
| 54 | def HasConflict (P : ParitySystem V) (r : ℕ) : Prop := |
| 55 | ∃ X, (X, 0) ∈ P.known r ∧ (X, 1) ∈ P.known r |
| 56 | |
| 57 | /-- The conflict round `τ(P)`: the first round with a conflict, or `⊤ = ∞` if none occurs. -/ |
| 58 | noncomputable def conflictRound (P : ParitySystem V) : ℕ∞ := |
| 59 | ⨅ (r : ℕ) (_ : P.HasConflict r), (r : ℕ∞) |
| 60 | |
| 61 | end ParitySystem |
| 62 | |
| 63 | end Lax119563.ParitySystems |
| 64 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments