# Theory PresburgerEx

Up to index of Isabelle/HOL/ex

theory PresburgerEx
imports Main
begin

    (*  Title:      HOL/ex/PresburgerEx.thy
        ID:         $Id: PresburgerEx.thy,v 1.7 2005/09/14 20:08:09 wenzelm Exp $
        Author:     Amine Chaieb, TU Muenchen
    *)

    header {* Some examples for Presburger Arithmetic *}

    theory PresburgerEx imports Main begin

    theorem "(∀(y::int). 3 dvd y) ==> ∀(x::int). b < x --> a ≤ x"
      by presburger

    theorem "!! (y::int) (z::int) (n::int). 3 dvd z ==> 2 dvd (y::int) ==>
      (∃(x::int).  2*x =  y) & (∃(k::int). 3*k = z)"
      by presburger

    theorem "!! (y::int) (z::int) n. Suc(n::nat) < 6 ==>  3 dvd z ==>
      2 dvd (y::int) ==> (∃(x::int).  2*x =  y) & (∃(k::int). 3*k = z)"
      by presburger

    theorem "∀(x::nat). ∃(y::nat). (0::nat) ≤ 5 --> y = 5 + x "
      by presburger

    text{*Very slow: about 55 seconds on a 1.8GHz machine.*}
    theorem "∀(x::nat). ∃(y::nat). y = 5 + x | x div 6 + 1= 2"
      by presburger

    theorem "∃(x::int). 0 < x"
      by presburger

    theorem "∀(x::int) y. x < y --> 2 * x + 1 < 2 * y"
      by presburger

    theorem "∀(x::int) y. 2 * x + 1 ≠ 2 * y"
      by presburger

    theorem "∃(x::int) y. 0 < x  & 0 ≤ y  & 3 * x - 5 * y = 1"
      by presburger

    theorem "~ (∃(x::int) (y::int) (z::int). 4*x + (-6::int)*y = 1)"
      by presburger

    theorem "∀(x::int). b < x --> a ≤ x"
      apply (presburger (no_quantify))
      oops

    theorem "~ (∃(x::int). False)"
      by presburger

    theorem "∀(x::int). (a::int) < 3 * x --> b < 3 * x"
      apply (presburger (no_quantify))
      oops

    theorem "∀(x::int). (2 dvd x) --> (∃(y::int). x = 2*y)"
      by presburger

    theorem "∀(x::int). (2 dvd x) --> (∃(y::int). x = 2*y)"
      by presburger

    theorem "∀(x::int). (2 dvd x) = (∃(y::int). x = 2*y)"
      by presburger

    theorem "∀(x::int). ((2 dvd x) = (∀(y::int). x ≠ 2*y + 1))"
      by presburger

    theorem "~ (∀(x::int).
                ((2 dvd x) = (∀(y::int). x ≠ 2*y+1) |
                 (∃(q::int) (u::int) i. 3*i + 2*q - u < 17)
                 --> 0 < x | ((~ 3 dvd x) &(x + 8 = 0))))"
      by presburger

    theorem "~ (∀(i::int). 4 ≤ i --> (∃x y. 0 ≤ x & 0 ≤ y & 3 * x + 5 * y = i))"
      by presburger

    theorem "∀(i::int). 8 ≤ i --> (∃x y. 0 ≤ x & 0 ≤ y & 3 * x + 5 * y = i)"
      by presburger

    theorem "∃(j::int). ∀i. j ≤ i --> (∃x y. 0 ≤ x & 0 ≤ y & 3 * x + 5 * y = i)"
      by presburger

    theorem "~ (∀j (i::int). j ≤ i --> (∃x y. 0 ≤ x & 0 ≤ y & 3 * x + 5 * y = i))"
      by presburger

    text{*Very slow: about 80 seconds on a 1.8GHz machine.*}
    theorem "(∃m::nat. n = 2 * m) --> (n + 1) div 2 = n div 2"
      by presburger

    theorem "(∃m::int. n = 2 * m) --> (n + 1) div 2 = n div 2"
      by presburger

    end

theorem

      ∀y. 3 dvd y ==> ∀x>b. a ≤ x

theorem

      [| 3 dvd z; 2 dvd y |] ==> (∃x. 2 * x = y) ∧ (∃k. 3 * k = z)

theorem

      [| Suc n < 6; 3 dvd z; 2 dvd y |] ==> (∃x. 2 * x = y) ∧ (∃k. 3 * k = z)

theorem

      ∀x. ∃y. 0 ≤ 5 --> y = 5 + x

theorem

      ∀x. ∃y. y = 5 + x ∨ x div 6 + 1 = 2

theorem

      ∃x. 0 < x

theorem

      ∀x y. x < y --> 2 * x + 1 < 2 * y

theorem

      ∀x y. 2 * x + 1 ≠ 2 * y

theorem

      ∃x y. 0 < x ∧ 0 ≤ y ∧ 3 * x - 5 * y = 1

theorem

      ¬ (∃x y z. 4 * x + -6 * y = 1)

theorem

      ¬ (∃x. False)

theorem

      ∀x. 2 dvd x --> (∃y. x = 2 * y)

theorem

      ∀x. 2 dvd x --> (∃y. x = 2 * y)

theorem

      ∀x. (2 dvd x) = (∃y. x = 2 * y)

theorem

      ∀x. (2 dvd x) = (∀y. x ≠ 2 * y + 1)

theorem

      ¬ (∀x. (2 dvd x) = (∀y. x ≠ 2 * y + 1) ∨ (∃q u i. 3 * i + 2 * q - u < 17) -->
             0 < x ∨ ¬ 3 dvd x ∧ x + 8 = 0)

theorem

      ¬ (∀i≥4. ∃x y. 0 ≤ x ∧ 0 ≤ y ∧ 3 * x + 5 * y = i)

theorem

      ∀i≥8. ∃x y. 0 ≤ x ∧ 0 ≤ y ∧ 3 * x + 5 * y = i

theorem

      ∃j. ∀i. j ≤ i --> (∃x y. 0 ≤ x ∧ 0 ≤ y ∧ 3 * x + 5 * y = i)

theorem

      ¬ (∀j i. j ≤ i --> (∃x y. 0 ≤ x ∧ 0 ≤ y ∧ 3 * x + 5 * y = i))

theorem

      (∃m. n = 2 * m) --> (n + 1) div 2 = n div 2

theorem

      (∃m. n = 2 * m) --> (n + 1) div 2 = n div 2