src/FOL/ex/Propositional_Cla.thy
author haftmann
Thu Nov 23 17:03:27 2017 +0000 (21 months ago)
changeset 67087 733017b19de9
parent 62020 5d208fd2507d
child 69590 e65314985426
permissions -rw-r--r--
generalized more lemmas
     1 (*  Title:      FOL/ex/Propositional_Cla.thy
     2     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     3     Copyright   1991  University of Cambridge
     4 *)
     5 
     6 section \<open>First-Order Logic: propositional examples (classical version)\<close>
     7 
     8 theory Propositional_Cla
     9 imports FOL
    10 begin
    11 
    12 text \<open>commutative laws of \<open>\<and>\<close> and \<open>\<or>\<close>\<close>
    13 
    14 lemma "P \<and> Q \<longrightarrow> Q \<and> P"
    15   by (tactic "IntPr.fast_tac @{context} 1")
    16 
    17 lemma "P \<or> Q \<longrightarrow> Q \<or> P"
    18   by fast
    19 
    20 
    21 text \<open>associative laws of \<open>\<and>\<close> and \<open>\<or>\<close>\<close>
    22 lemma "(P \<and> Q) \<and> R \<longrightarrow> P \<and> (Q \<and> R)"
    23   by fast
    24 
    25 lemma "(P \<or> Q) \<or> R \<longrightarrow>  P \<or> (Q \<or> R)"
    26   by fast
    27 
    28 
    29 text \<open>distributive laws of \<open>\<and>\<close> and \<open>\<or>\<close>\<close>
    30 lemma "(P \<and> Q) \<or> R \<longrightarrow> (P \<or> R) \<and> (Q \<or> R)"
    31   by fast
    32 
    33 lemma "(P \<or> R) \<and> (Q \<or> R) \<longrightarrow> (P \<and> Q) \<or> R"
    34   by fast
    35 
    36 lemma "(P \<or> Q) \<and> R \<longrightarrow> (P \<and> R) \<or> (Q \<and> R)"
    37   by fast
    38 
    39 lemma "(P \<and> R) \<or> (Q \<and> R) \<longrightarrow> (P \<or> Q) \<and> R"
    40   by fast
    41 
    42 
    43 text \<open>Laws involving implication\<close>
    44 
    45 lemma "(P \<longrightarrow> R) \<and> (Q \<longrightarrow> R) \<longleftrightarrow> (P \<or> Q \<longrightarrow> R)"
    46   by fast
    47 
    48 lemma "(P \<and> Q \<longrightarrow> R) \<longleftrightarrow> (P \<longrightarrow> (Q \<longrightarrow> R))"
    49   by fast
    50 
    51 lemma "((P \<longrightarrow> R) \<longrightarrow> R) \<longrightarrow> ((Q \<longrightarrow> R) \<longrightarrow> R) \<longrightarrow> (P \<and> Q \<longrightarrow> R) \<longrightarrow> R"
    52   by fast
    53 
    54 lemma "\<not> (P \<longrightarrow> R) \<longrightarrow> \<not> (Q \<longrightarrow> R) \<longrightarrow> \<not> (P \<and> Q \<longrightarrow> R)"
    55   by fast
    56 
    57 lemma "(P \<longrightarrow> Q \<and> R) \<longleftrightarrow> (P \<longrightarrow> Q) \<and> (P \<longrightarrow> R)"
    58   by fast
    59 
    60 
    61 text \<open>Propositions-as-types\<close>
    62 
    63 \<comment> \<open>The combinator K\<close>
    64 lemma "P \<longrightarrow> (Q \<longrightarrow> P)"
    65   by fast
    66 
    67 \<comment> \<open>The combinator S\<close>
    68 lemma "(P \<longrightarrow> Q \<longrightarrow> R) \<longrightarrow> (P \<longrightarrow> Q) \<longrightarrow> (P \<longrightarrow> R)"
    69   by fast
    70 
    71 
    72 \<comment> \<open>Converse is classical\<close>
    73 lemma "(P \<longrightarrow> Q) \<or> (P \<longrightarrow> R) \<longrightarrow> (P \<longrightarrow> Q \<or> R)"
    74   by fast
    75 
    76 lemma "(P \<longrightarrow> Q) \<longrightarrow> (\<not> Q \<longrightarrow> \<not> P)"
    77   by fast
    78 
    79 
    80 text \<open>Schwichtenberg's examples (via T. Nipkow)\<close>
    81 
    82 lemma stab_imp: "(((Q \<longrightarrow> R) \<longrightarrow> R) \<longrightarrow> Q) \<longrightarrow> (((P \<longrightarrow> Q) \<longrightarrow> R) \<longrightarrow> R) \<longrightarrow> P \<longrightarrow> Q"
    83   by fast
    84 
    85 lemma stab_to_peirce:
    86   "(((P \<longrightarrow> R) \<longrightarrow> R) \<longrightarrow> P) \<longrightarrow> (((Q \<longrightarrow> R) \<longrightarrow> R) \<longrightarrow> Q)
    87     \<longrightarrow> ((P \<longrightarrow> Q) \<longrightarrow> P) \<longrightarrow> P"
    88   by fast
    89 
    90 lemma peirce_imp1:
    91   "(((Q \<longrightarrow> R) \<longrightarrow> Q) \<longrightarrow> Q)
    92     \<longrightarrow> (((P \<longrightarrow> Q) \<longrightarrow> R) \<longrightarrow> P \<longrightarrow> Q) \<longrightarrow> P \<longrightarrow> Q"
    93   by fast
    94 
    95 lemma peirce_imp2: "(((P \<longrightarrow> R) \<longrightarrow> P) \<longrightarrow> P) \<longrightarrow> ((P \<longrightarrow> Q \<longrightarrow> R) \<longrightarrow> P) \<longrightarrow> P"
    96   by fast
    97 
    98 lemma mints: "((((P \<longrightarrow> Q) \<longrightarrow> P) \<longrightarrow> P) \<longrightarrow> Q) \<longrightarrow> Q"
    99   by fast
   100 
   101 lemma mints_solovev: "(P \<longrightarrow> (Q \<longrightarrow> R) \<longrightarrow> Q) \<longrightarrow> ((P \<longrightarrow> Q) \<longrightarrow> R) \<longrightarrow> R"
   102   by fast
   103 
   104 lemma tatsuta:
   105   "(((P7 \<longrightarrow> P1) \<longrightarrow> P10) \<longrightarrow> P4 \<longrightarrow> P5)
   106   \<longrightarrow> (((P8 \<longrightarrow> P2) \<longrightarrow> P9) \<longrightarrow> P3 \<longrightarrow> P10)
   107   \<longrightarrow> (P1 \<longrightarrow> P8) \<longrightarrow> P6 \<longrightarrow> P7
   108   \<longrightarrow> (((P3 \<longrightarrow> P2) \<longrightarrow> P9) \<longrightarrow> P4)
   109   \<longrightarrow> (P1 \<longrightarrow> P3) \<longrightarrow> (((P6 \<longrightarrow> P1) \<longrightarrow> P2) \<longrightarrow> P9) \<longrightarrow> P5"
   110   by fast
   111 
   112 lemma tatsuta1:
   113   "(((P8 \<longrightarrow> P2) \<longrightarrow> P9) \<longrightarrow> P3 \<longrightarrow> P10)
   114   \<longrightarrow> (((P3 \<longrightarrow> P2) \<longrightarrow> P9) \<longrightarrow> P4)
   115   \<longrightarrow> (((P6 \<longrightarrow> P1) \<longrightarrow> P2) \<longrightarrow> P9)
   116   \<longrightarrow> (((P7 \<longrightarrow> P1) \<longrightarrow> P10) \<longrightarrow> P4 \<longrightarrow> P5)
   117   \<longrightarrow> (P1 \<longrightarrow> P3) \<longrightarrow> (P1 \<longrightarrow> P8) \<longrightarrow> P6 \<longrightarrow> P7 \<longrightarrow> P5"
   118   by fast
   119 
   120 end