While this submission is a draft, it cannot be used by other submissions.

Executable finite model checking for both logics

Lax369799.FiniteModelChecking · concepts/Lax369799/FiniteModelChecking.lean · lax-369799

proven

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

    Theorem

    Finite graphs and set assignments are Boolean tables. Quantifiers range over explicitly finite types, including all Boolean set assignments. The fixed-point clauses test every pre-fixed or post-fixed subset.

    Concept map
    7 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.UnrestrictedLogic
    2import Mathlib.Data.Fintype.Pi
    3
    4/-!
    5---
    6title: Executable finite model checking for both logics
    7type: theorem
    8---
    9Finite graphs and set assignments are Boolean tables. Quantifiers range
    10over explicitly finite types, including all Boolean set assignments.
    11The fixed-point clauses test every pre-fixed or post-fixed subset.
    12-/
    13
    14namespace Lax369799.FiniteModelChecking
    15
    16abbrev Graph (P : Type) (k : ℕ) :=
    17 Fin (k+1) × (Fin (k+1) → Fin (k+1) → Bool) × (Fin (k+1) → P → Bool)
    18
    19def semantics {P : Type} {k : ℕ} (G : Graph P k) : UnrestrictedTransitionSystems.TransitionSystem P :=
    20 ⟨Fin (k+1),G.1,(fun v w => G.2.1 v w = true),(fun v => {p | G.2.2 v p = true})⟩
    21
    22def msoCheck {P : Type} {k : ℕ} (G : Graph P k) :
    23 {m n : ℕ} → MonadicSecondOrder.Formula P m n → (Fin m → Fin (k+1)) →
    24 (Fin n → Fin (k+1) → Bool) → Bool
    25 | _, _, .equal x y, ρ, _ => decide (ρ x = ρ y)
    26 | _, _, .initial x, ρ, _ => decide (ρ x = G.1)
    27 | _, _, .proposition p x, ρ, _ => G.2.2 (ρ x) p
    28 | _, _, .edge x y, ρ, _ => G.2.1 (ρ x) (ρ y)
    29 | _, _, .member x X, ρ, σ => σ X (ρ x)
    30 | _, _, .neg φ, ρ, σ => !(msoCheck G φ ρ σ)
    31 | _, _, .disj φ ψ, ρ, σ => msoCheck G φ ρ σ || msoCheck G ψ ρ σ
    32 | _, _, .existsVertex φ, ρ, σ => decide (∃ v,msoCheck G φ (Fin.cases v ρ) σ = true)
    33 | _, _, .existsSet φ, ρ, σ => decide (∃ X : Fin (k+1) → Bool,msoCheck G φ ρ (Fin.cases X σ) = true)
    34
    35def muCheck {P : Type} {k : ℕ} (G : Graph P k) :
    36 {n : ℕ} → ModalMuCalculus.Formula P n → (Fin n → Fin (k+1) → Bool) → Fin (k+1) → Bool
    37 | _, .top, _, _ => true
    38 | _, .bot, _, _ => false
    39 | _, .proposition p, _, v => G.2.2 v p
    40 | _, .negProposition p, _, v => !(G.2.2 v p)
    41 | _, .variable i, ρ, v => ρ i v
    42 | _, .conj φ ψ, ρ, v => muCheck G φ ρ v && muCheck G ψ ρ v
    43 | _, .disj φ ψ, ρ, v => muCheck G φ ρ v || muCheck G ψ ρ v
    44 | _, .diamond φ, ρ, v => decide (∃ w,G.2.1 v w = true ∧ muCheck G φ ρ w = true)
    45 | _, .box φ, ρ, v => decide (∀ w,G.2.1 v w = true → muCheck G φ ρ w = true)
    46 | _, .mu φ, ρ, v => decide (∀ X : Fin (k+1) → Bool,
    47 (∀ w,muCheck G φ (Fin.cases X ρ) w = true → X w = true) → X v = true)
    48 | _, .nu φ, ρ, v => decide (∃ X : Fin (k+1) → Bool,
    49 X v = true ∧ ∀ w,X w = true → muCheck G φ (Fin.cases X ρ) w = true)
    50
    51def mso {P : Type} {k : ℕ} (G : Graph P k) (φ : MonadicSecondOrder.Sentence P) : Bool :=
    52 msoCheck G φ Fin.elim0 Fin.elim0
    53
    54def mu {P : Type} {k : ℕ} (G : Graph P k) (φ : ModalMuCalculus.Sentence P) : Bool :=
    55 muCheck G φ Fin.elim0 G.1
    56
    57axiom mso_correct {P : Type} {k m n : ℕ} (G : Graph P k)
    58 (φ : MonadicSecondOrder.Formula P m n) (ρ : Fin m → Fin (k+1))
    59 (σ : Fin n → Fin (k+1) → Bool) :
    60 msoCheck G φ ρ σ = true ↔ UnrestrictedLogic.msoEval (semantics G) φ ρ (fun i => {v | σ i v = true})
    61
    62axiom mu_correct {P : Type} {k n : ℕ} (G : Graph P k)
    63 (φ : ModalMuCalculus.Formula P n) (ρ : Fin n → Fin (k+1) → Bool) (v : Fin (k+1)) :
    64 muCheck G φ ρ v = true ↔ v ∈ UnrestrictedLogic.muEval (semantics G) φ (fun i => {w | ρ i w = true})
    65
    66end Lax369799.FiniteModelChecking
    Show ProofShow Proof

    Discussion

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

    Loading discussion…