equal
deleted
inserted
replaced
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)" |