diff --git a/thys/FOL_Seq_Calc3/Main.hs b/thys/FOL_Seq_Calc3/Main.hs --- a/thys/FOL_Seq_Calc3/Main.hs +++ b/thys/FOL_Seq_Calc3/Main.hs @@ -1,59 +1,59 @@ import Prelude import Data.Char (chr, ord) import Data.List (intersperse) import System.Environment import Arith import Prover instance Show Arith.Nat where show (Nat n) = show n charFrom :: Char -> Arith.Nat -> Char charFrom c n = chr (ord c + fromInteger (Arith.integer_of_nat n)) instance Show Tm where show (Var n) = show n show (Fun f []) = charFrom 'a' f : "" show (Fun f ts) = charFrom 'f' f : "(" ++ concat (intersperse ", " (map show ts)) ++ ")" instance Show Fm where - show Falsity = "Falsity" + show Falsity = "Fls" show (Pre p []) = charFrom 'P' p : "" show (Pre p ts) = charFrom 'P' p : "(" ++ concat (intersperse ", " (map show ts)) ++ ")" - show (Imp p q) = "(" ++ show p ++ ") --> (" ++ show q ++ ")" + show (Imp p q) = "(" ++ show p ++ ") -> (" ++ show q ++ ")" show (Uni p) = "forall " ++ show p showRule :: Rule -> String showRule (Axiom n ts) = "Axiom on " ++ show (Pre n ts) showRule FlsL = "FlsL" showRule FlsR = "FlsR" showRule Idle = "Idle" showRule (ImpL p q) = "ImpL on " ++ show p ++ " and " ++ show q showRule (ImpR p q) = "ImpR on " ++ show p ++ " and " ++ show q showRule (UniL t p) = "UniL on " ++ show t ++ " and " ++ show p showRule (UniR p) = "UniR on " ++ show p showFms :: [Fm] -> String showFms ps = concat (intersperse ", " (map show ps)) showTree :: Int -> Tree (([Fm], [Fm]), Rule) -> String showTree n (Node ((l, r), rule) (Abs_fset (Set ts))) = let inc = if length ts > 1 then 2 else 0 in replicate n ' ' ++ showFms l ++ " |- " ++ showFms r ++ "\n" ++ replicate n ' ' ++ " + " ++ showRule rule ++ "\n" ++ concat (map (showTree (n + inc)) ts) instance Read Arith.Nat where readsPrec d s = map (\(n, s) -> (Arith.Nat n, s)) (readsPrec d s :: [(Integer, String)]) deriving instance Read Tm deriving instance Read Fm main :: IO () main = do args <- getArgs let p = read (head args) :: Fm let res = prove p putStrLn (showTree 0 res) diff --git a/thys/FOL_Seq_Calc3/Prover.thy b/thys/FOL_Seq_Calc3/Prover.thy --- a/thys/FOL_Seq_Calc3/Prover.thy +++ b/thys/FOL_Seq_Calc3/Prover.thy @@ -1,48 +1,43 @@ section \Prover\ theory Prover imports "Abstract_Completeness.Abstract_Completeness" Encoding Fair_Stream begin function eff :: \rule \ sequent \ (sequent fset) option\ where - \eff Idle (A, B) = - Some {| (A, B) |}\ -| \eff (Axiom P ts) (A, B) = (if \<^bold>\P ts [\] A \ \<^bold>\P ts [\] B then - Some {||} else None)\ -| \eff FlsL (A, B) = (if \<^bold>\ [\] A then - Some {||} else None)\ -| \eff FlsR (A, B) = (if \<^bold>\ [\] B then - Some {| (A, B [\
] \<^bold>\) |} else None)\ + \eff Idle (A, B) = Some {| (A, B) |}\ +| \eff (Axiom P ts) (A, B) = (if \<^bold>\P ts [\] A \ \<^bold>\P ts [\] B then Some {||} else None)\ +| \eff FlsL (A, B) = (if \<^bold>\ [\] A then Some {||} else None)\ +| \eff FlsR (A, B) = (if \<^bold>\ [\] B then Some {| (A, B [\
] \<^bold>\) |} else None)\ | \eff (ImpL p q) (A, B) = (if (p \<^bold>\ q) [\] A then Some {| (A [\
] (p \<^bold>\ q), p # B), (q # A [\
] (p \<^bold>\ q), B) |} else None)\ | \eff (ImpR p q) (A, B) = (if (p \<^bold>\ q) [\] B then Some {| (p # A, q # B [\
] (p \<^bold>\ q)) |} else None)\ -| \eff (UniL t p) (A, B) = (if \<^bold>\p [\] A then - Some {| (\t\p # A, B) |} else None)\ +| \eff (UniL t p) (A, B) = (if \<^bold>\p [\] A then Some {| (\t\p # A, B) |} else None)\ | \eff (UniR p) (A, B) = (if \<^bold>\p [\] B then Some {| (A, \\<^bold>#(fresh (A @ B))\p # B [\
] \<^bold>\p) |} else None)\ by pat_completeness auto termination by (relation \measure size\) standard definition rules :: \rule stream\ where \rules \ fair_stream rule_of_nat\ lemma UNIV_rules: \sset rules = UNIV\ unfolding rules_def using UNIV_stream surj_rule_of_nat . interpretation RuleSystem \\r s ss. eff r s = Some ss\ rules UNIV by unfold_locales (auto simp: UNIV_rules intro: exI[of _ Idle]) lemma per_rules': assumes \enabled r (A, B)\ \\ enabled r (A', B')\ \eff r' (A, B) = Some ss'\ \(A', B') |\| ss'\ shows \r' = r\ using assms by (cases r r' rule: rule.exhaust[case_product rule.exhaust]) (unfold enabled_def, auto split: if_splits) lemma per_rules: \per r\ unfolding per_def UNIV_rules using per_rules' by fast interpretation PersistentRuleSystem \\r s ss. eff r s = Some ss\ rules UNIV using per_rules by unfold_locales definition \prover \ mkTree rules\ end diff --git a/thys/FOL_Seq_Calc3/Syntax.thy b/thys/FOL_Seq_Calc3/Syntax.thy --- a/thys/FOL_Seq_Calc3/Syntax.thy +++ b/thys/FOL_Seq_Calc3/Syntax.thy @@ -1,97 +1,90 @@ section \Syntax\ theory Syntax imports List_Syntax begin subsection \Terms and Formulas\ datatype tm = Var nat (\\<^bold>#\) | Fun nat \tm list\ (\\<^bold>\\) datatype fm = Falsity (\\<^bold>\\) | Pre nat \tm list\ (\\<^bold>\\) | Imp fm fm (infixr \\<^bold>\\ 55) | Uni fm (\\<^bold>\\) type_synonym sequent = \fm list \ fm list\ subsubsection \Substitution\ primrec add_env :: \'a \ (nat \ 'a) \ nat \ 'a\ (infix \\\ 0) where \(t \ s) 0 = t\ | \(t \ s) (Suc n) = s n\ primrec lift_tm :: \tm \ tm\ where \lift_tm (\<^bold>#n) = \<^bold>#(n+1)\ | \lift_tm (\<^bold>\f ts) = \<^bold>\f (map lift_tm ts)\ primrec sub_tm :: \(nat \ tm) \ tm \ tm\ where \sub_tm s (\<^bold>#n) = s n\ | \sub_tm s (\<^bold>\f ts) = \<^bold>\f (map (sub_tm s) ts)\ primrec sub_fm :: \(nat \ tm) \ fm \ fm\ where - \sub_fm s \<^bold>\ = \<^bold>\\ + \sub_fm _ \<^bold>\ = \<^bold>\\ | \sub_fm s (\<^bold>\P ts) = \<^bold>\P (map (sub_tm s) ts)\ | \sub_fm s (p \<^bold>\ q) = sub_fm s p \<^bold>\ sub_fm s q\ | \sub_fm s (\<^bold>\p) = \<^bold>\(sub_fm (\<^bold>#0 \ \n. lift_tm (s n)) p)\ abbreviation inst_single :: \tm \ fm \ fm\ (\\_\\) where - \\t\p \ sub_fm (t \ \<^bold>#) p\ + \\t\ \ sub_fm (t \ \<^bold>#)\ subsubsection \Variables\ primrec vars_tm :: \tm \ nat list\ where \vars_tm (\<^bold>#n) = [n]\ | \vars_tm (\<^bold>\_ ts) = concat (map vars_tm ts)\ primrec vars_fm :: \fm \ nat list\ where \vars_fm \<^bold>\ = []\ | \vars_fm (\<^bold>\_ ts) = concat (map vars_tm ts)\ | \vars_fm (p \<^bold>\ q) = vars_fm p @ vars_fm q\ | \vars_fm (\<^bold>\p) = vars_fm p\ primrec max_list :: \nat list \ nat\ where \max_list [] = 0\ | \max_list (x # xs) = max x (max_list xs)\ lemma max_list_append: \max_list (xs @ ys) = max (max_list xs) (max_list ys)\ by (induct xs) auto lemma max_list_concat: \xs [\] xss \ max_list xs \ max_list (concat xss)\ by (induct xss) (auto simp: max_list_append) lemma max_list_in: \max_list xs < n \ n [\] xs\ by (induct xs) auto definition vars_fms :: \fm list \ nat list\ where \vars_fms A \ concat (map vars_fm A)\ lemma vars_fms_member: \p [\] A \ vars_fm p [\] vars_fms A\ unfolding vars_fms_def by (induct A) auto lemma max_list_mono: \A [\] B \ max_list A \ max_list B\ by (induct A) (simp, metis linorder_not_le list.set_intros(1) max.absorb2 max.absorb3 max_list.simps(2) max_list_in set_subset_Cons subset_code(1)) lemma max_list_vars_fms: assumes \max_list (vars_fms A) \ n\ \p [\] A\ shows \max_list (vars_fm p) \ n\ using assms max_list_mono vars_fms_member by (meson dual_order.trans) definition fresh :: \fm list \ nat\ where \fresh A \ Suc (max_list (vars_fms A))\ subsection \Rules\ -datatype rule - = Idle - | Axiom nat \tm list\ - | FlsL - | FlsR - | ImpL fm fm - | ImpR fm fm - | UniL tm fm - | UniR fm +datatype rule = + Idle | Axiom nat \tm list\ | FlsL | FlsR | ImpL fm fm | ImpR fm fm | UniL tm fm | UniR fm end