%------------------------------------------------------------------------------
% File     : SWW982_1 : TPTP v9.2.1. Released v9.1.0.
% Domain   : Software Verification
% Problem  : dutch-flag-1
% Version  : Especial.
% English  :

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

% Status   : Theorem
% Rating   : ? v9.1.0
% Syntax   : Number of formulae    :   20 (   1 unt;  11 typ;   0 def)
%            Number of atoms       :   37 (   8 equ)
%            Maximal formula atoms :   17 (   4 avg)
%            Number of connectives :   29 (   1   ~;   4   |;  15   &)
%                                         (   0 <=>;   9  =>;   0  <=;   0 <~>)
%            Maximal formula depth :    8 (   5 avg)
%            Maximal term depth    :    3 (   1 avg)
%            Number of X terms     :    2 (   0  [];   0 ite;   2 let)
%            Number arithmetic     :   47 (  25 atm;   2 fun;   7 num;  13 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    :   13 (   9 usr;   9 con; 0-3 aty)
%            Number of variables   :   17 (  17   !;   0   ?;  17   :)
% 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(high,type,
    high: $int ).

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

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

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

tff(pivot,type,
    pivot: $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,
    $greatereq(n,0) ).

tff(voogie_precondition_5,axiom,
    ( $lesseq(0,low)
    & $lesseq(low,i)
    & $lesseq(i,$sum(high,1))
    & $less(high,n) ) ).

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

tff(voogie_precondition_7,axiom,
    ! [K: $int] :
      ( ( $lesseq(low,K)
        & $less(K,i) )
     => ( select_int_int(a,K) = pivot ) ) ).

tff(voogie_precondition_8,axiom,
    ! [K: $int] :
      ( ( $less(high,K)
        & $less(K,n) )
     => $greater(select_int_int(a,K),pivot) ) ).

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

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