src/FOLP/FOLP.thy
changeset 36319 8feb2c4bef1a
parent 35762 af3ff2ba4c54
child 41779 a68f503805ed
equal deleted inserted replaced
36318:3567d0571932 36319:8feb2c4bef1a
    17   classical: "(!!x. x:~P ==> f(x):P) ==> cla(f):P"
    17   classical: "(!!x. x:~P ==> f(x):P) ==> cla(f):P"
    18 
    18 
    19 
    19 
    20 (*** Classical introduction rules for | and EX ***)
    20 (*** Classical introduction rules for | and EX ***)
    21 
    21 
    22 lemma disjCI:
    22 schematic_lemma disjCI:
    23   assumes "!!x. x:~Q ==> f(x):P"
    23   assumes "!!x. x:~Q ==> f(x):P"
    24   shows "?p : P|Q"
    24   shows "?p : P|Q"
    25   apply (rule classical)
    25   apply (rule classical)
    26   apply (assumption | rule assms disjI1 notI)+
    26   apply (assumption | rule assms disjI1 notI)+
    27   apply (assumption | rule disjI2 notE)+
    27   apply (assumption | rule disjI2 notE)+
    28   done
    28   done
    29 
    29 
    30 (*introduction rule involving only EX*)
    30 (*introduction rule involving only EX*)
    31 lemma ex_classical:
    31 schematic_lemma ex_classical:
    32   assumes "!!u. u:~(EX x. P(x)) ==> f(u):P(a)"
    32   assumes "!!u. u:~(EX x. P(x)) ==> f(u):P(a)"
    33   shows "?p : EX x. P(x)"
    33   shows "?p : EX x. P(x)"
    34   apply (rule classical)
    34   apply (rule classical)
    35   apply (rule exI, rule assms, assumption)
    35   apply (rule exI, rule assms, assumption)
    36   done
    36   done
    37 
    37 
    38 (*version of above, simplifying ~EX to ALL~ *)
    38 (*version of above, simplifying ~EX to ALL~ *)
    39 lemma exCI:
    39 schematic_lemma exCI:
    40   assumes "!!u. u:ALL x. ~P(x) ==> f(u):P(a)"
    40   assumes "!!u. u:ALL x. ~P(x) ==> f(u):P(a)"
    41   shows "?p : EX x. P(x)"
    41   shows "?p : EX x. P(x)"
    42   apply (rule ex_classical)
    42   apply (rule ex_classical)
    43   apply (rule notI [THEN allI, THEN assms])
    43   apply (rule notI [THEN allI, THEN assms])
    44   apply (erule notE)
    44   apply (erule notE)
    45   apply (erule exI)
    45   apply (erule exI)
    46   done
    46   done
    47 
    47 
    48 lemma excluded_middle: "?p : ~P | P"
    48 schematic_lemma excluded_middle: "?p : ~P | P"
    49   apply (rule disjCI)
    49   apply (rule disjCI)
    50   apply assumption
    50   apply assumption
    51   done
    51   done
    52 
    52 
    53 
    53 
    54 (*** Special elimination rules *)
    54 (*** Special elimination rules *)
    55 
    55 
    56 (*Classical implies (-->) elimination. *)
    56 (*Classical implies (-->) elimination. *)
    57 lemma impCE:
    57 schematic_lemma impCE:
    58   assumes major: "p:P-->Q"
    58   assumes major: "p:P-->Q"
    59     and r1: "!!x. x:~P ==> f(x):R"
    59     and r1: "!!x. x:~P ==> f(x):R"
    60     and r2: "!!y. y:Q ==> g(y):R"
    60     and r2: "!!y. y:Q ==> g(y):R"
    61   shows "?p : R"
    61   shows "?p : R"
    62   apply (rule excluded_middle [THEN disjE])
    62   apply (rule excluded_middle [THEN disjE])
    63    apply (tactic {* DEPTH_SOLVE (atac 1 ORELSE
    63    apply (tactic {* DEPTH_SOLVE (atac 1 ORELSE
    64        resolve_tac [@{thm r1}, @{thm r2}, @{thm major} RS @{thm mp}] 1) *})
    64        resolve_tac [@{thm r1}, @{thm r2}, @{thm major} RS @{thm mp}] 1) *})
    65   done
    65   done
    66 
    66 
    67 (*Double negation law*)
    67 (*Double negation law*)
    68 lemma notnotD: "p:~~P ==> ?p : P"
    68 schematic_lemma notnotD: "p:~~P ==> ?p : P"
    69   apply (rule classical)
    69   apply (rule classical)
    70   apply (erule notE)
    70   apply (erule notE)
    71   apply assumption
    71   apply assumption
    72   done
    72   done
    73 
    73 
    74 
    74 
    75 (*** Tactics for implication and contradiction ***)
    75 (*** Tactics for implication and contradiction ***)
    76 
    76 
    77 (*Classical <-> elimination.  Proof substitutes P=Q in
    77 (*Classical <-> elimination.  Proof substitutes P=Q in
    78     ~P ==> ~Q    and    P ==> Q  *)
    78     ~P ==> ~Q    and    P ==> Q  *)
    79 lemma iffCE:
    79 schematic_lemma iffCE:
    80   assumes major: "p:P<->Q"
    80   assumes major: "p:P<->Q"
    81     and r1: "!!x y.[| x:P; y:Q |] ==> f(x,y):R"
    81     and r1: "!!x y.[| x:P; y:Q |] ==> f(x,y):R"
    82     and r2: "!!x y.[| x:~P; y:~Q |] ==> g(x,y):R"
    82     and r2: "!!x y.[| x:~P; y:~Q |] ==> g(x,y):R"
    83   shows "?p : R"
    83   shows "?p : R"
    84   apply (insert major)
    84   apply (insert major)
    89       resolve_tac [@{thm r1}, @{thm r2}] 1) *})+
    89       resolve_tac [@{thm r1}, @{thm r2}] 1) *})+
    90   done
    90   done
    91 
    91 
    92 
    92 
    93 (*Should be used as swap since ~P becomes redundant*)
    93 (*Should be used as swap since ~P becomes redundant*)
    94 lemma swap:
    94 schematic_lemma swap:
    95   assumes major: "p:~P"
    95   assumes major: "p:~P"
    96     and r: "!!x. x:~Q ==> f(x):P"
    96     and r: "!!x. x:~Q ==> f(x):P"
    97   shows "?p : Q"
    97   shows "?p : Q"
    98   apply (rule classical)
    98   apply (rule classical)
    99   apply (rule major [THEN notE])
    99   apply (rule major [THEN notE])
   134 val FOLP_dup_cs =
   134 val FOLP_dup_cs =
   135   prop_cs addSIs [@{thm allI}] addIs [@{thm exCI}, @{thm ex1I}]
   135   prop_cs addSIs [@{thm allI}] addIs [@{thm exCI}, @{thm ex1I}]
   136     addSEs [@{thm exE}, @{thm ex1E}] addEs [@{thm all_dupE}];
   136     addSEs [@{thm exE}, @{thm ex1E}] addEs [@{thm all_dupE}];
   137 *}
   137 *}
   138 
   138 
   139 lemma cla_rews:
   139 schematic_lemma cla_rews:
   140   "?p1 : P | ~P"
   140   "?p1 : P | ~P"
   141   "?p2 : ~P | P"
   141   "?p2 : ~P | P"
   142   "?p3 : ~ ~ P <-> P"
   142   "?p3 : ~ ~ P <-> P"
   143   "?p4 : (~P --> P) <-> P"
   143   "?p4 : (~P --> P) <-> P"
   144   apply (tactic {* ALLGOALS (Cla.fast_tac FOLP_cs) *})
   144   apply (tactic {* ALLGOALS (Cla.fast_tac FOLP_cs) *})