src/Pure/Examples/First_Order_Logic.thy
changeset 80914 d97fdabd9e2b
parent 71924 e5df9c8d9d4b
equal deleted inserted replaced
80913:46f59511b7bb 80914:d97fdabd9e2b
    16 subsection \<open>Abstract syntax\<close>
    16 subsection \<open>Abstract syntax\<close>
    17 
    17 
    18 typedecl i
    18 typedecl i
    19 typedecl o
    19 typedecl o
    20 
    20 
    21 judgment Trueprop :: "o \<Rightarrow> prop"  ("_" 5)
    21 judgment Trueprop :: "o \<Rightarrow> prop"  (\<open>_\<close> 5)
    22 
    22 
    23 
    23 
    24 subsection \<open>Propositional logic\<close>
    24 subsection \<open>Propositional logic\<close>
    25 
    25 
    26 axiomatization false :: o  ("\<bottom>")
    26 axiomatization false :: o  (\<open>\<bottom>\<close>)
    27   where falseE [elim]: "\<bottom> \<Longrightarrow> A"
    27   where falseE [elim]: "\<bottom> \<Longrightarrow> A"
    28 
    28 
    29 
    29 
    30 axiomatization imp :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr "\<longrightarrow>" 25)
    30 axiomatization imp :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr \<open>\<longrightarrow>\<close> 25)
    31   where impI [intro]: "(A \<Longrightarrow> B) \<Longrightarrow> A \<longrightarrow> B"
    31   where impI [intro]: "(A \<Longrightarrow> B) \<Longrightarrow> A \<longrightarrow> B"
    32     and mp [dest]: "A \<longrightarrow> B \<Longrightarrow> A \<Longrightarrow> B"
    32     and mp [dest]: "A \<longrightarrow> B \<Longrightarrow> A \<Longrightarrow> B"
    33 
    33 
    34 
    34 
    35 axiomatization conj :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr "\<and>" 35)
    35 axiomatization conj :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr \<open>\<and>\<close> 35)
    36   where conjI [intro]: "A \<Longrightarrow> B \<Longrightarrow> A \<and> B"
    36   where conjI [intro]: "A \<Longrightarrow> B \<Longrightarrow> A \<and> B"
    37     and conjD1: "A \<and> B \<Longrightarrow> A"
    37     and conjD1: "A \<and> B \<Longrightarrow> A"
    38     and conjD2: "A \<and> B \<Longrightarrow> B"
    38     and conjD2: "A \<and> B \<Longrightarrow> B"
    39 
    39 
    40 theorem conjE [elim]:
    40 theorem conjE [elim]:
    46   from \<open>A \<and> B\<close> show B
    46   from \<open>A \<and> B\<close> show B
    47     by (rule conjD2)
    47     by (rule conjD2)
    48 qed
    48 qed
    49 
    49 
    50 
    50 
    51 axiomatization disj :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr "\<or>" 30)
    51 axiomatization disj :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr \<open>\<or>\<close> 30)
    52   where disjE [elim]: "A \<or> B \<Longrightarrow> (A \<Longrightarrow> C) \<Longrightarrow> (B \<Longrightarrow> C) \<Longrightarrow> C"
    52   where disjE [elim]: "A \<or> B \<Longrightarrow> (A \<Longrightarrow> C) \<Longrightarrow> (B \<Longrightarrow> C) \<Longrightarrow> C"
    53     and disjI1 [intro]: "A \<Longrightarrow> A \<or> B"
    53     and disjI1 [intro]: "A \<Longrightarrow> A \<or> B"
    54     and disjI2 [intro]: "B \<Longrightarrow> A \<or> B"
    54     and disjI2 [intro]: "B \<Longrightarrow> A \<or> B"
    55 
    55 
    56 
    56 
    57 definition true :: o  ("\<top>")
    57 definition true :: o  (\<open>\<top>\<close>)
    58   where "\<top> \<equiv> \<bottom> \<longrightarrow> \<bottom>"
    58   where "\<top> \<equiv> \<bottom> \<longrightarrow> \<bottom>"
    59 
    59 
    60 theorem trueI [intro]: \<top>
    60 theorem trueI [intro]: \<top>
    61   unfolding true_def ..
    61   unfolding true_def ..
    62 
    62 
    63 
    63 
    64 definition not :: "o \<Rightarrow> o"  ("\<not> _" [40] 40)
    64 definition not :: "o \<Rightarrow> o"  (\<open>\<not> _\<close> [40] 40)
    65   where "\<not> A \<equiv> A \<longrightarrow> \<bottom>"
    65   where "\<not> A \<equiv> A \<longrightarrow> \<bottom>"
    66 
    66 
    67 theorem notI [intro]: "(A \<Longrightarrow> \<bottom>) \<Longrightarrow> \<not> A"
    67 theorem notI [intro]: "(A \<Longrightarrow> \<bottom>) \<Longrightarrow> \<not> A"
    68   unfolding not_def ..
    68   unfolding not_def ..
    69 
    69 
    74   then have \<bottom> ..
    74   then have \<bottom> ..
    75   then show B ..
    75   then show B ..
    76 qed
    76 qed
    77 
    77 
    78 
    78 
    79 definition iff :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr "\<longleftrightarrow>" 25)
    79 definition iff :: "o \<Rightarrow> o \<Rightarrow> o"  (infixr \<open>\<longleftrightarrow>\<close> 25)
    80   where "A \<longleftrightarrow> B \<equiv> (A \<longrightarrow> B) \<and> (B \<longrightarrow> A)"
    80   where "A \<longleftrightarrow> B \<equiv> (A \<longrightarrow> B) \<and> (B \<longrightarrow> A)"
    81 
    81 
    82 theorem iffI [intro]:
    82 theorem iffI [intro]:
    83   assumes "A \<Longrightarrow> B"
    83   assumes "A \<Longrightarrow> B"
    84     and "B \<Longrightarrow> A"
    84     and "B \<Longrightarrow> A"
   110 qed
   110 qed
   111 
   111 
   112 
   112 
   113 subsection \<open>Equality\<close>
   113 subsection \<open>Equality\<close>
   114 
   114 
   115 axiomatization equal :: "i \<Rightarrow> i \<Rightarrow> o"  (infixl "=" 50)
   115 axiomatization equal :: "i \<Rightarrow> i \<Rightarrow> o"  (infixl \<open>=\<close> 50)
   116   where refl [intro]: "x = x"
   116   where refl [intro]: "x = x"
   117     and subst: "x = y \<Longrightarrow> P x \<Longrightarrow> P y"
   117     and subst: "x = y \<Longrightarrow> P x \<Longrightarrow> P y"
   118 
   118 
   119 theorem trans [trans]: "x = y \<Longrightarrow> y = z \<Longrightarrow> x = z"
   119 theorem trans [trans]: "x = y \<Longrightarrow> y = z \<Longrightarrow> x = z"
   120   by (rule subst)
   120   by (rule subst)
   127 qed
   127 qed
   128 
   128 
   129 
   129 
   130 subsection \<open>Quantifiers\<close>
   130 subsection \<open>Quantifiers\<close>
   131 
   131 
   132 axiomatization All :: "(i \<Rightarrow> o) \<Rightarrow> o"  (binder "\<forall>" 10)
   132 axiomatization All :: "(i \<Rightarrow> o) \<Rightarrow> o"  (binder \<open>\<forall>\<close> 10)
   133   where allI [intro]: "(\<And>x. P x) \<Longrightarrow> \<forall>x. P x"
   133   where allI [intro]: "(\<And>x. P x) \<Longrightarrow> \<forall>x. P x"
   134     and allD [dest]: "\<forall>x. P x \<Longrightarrow> P a"
   134     and allD [dest]: "\<forall>x. P x \<Longrightarrow> P a"
   135 
   135 
   136 axiomatization Ex :: "(i \<Rightarrow> o) \<Rightarrow> o"  (binder "\<exists>" 10)
   136 axiomatization Ex :: "(i \<Rightarrow> o) \<Rightarrow> o"  (binder \<open>\<exists>\<close> 10)
   137   where exI [intro]: "P a \<Longrightarrow> \<exists>x. P x"
   137   where exI [intro]: "P a \<Longrightarrow> \<exists>x. P x"
   138     and exE [elim]: "\<exists>x. P x \<Longrightarrow> (\<And>x. P x \<Longrightarrow> C) \<Longrightarrow> C"
   138     and exE [elim]: "\<exists>x. P x \<Longrightarrow> (\<And>x. P x \<Longrightarrow> C) \<Longrightarrow> C"
   139 
   139 
   140 
   140 
   141 lemma "(\<exists>x. P (f x)) \<longrightarrow> (\<exists>y. P y)"
   141 lemma "(\<exists>x. P (f x)) \<longrightarrow> (\<exists>y. P y)"