Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.
Rust ai-nativedescription-logicsformal-verificationinfrastructure-as-codeisabelle-languageknowledge-graphleanlean4mcpmcp-serverontologyowlowl2reasoningrustshaclsparqltheorem-proving
import Fo.Term
/-!
Literals, clauses, and what it means for a structure to satisfy a clause set.
A clause is a list of literals read as a DISJUNCTION, with its variables
UNIVERSALLY quantified. That second half is what makes instantiation free:
a model of a clause is a model of every instance of it, which is the whole
reason a resolution step may apply a substitution to its parents without
asking anyone's permission.
-/
namespace Fo
/-- An atom: a predicate symbol applied to arguments. -/
structure Atom where
pred : Nat
args : List Term
deriving Repr, Inhabited
def Atom.beq (a b : Atom) : Bool := a.pred == b.pred && Term.beqs a.args b.args
instance : BEq Atom := ⟨Atom.beq⟩
theorem Atom.eq_of_beq {a b : Atom} (h : Atom.beq a b = true) : a = b := by
simp only [Atom.beq, Bool.and_eq_true, beq_iff_eq] at h
cases a; cases b
simp only [Atom.mk.injEq]
exact ⟨h.1, Term.eqs_of_beqs h.2⟩
/-- A literal: an atom and a polarity. Same choice as the propositional
checker, and for the same reason: a polarity kept in a field is a polarity no
proof has to recover from an encoding. -/
structure Lit where
pos : Bool
atom : Atom
deriving Repr, Inhabited
def Lit.neg (l : Lit) : Lit := ⟨!l.pos, l.atom⟩
def Lit.beq (a b : Lit) : Bool := a.pos == b.pos && Atom.beq a.atom b.atom
instance : BEq Lit := ⟨Lit.beq⟩
theorem Lit.eq_of_beq {a b : Lit} (h : Lit.beq a b = true) : a = b := by
simp only [Lit.beq, Bool.and_eq_true, beq_iff_eq] at h
cases a; cases b
simp only [Lit.mk.injEq]
exact ⟨h.1, Atom.eq_of_beq h.2⟩
/-- A clause: a disjunction of literals, variables universally quantified. -/
abbrev Clause := List Lit
/-- A clause set. Indexed, because a certificate names its premises. -/
abbrev Formula := List (Nat × Clause)
def applyA (σ : Subst) (a : Atom) : Atom := ⟨a.pred, applyTs σ a.args⟩
def applyL (σ : Subst) (l : Lit) : Lit := ⟨l.pos, applyA σ l.atom⟩
def applyC (σ : Subst) (c : Clause) : Clause := c.map (applyL σ)
/-! ## Semantics -/
def holdsA {α : Type} (M : Struct α) (ρ : Env α) (a : Atom) : Prop :=
M.rel a.pred (evalTs M ρ a.args)
def holdsL {α : Type} (M : Struct α) (ρ : Env α) (l : Lit) : Prop :=
if l.pos then holdsA M ρ l.atom else ¬ holdsA M ρ l.atom
/-- A clause holds under ONE environment when some literal does. -/
def holdsC {α : Type} (M : Struct α) (ρ : Env α) (c : Clause) : Prop :=
∃ l, l ∈ c ∧ holdsL M ρ l
/-- A model satisfies a clause when it holds under EVERY environment: the
variables are universally quantified. -/
def Sat {α : Type} (M : Struct α) (c : Clause) : Prop :=
∀ ρ : Env α, holdsC M ρ c
def Models {α : Type} (M : Struct α) (F : Formula) : Prop :=
∀ p, p ∈ F → Sat M p.2
/-- No structure, over any carrier, satisfies every clause. -/
def Unsat (F : Formula) : Prop :=
∀ (α : Type) (M : Struct α), ¬ Models M F
/-! ## Instantiation is free
The three lemmas that let a resolution step substitute into its parents. Each
is the substitution lemma of `Fo.Term` carried up one level. -/
theorem holdsA_applyA {α : Type} (M : Struct α) (ρ : Env α) (σ : Subst) (a : Atom) :
holdsA M ρ (applyA σ a) ↔ holdsA M (fun n => evalT M ρ (σ n)) a := by
simp only [holdsA, applyA]
rw [evalTs_applyTs]
theorem holdsL_applyL {α : Type} (M : Struct α) (ρ : Env α) (σ : Subst) (l : Lit) :
holdsL M ρ (applyL σ l) ↔ holdsL M (fun n => evalT M ρ (σ n)) l := by
obtain ⟨pos, atom⟩ := l
simp only [holdsL, applyL]
cases pos <;> simp [holdsA_applyA]
/-- A literal and its negation never hold together. -/
theorem holdsL_neg {α : Type} (M : Struct α) (ρ : Env α) (l : Lit) :
holdsL M ρ l.neg ↔ ¬ holdsL M ρ l := by
obtain ⟨pos, atom⟩ := l
cases pos
· show holdsA M ρ atom ↔ ¬ ¬ holdsA M ρ atom
exact ⟨fun h hn => hn h, fun h => Classical.byContradiction h⟩
· show ¬ holdsA M ρ atom ↔ ¬ holdsA M ρ atom
exact Iff.rfl
/-- **A model of a clause is a model of every instance of it.** -/
theorem sat_applyC {α : Type} {M : Struct α} {c : Clause} (h : Sat M c) (σ : Subst) :
Sat M (applyC σ c) := by
intro ρ
obtain ⟨l, hl, hv⟩ := h (fun n => evalT M ρ (σ n))
exact ⟨applyL σ l, List.mem_map_of_mem hl, (holdsL_applyL M ρ σ l).mpr hv⟩
end Fo