Theory Formula

section "Formula"

theory Formula
  imports Base 
begin

subsection "Variables"

datatype vbl = X nat
  ― ‹FIXME there's a lot of stuff about this datatype that is
  really just a lifting from nat (what else could it be). Makes me
  wonder whether things wouldn't be clearer is we just identified vbls
  with nats›

primrec deX :: "vbl ⇒ nat" where "deX (X n) = n"

lemma X_deX[simp]: "X (deX a) = a"
  by(cases a) simp

definition "zeroX = X 0"

primrec
  nextX :: "vbl ⇒ vbl" where
  "nextX (X n) = X (Suc n)"

definition
  vblcase :: "['a,vbl ⇒ 'a,vbl] ⇒ 'a" where
  "vblcase a f n ≡ (@z. (n=zeroX ⟶ z=a) ∧ (!x. n=nextX x ⟶ z=f(x)))"

declare [[case_translation vblcase zeroX nextX]]

definition
  freshVar :: "vbl set ⇒ vbl" where
  "freshVar vs = X (LEAST n. n ∉ deX ` vs)"
    
lemma nextX_nextX[iff]: "nextX x = nextX y = (x = y)"
  by (metis Suc_inject nextX.simps vbl.exhaust vbl.inject)

lemma inj_nextX: "inj nextX"
  by(auto simp add: inj_on_def)

lemma ind: 
  assumes "P zeroX" "⋀ v. P v ⟹ P (nextX v)"
  shows "P v'"
proof -
  have "P (X n)" for n
    by (induction n) (use assms zeroX_def nextX_def in force)+
  then show ?thesis
    by (metis X_deX)
qed

lemma zeroX_nextX[iff]: "zeroX ≠ nextX a"
  by (metis nat.discI nextX.simps vbl.exhaust vbl.inject zeroX_def)

lemmas nextX_zeroX[iff] = not_sym[OF zeroX_nextX]

lemma nextX: "nextX (X n) = X (Suc n)"
  by simp

lemma vblcase_zeroX[simp]: "vblcase a b zeroX = a" 
  by(simp add: vblcase_def)

lemma vblcase_nextX[simp]: "vblcase a b (nextX n) = b n" 
  by(simp add: vblcase_def)

lemma vbl_cases: "x = zeroX ∨ (∃y. x = nextX y)"
  by (metis X_deX nextX old.nat.exhaust zeroX_def)

lemma vbl_casesE: "⟦ x = zeroX ⟹ P; ⋀ y. x = nextX y ⟹ P ⟧ ⟹ P"
  using vbl_cases by blast

lemma comp_vblcase: "f ∘ vblcase a b = vblcase (f a) (f ∘ b)"
proof
  fix x
  show "(f ∘ vblcase a b) x = (case x of zeroX ⇒ f a | nextX x ⇒ (f ∘ b) x)"
    using vbl_cases [of x] by auto
qed

lemma equalOn_vblcaseI': "equalOn (preImage nextX A) f g ⟹ equalOn A (vblcase x f) (vblcase x g)"
  unfolding equalOn_def
  by (metis vbl_casesE vblcase_nextX vblcase_zeroX vimageI2) 
    
lemma equalOn_vblcaseI: "(zeroX ∈ A ⟹ x=y) ⟹ equalOn (preImage nextX A) f g ⟹ equalOn A (vblcase x f) (vblcase y g)"
  by (smt (verit) equalOnD equalOnI equalOn_vblcaseI' vbl_casesE vblcase_nextX)

lemma X_deX_connection: "X n ∈ A = (n ∈ (deX ` A))"
  by force

lemma finiteFreshVar: "finite A ⟹ freshVar A ∉ A"
  unfolding freshVar_def
  by (metis (no_types, lifting) LeastI_ex X_deX finite_imageI
      finite_nat_set_iff_bounded image_eqI order_less_imp_triv
      vbl.inject)

lemma freshVarI: "⟦finite A; B ⊆ A⟧ ⟹ freshVar A ∉ B"
  using finiteFreshVar in_mono by blast

lemma freshVarI2: "⟦finite A; ⋀x . x ∉ A ⟹ P x⟧ ⟹ P (freshVar A)"
  using finiteFreshVar by presburger

lemmas vblsimps = vblcase_zeroX vblcase_nextX zeroX_nextX
  nextX_zeroX nextX_nextX comp_vblcase


subsection "Predicates"

datatype predicate = Predicate nat

datatype signs = Pos | Neg

primrec sign :: "signs ⇒ bool ⇒ bool"
  where
    "sign Pos x = x"
  | "sign Neg x = (¬ x)"

primrec invSign :: "signs ⇒ signs"
  where
    "invSign Pos = Neg"
  | "invSign Neg = Pos"


subsection "Formulas"

datatype formula =
  FAtom signs predicate "(vbl list)"
  | FConj signs formula formula
  | FAll  signs formula  


subsection "formula signs induct, formula signs cases"

lemma formula_signs_induct [case_names FAtomP FAtomN FConjP FConjN FAllP FAllN, cases type: formula]: 
  "⟦⋀p vs. P (FAtom Pos p vs);
  ⋀p vs. P (FAtom Neg p vs);
  ⋀A B  . ⟦P A; P B⟧ ⟹ P (FConj Pos A B);
  ⋀A B  . ⟦P A; P B⟧ ⟹ P (FConj Neg A B);
  ⋀A    . ⟦P A⟧ ⟹ P (FAll  Pos A); 
  ⋀A    . ⟦P A⟧ ⟹ P (FAll  Neg A) 
 ⟧ ⟹ P A"
  by (induct A; rule signs.induct; force)

    ― ‹induction using nat induction, not wellfounded induction›

lemma sizelemmas: "size A < size (FConj z A B)"
  "size B < size (FConj z A B)"
  "size A < size (FAll  z A)"
  by auto

primrec FNot :: "formula ⇒ formula"
  where
    FNot_FAtom: "FNot (FAtom z P vs)  = FAtom (invSign z) P vs"
  | FNot_FConj: "FNot (FConj z A0 A1) = FConj (invSign z) (FNot A0) (FNot A1)"    
  | FNot_FAll:  "FNot (FAll  z body)  = FAll  (invSign z) (FNot body)"

primrec neg  :: "signs ⇒ signs"
  where
    "neg Pos = Neg"
  | "neg Neg = Pos"

primrec
  dual :: "[(signs ⇒ signs),(signs ⇒ signs),(signs ⇒ signs)] ⇒ formula ⇒ formula"
  where
    dual_FAtom: "dual p q r (FAtom z P vs)  = FAtom (p z) P vs"
  | dual_FConj: "dual p q r (FConj z A0 A1) = FConj (q z) (dual p q r A0) (dual p q r A1)"
  | dual_FAll:  "dual p q r (FAll  z body)  = FAll  (r z) (dual p q r body)"

lemma dualCompose: "dual p q r ∘ dual P Q R = dual (p ∘ P) (q ∘ Q) (r ∘ R)"
proof
  fix x
  show "(dual p q r ∘ dual P Q R) x = dual (p ∘ P) (q ∘ Q) (r ∘ R) x"
    by (induct x) auto
qed

lemma dualFNot': "dual invSign invSign invSign = FNot"
proof
  fix x
  show "dual invSign invSign invSign x = FNot x"
    by (induct x) auto
qed

lemma dualFNot: "dual invSign id id (FNot A) = FNot (dual invSign id id A)"
  by(induct A) (auto simp: id_def)

lemma dualId: "dual id id id A = A"
  by(induct A) (auto simp: id_def)


subsection "Frees"

primrec freeVarsF  :: "formula ⇒ vbl set"
  where
    freeVarsFAtom: "freeVarsF (FAtom z P vs)  = set vs"
  | freeVarsFConj: "freeVarsF (FConj z A0 A1) = (freeVarsF A0) ∪ (freeVarsF A1)"    
  | freeVarsFAll:  "freeVarsF (FAll  z body)  = preImage nextX (freeVarsF body)"

definition
  freeVarsFL :: "formula list ⇒ vbl set" where
  "freeVarsFL Γ = Union (freeVarsF ` (set Γ))"

lemma freeVarsF_FNot[simp]: "freeVarsF (FNot A) = freeVarsF A"
  by(induct A) auto

lemma finite_freeVarsF[simp]: "finite (freeVarsF A)"
  by(induct A) (auto simp add: inj_nextX) 

lemma freeVarsFL_nil[simp]: "freeVarsFL ([]) = {}"
  by(simp add: freeVarsFL_def)

lemma freeVarsFL_cons: "freeVarsFL (A#Γ) = freeVarsF A ∪ freeVarsFL Γ"
  by(simp add: freeVarsFL_def)

lemma finite_freeVarsFL[simp]: "finite (freeVarsFL Γ)"
  by(induct Γ) (auto simp: freeVarsFL_cons)

lemma freeVarsDual: "freeVarsF (dual p q r A) = freeVarsF A"
  by(induct A) auto


subsection "Substitutions"

primrec subF :: "[vbl ⇒ vbl,formula] ⇒ formula"
  where
    subFAtom: "subF theta (FAtom z P vs)  = FAtom z P (map theta vs)"
  | subFConj: "subF theta (FConj z A0 A1) = FConj z (subF theta A0) (subF theta A1)"
  | subFAll: "subF theta (FAll z body) = 
      FAll z (subF (λv . (case v of zeroX ⇒ zeroX | nextX v ⇒ nextX (theta v))) body)"

lemma size_subF: "size (subF theta A) = size (A::formula)"
  by(induct A arbitrary: theta) auto

lemma subFNot: "subF theta (FNot A) = FNot (subF theta A)"
  by(induct A arbitrary: theta) auto

lemma subFDual: "subF theta (dual p q r A) = dual p q r (subF theta A)"
  by(induct A arbitrary: theta) auto

definition
  instanceF :: "[vbl,formula] ⇒ formula" where
  "instanceF w body = subF (λv. case v of zeroX ⇒ w | nextX v ⇒ v) body"

lemma size_instance: "size (instanceF v A) = size A"
  by (simp add: instanceF_def size_subF)

lemma instanceFDual: "instanceF u (dual p q r A) = dual p q r (instanceF u A)" 
  by(induct A) (simp_all add: instanceF_def subFDual)


subsection "Models"

typedecl
  object

axiomatization obj :: "nat ⇒ object"
  where inj_obj: "inj obj"


subsection "model, non empty set and positive atom valuation"

definition "model = {z :: (object set * ([predicate,object list] ⇒ bool)). (fst z ≠ {})}"

typedef model = model
  unfolding model_def by auto

definition
  objects :: "model ⇒ object set" where
  "objects M = fst (Rep_model M)"

definition
  evalP :: "model ⇒ predicate ⇒ object list ⇒ bool" where
  "evalP M = snd (Rep_model M)"

lemma objectsNonEmpty: "objects M ≠ {}"
  using Rep_model[of M]
  by(simp add: objects_def model_def)

lemma modelsNonEmptyI: "fst (Rep_model M) ≠ {}"
  using Rep_model[of M] by(simp add: objects_def model_def)


subsection "Validity"

primrec evalF :: "[model,vbl ⇒ object,formula] ⇒ bool"
  where
    evalFAtom: "evalF M φ (FAtom z P vs)  = sign z (evalP M P (map φ vs))"
  | evalFConj: "evalF M φ (FConj z A0 A1) = sign z (sign z (evalF M φ A0) ∧ sign z (evalF M φ A1))"
  | evalFAll:  "evalF M φ (FAll  z body)  = 
      sign z (∀x∈objects M. sign z (evalF M (λv . (case v of zeroX   ⇒ x | nextX v ⇒ φ v)) body))"

definition
  valid :: "formula ⇒ bool" where
  "valid F ≡ (∀M φ. evalF M φ F = True)"


lemma evalF_FAll: "evalF M φ (FAll Pos A) = (∀x∈objects M. (evalF M (vblcase x φ) A))"
  by simp
  
lemma evalF_FEx: "evalF M φ (FAll Neg A) = (∃x∈objects M. (evalF M (vblcase x φ) A))"
  by simp

lemma evalF_arg2_cong: "x = y ⟹ evalF M p x = evalF M p y" 
  by simp

lemma evalF_FNot: "!!φ. evalF M φ (FNot A) = (¬ evalF M φ A)"
  by(induct A rule: formula_signs_induct) simp_all

lemma evalF_equiv:  "equalOn (freeVarsF A) f g ⟹ evalF M f A = evalF M g A"
proof(induction A arbitrary: f g)
  case (FAtom x1 x2 x3)
  then show ?case
    unfolding equalOn_def
    by (metis (mono_tags, lifting) evalFAtom freeVarsFAtom map_eq_conv)
next
  case (FConj x1 A1 A2)
  then show ?case
    by (smt (verit, ccfv_SIG) FConj equalOn_UnD evalFConj freeVarsFConj)
next
  case (FAll x1 A)
  then show ?case
    by (metis (full_types) equalOn_vblcaseI' evalF_FAll evalF_FEx freeVarsFAll
        signs.exhaust)
qed

    ― ‹composition of substitutions›
lemma evalF_subF_eq: "evalF M φ (subF theta A) = evalF M (φ ∘ theta) A"
proof (induction A arbitrary: φ theta)
  case (FAtom x1 x2 x3)
  then show ?case
    by (metis evalFAtom list.map_comp subFAtom)
next
  case (FConj x1 A1 A2)
  then show ?case
    by auto
next
  case (FAll x1 A)
  then have "(vblcase x φ ∘ vblcase zeroX (λv. nextX (theta v))) = (vblcase x (φ ∘ theta))"
    if "x ∈ objects M" for x
    using that 
    apply (clarsimp simp add: o_def fun_eq_iff split: vbl.splits)
    by (metis vbl_cases vblcase_nextX vblcase_zeroX)
  with FAll show ?case
    by (simp add: comp_def)
qed

lemma evalF_instance: "evalF M φ (instanceF u A) = evalF M (vblcase (φ u) φ) A"
  by (metis comp_id comp_vblcase evalF_subF_eq fun.map_ident instanceF_def)

lemma instanceF_E: "instanceF g formula ≠ FAll signs formula"
  by (metis less_irrefl_nat size_instance sizelemmas(3))

end