487 by (unfold if_def) blast |
487 by (unfold if_def) blast |
488 |
488 |
489 lemma split_if: "P (if Q then x else y) = ((Q --> P(x)) & (~Q --> P(y)))" |
489 lemma split_if: "P (if Q then x else y) = ((Q --> P(x)) & (~Q --> P(y)))" |
490 apply (rule case_split [of Q]) |
490 apply (rule case_split [of Q]) |
491 apply (subst if_P) |
491 apply (subst if_P) |
492 prefer 3 apply (subst if_not_P) |
492 prefer 3 apply (subst if_not_P, blast+) |
493 apply blast+ |
|
494 done |
493 done |
495 |
494 |
496 lemma split_if_asm: "P (if Q then x else y) = (~((Q & ~P x) | (~Q & ~P y)))" |
495 lemma split_if_asm: "P (if Q then x else y) = (~((Q & ~P x) | (~Q & ~P y)))" |
497 apply (subst split_if) |
496 by (subst split_if, blast) |
498 apply blast |
|
499 done |
|
500 |
497 |
501 lemmas if_splits = split_if split_if_asm |
498 lemmas if_splits = split_if split_if_asm |
502 |
499 |
503 lemma if_def2: "(if Q then x else y) = ((Q --> x) & (~ Q --> y))" |
500 lemma if_def2: "(if Q then x else y) = ((Q --> x) & (~ Q --> y))" |
504 by (rule split_if) |
501 by (rule split_if) |
505 |
502 |
506 lemma if_cancel: "(if c then x else x) = x" |
503 lemma if_cancel: "(if c then x else x) = x" |
507 apply (subst split_if) |
504 by (subst split_if, blast) |
508 apply blast |
|
509 done |
|
510 |
505 |
511 lemma if_eq_cancel: "(if x = y then y else x) = x" |
506 lemma if_eq_cancel: "(if x = y then y else x) = x" |
512 apply (subst split_if) |
507 by (subst split_if, blast) |
513 apply blast |
|
514 done |
|
515 |
508 |
516 lemma if_bool_eq_conj: "(if P then Q else R) = ((P-->Q) & (~P-->R))" |
509 lemma if_bool_eq_conj: "(if P then Q else R) = ((P-->Q) & (~P-->R))" |
517 -- {* This form is useful for expanding @{text if}s on the RIGHT of the @{text "==>"} symbol. *} |
510 -- {* This form is useful for expanding @{text if}s on the RIGHT of the @{text "==>"} symbol. *} |
518 by (rule split_if) |
511 by (rule split_if) |
519 |
512 |
520 lemma if_bool_eq_disj: "(if P then Q else R) = ((P&Q) | (~P&R))" |
513 lemma if_bool_eq_disj: "(if P then Q else R) = ((P&Q) | (~P&R))" |
521 -- {* And this form is useful for expanding @{text if}s on the LEFT. *} |
514 -- {* And this form is useful for expanding @{text if}s on the LEFT. *} |
522 apply (subst split_if) |
515 apply (subst split_if, blast) |
523 apply blast |
|
524 done |
516 done |
525 |
517 |
526 lemma Eq_TrueI: "P ==> P == True" by (unfold atomize_eq) rules |
518 lemma Eq_TrueI: "P ==> P == True" by (unfold atomize_eq) rules |
527 lemma Eq_FalseI: "~P ==> P == False" by (unfold atomize_eq) rules |
519 lemma Eq_FalseI: "~P ==> P == False" by (unfold atomize_eq) rules |
528 |
520 |
550 apply (rule ccontr) |
542 apply (rule ccontr) |
551 apply (erule_tac x = "%z. if z = x then y else f z" in allE) |
543 apply (erule_tac x = "%z. if z = x then y else f z" in allE) |
552 apply (erule impE) |
544 apply (erule impE) |
553 apply (rule allI) |
545 apply (rule allI) |
554 apply (rule_tac P = "xa = x" in case_split_thm) |
546 apply (rule_tac P = "xa = x" in case_split_thm) |
555 apply (drule_tac [3] x = x in fun_cong) |
547 apply (drule_tac [3] x = x in fun_cong, simp_all) |
556 apply simp_all |
|
557 done |
548 done |
558 |
549 |
559 text{*Needs only HOL-lemmas:*} |
550 text{*Needs only HOL-lemmas:*} |
560 lemma mk_left_commute: |
551 lemma mk_left_commute: |
561 assumes a: "\<And>x y z. f (f x y) z = f x (f y z)" and |
552 assumes a: "\<And>x y z. f (f x y) z = f x (f y z)" and |
704 lemma order_less_irrefl [iff]: "~ x < (x::'a::order)" |
695 lemma order_less_irrefl [iff]: "~ x < (x::'a::order)" |
705 by (simp add: order_less_le) |
696 by (simp add: order_less_le) |
706 |
697 |
707 lemma order_le_less: "((x::'a::order) <= y) = (x < y | x = y)" |
698 lemma order_le_less: "((x::'a::order) <= y) = (x < y | x = y)" |
708 -- {* NOT suitable for iff, since it can cause PROOF FAILED. *} |
699 -- {* NOT suitable for iff, since it can cause PROOF FAILED. *} |
709 apply (simp add: order_less_le) |
700 apply (simp add: order_less_le, blast) |
710 apply blast |
|
711 done |
701 done |
712 |
702 |
713 lemmas order_le_imp_less_or_eq = order_le_less [THEN iffD1, standard] |
703 lemmas order_le_imp_less_or_eq = order_le_less [THEN iffD1, standard] |
714 |
704 |
715 lemma order_less_imp_le: "!!x::'a::order. x < y ==> x <= y" |
705 lemma order_less_imp_le: "!!x::'a::order. x < y ==> x <= y" |
721 lemma order_less_not_sym: "(x::'a::order) < y ==> ~ (y < x)" |
711 lemma order_less_not_sym: "(x::'a::order) < y ==> ~ (y < x)" |
722 by (simp add: order_less_le order_antisym) |
712 by (simp add: order_less_le order_antisym) |
723 |
713 |
724 lemma order_less_asym: "x < (y::'a::order) ==> (~P ==> y < x) ==> P" |
714 lemma order_less_asym: "x < (y::'a::order) ==> (~P ==> y < x) ==> P" |
725 apply (drule order_less_not_sym) |
715 apply (drule order_less_not_sym) |
726 apply (erule contrapos_np) |
716 apply (erule contrapos_np, simp) |
727 apply simp |
|
728 done |
717 done |
729 |
718 |
730 |
719 |
731 text {* Transitivity. *} |
720 text {* Transitivity. *} |
732 |
721 |
804 axclass linorder < order |
793 axclass linorder < order |
805 linorder_linear: "x <= y | y <= x" |
794 linorder_linear: "x <= y | y <= x" |
806 |
795 |
807 lemma linorder_less_linear: "!!x::'a::linorder. x<y | x=y | y<x" |
796 lemma linorder_less_linear: "!!x::'a::linorder. x<y | x=y | y<x" |
808 apply (simp add: order_less_le) |
797 apply (simp add: order_less_le) |
809 apply (insert linorder_linear) |
798 apply (insert linorder_linear, blast) |
810 apply blast |
|
811 done |
799 done |
812 |
800 |
813 lemma linorder_cases [case_names less equal greater]: |
801 lemma linorder_cases [case_names less equal greater]: |
814 "((x::'a::linorder) < y ==> P) ==> (x = y ==> P) ==> (y < x ==> P) ==> P" |
802 "((x::'a::linorder) < y ==> P) ==> (x = y ==> P) ==> (y < x ==> P) ==> P" |
815 apply (insert linorder_less_linear) |
803 apply (insert linorder_less_linear, blast) |
816 apply blast |
|
817 done |
804 done |
818 |
805 |
819 lemma linorder_not_less: "!!x::'a::linorder. (~ x < y) = (y <= x)" |
806 lemma linorder_not_less: "!!x::'a::linorder. (~ x < y) = (y <= x)" |
820 apply (simp add: order_less_le) |
807 apply (simp add: order_less_le) |
821 apply (insert linorder_linear) |
808 apply (insert linorder_linear) |
827 apply (insert linorder_linear) |
814 apply (insert linorder_linear) |
828 apply (blast intro: order_antisym) |
815 apply (blast intro: order_antisym) |
829 done |
816 done |
830 |
817 |
831 lemma linorder_neq_iff: "!!x::'a::linorder. (x ~= y) = (x<y | y<x)" |
818 lemma linorder_neq_iff: "!!x::'a::linorder. (x ~= y) = (x<y | y<x)" |
832 apply (cut_tac x = x and y = y in linorder_less_linear) |
819 by (cut_tac x = x and y = y in linorder_less_linear, auto) |
833 apply auto |
|
834 done |
|
835 |
820 |
836 lemma linorder_neqE: "x ~= (y::'a::linorder) ==> (x < y ==> R) ==> (y < x ==> R) ==> R" |
821 lemma linorder_neqE: "x ~= (y::'a::linorder) ==> (x < y ==> R) ==> (y < x ==> R) ==> R" |
837 apply (simp add: linorder_neq_iff) |
822 by (simp add: linorder_neq_iff, blast) |
838 apply blast |
|
839 done |
|
840 |
823 |
841 |
824 |
842 subsubsection "Min and max on (linear) orders" |
825 subsubsection "Min and max on (linear) orders" |
843 |
826 |
844 lemma min_same [simp]: "min (x::'a::order) x = x" |
827 lemma min_same [simp]: "min (x::'a::order) x = x" |