%------------------------------------------------------------------------------
% File     : SWW987_1 : TPTP v9.2.1. Released v9.1.0.
% Domain   : Software Verification
% Problem  : insertion-sort-1
% Version  : Especial.
% English  :

% Refs     : [Kot17] Kotelnikov (2017), Email to Geoff Sutcliffe
% Source   : [Kot17]
% Names    : insertion-sort-1 [Kot17]

% Status   : Theorem
% Rating   : ? v9.1.0
% Syntax   : Number of formulae    :   22 (   1 unt;   9 typ;   0 def)
%            Number of atoms       :   55 (   6 equ)
%            Maximal formula atoms :   22 (   4 avg)
%            Number of connectives :   43 (   1   ~;   5   |;  26   &)
%                                         (   0 <=>;  11  =>;   0  <=;   0 <~>)
%            Maximal formula depth :   11 (   5 avg)
%            Maximal term depth    :    3 (   1 avg)
%            Number of X terms     :    3 (   0  [];   0 ite;   3 let)
%            Number arithmetic     :  104 (  44 atm;  14 fun;  24 num;  22 var)
%            Number of types       :    3 (   1 usr;   1 ari)
%            Number of type conns  :    5 (   2   >;   3   *;   0   +;   0  <<)
%            Number of predicates  :    7 (   1 usr;   2 prp; 0-2 aty)
%            Number of functors    :   12 (   7 usr;   7 con; 0-3 aty)
%            Number of variables   :   26 (  26   !;   0   ?;  26   :)
% SPC      : TX0_THM_EQU_ARI

% Comments : This file was generated by Voogie.
%------------------------------------------------------------------------------
tff(array_int_int,type,
    array_int_int: $tType ).

tff(select_int_int,type,
    select_int_int: ( array_int_int * $int ) > $int ).

tff(store_int_int,type,
    store_int_int: ( array_int_int * $int * $int ) > array_int_int ).

tff(a,type,
    a: array_int_int ).

tff(bad,type,
    bad: $o ).

tff(n,type,
    n: $int ).

tff(sortedFrom,type,
    sortedFrom: $int ).

tff(sortedUntil,type,
    sortedUntil: $int ).

tff(t,type,
    t: $int ).

tff(voogie_precondition_1,axiom,
    ! [A: array_int_int,V: $int,I: $int,J: $int] :
      ( ( I = J )
     => ( select_int_int(store_int_int(A,I,V),J) = V ) ) ).

tff(voogie_precondition_2,axiom,
    ! [A: array_int_int,V: $int,I: $int,J: $int] :
      ( ( I != J )
     => ( select_int_int(store_int_int(A,I,V),J) = select_int_int(A,J) ) ) ).

tff(voogie_precondition_3,axiom,
    ! [A: array_int_int,B: array_int_int] :
      ( ! [I: $int] : ( select_int_int(A,I) = select_int_int(B,I) )
     => ( A = B ) ) ).

tff(voogie_precondition_4,axiom,
    $greater(n,0) ).

tff(voogie_precondition_5,axiom,
    ( $less(0,sortedUntil)
    & $lesseq(sortedUntil,n) ) ).

tff(voogie_precondition_6,axiom,
    ! [K: $int,M: $int] :
      ( ( $lesseq(0,K)
        & $less(K,M)
        & $less(M,sortedUntil) )
     => $lesseq(select_int_int(a,K),select_int_int(a,M)) ) ).

tff(voogie_precondition_7,axiom,
    ! [K: $int] :
      ( ( $lesseq(0,K)
        & $less(K,$difference(sortedUntil,1)) )
     => $lesseq(select_int_int(a,K),select_int_int(a,$difference(sortedUntil,1))) ) ).

tff(voogie_precondition_8,axiom,
    ( $less(0,sortedUntil)
    & $lesseq(sortedUntil,n) ) ).

tff(voogie_precondition_9,axiom,
    ( $lesseq($uminus(1),sortedFrom)
    & $lesseq(sortedFrom,$difference(sortedUntil,1)) ) ).

tff(voogie_precondition_10,axiom,
    ! [K: $int,M: $int] :
      ( ( $lesseq(0,K)
        & $less(K,$sum(sortedFrom,1))
        & $less($sum(sortedFrom,1),M)
        & $lesseq(M,sortedUntil) )
     => $lesseq(select_int_int(a,K),select_int_int(a,M)) ) ).

tff(voogie_precondition_11,axiom,
    ! [K: $int,M: $int] :
      ( ( $lesseq(0,K)
        & $less(K,M)
        & $less(M,$sum(sortedFrom,1)) )
     => $lesseq(select_int_int(a,K),select_int_int(a,M)) ) ).

tff(voogie_precondition_12,axiom,
    ! [K: $int,M: $int] :
      ( ( $lesseq($sum(sortedFrom,1),K)
        & $less(K,M)
        & $lesseq(M,sortedUntil) )
     => $lesseq(select_int_int(a,K),select_int_int(a,M)) ) ).

tff(voogie_conjecture,conjecture,
    $let(
      bad: $o,
      bad:= 
        $ite(~ $greatereq(sortedFrom,0),$true,bad),
      $let(
        [ t: $int,
          a: array_int_int ],
        [t,a]:= 
          $ite(
            $greater(select_int_int(a,sortedFrom),select_int_int(a,$sum(sortedFrom,1))),
            $let(
              t: $int,
              t:= select_int_int(a,sortedFrom),
              $let(
                a: array_int_int,
                a:= store_int_int(a,sortedFrom,select_int_int(a,$sum(sortedFrom,1))),
                $let(
                  a: array_int_int,
                  a:= store_int_int(a,$sum(sortedFrom,1),t),
                  [t,a] ) ) ),
            [t,a] ),
        $let(
          sortedFrom: $int,
          sortedFrom:= $difference(sortedFrom,1),
          ( ( bad
            | ( $less(0,sortedUntil)
              & $lesseq(sortedUntil,n) ) )
          & ( bad
            | ( $lesseq($uminus(1),sortedFrom)
              & $lesseq(sortedFrom,$difference(sortedUntil,1)) ) )
          & ( bad
            | ! [K: $int,M: $int] :
                ( ( $lesseq(0,K)
                  & $less(K,$sum(sortedFrom,1))
                  & $less($sum(sortedFrom,1),M)
                  & $lesseq(M,sortedUntil) )
               => $lesseq(select_int_int(a,K),select_int_int(a,M)) ) )
          & ( bad
            | ! [K: $int,M: $int] :
                ( ( $lesseq(0,K)
                  & $less(K,M)
                  & $less(M,$sum(sortedFrom,1)) )
               => $lesseq(select_int_int(a,K),select_int_int(a,M)) ) )
          & ( bad
            | ! [K: $int,M: $int] :
                ( ( $lesseq($sum(sortedFrom,1),K)
                  & $less(K,M)
                  & $lesseq(M,sortedUntil) )
               => $lesseq(select_int_int(a,K),select_int_int(a,M)) ) ) ) ) ) ) ).

%------------------------------------------------------------------------------