42 nitpick [dont_specialize, show_consts, expect = genuine] |
42 nitpick [dont_specialize, show_consts, expect = genuine] |
43 oops |
43 oops |
44 |
44 |
45 lemma "\<exists>!x. P x \<Longrightarrow> P (THE y. P y)" |
45 lemma "\<exists>!x. P x \<Longrightarrow> P (THE y. P y)" |
46 nitpick [expect = none] |
46 nitpick [expect = none] |
47 nitpick [card 'a = 1\<midarrow>50, expect = none] |
47 nitpick [card 'a = 1\<emdash>50, expect = none] |
48 (* sledgehammer *) |
48 (* sledgehammer *) |
49 apply (metis the_equality) |
49 apply (metis the_equality) |
50 done |
50 done |
51 |
51 |
52 subsection {* 3.4. Skolemization *} |
52 subsection {* 3.4. Skolemization *} |
225 nitpick [verbose, expect = genuine] |
225 nitpick [verbose, expect = genuine] |
226 oops |
226 oops |
227 |
227 |
228 lemma "\<lbrakk>xs = LCons a xs; ys = LCons a ys\<rbrakk> \<Longrightarrow> xs = ys" |
228 lemma "\<lbrakk>xs = LCons a xs; ys = LCons a ys\<rbrakk> \<Longrightarrow> xs = ys" |
229 nitpick [bisim_depth = -1, show_datatypes, expect = quasi_genuine] |
229 nitpick [bisim_depth = -1, show_datatypes, expect = quasi_genuine] |
230 nitpick [card = 1\<midarrow>5, expect = none] |
230 nitpick [card = 1\<emdash>5, expect = none] |
231 sorry |
231 sorry |
232 |
232 |
233 subsection {* 3.10. Boxing *} |
233 subsection {* 3.10. Boxing *} |
234 |
234 |
235 datatype tm = Var nat | Lam tm | App tm tm |
235 datatype tm = Var nat | Lam tm | App tm tm |
261 "subst\<^isub>2 \<sigma> (Lam t) = |
261 "subst\<^isub>2 \<sigma> (Lam t) = |
262 Lam (subst\<^isub>2 (\<lambda>n. case n of 0 \<Rightarrow> Var 0 | Suc m \<Rightarrow> lift (\<sigma> m) 0) t)" | |
262 Lam (subst\<^isub>2 (\<lambda>n. case n of 0 \<Rightarrow> Var 0 | Suc m \<Rightarrow> lift (\<sigma> m) 0) t)" | |
263 "subst\<^isub>2 \<sigma> (App t u) = App (subst\<^isub>2 \<sigma> t) (subst\<^isub>2 \<sigma> u)" |
263 "subst\<^isub>2 \<sigma> (App t u) = App (subst\<^isub>2 \<sigma> t) (subst\<^isub>2 \<sigma> u)" |
264 |
264 |
265 lemma "\<not> loose t 0 \<Longrightarrow> subst\<^isub>2 \<sigma> t = t" |
265 lemma "\<not> loose t 0 \<Longrightarrow> subst\<^isub>2 \<sigma> t = t" |
266 nitpick [card = 1\<midarrow>5, expect = none] |
266 nitpick [card = 1\<emdash>5, expect = none] |
267 sorry |
267 sorry |
268 |
268 |
269 subsection {* 3.11. Scope Monotonicity *} |
269 subsection {* 3.11. Scope Monotonicity *} |
270 |
270 |
271 lemma "length xs = length ys \<Longrightarrow> rev (zip xs ys) = zip xs (rev ys)" |
271 lemma "length xs = length ys \<Longrightarrow> rev (zip xs ys) = zip xs (rev ys)" |
286 |
286 |
287 lemma "n \<in> reach \<Longrightarrow> 2 dvd n" |
287 lemma "n \<in> reach \<Longrightarrow> 2 dvd n" |
288 (* nitpick *) |
288 (* nitpick *) |
289 apply (induct set: reach) |
289 apply (induct set: reach) |
290 apply auto |
290 apply auto |
291 nitpick [card = 1\<midarrow>4, bits = 1\<midarrow>4, expect = none] |
291 nitpick [card = 1\<emdash>4, bits = 1\<emdash>4, expect = none] |
292 apply (thin_tac "n \<in> reach") |
292 apply (thin_tac "n \<in> reach") |
293 nitpick [expect = genuine] |
293 nitpick [expect = genuine] |
294 oops |
294 oops |
295 |
295 |
296 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<noteq> 0" |
296 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<noteq> 0" |
297 (* nitpick *) |
297 (* nitpick *) |
298 apply (induct set: reach) |
298 apply (induct set: reach) |
299 apply auto |
299 apply auto |
300 nitpick [card = 1\<midarrow>4, bits = 1\<midarrow>4, expect = none] |
300 nitpick [card = 1\<emdash>4, bits = 1\<emdash>4, expect = none] |
301 apply (thin_tac "n \<in> reach") |
301 apply (thin_tac "n \<in> reach") |
302 nitpick [expect = genuine] |
302 nitpick [expect = genuine] |
303 oops |
303 oops |
304 |
304 |
305 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<ge> 4" |
305 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<ge> 4" |
382 | "w \<in> S\<^isub>3 \<Longrightarrow> b # w \<in> B\<^isub>3" |
382 | "w \<in> S\<^isub>3 \<Longrightarrow> b # w \<in> B\<^isub>3" |
383 | "\<lbrakk>v \<in> B\<^isub>3; w \<in> B\<^isub>3\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>3" |
383 | "\<lbrakk>v \<in> B\<^isub>3; w \<in> B\<^isub>3\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>3" |
384 |
384 |
385 theorem S\<^isub>3_sound: |
385 theorem S\<^isub>3_sound: |
386 "w \<in> S\<^isub>3 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]" |
386 "w \<in> S\<^isub>3 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]" |
387 nitpick [card = 1\<midarrow>5, expect = none] |
387 nitpick [card = 1\<emdash>5, expect = none] |
388 sorry |
388 sorry |
389 |
389 |
390 theorem S\<^isub>3_complete: |
390 theorem S\<^isub>3_complete: |
391 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>3" |
391 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>3" |
392 nitpick [expect = genuine] |
392 nitpick [expect = genuine] |
401 | "w \<in> S\<^isub>4 \<Longrightarrow> b # w \<in> B\<^isub>4" |
401 | "w \<in> S\<^isub>4 \<Longrightarrow> b # w \<in> B\<^isub>4" |
402 | "\<lbrakk>v \<in> B\<^isub>4; w \<in> B\<^isub>4\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>4" |
402 | "\<lbrakk>v \<in> B\<^isub>4; w \<in> B\<^isub>4\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>4" |
403 |
403 |
404 theorem S\<^isub>4_sound: |
404 theorem S\<^isub>4_sound: |
405 "w \<in> S\<^isub>4 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]" |
405 "w \<in> S\<^isub>4 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]" |
406 nitpick [card = 1\<midarrow>5, expect = none] |
406 nitpick [card = 1\<emdash>5, expect = none] |
407 sorry |
407 sorry |
408 |
408 |
409 theorem S\<^isub>4_complete: |
409 theorem S\<^isub>4_complete: |
410 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>4" |
410 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>4" |
411 nitpick [card = 1\<midarrow>5, expect = none] |
411 nitpick [card = 1\<emdash>5, expect = none] |
412 sorry |
412 sorry |
413 |
413 |
414 theorem S\<^isub>4_A\<^isub>4_B\<^isub>4_sound_and_complete: |
414 theorem S\<^isub>4_A\<^isub>4_B\<^isub>4_sound_and_complete: |
415 "w \<in> S\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]" |
415 "w \<in> S\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]" |
416 "w \<in> A\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] + 1" |
416 "w \<in> A\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] + 1" |
417 "w \<in> B\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = b] = length [x \<leftarrow> w. x = a] + 1" |
417 "w \<in> B\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = b] = length [x \<leftarrow> w. x = a] + 1" |
418 nitpick [card = 1\<midarrow>5, expect = none] |
418 nitpick [card = 1\<emdash>5, expect = none] |
419 sorry |
419 sorry |
420 |
420 |
421 subsection {* 4.2. AA Trees *} |
421 subsection {* 4.2. AA Trees *} |
422 |
422 |
423 datatype 'a aa_tree = \<Lambda> | N "'a\<Colon>linorder" nat "'a aa_tree" "'a aa_tree" |
423 datatype 'a aa_tree = \<Lambda> | N "'a\<Colon>linorder" nat "'a aa_tree" "'a aa_tree" |
467 N x k t u)" |
467 N x k t u)" |
468 |
468 |
469 theorem dataset_skew_split: |
469 theorem dataset_skew_split: |
470 "dataset (skew t) = dataset t" |
470 "dataset (skew t) = dataset t" |
471 "dataset (split t) = dataset t" |
471 "dataset (split t) = dataset t" |
472 nitpick [card = 1\<midarrow>5, expect = none] |
472 nitpick [card = 1\<emdash>5, expect = none] |
473 sorry |
473 sorry |
474 |
474 |
475 theorem wf_skew_split: |
475 theorem wf_skew_split: |
476 "wf t \<Longrightarrow> skew t = t" |
476 "wf t \<Longrightarrow> skew t = t" |
477 "wf t \<Longrightarrow> split t = t" |
477 "wf t \<Longrightarrow> split t = t" |
478 nitpick [card = 1\<midarrow>5, expect = none] |
478 nitpick [card = 1\<emdash>5, expect = none] |
479 sorry |
479 sorry |
480 |
480 |
481 primrec insort\<^isub>1 where |
481 primrec insort\<^isub>1 where |
482 "insort\<^isub>1 \<Lambda> x = N x 1 \<Lambda> \<Lambda>" | |
482 "insort\<^isub>1 \<Lambda> x = N x 1 \<Lambda> \<Lambda>" | |
483 "insort\<^isub>1 (N y k t u) x = |
483 "insort\<^isub>1 (N y k t u) x = |
497 "insort\<^isub>2 (N y k t u) x = |
497 "insort\<^isub>2 (N y k t u) x = |
498 (split \<circ> skew) (N y k (if x < y then insort\<^isub>2 t x else t) |
498 (split \<circ> skew) (N y k (if x < y then insort\<^isub>2 t x else t) |
499 (if x > y then insort\<^isub>2 u x else u))" |
499 (if x > y then insort\<^isub>2 u x else u))" |
500 |
500 |
501 theorem wf_insort\<^isub>2: "wf t \<Longrightarrow> wf (insort\<^isub>2 t x)" |
501 theorem wf_insort\<^isub>2: "wf t \<Longrightarrow> wf (insort\<^isub>2 t x)" |
502 nitpick [card = 1\<midarrow>5, expect = none] |
502 nitpick [card = 1\<emdash>5, expect = none] |
503 sorry |
503 sorry |
504 |
504 |
505 theorem dataset_insort\<^isub>2: "dataset (insort\<^isub>2 t x) = {x} \<union> dataset t" |
505 theorem dataset_insort\<^isub>2: "dataset (insort\<^isub>2 t x) = {x} \<union> dataset t" |
506 nitpick [card = 1\<midarrow>5, expect = none] |
506 nitpick [card = 1\<emdash>5, expect = none] |
507 sorry |
507 sorry |
508 |
508 |
509 end |
509 end |