%------------------------------------------------------------------------------
% File     : SWW973_1 : TPTP v9.2.1. Released v9.1.0.
% Domain   : Software Verification
% Problem  : binary-search-2
% Version  : Especial.
% English  :

% Refs     : [Kot17] Kotelnikov (2017), Email to Geoff Sutcliffe
% Source   : [Kot17]
% Names    : binary-search-2 [Kot17]

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

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

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

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

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

tff(n,type,
    n: $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,
    ! [J: $int,K: $int] :
      ( ( $lesseq(0,J)
        & $lesseq(J,K)
        & $less(K,n) )
     => $lesseq(select_int_int(a,J),select_int_int(a,K)) ) ).

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

tff(voogie_precondition_7,axiom,
    ( $greatereq(i,0)
   => ( select_int_int(a,i) = e ) ) ).

tff(voogie_precondition_8,axiom,
    ! [K: $int] :
      ( ( $greatereq(K,0)
        & $less(K,low) )
     => $less(select_int_int(a,K),e) ) ).

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

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

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