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"; |