src/HOL/Induct/PropLog.ML
changeset 5069 3ea049f7979d
parent 4831 dae4d63a1318
child 5143 b94cd208f073
equal deleted inserted replaced
5068:fb28eaa07e01 5069:3ea049f7979d
     9 *)
     9 *)
    10 
    10 
    11 open PropLog;
    11 open PropLog;
    12 
    12 
    13 (** Monotonicity **)
    13 (** Monotonicity **)
    14 goalw PropLog.thy thms.defs "!!G H. G<=H ==> thms(G) <= thms(H)";
    14 Goalw thms.defs "!!G H. G<=H ==> thms(G) <= thms(H)";
    15 by (rtac lfp_mono 1);
    15 by (rtac lfp_mono 1);
    16 by (REPEAT (ares_tac basic_monos 1));
    16 by (REPEAT (ares_tac basic_monos 1));
    17 qed "thms_mono";
    17 qed "thms_mono";
    18 
    18 
    19 (*Rule is called I for Identity Combinator, not for Introduction*)
    19 (*Rule is called I for Identity Combinator, not for Introduction*)
    20 goal PropLog.thy "H |- p->p";
    20 Goal "H |- p->p";
    21 by (best_tac (claset() addIs [thms.K,thms.S,thms.MP]) 1);
    21 by (best_tac (claset() addIs [thms.K,thms.S,thms.MP]) 1);
    22 qed "thms_I";
    22 qed "thms_I";
    23 
    23 
    24 (** Weakening, left and right **)
    24 (** Weakening, left and right **)
    25 
    25 
    32 val weaken_left_insert = subset_insertI RS weaken_left;
    32 val weaken_left_insert = subset_insertI RS weaken_left;
    33 
    33 
    34 val weaken_left_Un1  =    Un_upper1 RS weaken_left;
    34 val weaken_left_Un1  =    Un_upper1 RS weaken_left;
    35 val weaken_left_Un2  =    Un_upper2 RS weaken_left;
    35 val weaken_left_Un2  =    Un_upper2 RS weaken_left;
    36 
    36 
    37 goal PropLog.thy "!!H. H |- q ==> H |- p->q";
    37 Goal "!!H. H |- q ==> H |- p->q";
    38 by (fast_tac (claset() addIs [thms.K,thms.MP]) 1);
    38 by (fast_tac (claset() addIs [thms.K,thms.MP]) 1);
    39 qed "weaken_right";
    39 qed "weaken_right";
    40 
    40 
    41 (*The deduction theorem*)
    41 (*The deduction theorem*)
    42 goal PropLog.thy "!!H. insert p H |- q  ==>  H |- p->q";
    42 Goal "!!H. insert p H |- q  ==>  H |- p->q";
    43 by (etac thms.induct 1);
    43 by (etac thms.induct 1);
    44 by (ALLGOALS 
    44 by (ALLGOALS 
    45     (fast_tac (claset() addIs [thms_I, thms.H, thms.K, thms.S, thms.DN, 
    45     (fast_tac (claset() addIs [thms_I, thms.H, thms.K, thms.S, thms.DN, 
    46 			       thms.S RS thms.MP RS thms.MP, weaken_right])));
    46 			       thms.S RS thms.MP RS thms.MP, weaken_right])));
    47 qed "deduction";
    47 qed "deduction";
    58 (* [| H |- p->false;  H |- p;  q: pl |] ==> H |- q *)
    58 (* [| H |- p->false;  H |- p;  q: pl |] ==> H |- q *)
    59 bind_thm ("thms_notE", (thms.MP RS thms_falseE));
    59 bind_thm ("thms_notE", (thms.MP RS thms_falseE));
    60 
    60 
    61 (** The function eval **)
    61 (** The function eval **)
    62 
    62 
    63 goalw PropLog.thy [eval_def] "tt[false] = False";
    63 Goalw [eval_def] "tt[false] = False";
    64 by (Simp_tac 1);
    64 by (Simp_tac 1);
    65 qed "eval_false";
    65 qed "eval_false";
    66 
    66 
    67 goalw PropLog.thy [eval_def] "tt[#v] = (v:tt)";
    67 Goalw [eval_def] "tt[#v] = (v:tt)";
    68 by (Simp_tac 1);
    68 by (Simp_tac 1);
    69 qed "eval_var";
    69 qed "eval_var";
    70 
    70 
    71 goalw PropLog.thy [eval_def] "tt[p->q] = (tt[p]-->tt[q])";
    71 Goalw [eval_def] "tt[p->q] = (tt[p]-->tt[q])";
    72 by (Simp_tac 1);
    72 by (Simp_tac 1);
    73 qed "eval_imp";
    73 qed "eval_imp";
    74 
    74 
    75 Addsimps [eval_false, eval_var, eval_imp];
    75 Addsimps [eval_false, eval_var, eval_imp];
    76 
    76 
    77 (*Soundness of the rules wrt truth-table semantics*)
    77 (*Soundness of the rules wrt truth-table semantics*)
    78 goalw PropLog.thy [sat_def] "!!H. H |- p ==> H |= p";
    78 Goalw [sat_def] "!!H. H |- p ==> H |= p";
    79 by (etac thms.induct 1);
    79 by (etac thms.induct 1);
    80 by (fast_tac (claset() addSDs [eval_imp RS iffD1 RS mp]) 5);
    80 by (fast_tac (claset() addSDs [eval_imp RS iffD1 RS mp]) 5);
    81 by (ALLGOALS Asm_simp_tac);
    81 by (ALLGOALS Asm_simp_tac);
    82 qed "soundness";
    82 qed "soundness";
    83 
    83 
    84 (*** Towards the completeness proof ***)
    84 (*** Towards the completeness proof ***)
    85 
    85 
    86 goal PropLog.thy "!!H. H |- p->false ==> H |- p->q";
    86 Goal "!!H. H |- p->false ==> H |- p->q";
    87 by (rtac deduction 1);
    87 by (rtac deduction 1);
    88 by (etac (weaken_left_insert RS thms_notE) 1);
    88 by (etac (weaken_left_insert RS thms_notE) 1);
    89 by (rtac thms.H 1);
    89 by (rtac thms.H 1);
    90 by (rtac insertI1 1);
    90 by (rtac insertI1 1);
    91 qed "false_imp";
    91 qed "false_imp";
    98 by (rtac insertI1 1);
    98 by (rtac insertI1 1);
    99 by (rtac (premp RS weaken_left_insert) 1);
    99 by (rtac (premp RS weaken_left_insert) 1);
   100 qed "imp_false";
   100 qed "imp_false";
   101 
   101 
   102 (*This formulation is required for strong induction hypotheses*)
   102 (*This formulation is required for strong induction hypotheses*)
   103 goal PropLog.thy "hyps p tt |- (if tt[p] then p else p->false)";
   103 Goal "hyps p tt |- (if tt[p] then p else p->false)";
   104 by (rtac (split_if RS iffD2) 1);
   104 by (rtac (split_if RS iffD2) 1);
   105 by (PropLog.pl.induct_tac "p" 1);
   105 by (PropLog.pl.induct_tac "p" 1);
   106 by (ALLGOALS (simp_tac (simpset() addsimps [thms_I, thms.H])));
   106 by (ALLGOALS (simp_tac (simpset() addsimps [thms_I, thms.H])));
   107 by (fast_tac (claset() addIs [weaken_left_Un1, weaken_left_Un2, 
   107 by (fast_tac (claset() addIs [weaken_left_Un1, weaken_left_Un2, 
   108 			      weaken_right, imp_false]
   108 			      weaken_right, imp_false]
   120 
   120 
   121 AddSIs [deduction];
   121 AddSIs [deduction];
   122 AddIs [thms.H, thms.H RS thms.MP];
   122 AddIs [thms.H, thms.H RS thms.MP];
   123 
   123 
   124 (*The excluded middle in the form of an elimination rule*)
   124 (*The excluded middle in the form of an elimination rule*)
   125 goal PropLog.thy "H |- (p->q) -> ((p->false)->q) -> q";
   125 Goal "H |- (p->q) -> ((p->false)->q) -> q";
   126 by (rtac (deduction RS deduction) 1);
   126 by (rtac (deduction RS deduction) 1);
   127 by (rtac (thms.DN RS thms.MP) 1);
   127 by (rtac (thms.DN RS thms.MP) 1);
   128 by (ALLGOALS (best_tac (claset() addSIs prems)));
   128 by (ALLGOALS (best_tac (claset() addSIs prems)));
   129 qed "thms_excluded_middle";
   129 qed "thms_excluded_middle";
   130 
   130 
   137 
   137 
   138 (*** Completeness -- lemmas for reducing the set of assumptions ***)
   138 (*** Completeness -- lemmas for reducing the set of assumptions ***)
   139 
   139 
   140 (*For the case hyps(p,t)-insert(#v,Y) |- p;
   140 (*For the case hyps(p,t)-insert(#v,Y) |- p;
   141   we also have hyps(p,t)-{#v} <= hyps(p, t-{v}) *)
   141   we also have hyps(p,t)-{#v} <= hyps(p, t-{v}) *)
   142 goal PropLog.thy "hyps p (t-{v}) <= insert (#v->false) ((hyps p t)-{#v})";
   142 Goal "hyps p (t-{v}) <= insert (#v->false) ((hyps p t)-{#v})";
   143 by (PropLog.pl.induct_tac "p" 1);
   143 by (PropLog.pl.induct_tac "p" 1);
   144 by (ALLGOALS Simp_tac);
   144 by (ALLGOALS Simp_tac);
   145 by (Fast_tac 1);
   145 by (Fast_tac 1);
   146 qed "hyps_Diff";
   146 qed "hyps_Diff";
   147 
   147 
   148 (*For the case hyps(p,t)-insert(#v -> false,Y) |- p;
   148 (*For the case hyps(p,t)-insert(#v -> false,Y) |- p;
   149   we also have hyps(p,t)-{#v->false} <= hyps(p, insert(v,t)) *)
   149   we also have hyps(p,t)-{#v->false} <= hyps(p, insert(v,t)) *)
   150 goal PropLog.thy "hyps p (insert v t) <= insert (#v) (hyps p t-{#v->false})";
   150 Goal "hyps p (insert v t) <= insert (#v) (hyps p t-{#v->false})";
   151 by (PropLog.pl.induct_tac "p" 1);
   151 by (PropLog.pl.induct_tac "p" 1);
   152 by (ALLGOALS Simp_tac);
   152 by (ALLGOALS Simp_tac);
   153 by (Fast_tac 1);
   153 by (Fast_tac 1);
   154 qed "hyps_insert";
   154 qed "hyps_insert";
   155 
   155 
   161 
   161 
   162 goal Set.thy "insert a (B-{c}) - D <= insert a (B-insert c D)";
   162 goal Set.thy "insert a (B-{c}) - D <= insert a (B-insert c D)";
   163 by (Fast_tac 1);
   163 by (Fast_tac 1);
   164 qed "insert_Diff_subset2";
   164 qed "insert_Diff_subset2";
   165 
   165 
   166 goal PropLog.thy "finite(hyps p t)";
   166 Goal "finite(hyps p t)";
   167 by (induct_tac "p" 1);
   167 by (induct_tac "p" 1);
   168 by (ALLGOALS Asm_simp_tac);
   168 by (ALLGOALS Asm_simp_tac);
   169 qed "hyps_finite";
   169 qed "hyps_finite";
   170 
   170 
   171 goal PropLog.thy "hyps p t <= (UN v. {#v, #v->false})";
   171 Goal "hyps p t <= (UN v. {#v, #v->false})";
   172 by (PropLog.pl.induct_tac "p" 1);
   172 by (PropLog.pl.induct_tac "p" 1);
   173 by (ALLGOALS Simp_tac);
   173 by (ALLGOALS Simp_tac);
   174 by (Blast_tac 1);
   174 by (Blast_tac 1);
   175 qed "hyps_subset";
   175 qed "hyps_subset";
   176 
   176 
   204 by (rtac (Diff_cancel RS subst) 1);
   204 by (rtac (Diff_cancel RS subst) 1);
   205 by (rtac (sat RS (completeness_0_lemma RS spec)) 1);
   205 by (rtac (sat RS (completeness_0_lemma RS spec)) 1);
   206 qed "completeness_0";
   206 qed "completeness_0";
   207 
   207 
   208 (*A semantic analogue of the Deduction Theorem*)
   208 (*A semantic analogue of the Deduction Theorem*)
   209 goalw PropLog.thy [sat_def] "!!p H. insert p H |= q ==> H |= p->q";
   209 Goalw [sat_def] "!!p H. insert p H |= q ==> H |= p->q";
   210 by (Simp_tac 1);
   210 by (Simp_tac 1);
   211 by (Fast_tac 1);
   211 by (Fast_tac 1);
   212 qed "sat_imp";
   212 qed "sat_imp";
   213 
   213 
   214 goal PropLog.thy "!!H. finite H ==> !p. H |= p --> H |- p";
   214 Goal "!!H. finite H ==> !p. H |= p --> H |- p";
   215 by (etac finite_induct 1);
   215 by (etac finite_induct 1);
   216 by (safe_tac ((claset_of Fun.thy) addSIs [completeness_0]));
   216 by (safe_tac ((claset_of Fun.thy) addSIs [completeness_0]));
   217 by (rtac (weaken_left_insert RS thms.MP) 1);
   217 by (rtac (weaken_left_insert RS thms.MP) 1);
   218 by (fast_tac ((claset_of Fun.thy) addSIs [sat_imp]) 1);
   218 by (fast_tac ((claset_of Fun.thy) addSIs [sat_imp]) 1);
   219 by (Fast_tac 1);
   219 by (Fast_tac 1);
   220 qed "completeness_lemma";
   220 qed "completeness_lemma";
   221 
   221 
   222 val completeness = completeness_lemma RS spec RS mp;
   222 val completeness = completeness_lemma RS spec RS mp;
   223 
   223 
   224 goal PropLog.thy "!!H. finite H ==> (H |- p) = (H |= p)";
   224 Goal "!!H. finite H ==> (H |- p) = (H |= p)";
   225 by (fast_tac (claset() addSEs [soundness, completeness]) 1);
   225 by (fast_tac (claset() addSEs [soundness, completeness]) 1);
   226 qed "syntax_iff_semantics";
   226 qed "syntax_iff_semantics";