Documentation

Validator.StateSetFormalism.Formula

Formulas #

This file provides typeclasses for formulas and different operations these formulas can support. Note that this file does not implement any of these operations, but it formalizes what these operations should do.

Formula #

class Validator.Formula (n : ℕ) (R : Type) :

Type class for formulas with variables Fin n. The variables are ordered by ordering <.

  • vars (φ : R) : STRIPS.VarSet n

    The variables associated with the formula φ. Note that not all of these variables need to 'appear' in φ.

  • models (φ : R) : Models n

    The models of the formula φ

  • models_equiv_right (φ : R) (M M' : Model n) : (∀ i ∈ vars φ, M i = M' i) → M ∈ models φ → M' ∈ models φ

    If two assignments coincide on the variables of φ, then the second is a model of φ if the first one is a model of φ.

Instances
    theorem Validator.Formula.models_equiv {n : ℕ} {R : Type} [h : Formula n R] {φ : R} {M M' : Model n} (h1 : ∀ i ∈ vars φ, M i = M' i) :
    M ∈ models φ ↔ M' ∈ models φ

    If two assignments M and M' coincide on the variables of φ, then M is a model of φ iff M' is a model of φ.

    Renaming #

    structure Validator.Renaming {n : ℕ} (dom : STRIPS.VarSet n) :
    Instances For
      theorem Validator.Renaming.ne {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} (i : Fin n) :
      i ∈ dom → ∀ j ∈ dom, i ≠ j → r.rename i ≠ r.rename j
      def Validator.Model.rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) (M : Model n) :
      Equations
      Instances For
        @[simp]
        theorem Validator.Model.rename_iff {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {M : Model n} {i : Fin n} :
        rename r M i ↔ M (r.rename i)
        def Validator.Literal.rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) (l : Literal n) :
        Equations
        Instances For
          @[simp]
          theorem Validator.Literal.var_rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) {l : Literal n} :
          (rename r l).var = r.rename l.var
          @[simp]
          theorem Validator.Literal.isPos_rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) {l : Literal n} :
          @[simp]
          def Validator.Clause.rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) (γ : Clause n) :
          Equations
          Instances For
            theorem Validator.Clause.rename_eq {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {γ : Clause n} :
            @[simp]
            theorem Validator.Clause.mem_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {γ : Clause n} {l : Literal n} :
            l ∈ rename r γ ↔ ∃ l' ∈ γ, l = Literal.rename r l'
            @[simp]
            theorem Validator.Clause.mem_vars_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {γ : Clause n} {i : Fin n} :
            i ∈ (rename r γ).vars ↔ ∃ j ∈ γ.vars, i = r.rename j
            @[simp]
            theorem Validator.Clause.models_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {γ : Clause n} :
            def Validator.Cube.rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) (δ : Cube n) :
            Equations
            Instances For
              def Validator.CNF.rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) (φ : CNF n) :
              CNF n
              Equations
              Instances For
                @[simp]
                theorem Validator.CNF.mem_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {φ : CNF n} {γ : Clause n} :
                γ ∈ rename r φ ↔ ∃ γ' ∈ φ, γ = Clause.rename r γ'
                @[simp]
                theorem Validator.CNF.mem_vars_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {φ : CNF n} {i : Fin n} :
                i ∈ (rename r φ).vars ↔ ∃ j ∈ φ.vars, i = r.rename j
                @[simp]
                theorem Validator.CNF.models_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {φ : CNF n} :
                Equations
                Instances For
                  @[simp]
                  theorem Validator.VarSet.mem_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {V : STRIPS.VarSet n} {i : Fin n} :
                  i ∈ rename r V ↔ ∃ j ∈ V, i = r.rename j
                  def Validator.PartialModel.rename {n : ℕ} {dom : STRIPS.VarSet n} (r : Renaming dom) (M : PartialModel n) (h1 : M.vars ⊆ dom) :
                  Equations
                  Instances For
                    @[simp]
                    theorem Validator.PartialModel.mem_vars_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {M : PartialModel n} {h1 : M.vars ⊆ dom} {i : Fin n} :
                    i ∈ (rename r M h1).vars ↔ ∃ j ∈ M.vars, i = r.rename j
                    @[simp]
                    theorem Validator.PartialModel.models_rename {n : ℕ} {dom : STRIPS.VarSet n} {r : Renaming dom} {M : PartialModel n} {h1 : M.vars ⊆ dom} :

                    Operations on Formulas #

                    class Validator.Formula.Top (n : ℕ) (R : Type) [F : Formula n R] :
                    Instances
                      class Validator.Formula.Bot (n : ℕ) (R : Type) [F : Formula n R] :
                      Instances
                        class Validator.Formula.Consistency (n : ℕ) (R : Type) [F : Formula n R] :
                        Instances
                          Instances
                            class Validator.Formula.Implicant (n : ℕ) (R : Type) [F : Formula n R] :
                            Instances
                              Instances
                                Instances

                                  The time complexity of andList is generally bad, therefore it should only be used if the number of conjuncts is bounded.

                                  Equations
                                  Instances For
                                    theorem Validator.Formula.BoundedConjuction.models_andList {n : ℕ} {R : Type} [F : Formula n R] [Top n R] [h : BoundedConjuction n R] {l : List R} :
                                    models (andList l) = {M : Model n | ∀ φ ∈ l, M ∈ models φ}
                                    Instances

                                      The timecomplexity of andList is generally bad, therefore it should only be used if the number of conjuncts is bounded.

                                      Equations
                                      Instances For
                                        theorem Validator.Formula.BoundedDisjunction.models_orList {n : ℕ} {R : Type} [F : Formula n R] [Bot n R] [h : BoundedDisjunction n R] {l : List R} :
                                        models (orList l) = {M : Model n | ∃ φ ∈ l, M ∈ models φ}
                                        Instances
                                          class Validator.Formula.Rename (n : ℕ) (R : Type) [F : Formula n R] :

                                          Renaming consistent with order

                                          Instances
                                            theorem Validator.Formula.Rename.mem_rename_models {n : ℕ} {R : Type} [F : Formula n R] [Rename n R] {φ : R} {V : STRIPS.VarSet n} {r : Renaming V} {h : vars φ ⊆ V} {M : Model n} :
                                            class Validator.Formula.ToCNF (n : ℕ) (R : Type) [F : Formula n R] :
                                            Instances
                                              theorem Validator.Formula.ToCNF.models_disjunctionToCNF {n : ℕ} {R : Type} [F : Formula n R] [h : ToCNF n R] {φs : List R} :
                                              (disjunctionToCNF φs).models = {M : Model n | ∃ φ ∈ φs, M ∈ models φ}
                                              def Validator.Formula.ToCNF.negToDNF {n : ℕ} {R : Type} [Formula n R] [h : ToCNF n R] (φ : R) :
                                              DNF n

                                              Transform ¬x to a DNF formula by translating x to a CNF-formula and applying De Morgans laws.

                                              Equations
                                              Instances For
                                                theorem Validator.Formula.ToCNF.models_negToDNF {n : ℕ} {R : Type} [F : Formula n R] [h : ToCNF n R] {φ : R} :
                                                class Validator.Formula.ToDNF (n : ℕ) (R : Type) [F : Formula n R] :
                                                Instances
                                                  theorem Validator.Formula.ToDNF.models_conjunctionToDnF {n : ℕ} {R : Type} [F : Formula n R] [h : ToDNF n R] {φs : List R} :
                                                  (conjunctionToDNF φs).models = {M : Model n | ∀ φ ∈ φs, M ∈ models φ}
                                                  def Validator.Formula.ToDNF.negToCNF {n : ℕ} {R : Type} [Formula n R] [h : ToDNF n R] (φ : R) :
                                                  CNF n

                                                  Transform ¬x to a CNF formula by translating x to a DNF-formula and applying De Morgans laws.

                                                  Equations
                                                  Instances For
                                                    theorem Validator.Formula.ToDNF.models_negToCNF {n : ℕ} {R : Type} [F : Formula n R] [h : ToDNF n R] {φ : R} :