The TPTP Language

Table of Contents

Annotated Formulae

TPTP problems and TSTP solutions are built from annotated formulae of the form language(name,role,formula,source,[useful_info]).. The languages currently supported are thf - formulae in typed higher-order form, tff - formulae in typed first-order form (including extended form), fof - formulae in first order form, and cnf - formulae in clause normal form. The name identifies the formula within the problem. The role gives the user semantics of the formula, one of axiom, hypothesis, definition, assumption, lemma, theorem, corollary, conjecture, negated_conjecture, plain, type, interpretation, logic, and unknown.

The syntax for atoms is that of Prolog: variables start with upper case letters, atoms and terms are written in prefix notation, uninterpreted predicates and functors either start with lower case and contain alphanumerics and underscore, or are in 'single quotes'. The language also supports interpreted predicates and functors. These come in two varieties: defined predicates and functors, whose interpretation is specified by the TPTP language, and system predicates and functors, whose interpretation is ATP system specific. Interpreted predicates and functors are syntactically distinct from uninterpreted ones - they are = and !=, or start with a $, a ", or a digit. Non-variable symbols can be given a type globally, in the formula with role type. The defined types are $o - the Boolean type, $i - the type of individuals, $real - the type of reals, $rat - the type of rational, and $int - the type of integers. New types are introduced in formulae with the type role, based on $tType - the type of all types. Full details of the THF and TFF type systems are provided in [SS+12,BP13,SB10,KSR16], with the last providing an overview of the first three.

The defined predicates recognized so far are

The defined functors recognized so far are

System predicates and functors are used for interpreted predicates and functors that are available in particular ATP tools. System predicates and functors start with $$. The names are not controlled by the TPTP language, so they must be used with caution.

The connectives used to build non-atomic formulae are written using intuitive notations. The universal quantifier is !, the existential quantifier is ?, and the lambda binder is ^. Quantified formulae are written in the form Quantifier [Variables] :  Formula. In the THF, TFF, and FOF languages, every variable in a Formula must be bound by a preceding quantification with adequate scope. Typed Variables are given their type by a :type suffix. The binary connectives are infix | for disjunction, infix & for conjunction, infix <=> for equivalence, infix => for implication, infix <= for reverse implication, infix <~> for non-equivalence (XOR), infix ~| for negated disjunction (NOR), infix ~& for negated conjunction (NAND), infix @ for application. The only unary connective is prefix ~ for negation. Negation has higher precedence than quantification, which in turn has higher precedence than the binary connectives. No precedence is specified between the binary connectives; brackets are used to ensure the correct association. The binary connectives are left associative.

The THF and TFF languages have conditional and let expressions.

The useful_info field of an annotated formula is optional, and if it is not used then the source field becomes optional. The source field is used to record where the annotated formula came from, and is most commonly a file record or an inference record. A file record stores the name of the file from which the annotated formula was read, and optionally the name of the annotated formula as it occurs in that file - this might be different from the name of the annotated formula itself, e.g., if an ATP systems reads an annotated formula, renames it, and then prints it out. An inference record stores information about an inferred formula. The useful_info field of an annotated formula is a list of arbitrary useful information formatted as Prolog terms, as required for user applications.

An example of a THF formula section, extracted from the problem file LCL633^1.p, is shown below. An example of a TFF formula section, extracted from the problem file DAT013=1.p, is shown below that. Example THF formulae. An example of a FOF formula section, extracted from the problem file GRP194+1.p, is shown below that. An example of a clause section, extracted from the problem file GRP039-7.p, is shown below that.

    a: $tType )).

    p: ( a > $i > $o ) > $i > $o )).

    g: a > $i > $o )).

    e: ( a > $i > $o ) > a > $i > $o )).

    r: $i > $i > $o )).

    ! [X: a > $i > $o] :
      ( mvalid
      @ ( mimpl @ ( mnot @ ( p @ X ) )
        @ ( p
          @ ^ [Z: a] :
              ( mnot @ ( X @ Z ) ) ) ) ) )).

    ( g
    = ( ^ [Z: a,W: $i] :
        ! [X: a > $i > $o] :
          ( mimpl @ ( p @ X ) @ ( X @ Z ) @ W ) ) )).

    ( e
    = ( ^ [X: a > $i > $o,Z: a,P: $i] :
        ! [Y: a > $i > $o] :
          ( mimpl @ ( Y @ Z )
          @ ( mbox @ r
            @ ^ [Q: $i] :
              ! [W: a] :
                ( mimpl @ ( X @ W ) @ ( Y @ W ) @ Q ) )
          @ P ) ) )).

    ( mvalid
    @ ^ [W: $i] :
      ! [Z: a] :
        ( mimpl @ ( g @ Z ) @ ( e @ g @ Z ) @ W ) )).
Example of a THF problem file formulae section (LCL633^1.p).
    list: $tType )).

    nil: list )).

    mycons: ( $int * list ) > list )).

    fib_sorted: list > $o )).

    fib_sorted(nil) )).

    ! [X: $int] : fib_sorted(mycons(X,nil)) )).

    ! [X: $int,Y: $int] :
      ( $less(X,Y)
     => fib_sorted(mycons(X,mycons(Y,nil))) ) )).

    ! [X: $int,Y: $int,Z: $int,R: list] :
      ( ( $less(X,Y)
        & $greatereq(Z,$sum(X,Y))
        & fib_sorted(mycons(Y,mycons(Z,R))) )
     => fib_sorted(mycons(X,mycons(Y,mycons(Z,R)))) ) )).

    fib_sorted(mycons(1,mycons(2,mycons(4,mycons(7,mycons(100,nil)))))) )).
Example of a TFF problem file formulae section (DAT002=1.p).
%----Definition of a homomorphism
    ( ! [X] :
        ( group_member(X,f)
       => group_member(phi(X),h) ) )).

    ( ! [X,Y] :
        ( ( group_member(X,f)
          & group_member(Y,f) )
       => multiply(h,phi(X),phi(Y)) = phi(multiply(f,X,Y)) ) )).

    ( ! [X] :
        ( group_member(X,h)
       => ? [Y] :
            ( group_member(Y,f)
            & phi(Y) = X ) ) )).

%----Definition of left zero
    ( ! [G,X] :
        ( left_zero(G,X)
      <=> ( group_member(X,G)
          & ! [Y] :
              ( group_member(Y,G)
             => multiply(G,X,Y) = X ) ) ) )).

%----The conjecture
    ( left_zero(f,f_left_zero) )).

    ( left_zero(h,phi(f_left_zero)) )).
Example of a FOF problem file formulae section (GRP194+1.p).

%----Redundant two axioms
    ( multiply(X,identity) = X )).

    ( multiply(X,inverse(X)) = identity )).

... some clauses omitted here for brevity

    ( subgroup_member(X)
    | subgroup_member(Y)
    | multiply(X,element_in_O2(X,Y)) = Y )).

%----Denial of theorem
    ( subgroup_member(b) )).

    ( multiply(b,inverse(a)) = c )).

    ( multiply(a,c) = d )).

    ( ~ subgroup_member(d) )).
Example of a CNF problem file clause section (GRP039-7.p).

The Arithmetic System

Arithmetic must be done in the context of the THF or TFF types logics, which support the predefined atomic numeric types $int, $rat, and $real. Using THF or TFF enforces semantics that separate $int from $rat from $real from $i from $o. The numbers are unbounded, and the reals of infinite precision (rather than some specific implementation such as 32 bit 2's complement integer, or IEEE floating point). Systems that implement limited arithmetic must halt in an
SZS error state if they hit overflow.

The following interpreted predicates and interpreted functions are defined. Each symbol is ad-hoc polymorphic over the numeric types (with one exception - $quotient is not defined for $int). All arguments must have the same numeric type. All the functions, except for the coercion functions $to_int and $to_rat, have the same range type as their arguments. For example, $sum can be used with the type signatures ($int * $int) > $int, ($rat * $rat) > $rat, and ($real * $real) > $real. The coercion function $to_int always has a $int result, and the coercion function $to_rat always has a $rat result. All the predicates have a $o result. For example, $less can be used with the type signatures ($int * $int) > $o, ($rat * $rat) > $o, and ($real * $real) > $o.

Symbol Operation Comments, examples                                        -
$int The type of integers 123, -123
<integer>            ::- (<signed_integer>|<unsigned_integer>)
<signed_integer>     ::- <sign><unsigned_integer>
<unsigned_integer>   ::- <decimal>
<decimal>            ::- (<zero_numeric>|<positive_decimal>)
<positive_decimal>   ::- <non_zero_numeric><numeric>*
<sign>               ::: [+-]
<zero_numeric>       ::: [0]
<non_zero_numeric>   ::: [1-9]
<numeric>            ::: [0-9]
$rat The type of rationals 123/456, -123/456, +123/456
<rational>           ::- (<signed_rational>|<unsigned_rational>)
<signed_rational>    ::- <sign><unsigned_rational>
<unsigned_rational>  ::- <decimal><slash><positive_decimal>
<slash>              ::: [/]
$real The type of reals 123.456, -123.456,
123.456E789, 123.456e789, -123.456E789,
123.456E-789, -123.456E-789
<real>               ::- (<signed_real>|<unsigned_real>)
<signed_real>        ::- <sign><unsigned_real>
<unsigned_real>      ::- (<decimal_fraction>|<decimal_exponent>)
<decimal_exponent>   ::- (<decimal>|<decimal_fraction>)<exponent><decimal>
<decimal_fraction>   ::- <decimal><dot_decimal>
<dot_decimal>        ::- <dot><numeric><numeric>*
<dot>                ::: [.]
<exponent>           ::: [Ee]
= (infix) Comparison of two numbers. The numbers must be the same atomic type (see the type system).
$less/2 Less-than comparison of two numbers. $less, $lesseq, $greater, and $greatereq are related by
  ! [X,Y] : ( $lesseq(X,Y) <=> ( $less(X,Y) | X = Y ) )
  ! [X,Y] : ( $greater(X,Y) <=> $less(Y,X) )
  ! [X,Y] : ( $greatereq(X,Y) <=> $lesseq(Y,X) )
i.e, only $less and equality need to be implemented to get all four relational operators.
$lesseq/2 Less-than-or-equal-to comparison of two numbers.
$greater/2 Greater-than comparison of two numbers.
$greatereq/2 Greater-than-or-equal-to comparison of two numbers.
$uminus/1 Unary minus of a number. $uminus, $sum, and $difference are related by
  ! [X,Y] : $difference(X,Y) = $sum(X,$uminus(Y))
i.e, only $uminus and $sum need to be implemented to get all three additive operators.
$sum/2 Sum of two numbers.
$difference/2 Difference between two numbers.
$product/2 Product of two numbers.
$quotient/2 Exact quotient of two $rat or $real numbers. For non-zero divisors, the result can be computed. For zero divisors the result is not specified. In practice, if an ATP system does not "know" that the divisor is non-zero, it should simply not evaluate the $quotient. Users should always guard their use of $quotient using inequality, e.g.,
  ! [X: $real] : ( X != 0.0 => p($quotient(5.0,X)) )
$quotient_e/2, $quotient_t/2, $quotient_f/2 Integral quotient of two numbers. The three variants use different rounding to an integral result:
  • $quotient_e(N,D) - the Euclidean quotient, which has a non-negative remainder. If D is positive then $quotient_e(N,D) is the floor (in the type of N and D) of the real division N/D, and if D is negative then $quotient_e(N,D) is the ceiling of N/D.
  • $quotient_t(N,D) - the truncation of the real division N/D.
  • $quotient_f(N,D) - the floor of the real division N/D.
For zero divisors the result is not specified.
$remainder_e/2, $remainder_t/2, $remainder_f/2 Remainder after integral division of two numbers. For τ ∈ {$int,$rat, $real}, ρ ∈ {e, t,f}, $quotient_ρ and $remainder_ρ are related by
  ! [N:τ,D:τ] : $sum($product($quotient_ρ(N,D),D),$remainder_ρ(N,D)) = N
For zero divisors the result is not specified.
$floor/1 Floor of a number. The largest integral value (in the type of the argument) not greater than the argument.
$ceiling/1 Ceiling of a number. The smallest integral value (in the type of the argument) not less than the argument.
$truncate/1 Truncation of a number. The nearest integral value (in the type of the argument) with magnitude not greater than the absolute value of the argument.
$round/1 Rounding of a number. The nearest integral value (in the type of the argument) to the argument. If the argument is halfway between two integral values, the nearest even integral value to the argument.
$is_int/1 Test for coincidence with an $int value.
$is_rat/1 Test for coincidence with a $rat value.
$to_int/1 Coercion of a number to $int. The largest $int not greater than the argument. If applied to an argument of type $int this is the identity function.
$to_rat/1 Coercion of a number to $rat. This function is not fully specified. If applied to a $int the result is the argument over 1. If applied to a $rat this is the identity function. If applied to a $real that is (known to be) rational the result is the $rat value. For other reals the result is not specified. In practice, if an ATP system does not "know" that the argument is rational, it should simply not evaluate the $to_rat. Users should always guard their use of $to_rat using $is_rat, e.g.,
  ! [X: $real] : ( $is_rat(X) => p($to_rat(X)) )
$to_real/1 Coercion of a number to $real.

The extent to which ATP systems are able to work with the arithmetic predicates and functions can vary, from a simple ability to evaluate ground terms, e.g., $sum(2,3) can be evaluated to 5, through an ability to instantiate variables in equations involving such functions, e.g., $product(2,$uminus(X)) = $uminus($sum(X,2)) can instantiate X to 2, to extensive algebraic manipulation capability. The syntax does not axiomatize arithmetic theory, but may be used to write axioms of the theory.

The Non-classical Logics

The TPTP recognizes several normal modal logics, and one temporal logic. Each logic has a define name: Connectives
The non-classical connectives of NTF have the form {$name}. For the logics recognized by the TPTP the connectives are: (System names may also be used for user-defined connectives, e.g., {$$canadian_conditional}, thus allowing use of the TPTP syntax when experimenting with logics that have not yet been formalized in the TPTP.) A connective can be parameterized to reflect more complex non-classical connectives. The form is {$name(param1,param2,param2)}. If the connective is indexed the index is given as the first parameter prefixed with a #, e.g., {$knows(#manuel)} @ (nothing)}, so that the connective is {$knows(#manuel)} (and not the connective {$knows} applied to the index #manuel). All other parameters are key-value assignments, e.g., to list the agents of common knowledge the form might be {$common($agents:=[alice,bob,claire])}.

In NXF the non-classical connectives are applied in a mixed higher-order-applied/first-order-functional style, with the connectives applied using @ to a ()ed list of arguments. In NHF the non-classical connectives are applied using @ in usual higher-order style with curried function applications. There are also short form unary connectives for unparameterised {$box} and {$dia}, applied directly like negation: [.] and <.>, e.g., {$box} @ (p) can be written [.] p. Short forms and long forms can be used together, e.g., it’s OK to use {$necessary} and [.] in the same problem or formula.

Full specification of the connectives and their use in formulae is in the BNF starting at <nxf_atom> and <thf_defined_atomic>.

Semantics Specification
An annotated formula with the role logic is used to specify the semantics of formulae. The semantic specification typically comes first in a file. A semantic specification consists of the defined name of the logic followed by == and a list of properties value assignments. Each specification is the property name, followed by == and either a value or a tuple of specification details. If the first element of a list of details is a value, that is the default value for all cases that are not specified in the rest of the list. Each detail after the optional default value is the name of a relevant part of the vocabulary of the problem, followed by == and a value for that named part. The BNF grammar is
here. The grammar is not very restrictive on purpose, to enable working with other logics as well. It is possible to create a lot of nonsense specifications, and to say the same thing in different meaningful ways. A tool to check the sanity of a specification is available.

A semantic specification changes the meaning of things such as the boolean type $o, universal quantification with !, etc - their existing meaning in classical logic should not be confused with the meaning in the declared logic.

For plain $modal and all the *_modal logics the properties that may be specified are $domains, $designation, $terms, and $modalities.

For $temporal_instant the properties are the $domains, $designation, and $terms of the modal logic, $modalities with different possible values, and another property $time.

The formulae of a problem can be either local (true in the current world) or global (true in all worlds). By default, formulae with the roles hypothesis and conjecture are local, and all others are global. These defaults can be overridden by adding a subrole, e.g., axiom-$local, conjecture-$global.