Clauses, literals and binary numbers

Lax799700.Common · concepts/Lax799700/Common.lean · lax-799700

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    8 concepts; 7 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

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

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…