Documentation

Validator.StateSetFormalism.Basic

Basic definitions for formulas #

This file provides definitions and lemmas for models, literals, clauses, cubes, CNF-formulas and DNF-formulas.

Model #

@[reducible, inline]
abbrev Validator.Model (n : ℕ) :

Model is usually in the in the context of a formula, where it represents a model of this formula, i.e. an assignment of variables making the formula true. It is used to show the correctness of operations.

Equations
Instances For
    @[reducible, inline]
    abbrev Validator.Models (n : ℕ) :

    A set of models.

    Equations
    Instances For

      Literal #

      @[unbox]
      structure Validator.Literal (n : ℕ) :

      A Literal is a variable i (represented by (i, true)) or its negation (represented by (i, false)).

      Instances For
        theorem Validator.Literal.ext {n : ℕ} {x y : Literal n} (var : x.var = y.var) (isPos : x.isPos = y.isPos) :
        x = y
        theorem Validator.Literal.ext_iff {n : ℕ} {x y : Literal n} :
        x = y ↔ x.var = y.var ∧ x.isPos = y.isPos
        def Validator.instDecidableEqLiteral.decEq {n✝ : ℕ} (x✝ x✝¹ : Literal n✝) :
        Decidable (x✝ = x✝¹)
        Equations
        Instances For
          Equations
          Instances For
            theorem Validator.Literal.mem_models {n : ℕ} (l : Literal n) (M : Model n) :
            M ∈ l.models ↔ (M l.var ↔ l.isPos = true)
            theorem Validator.Literal.forall_iff {n : ℕ} {p : Literal n → Prop} :
            (∀ (l : Literal n), p l) ↔ ∀ (i : Fin n) (b : Bool), p { var := i, isPos := b }
            theorem Validator.Literal.exists_iff {n : ℕ} {p : Literal n → Prop} :
            (∃ (l : Literal n), p l) ↔ ∃ (i : Fin n), ∃ (b : Bool), p { var := i, isPos := b }
            Equations
            Instances For
              theorem Validator.Literal.negate_eq {n : ℕ} (l : Literal n) :
              l.negate = { var := l.var, isPos := !l.isPos }
              @[simp]

              Clause #

              @[reducible, inline]
              abbrev Validator.Clause (n : ℕ) :

              A clause is a disjuction of literals.

              Equations
              Instances For
                Equations
                Instances For
                  @[simp]
                  theorem Validator.Clause.mem_models {n : ℕ} (γ : Clause n) (M : Model n) :
                  @[simp]
                  theorem Validator.Clause.models_append {n : ℕ} (γ1 γ2 : Clause n) :
                  (γ1 ++ γ2).models = γ1.models ∪ γ2.models
                  @[simp]
                  theorem Validator.Clause.mem_vars {n : ℕ} (γ : Clause n) {i : Fin n} :
                  i ∈ γ.vars ↔ ∃ (l : Literal n), l ∈ γ ∧ l.var = i
                  @[simp]
                  theorem Validator.Clause.vars_cons {n : ℕ} (γ : Clause n) {l : Literal n} :

                  Cube #

                  @[reducible, inline]
                  abbrev Validator.Cube (n : ℕ) :

                  A cube is a conjunction of literals.

                  Equations
                  Instances For
                    def Validator.Cube.models {n : ℕ} (δ : Cube n) :
                    Equations
                    Instances For
                      @[simp]
                      theorem Validator.Cube.mem_models {n : ℕ} (δ : Cube n) (M : Model n) :
                      M ∈ δ.models ↔ ∀ (l : Literal n), l ∈ δ → M ∈ l.models
                      @[simp]
                      theorem Validator.Cube.models_append {n : ℕ} (δ1 δ2 : Cube n) :
                      (δ1 ++ δ2).models = δ1.models ∩ δ2.models
                      @[simp]
                      theorem Validator.Cube.models_cons {n : ℕ} {l : Literal n} (δ : Cube n) :
                      models (l :: δ) = l.models ∩ δ.models
                      @[simp]
                      theorem Validator.Cube.mem_vars {n : ℕ} (δ : Cube n) (i : Fin n) :
                      i ∈ δ.vars ↔ ∃ (l : Literal n), l ∈ δ ∧ i = l.var
                      @[simp]
                      theorem Validator.Cube.vars_cons {n : ℕ} (δ : Cube n) {l : Literal n} :
                      theorem Validator.Cube.vars_append {n : ℕ} (δ δ' : Cube n) :
                      (δ ++ δ').vars = δ.vars ∪ δ'.vars
                      Equations
                      Instances For
                        def Validator.Clause.neg {n : ℕ} (γ : Clause n) :

                        The negation of a clause

                        Equations
                        Instances For
                          def Validator.Cube.neg {n : ℕ} (δ : Cube n) :

                          The negation of a cube

                          Equations
                          Instances For

                            CNF #

                            @[reducible, inline]
                            abbrev Validator.CNF (n : ℕ) :

                            A CNF-formula is a conjunction of clauses.

                            Equations
                            Instances For
                              def Validator.CNF.models {n : ℕ} (φ : CNF n) :
                              Equations
                              Instances For
                                @[simp]
                                theorem Validator.CNF.mem_models {n : ℕ} (φ : CNF n) {M : Model n} :
                                M ∈ φ.models ↔ ∀ (γ : Clause n), γ ∈ φ → M ∈ γ.models
                                @[simp]
                                theorem Validator.CNF.models_cons {n : ℕ} (φ : CNF n) {γ : Clause n} :
                                models (γ :: φ) = γ.models ∩ φ.models
                                @[simp]
                                theorem Validator.CNF.models_append {n : ℕ} (φ ψ : CNF n) :
                                (φ ++ ψ).models = φ.models ∩ ψ.models
                                theorem Validator.CNF.models_mem_empty {n : ℕ} (φ : CNF n) (h : [] ∈ φ) :
                                def Validator.CNF.vars {n : ℕ} (φ : CNF n) :
                                Equations
                                Instances For
                                  @[simp]
                                  theorem Validator.CNF.mem_vars {n : ℕ} (φ : CNF n) {i : Fin n} :
                                  i ∈ φ.vars ↔ ∃ (γ : Clause n), γ ∈ φ ∧ i ∈ γ.vars
                                  @[simp]
                                  theorem Validator.CNF.vars_cons {n : ℕ} {γ : Clause n} {φ : CNF n} :
                                  vars (γ :: φ) = γ.vars ∪ φ.vars
                                  @[simp]
                                  theorem Validator.CNF.forall_iff_subset_models {n : ℕ} {φ : CNF n} {Ms : Models n} :
                                  (∀ (γ : Clause n), γ ∈ φ → Ms ⊆ γ.models) ↔ Ms ⊆ φ.models
                                  theorem Validator.CNF.models_equiv_right {n : ℕ} {φ : CNF n} {M M' : Model n} :
                                  (∀ (i : Fin n), i ∈ φ.vars → M i = M' i) → M ∈ φ.models → M' ∈ φ.models

                                  DNF #

                                  @[reducible, inline]
                                  abbrev Validator.DNF (n : ℕ) :

                                  A DNF-formula is a conjunction of cubes.

                                  Equations
                                  Instances For
                                    def Validator.DNF.models {n : ℕ} (φ : DNF n) :
                                    Equations
                                    Instances For
                                      @[simp]
                                      theorem Validator.DNF.mem_models {n : ℕ} (φ : DNF n) {M : Model n} :
                                      M ∈ φ.models ↔ ∃ (δ : Cube n), δ ∈ φ ∧ M ∈ δ.models
                                      @[simp]
                                      theorem Validator.DNF.exists_iff_models_subset {n : ℕ} {φ : DNF n} {Ms : Models n} :
                                      (∀ (δ : Cube n), δ ∈ φ → δ.models ⊆ Ms) ↔ φ.models ⊆ Ms