src/HOL/ex/Qsort.ML
changeset 4423 a129b817b58a
parent 4089 96fba19bcbe2
child 4686 74a12e86b20b
equal deleted inserted replaced
4422:21238c9d363e 4423:a129b817b58a
    13 A short proof of Konrad's wf_minimal in WF1.ML:
    13 A short proof of Konrad's wf_minimal in WF1.ML:
    14 
    14 
    15 val [p1] = goalw WF.thy [wf_def]
    15 val [p1] = goalw WF.thy [wf_def]
    16 "wf(R) ==> (!Q. (? x. Q x) --> (? min. Q min & (!b. (b,min):R --> (~ Q b))))";
    16 "wf(R) ==> (!Q. (? x. Q x) --> (? min. Q min & (!b. (b,min):R --> (~ Q b))))";
    17 by (rtac allI 1);
    17 by (rtac allI 1);
    18 by(cut_inst_tac[("x","%u.~Q u")](p1 RS spec) 1);
    18 by (cut_inst_tac[("x","%u.~Q u")](p1 RS spec) 1);
    19 by (fast_tac HOL_cs 1);
    19 by (fast_tac HOL_cs 1);
    20 val wf_minimal = result();
    20 val wf_minimal = result();
    21 
    21 
    22 *)
    22 *)
    23 
    23 
    28 by (res_inst_tac[("xs","xs"),("p","le")]Qsort.qsort_ind 1);
    28 by (res_inst_tac[("xs","xs"),("p","le")]Qsort.qsort_ind 1);
    29 by (ALLGOALS(asm_simp_tac (simpset() addsplits [expand_if])));
    29 by (ALLGOALS(asm_simp_tac (simpset() addsplits [expand_if])));
    30 qed "qsort_permutes";
    30 qed "qsort_permutes";
    31 
    31 
    32 goal Qsort.thy "set(qsort le xs) = set xs";
    32 goal Qsort.thy "set(qsort le xs) = set xs";
    33 by(simp_tac (simpset() addsimps [set_via_mset,qsort_permutes]) 1);
    33 by (simp_tac (simpset() addsimps [set_via_mset,qsort_permutes]) 1);
    34 qed "set_qsort";
    34 qed "set_qsort";
    35 Addsimps [set_qsort];
    35 Addsimps [set_qsort];
    36 
    36 
    37 goal List.thy
    37 goal List.thy
    38   "(!x:set[x:xs. P(x)].Q(x)) = (!x:set xs. P(x)-->Q(x))";
    38   "(!x:set[x:xs. P(x)].Q(x)) = (!x:set xs. P(x)-->Q(x))";