src/FOLP/IFOLP.thy
 author wenzelm Wed Dec 31 15:30:10 2008 +0100 (2008-12-31) changeset 29269 5c25a2012975 parent 27152 192954a9a549 child 29305 76af2a3c9d28 permissions -rw-r--r--
moved term order operations to structure TermOrd (cf. Pure/term_ord.ML);
tuned signature of structure Term;
1 (*  Title:      FOLP/IFOLP.thy
2     Author:     Martin D Coen, Cambridge University Computer Laboratory
3     Copyright   1992  University of Cambridge
4 *)
6 header {* Intuitionistic First-Order Logic with Proofs *}
8 theory IFOLP
9 imports Pure
10 uses ("hypsubst.ML") ("intprover.ML")
11 begin
13 setup PureThy.old_appl_syntax_setup
15 global
17 classes "term"
18 defaultsort "term"
20 typedecl p
21 typedecl o
23 consts
24       (*** Judgements ***)
25  "@Proof"       ::   "[p,o]=>prop"      ("(_ /: _)" [51,10] 5)
26  Proof          ::   "[o,p]=>prop"
27  EqProof        ::   "[p,p,o]=>prop"    ("(3_ /= _ :/ _)" [10,10,10] 5)
29       (*** Logical Connectives -- Type Formers ***)
30  "="            ::      "['a,'a] => o"  (infixl 50)
31  True           ::      "o"
32  False          ::      "o"
33  Not            ::      "o => o"        ("~ _"  40)
34  "&"            ::      "[o,o] => o"    (infixr 35)
35  "|"            ::      "[o,o] => o"    (infixr 30)
36  "-->"          ::      "[o,o] => o"    (infixr 25)
37  "<->"          ::      "[o,o] => o"    (infixr 25)
38       (*Quantifiers*)
39  All            ::      "('a => o) => o"        (binder "ALL " 10)
40  Ex             ::      "('a => o) => o"        (binder "EX " 10)
41  Ex1            ::      "('a => o) => o"        (binder "EX! " 10)
43  NORM           ::      "o => o"
44  norm           ::      "'a => 'a"
46       (*** Proof Term Formers: precedence must exceed 50 ***)
47  tt             :: "p"
48  contr          :: "p=>p"
49  fst            :: "p=>p"
50  snd            :: "p=>p"
51  pair           :: "[p,p]=>p"           ("(1<_,/_>)")
52  split          :: "[p, [p,p]=>p] =>p"
53  inl            :: "p=>p"
54  inr            :: "p=>p"
55  when           :: "[p, p=>p, p=>p]=>p"
56  lambda         :: "(p => p) => p"      (binder "lam " 55)
57  "`"            :: "[p,p]=>p"           (infixl 60)
58  alll           :: "['a=>p]=>p"         (binder "all " 55)
59  "^"            :: "[p,'a]=>p"          (infixl 55)
60  exists         :: "['a,p]=>p"          ("(1[_,/_])")
61  xsplit         :: "[p,['a,p]=>p]=>p"
62  ideq           :: "'a=>p"
63  idpeel         :: "[p,'a=>p]=>p"
64  nrm            :: p
65  NRM            :: p
67 local
69 ML {*
71 (*show_proofs:=true displays the proof terms -- they are ENORMOUS*)
72 val show_proofs = ref false;
74 fun proof_tr [p,P] = Const (@{const_name Proof}, dummyT) \$ P \$ p;
76 fun proof_tr' [P,p] =
77     if !show_proofs then Const("@Proof",dummyT) \$ p \$ P
78     else P  (*this case discards the proof term*);
79 *}
81 parse_translation {* [("@Proof", proof_tr)] *}
82 print_translation {* [("Proof", proof_tr')] *}
84 axioms
86 (**** Propositional logic ****)
88 (*Equality*)
89 (* Like Intensional Equality in MLTT - but proofs distinct from terms *)
91 ieqI:      "ideq(a) : a=a"
92 ieqE:      "[| p : a=b;  !!x. f(x) : P(x,x) |] ==> idpeel(p,f) : P(a,b)"
94 (* Truth and Falsity *)
96 TrueI:     "tt : True"
97 FalseE:    "a:False ==> contr(a):P"
99 (* Conjunction *)
101 conjI:     "[| a:P;  b:Q |] ==> <a,b> : P&Q"
102 conjunct1: "p:P&Q ==> fst(p):P"
103 conjunct2: "p:P&Q ==> snd(p):Q"
105 (* Disjunction *)
107 disjI1:    "a:P ==> inl(a):P|Q"
108 disjI2:    "b:Q ==> inr(b):P|Q"
109 disjE:     "[| a:P|Q;  !!x. x:P ==> f(x):R;  !!x. x:Q ==> g(x):R
110            |] ==> when(a,f,g):R"
112 (* Implication *)
114 impI:      "(!!x. x:P ==> f(x):Q) ==> lam x. f(x):P-->Q"
115 mp:        "[| f:P-->Q;  a:P |] ==> f`a:Q"
117 (*Quantifiers*)
119 allI:      "(!!x. f(x) : P(x)) ==> all x. f(x) : ALL x. P(x)"
120 spec:      "(f:ALL x. P(x)) ==> f^x : P(x)"
122 exI:       "p : P(x) ==> [x,p] : EX x. P(x)"
123 exE:       "[| p: EX x. P(x);  !!x u. u:P(x) ==> f(x,u) : R |] ==> xsplit(p,f):R"
125 (**** Equality between proofs ****)
127 prefl:     "a : P ==> a = a : P"
128 psym:      "a = b : P ==> b = a : P"
129 ptrans:    "[| a = b : P;  b = c : P |] ==> a = c : P"
131 idpeelB:   "[| !!x. f(x) : P(x,x) |] ==> idpeel(ideq(a),f) = f(a) : P(a,a)"
133 fstB:      "a:P ==> fst(<a,b>) = a : P"
134 sndB:      "b:Q ==> snd(<a,b>) = b : Q"
135 pairEC:    "p:P&Q ==> p = <fst(p),snd(p)> : P&Q"
137 whenBinl:  "[| a:P;  !!x. x:P ==> f(x) : Q |] ==> when(inl(a),f,g) = f(a) : Q"
138 whenBinr:  "[| b:P;  !!x. x:P ==> g(x) : Q |] ==> when(inr(b),f,g) = g(b) : Q"
139 plusEC:    "a:P|Q ==> when(a,%x. inl(x),%y. inr(y)) = a : P|Q"
141 applyB:     "[| a:P;  !!x. x:P ==> b(x) : Q |] ==> (lam x. b(x)) ` a = b(a) : Q"
142 funEC:      "f:P ==> f = lam x. f`x : P"
144 specB:      "[| !!x. f(x) : P(x) |] ==> (all x. f(x)) ^ a = f(a) : P(a)"
147 (**** Definitions ****)
149 not_def:              "~P == P-->False"
150 iff_def:         "P<->Q == (P-->Q) & (Q-->P)"
152 (*Unique existence*)
153 ex1_def:   "EX! x. P(x) == EX x. P(x) & (ALL y. P(y) --> y=x)"
155 (*Rewriting -- special constants to flag normalized terms and formulae*)
156 norm_eq: "nrm : norm(x) = x"
157 NORM_iff:        "NRM : NORM(P) <-> P"
159 (*** Sequent-style elimination rules for & --> and ALL ***)
161 lemma conjE:
162   assumes "p:P&Q"
163     and "!!x y.[| x:P; y:Q |] ==> f(x,y):R"
164   shows "?a:R"
165   apply (rule assms(2))
166    apply (rule conjunct1 [OF assms(1)])
167   apply (rule conjunct2 [OF assms(1)])
168   done
170 lemma impE:
171   assumes "p:P-->Q"
172     and "q:P"
173     and "!!x. x:Q ==> r(x):R"
174   shows "?p:R"
175   apply (rule assms mp)+
176   done
178 lemma allE:
179   assumes "p:ALL x. P(x)"
180     and "!!y. y:P(x) ==> q(y):R"
181   shows "?p:R"
182   apply (rule assms spec)+
183   done
185 (*Duplicates the quantifier; for use with eresolve_tac*)
186 lemma all_dupE:
187   assumes "p:ALL x. P(x)"
188     and "!!y z.[| y:P(x); z:ALL x. P(x) |] ==> q(y,z):R"
189   shows "?p:R"
190   apply (rule assms spec)+
191   done
194 (*** Negation rules, which translate between ~P and P-->False ***)
196 lemma notI:
197   assumes "!!x. x:P ==> q(x):False"
198   shows "?p:~P"
199   unfolding not_def
200   apply (assumption | rule assms impI)+
201   done
203 lemma notE: "p:~P \<Longrightarrow> q:P \<Longrightarrow> ?p:R"
204   unfolding not_def
205   apply (drule (1) mp)
206   apply (erule FalseE)
207   done
209 (*This is useful with the special implication rules for each kind of P. *)
210 lemma not_to_imp:
211   assumes "p:~P"
212     and "!!x. x:(P-->False) ==> q(x):Q"
213   shows "?p:Q"
214   apply (assumption | rule assms impI notE)+
215   done
217 (* For substitution int an assumption P, reduce Q to P-->Q, substitute into
218    this implication, then apply impI to move P back into the assumptions.*)
219 lemma rev_mp: "[| p:P;  q:P --> Q |] ==> ?p:Q"
220   apply (assumption | rule mp)+
221   done
224 (*Contrapositive of an inference rule*)
225 lemma contrapos:
226   assumes major: "p:~Q"
227     and minor: "!!y. y:P==>q(y):Q"
228   shows "?a:~P"
229   apply (rule major [THEN notE, THEN notI])
230   apply (erule minor)
231   done
233 (** Unique assumption tactic.
234     Ignores proof objects.
235     Fails unless one assumption is equal and exactly one is unifiable
236 **)
238 ML {*
239 local
240   fun discard_proof (Const (@{const_name Proof}, _) \$ P \$ _) = P;
241 in
242 val uniq_assume_tac =
243   SUBGOAL
244     (fn (prem,i) =>
245       let val hyps = map discard_proof (Logic.strip_assums_hyp prem)
246           and concl = discard_proof (Logic.strip_assums_concl prem)
247       in
248           if exists (fn hyp => hyp aconv concl) hyps
249           then case distinct (op =) (filter (fn hyp => Term.could_unify (hyp, concl)) hyps) of
250                    [_] => assume_tac i
251                  |  _  => no_tac
252           else no_tac
253       end);
254 end;
255 *}
258 (*** Modus Ponens Tactics ***)
260 (*Finds P-->Q and P in the assumptions, replaces implication by Q *)
261 ML {*
262   fun mp_tac i = eresolve_tac [@{thm notE}, make_elim @{thm mp}] i  THEN  assume_tac i
263 *}
265 (*Like mp_tac but instantiates no variables*)
266 ML {*
267   fun int_uniq_mp_tac i = eresolve_tac [@{thm notE}, @{thm impE}] i  THEN  uniq_assume_tac i
268 *}
271 (*** If-and-only-if ***)
273 lemma iffI:
274   assumes "!!x. x:P ==> q(x):Q"
275     and "!!x. x:Q ==> r(x):P"
276   shows "?p:P<->Q"
277   unfolding iff_def
278   apply (assumption | rule assms conjI impI)+
279   done
282 (*Observe use of rewrite_rule to unfold "<->" in meta-assumptions (prems) *)
284 lemma iffE:
285   assumes "p:P <-> Q"
286     and "!!x y.[| x:P-->Q; y:Q-->P |] ==> q(x,y):R"
287   shows "?p:R"
288   apply (rule conjE)
289    apply (rule assms(1) [unfolded iff_def])
290   apply (rule assms(2))
291    apply assumption+
292   done
294 (* Destruct rules for <-> similar to Modus Ponens *)
296 lemma iffD1: "[| p:P <-> Q; q:P |] ==> ?p:Q"
297   unfolding iff_def
298   apply (rule conjunct1 [THEN mp], assumption+)
299   done
301 lemma iffD2: "[| p:P <-> Q; q:Q |] ==> ?p:P"
302   unfolding iff_def
303   apply (rule conjunct2 [THEN mp], assumption+)
304   done
306 lemma iff_refl: "?p:P <-> P"
307   apply (rule iffI)
308    apply assumption+
309   done
311 lemma iff_sym: "p:Q <-> P ==> ?p:P <-> Q"
312   apply (erule iffE)
313   apply (rule iffI)
314    apply (erule (1) mp)+
315   done
317 lemma iff_trans: "[| p:P <-> Q; q:Q<-> R |] ==> ?p:P <-> R"
318   apply (rule iffI)
319    apply (assumption | erule iffE | erule (1) impE)+
320   done
322 (*** Unique existence.  NOTE THAT the following 2 quantifications
323    EX!x such that [EX!y such that P(x,y)]     (sequential)
324    EX!x,y such that P(x,y)                    (simultaneous)
325  do NOT mean the same thing.  The parser treats EX!x y.P(x,y) as sequential.
326 ***)
328 lemma ex1I:
329   assumes "p:P(a)"
330     and "!!x u. u:P(x) ==> f(u) : x=a"
331   shows "?p:EX! x. P(x)"
332   unfolding ex1_def
333   apply (assumption | rule assms exI conjI allI impI)+
334   done
336 lemma ex1E:
337   assumes "p:EX! x. P(x)"
338     and "!!x u v. [| u:P(x);  v:ALL y. P(y) --> y=x |] ==> f(x,u,v):R"
339   shows "?a : R"
340   apply (insert assms(1) [unfolded ex1_def])
341   apply (erule exE conjE | assumption | rule assms(1))+
342   done
345 (*** <-> congruence rules for simplification ***)
347 (*Use iffE on a premise.  For conj_cong, imp_cong, all_cong, ex_cong*)
348 ML {*
349 fun iff_tac prems i =
350     resolve_tac (prems RL [@{thm iffE}]) i THEN
351     REPEAT1 (eresolve_tac [asm_rl, @{thm mp}] i)
352 *}
354 lemma conj_cong:
355   assumes "p:P <-> P'"
356     and "!!x. x:P' ==> q(x):Q <-> Q'"
357   shows "?p:(P&Q) <-> (P'&Q')"
358   apply (insert assms(1))
359   apply (assumption | rule iffI conjI |
360     erule iffE conjE mp | tactic {* iff_tac @{thms assms} 1 *})+
361   done
363 lemma disj_cong:
364   "[| p:P <-> P'; q:Q <-> Q' |] ==> ?p:(P|Q) <-> (P'|Q')"
365   apply (erule iffE disjE disjI1 disjI2 | assumption | rule iffI | tactic {* mp_tac 1 *})+
366   done
368 lemma imp_cong:
369   assumes "p:P <-> P'"
370     and "!!x. x:P' ==> q(x):Q <-> Q'"
371   shows "?p:(P-->Q) <-> (P'-->Q')"
372   apply (insert assms(1))
373   apply (assumption | rule iffI impI | erule iffE | tactic {* mp_tac 1 *} |
374     tactic {* iff_tac @{thms assms} 1 *})+
375   done
377 lemma iff_cong:
378   "[| p:P <-> P'; q:Q <-> Q' |] ==> ?p:(P<->Q) <-> (P'<->Q')"
379   apply (erule iffE | assumption | rule iffI | tactic {* mp_tac 1 *})+
380   done
382 lemma not_cong:
383   "p:P <-> P' ==> ?p:~P <-> ~P'"
384   apply (assumption | rule iffI notI | tactic {* mp_tac 1 *} | erule iffE notE)+
385   done
387 lemma all_cong:
388   assumes "!!x. f(x):P(x) <-> Q(x)"
389   shows "?p:(ALL x. P(x)) <-> (ALL x. Q(x))"
390   apply (assumption | rule iffI allI | tactic {* mp_tac 1 *} | erule allE |
391     tactic {* iff_tac @{thms assms} 1 *})+
392   done
394 lemma ex_cong:
395   assumes "!!x. f(x):P(x) <-> Q(x)"
396   shows "?p:(EX x. P(x)) <-> (EX x. Q(x))"
397   apply (erule exE | assumption | rule iffI exI | tactic {* mp_tac 1 *} |
398     tactic {* iff_tac @{thms assms} 1 *})+
399   done
401 (*NOT PROVED
402 bind_thm ("ex1_cong", prove_goal (the_context ())
403     "(!!x.f(x):P(x) <-> Q(x)) ==> ?p:(EX! x.P(x)) <-> (EX! x.Q(x))"
404  (fn prems =>
405   [ (REPEAT   (eresolve_tac [ex1E, spec RS mp] 1 ORELSE ares_tac [iffI,ex1I] 1
406       ORELSE   mp_tac 1
407       ORELSE   iff_tac prems 1)) ]))
408 *)
410 (*** Equality rules ***)
412 lemmas refl = ieqI
414 lemma subst:
415   assumes prem1: "p:a=b"
416     and prem2: "q:P(a)"
417   shows "?p : P(b)"
418   apply (rule prem2 [THEN rev_mp])
419   apply (rule prem1 [THEN ieqE])
420   apply (rule impI)
421   apply assumption
422   done
424 lemma sym: "q:a=b ==> ?c:b=a"
425   apply (erule subst)
426   apply (rule refl)
427   done
429 lemma trans: "[| p:a=b;  q:b=c |] ==> ?d:a=c"
430   apply (erule (1) subst)
431   done
433 (** ~ b=a ==> ~ a=b **)
434 lemma not_sym: "p:~ b=a ==> ?q:~ a=b"
435   apply (erule contrapos)
436   apply (erule sym)
437   done
439 (*calling "standard" reduces maxidx to 0*)
440 lemmas ssubst = sym [THEN subst, standard]
442 (*A special case of ex1E that would otherwise need quantifier expansion*)
443 lemma ex1_equalsE: "[| p:EX! x. P(x);  q:P(a);  r:P(b) |] ==> ?d:a=b"
444   apply (erule ex1E)
445   apply (rule trans)
446    apply (rule_tac  sym)
447    apply (assumption | erule spec [THEN mp])+
448   done
450 (** Polymorphic congruence rules **)
452 lemma subst_context: "[| p:a=b |]  ==>  ?d:t(a)=t(b)"
453   apply (erule ssubst)
454   apply (rule refl)
455   done
457 lemma subst_context2: "[| p:a=b;  q:c=d |]  ==>  ?p:t(a,c)=t(b,d)"
458   apply (erule ssubst)+
459   apply (rule refl)
460   done
462 lemma subst_context3: "[| p:a=b;  q:c=d;  r:e=f |]  ==>  ?p:t(a,c,e)=t(b,d,f)"
463   apply (erule ssubst)+
464   apply (rule refl)
465   done
467 (*Useful with eresolve_tac for proving equalties from known equalities.
468         a = b
469         |   |
470         c = d   *)
471 lemma box_equals: "[| p:a=b;  q:a=c;  r:b=d |] ==> ?p:c=d"
472   apply (rule trans)
473    apply (rule trans)
474     apply (rule sym)
475     apply assumption+
476   done
478 (*Dual of box_equals: for proving equalities backwards*)
479 lemma simp_equals: "[| p:a=c;  q:b=d;  r:c=d |] ==> ?p:a=b"
480   apply (rule trans)
481    apply (rule trans)
482     apply (assumption | rule sym)+
483   done
485 (** Congruence rules for predicate letters **)
487 lemma pred1_cong: "p:a=a' ==> ?p:P(a) <-> P(a')"
488   apply (rule iffI)
489    apply (tactic {* DEPTH_SOLVE (atac 1 ORELSE eresolve_tac [@{thm subst}, @{thm ssubst}] 1) *})
490   done
492 lemma pred2_cong: "[| p:a=a';  q:b=b' |] ==> ?p:P(a,b) <-> P(a',b')"
493   apply (rule iffI)
494    apply (tactic {* DEPTH_SOLVE (atac 1 ORELSE eresolve_tac [@{thm subst}, @{thm ssubst}] 1) *})
495   done
497 lemma pred3_cong: "[| p:a=a';  q:b=b';  r:c=c' |] ==> ?p:P(a,b,c) <-> P(a',b',c')"
498   apply (rule iffI)
499    apply (tactic {* DEPTH_SOLVE (atac 1 ORELSE eresolve_tac [@{thm subst}, @{thm ssubst}] 1) *})
500   done
502 lemmas pred_congs = pred1_cong pred2_cong pred3_cong
504 (*special case for the equality predicate!*)
505 lemmas eq_cong = pred2_cong [where P = "op =", standard]
508 (*** Simplifications of assumed implications.
509      Roy Dyckhoff has proved that conj_impE, disj_impE, and imp_impE
510      used with mp_tac (restricted to atomic formulae) is COMPLETE for
511      intuitionistic propositional logic.  See
512    R. Dyckhoff, Contraction-free sequent calculi for intuitionistic logic
513     (preprint, University of St Andrews, 1991)  ***)
515 lemma conj_impE:
516   assumes major: "p:(P&Q)-->S"
517     and minor: "!!x. x:P-->(Q-->S) ==> q(x):R"
518   shows "?p:R"
519   apply (assumption | rule conjI impI major [THEN mp] minor)+
520   done
522 lemma disj_impE:
523   assumes major: "p:(P|Q)-->S"
524     and minor: "!!x y.[| x:P-->S; y:Q-->S |] ==> q(x,y):R"
525   shows "?p:R"
526   apply (tactic {* DEPTH_SOLVE (atac 1 ORELSE
527       resolve_tac [@{thm disjI1}, @{thm disjI2}, @{thm impI},
528         @{thm major} RS @{thm mp}, @{thm minor}] 1) *})
529   done
531 (*Simplifies the implication.  Classical version is stronger.
532   Still UNSAFE since Q must be provable -- backtracking needed.  *)
533 lemma imp_impE:
534   assumes major: "p:(P-->Q)-->S"
535     and r1: "!!x y.[| x:P; y:Q-->S |] ==> q(x,y):Q"
536     and r2: "!!x. x:S ==> r(x):R"
537   shows "?p:R"
538   apply (assumption | rule impI major [THEN mp] r1 r2)+
539   done
541 (*Simplifies the implication.  Classical version is stronger.
542   Still UNSAFE since ~P must be provable -- backtracking needed.  *)
543 lemma not_impE:
544   assumes major: "p:~P --> S"
545     and r1: "!!y. y:P ==> q(y):False"
546     and r2: "!!y. y:S ==> r(y):R"
547   shows "?p:R"
548   apply (assumption | rule notI impI major [THEN mp] r1 r2)+
549   done
551 (*Simplifies the implication.   UNSAFE.  *)
552 lemma iff_impE:
553   assumes major: "p:(P<->Q)-->S"
554     and r1: "!!x y.[| x:P; y:Q-->S |] ==> q(x,y):Q"
555     and r2: "!!x y.[| x:Q; y:P-->S |] ==> r(x,y):P"
556     and r3: "!!x. x:S ==> s(x):R"
557   shows "?p:R"
558   apply (assumption | rule iffI impI major [THEN mp] r1 r2 r3)+
559   done
561 (*What if (ALL x.~~P(x)) --> ~~(ALL x.P(x)) is an assumption? UNSAFE*)
562 lemma all_impE:
563   assumes major: "p:(ALL x. P(x))-->S"
564     and r1: "!!x. q:P(x)"
565     and r2: "!!y. y:S ==> r(y):R"
566   shows "?p:R"
567   apply (assumption | rule allI impI major [THEN mp] r1 r2)+
568   done
570 (*Unsafe: (EX x.P(x))-->S  is equivalent to  ALL x.P(x)-->S.  *)
571 lemma ex_impE:
572   assumes major: "p:(EX x. P(x))-->S"
573     and r: "!!y. y:P(a)-->S ==> q(y):R"
574   shows "?p:R"
575   apply (assumption | rule exI impI major [THEN mp] r)+
576   done
579 lemma rev_cut_eq:
580   assumes "p:a=b"
581     and "!!x. x:a=b ==> f(x):R"
582   shows "?p:R"
583   apply (rule assms)+
584   done
586 lemma thin_refl: "!!X. [|p:x=x; PROP W|] ==> PROP W" .
588 use "hypsubst.ML"
590 ML {*
592 (*** Applying HypsubstFun to generate hyp_subst_tac ***)
594 structure Hypsubst_Data =
595 struct
596   (*Take apart an equality judgement; otherwise raise Match!*)
597   fun dest_eq (Const (@{const_name Proof}, _) \$
598     (Const (@{const_name "op ="}, _)  \$ t \$ u) \$ _) = (t, u);
600   val imp_intr = @{thm impI}
602   (*etac rev_cut_eq moves an equality to be the last premise. *)
603   val rev_cut_eq = @{thm rev_cut_eq}
605   val rev_mp = @{thm rev_mp}
606   val subst = @{thm subst}
607   val sym = @{thm sym}
608   val thin_refl = @{thm thin_refl}
609 end;
611 structure Hypsubst = HypsubstFun(Hypsubst_Data);
612 open Hypsubst;
613 *}
615 use "intprover.ML"
618 (*** Rewrite rules ***)
620 lemma conj_rews:
621   "?p1 : P & True <-> P"
622   "?p2 : True & P <-> P"
623   "?p3 : P & False <-> False"
624   "?p4 : False & P <-> False"
625   "?p5 : P & P <-> P"
626   "?p6 : P & ~P <-> False"
627   "?p7 : ~P & P <-> False"
628   "?p8 : (P & Q) & R <-> P & (Q & R)"
629   apply (tactic {* fn st => IntPr.fast_tac 1 st *})+
630   done
632 lemma disj_rews:
633   "?p1 : P | True <-> True"
634   "?p2 : True | P <-> True"
635   "?p3 : P | False <-> P"
636   "?p4 : False | P <-> P"
637   "?p5 : P | P <-> P"
638   "?p6 : (P | Q) | R <-> P | (Q | R)"
639   apply (tactic {* IntPr.fast_tac 1 *})+
640   done
642 lemma not_rews:
643   "?p1 : ~ False <-> True"
644   "?p2 : ~ True <-> False"
645   apply (tactic {* IntPr.fast_tac 1 *})+
646   done
648 lemma imp_rews:
649   "?p1 : (P --> False) <-> ~P"
650   "?p2 : (P --> True) <-> True"
651   "?p3 : (False --> P) <-> True"
652   "?p4 : (True --> P) <-> P"
653   "?p5 : (P --> P) <-> True"
654   "?p6 : (P --> ~P) <-> ~P"
655   apply (tactic {* IntPr.fast_tac 1 *})+
656   done
658 lemma iff_rews:
659   "?p1 : (True <-> P) <-> P"
660   "?p2 : (P <-> True) <-> P"
661   "?p3 : (P <-> P) <-> True"
662   "?p4 : (False <-> P) <-> ~P"
663   "?p5 : (P <-> False) <-> ~P"
664   apply (tactic {* IntPr.fast_tac 1 *})+
665   done
667 lemma quant_rews:
668   "?p1 : (ALL x. P) <-> P"
669   "?p2 : (EX x. P) <-> P"
670   apply (tactic {* IntPr.fast_tac 1 *})+
671   done
673 (*These are NOT supplied by default!*)
674 lemma distrib_rews1:
675   "?p1 : ~(P|Q) <-> ~P & ~Q"
676   "?p2 : P & (Q | R) <-> P&Q | P&R"
677   "?p3 : (Q | R) & P <-> Q&P | R&P"
678   "?p4 : (P | Q --> R) <-> (P --> R) & (Q --> R)"
679   apply (tactic {* IntPr.fast_tac 1 *})+
680   done
682 lemma distrib_rews2:
683   "?p1 : ~(EX x. NORM(P(x))) <-> (ALL x. ~NORM(P(x)))"
684   "?p2 : ((EX x. NORM(P(x))) --> Q) <-> (ALL x. NORM(P(x)) --> Q)"
685   "?p3 : (EX x. NORM(P(x))) & NORM(Q) <-> (EX x. NORM(P(x)) & NORM(Q))"
686   "?p4 : NORM(Q) & (EX x. NORM(P(x))) <-> (EX x. NORM(Q) & NORM(P(x)))"
687   apply (tactic {* IntPr.fast_tac 1 *})+
688   done
690 lemmas distrib_rews = distrib_rews1 distrib_rews2
692 lemma P_Imp_P_iff_T: "p:P ==> ?p:(P <-> True)"
693   apply (tactic {* IntPr.fast_tac 1 *})
694   done
696 lemma not_P_imp_P_iff_F: "p:~P ==> ?p:(P <-> False)"
697   apply (tactic {* IntPr.fast_tac 1 *})
698   done
700 end