src/HOL/HOL.thy
changeset 14208 144f45277d5a
parent 14201 7ad7ab89c402
child 14223 0ee05eef881b
equal deleted inserted replaced
14207:f20fbb141673 14208:144f45277d5a
   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"