Clauses, literals and binary numbers
Lax799700.Common · concepts/Lax799700/Common.lean · lax-799700
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The two pieces of shared vocabulary the catalog's problems are stated with. On a CNF structure of the NP core's vocabulary, IsCl, PosIn, NegIn and OccIn read off clauses and the signed occurrences of variables in them, and LitTrue evaluates a literal under an assignment; the satisfiability variants (3SAT, NAE-SAT, 1-in-SAT) are written with these. On a structure carrying a set of bit positions and an order on them, bitRank is the number of positions strictly below a position and binNum decodes a set of positions as the number whose binary digits they are; the problems written in binary (Knapsack, Partition, 0-1 integer programming, job sequencing) compare numbers decoded this way. Both decoders are total, defined for an arbitrary relation in place of the order, so that isomorphism-invariance is a plain transport statement.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Algebra.BigOperators.Finprod |
| 2 | import Mathlib.Data.Set.Finite.Lemmas |
| 3 | import Mathlib.Data.Fintype.EquivFin |
| 4 | import Mathlib.Data.Set.Card |
| 5 | import Mathlib.SetTheory.Cardinal.Finite |
| 6 | import Mathlib.Logic.Equiv.Prod |
| 7 | import Mathlib.Tactic.FinCases |
| 8 | import Mathlib.Order.PiLex |
| 9 | import Mathlib.Data.Prod.Lex |
| 10 | import Mathlib.ModelTheory.Order |
| 11 | import Mathlib.ModelTheory.Semantics |
| 12 | import Mathlib.ModelTheory.Complexity |
| 13 | import Mathlib.Logic.Equiv.Fin.Basic |
| 14 | import Mathlib.Data.Finite.Sigma |
| 15 | import Mathlib.Data.Fintype.Lattice |
| 16 | import Mathlib.ModelTheory.Syntax |
| 17 | import Lax904597.Sat |
| 18 | import Lax904597.Classes |
| 19 | import Lax799700.Problems |
| 20 | |
| 21 | /-! |
| 22 | --- |
| 23 | title: Clauses, literals and binary numbers |
| 24 | type: definition |
| 25 | --- |
| 26 | The two pieces of shared vocabulary the catalog's problems are stated |
| 27 | with. On a CNF structure of the NP core's vocabulary, IsCl, PosIn, NegIn |
| 28 | and OccIn read off clauses and the signed occurrences of variables in |
| 29 | them, and LitTrue evaluates a literal under an assignment; the |
| 30 | satisfiability variants (3SAT, NAE-SAT, 1-in-SAT) are written with these. |
| 31 | On a structure carrying a set of bit positions and an order on them, |
| 32 | bitRank is the number of positions strictly below a position and binNum |
| 33 | decodes a set of positions as the number whose binary digits they are; |
| 34 | the problems written in binary (Knapsack, Partition, 0-1 integer |
| 35 | programming, job sequencing) compare numbers decoded this way. Both |
| 36 | decoders are total, defined for an arbitrary relation in place of the |
| 37 | order, so that isomorphism-invariance is a plain transport statement. |
| 38 | |
| 39 | -/ |
| 40 | |
| 41 | namespace Lax799700.Common |
| 42 | |
| 43 | open Lax904597.Sat |
| 44 | |
| 45 | section Decode |
| 46 | |
| 47 | variable {A : Type} |
| 48 | |
| 49 | /-- The rank of a position: the number of positions strictly below it. This is |
| 50 | the place value's exponent. -/ |
| 51 | noncomputable def bitRank (Le : A → A → Prop) (Posn : A → Prop) (p : A) : ℕ := |
| 52 | ({q | Posn q ∧ Le q p ∧ q ≠ p} : Set A).ncard |
| 53 | |
| 54 | /-- The number encoded by the set `b` of positions: `∑ 2 ^ rank`. -/ |
| 55 | noncomputable def binNum (Le : A → A → Prop) (Posn b : A → Prop) : ℕ := |
| 56 | ∑ᶠ p ∈ {p | Posn p ∧ b p}, 2 ^ bitRank Le Posn p |
| 57 | |
| 58 | end Decode |
| 59 | |
| 60 | open FirstOrder |
| 61 | |
| 62 | namespace SatOcc |
| 63 | |
| 64 | open Language Structure |
| 65 | |
| 66 | variable {A : Type} [sat.Structure A] |
| 67 | |
| 68 | /-- `c` is a clause. -/ |
| 69 | def IsCl (c : A) : Prop := RelMap satIsClause ![c] |
| 70 | |
| 71 | /-- `x` occurs positively in `c`. -/ |
| 72 | def PosIn (c x : A) : Prop := RelMap satPosIn ![c, x] |
| 73 | |
| 74 | /-- `x` occurs negatively in `c`. -/ |
| 75 | def NegIn (c x : A) : Prop := RelMap satNegIn ![c, x] |
| 76 | |
| 77 | /-- The literal `(x, s)` occurs in the clause `c` (`s = true` for a positive |
| 78 | occurrence). Occurrences are restricted to actual clauses, so that stray |
| 79 | `posIn`/`negIn` facts on non-clause elements do not create gadgets. -/ |
| 80 | def OccIn (c x : A) (s : Bool) : Prop := IsCl c ∧ if s then PosIn c x else NegIn c x |
| 81 | |
| 82 | /-- The literal `(x, s)` is true under the assignment `ν`. -/ |
| 83 | def LitTrue (ν : A → Prop) (x : A) (s : Bool) : Prop := if s then ν x else ¬ν x |
| 84 | |
| 85 | end SatOcc |
| 86 | |
| 87 | end Lax799700.Common |
| 88 |
Used by
From Mathlib
Mathlib.Algebra.BigOperators.FinprodMathlib.Data.Finite.SigmaMathlib.Data.Fintype.EquivFinMathlib.Data.Fintype.LatticeMathlib.Data.Prod.LexMathlib.Data.Set.CardMathlib.Data.Set.Finite.LemmasMathlib.Logic.Equiv.Fin.BasicMathlib.Logic.Equiv.ProdMathlib.ModelTheory.ComplexityMathlib.ModelTheory.OrderMathlib.ModelTheory.SemanticsMathlib.ModelTheory.SyntaxMathlib.Order.PiLexMathlib.SetTheory.Cardinal.FiniteMathlib.Tactic.FinCases
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments