%------------------------------------------------------------------------------
% File : SWW986_1 : TPTP v9.2.1. Released v9.1.0.
% Domain : Software Verification
% Problem : dutch-flag-5
% Version : Especial.
% English :
% Refs : [Kot17] Kotelnikov (2017), Email to Geoff Sutcliffe
% Source : [Kot17]
% Names : dutch-flag-5 [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 : 10 ( 0 []; 0 ite; 10 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] ) ),
$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] ) ),
$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] ) ),
$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] ) ),
$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) ) ) ) ) ) ) ) ) ) ) ) ) ) ).
%------------------------------------------------------------------------------