equal
deleted
inserted
replaced
24 -- {* here 'refute 3' would cause an exception, since we only have 2 subgoals *} |
24 -- {* here 'refute 3' would cause an exception, since we only have 2 subgoals *} |
25 refute [maxsize=5] -- {* we can override parameters ... *} |
25 refute [maxsize=5] -- {* we can override parameters ... *} |
26 refute [satsolver="dpll"] 2 -- {* ... and specify a subgoal at the same time *} |
26 refute [satsolver="dpll"] 2 -- {* ... and specify a subgoal at the same time *} |
27 oops |
27 oops |
28 |
28 |
29 refute_params |
29 refute_params [satsolver="dpll"] |
30 |
30 |
31 section {* Examples and Test Cases *} |
31 section {* Examples and Test Cases *} |
32 |
32 |
33 subsection {* Propositional logic *} |
33 subsection {* Propositional logic *} |
34 |
34 |
153 oops |
153 oops |
154 |
154 |
155 text {* A true statement (also testing names of free and bound variables being identical) *} |
155 text {* A true statement (also testing names of free and bound variables being identical) *} |
156 |
156 |
157 lemma "(\<forall>x y. P x y \<longrightarrow> P y x) \<longrightarrow> (\<forall>x. P x y) \<longrightarrow> P y x" |
157 lemma "(\<forall>x y. P x y \<longrightarrow> P y x) \<longrightarrow> (\<forall>x. P x y) \<longrightarrow> P y x" |
158 refute [maxsize=2] (* [maxsize=5] works well with ZChaff *) |
158 refute |
159 apply fast |
159 apply fast |
160 done |
160 done |
161 |
161 |
162 text {* "A type has at most 3 elements." *} |
162 text {* "A type has at most 3 elements." *} |
163 |
163 |
170 oops |
170 oops |
171 |
171 |
172 text {* "Every reflexive and symmetric relation is transitive." *} |
172 text {* "Every reflexive and symmetric relation is transitive." *} |
173 |
173 |
174 lemma "\<lbrakk> \<forall>x. P x x; \<forall>x y. P x y \<longrightarrow> P y x \<rbrakk> \<Longrightarrow> P x y \<longrightarrow> P y z \<longrightarrow> P x z" |
174 lemma "\<lbrakk> \<forall>x. P x x; \<forall>x y. P x y \<longrightarrow> P y x \<rbrakk> \<Longrightarrow> P x y \<longrightarrow> P y z \<longrightarrow> P x z" |
175 (* refute -- works well with ZChaff, but the internal solver is too slow *) |
175 refute |
176 oops |
176 oops |
177 |
177 |
178 text {* The "Drinker's theorem" ... *} |
178 text {* The "Drinker's theorem" ... *} |
179 |
179 |
180 lemma "\<exists>x. f x = g x \<longrightarrow> f = g" |
180 lemma "\<exists>x. f x = g x \<longrightarrow> f = g" |
181 refute [maxsize=4] (* [maxsize=6] works well with ZChaff *) |
181 refute |
182 apply (auto simp add: ext) |
182 apply (auto simp add: ext) |
183 done |
183 done |
184 |
184 |
185 text {* ... and an incorrect version of it *} |
185 text {* ... and an incorrect version of it *} |
186 |
186 |
260 |
260 |
261 lemma "(\<forall>x y. (P x y | R x y) \<longrightarrow> T x y) \<longrightarrow> trans T \<longrightarrow> (\<forall>Q. (\<forall>x y. (P x y | R x y) \<longrightarrow> Q x y) \<longrightarrow> trans Q \<longrightarrow> subset T Q) |
261 lemma "(\<forall>x y. (P x y | R x y) \<longrightarrow> T x y) \<longrightarrow> trans T \<longrightarrow> (\<forall>Q. (\<forall>x y. (P x y | R x y) \<longrightarrow> Q x y) \<longrightarrow> trans Q \<longrightarrow> subset T Q) |
262 \<longrightarrow> trans_closure TP P |
262 \<longrightarrow> trans_closure TP P |
263 \<longrightarrow> trans_closure TR R |
263 \<longrightarrow> trans_closure TR R |
264 \<longrightarrow> (T x y = (TP x y | TR x y))" |
264 \<longrightarrow> (T x y = (TP x y | TR x y))" |
265 (* refute -- works well with ZChaff, but the internal solver is too slow *) |
265 refute |
266 oops |
266 oops |
267 |
267 |
268 text {* "Every surjective function is invertible." *} |
268 text {* "Every surjective function is invertible." *} |
269 |
269 |
270 lemma "(\<forall>y. \<exists>x. y = f x) \<longrightarrow> (\<exists>g. \<forall>x. g (f x) = x)" |
270 lemma "(\<forall>y. \<exists>x. y = f x) \<longrightarrow> (\<exists>g. \<forall>x. g (f x) = x)" |
278 oops |
278 oops |
279 |
279 |
280 text {* Every point is a fixed point of some function. *} |
280 text {* Every point is a fixed point of some function. *} |
281 |
281 |
282 lemma "\<exists>f. f x = x" |
282 lemma "\<exists>f. f x = x" |
283 refute [maxsize=4] |
283 refute [maxsize=5] |
284 apply (rule_tac x="\<lambda>x. x" in exI) |
284 apply (rule_tac x="\<lambda>x. x" in exI) |
285 apply simp |
285 apply simp |
286 done |
286 done |
287 |
287 |
288 text {* Axiom of Choice: first an incorrect version ... *} |
288 text {* Axiom of Choice: first an incorrect version ... *} |
292 oops |
292 oops |
293 |
293 |
294 text {* ... and now two correct ones *} |
294 text {* ... and now two correct ones *} |
295 |
295 |
296 lemma "(\<forall>x. \<exists>y. P x y) \<longrightarrow> (\<exists>f. \<forall>x. P x (f x))" |
296 lemma "(\<forall>x. \<exists>y. P x y) \<longrightarrow> (\<exists>f. \<forall>x. P x (f x))" |
297 refute [maxsize=5] |
297 refute |
298 apply (simp add: choice) |
298 apply (simp add: choice) |
299 done |
299 done |
300 |
300 |
301 lemma "(\<forall>x. EX!y. P x y) \<longrightarrow> (EX!f. \<forall>x. P x (f x))" |
301 lemma "(\<forall>x. EX!y. P x y) \<longrightarrow> (EX!f. \<forall>x. P x (f x))" |
302 refute [maxsize=3] (* [maxsize=4] works well with ZChaff *) |
302 refute |
303 apply auto |
303 apply auto |
304 apply (simp add: ex1_implies_ex choice) |
304 apply (simp add: ex1_implies_ex choice) |
305 apply (fast intro: ext) |
305 apply (fast intro: ext) |
306 done |
306 done |
307 |
307 |
359 lemma "P (A::'a set set)" |
359 lemma "P (A::'a set set)" |
360 refute |
360 refute |
361 oops |
361 oops |
362 |
362 |
363 lemma "{x. P x} = {y. P y}" |
363 lemma "{x. P x} = {y. P y}" |
364 refute [maxsize=2] (* [maxsize=8] works well with ZChaff *) |
364 refute |
365 apply simp |
365 apply simp |
366 done |
366 done |
367 |
367 |
368 lemma "x : {x. P x}" |
368 lemma "x : {x. P x}" |
369 refute |
369 refute |
428 lemma "(THE x. x=y) = z" |
428 lemma "(THE x. x=y) = z" |
429 refute |
429 refute |
430 oops |
430 oops |
431 |
431 |
432 lemma "Ex P \<longrightarrow> P (The P)" |
432 lemma "Ex P \<longrightarrow> P (The P)" |
433 (* refute -- works well with ZChaff, but the internal solver is too slow *) |
433 refute |
434 oops |
434 oops |
435 |
435 |
436 subsection {* Eps *} |
436 subsection {* Eps *} |
437 |
437 |
438 lemma "Eps P" |
438 lemma "Eps P" |
450 lemma "(SOME x. x=y) = z" |
450 lemma "(SOME x. x=y) = z" |
451 refute |
451 refute |
452 oops |
452 oops |
453 |
453 |
454 lemma "Ex P \<longrightarrow> P (Eps P)" |
454 lemma "Ex P \<longrightarrow> P (Eps P)" |
455 refute [maxsize=2] (* [maxsize=3] works well with ZChaff *) |
455 refute [maxsize=3] |
456 apply (auto simp add: someI) |
456 apply (auto simp add: someI) |
457 done |
457 done |
458 |
458 |
459 subsection {* Inductive datatypes *} |
459 subsection {* Inductive datatypes *} |
460 |
460 |