Predicates in Computer Science

1. Introduction

A predicate asks a question where the answer is true or false or, said another way, yes or no.

In computer science and in mathematics, this question comes in the form of a function. The result of the function is true or false (yes or no). The data type of the answer, again both in mathematics and in computer science is called a boolean.

In this tutorial, we’ll go into these concepts in a bit more depth with some examples.

2. Simple Definition

A predicate is a function of a set of parameters that returns a boolean as an answer:

boolean predicate(set of parameters)

A boolean has the value either true or false (yes or no). The input to the function can be any set of parameters we want.

For example, if we have a numerical question such as “Is the temperature greater than 25”, we can write:

temperature > 25

The answer is either true, for example, if the temperature is 30 or false, for example, if the temperature is 20.

If we were to write this predicate as a function in Java, we could write:

boolean checkTemperature(int temperature) {
    return temperature > 25;
}

3. Boolean Values and Boolean Expressions

Every programming language has a boolean data type and each has a way to express true, false, and the set of boolean operations.

We can see some examples in this table:

3.1. No Explicit Boolean Value

Some languages, such as Perl, Tcl, LISP, and SQL, do not have an explicit boolean data type. These languages, though not explicitly stated, use an integer, a byte, or even a bit as the basis of a boolean data type. Essentially, zero is false and anything else is true.

For example, in the C-language, the bool data type comes from the _BOOL data type. Using bool was considered more user-friendly.

The _BOOL data type is based on an unsigned int. Suppose we assign X to have the data type _BOOL as in the following code:

_BOOL X;
X = 0      /* X gets assigned 0 */
X = 1      /* X gets assigned 1 */
X = 5      /* X gets assigned 1 */
X = "Hi"   /* X gets assigned 1 */

Here we see that X assumes the value of one when anything other than zero is assigned.

4. Predicates in Programming

4.1. Flow Control in Imperative Programs

Whenever we have to make a decision in programming, we need a predicate.

In an imperative programming language, such as common programming languages like C, Java, Python, and Fortran, just to name a few, a common decision statement is the IF statement: If a set of conditions is true, then do something; otherwise, do something else.

For example in Java, we can write:

if (x > 25) {
    /* true: do something */
} else {
    /* false: do something else */
}

The x>25 is the predicate. It’s a function of a numerical parameter x that gives a boolean, meaning true or false, as an answer.

Written as a function, we could say (as in this Java example):

boolean checkX(int x) {
    return x > 25;
}

4.2. Predicate as a Filter

A predicate can be viewed as a filter of objects. With a predicate, we can filter out a set of objects that do not satisfy the predicate.

For example, suppose we had a set of objects, named objects, that we wanted to filter. Our filter criteria are the body of our function, predicate(object). If predicate(object) is true, we want to put the object in the filteredset; otherwise, we ignore it.

The pseudo-code might look something like:

algorithm FilterByPredicate(originalSet):
    // INPUT
    //   originalSet = Set of objects
    // OUTPUT
    //   filteredSet = Filtered set of objects
    initialize filteredSet
    for object in originalSet:
        if predicate(object) is true:
            add object to filteredSet
    return filteredSet

But predicates don’t always have to use numbers. For example, we can filter on a set of animals:

lion, elephant, parrot, whale, horse, eagle, cat, dog, human, robin, squirrel

If we want to create a set of birds, then we would use the predicate:

isABird(animal) := true if animal is a bird

and the final set would be:

parrot,eagle,robin

How we would actually program this would depend on our representation of animals.

For example, we could represent each animal as a set of double values in a matrix, AnimalDescription. Each row is a different animal, and each column is the particular property of the animal:

• 0: IDOfAnimal
• 1: TypicalHeight in meters
• 2: TypicalWeight in grams
• 3: TypicalSpeed in meters per second
• 4: HasFeathers, 0.0 for no and 1.0 for yes
• 5: CanFly, 0.0 for no and 1.0 for yes
• 6: NumberOfLegs
• 7: LaysEggs, 0.0 for no and 1.0 for yes

Then maybe we formulate the predicate for identifying the bird as:

AnimalDescription(animal, 4) == 1

We’d, of course, ask our biologist friend if this is enough.

4.3. Predicates in Sorting Algorithms

The key to a sorting algorithm is determining the relationship between two objects. We see that regardless of the method of sorting, all algorithms have to determine the relationship between the objects. It’s the role of the predicate to give this relationship.

Often, we have to determine whether one object is “greater-than” the other object:

isGreaterThan(object1,object2) := true if object1 is greater than object2

The definition of “greater-than” would depend on the objects and on how we want to view them.

For example, in our previous example with animals, we could define:

isGreaterThan(animal1,animal2) := true if animal1 weighs more than animal2

This could give us a list of animals from the largest weight to the smallest weight.

But what if we wanted the animals to be listed from smallest to largest? This can be easily accomplished by:

isGreaterThan(animal1,animal2) := true if animal weighs less than animal2

That is to say, even though the algorithm needs an “isGreaterThan” predicate, we can define this predicate in any way we want, even with a “less than” instead of “greater than”. In the example representation given before, our predicate would be:

isGreaterThan(animal1,animal2) := AnimalDescription(animal1, 2) < AnimalDescription(animal2, 2)

4.4. Object-Oriented Predicates in Sorting and Filtering

In object-oriented programming, a predicate can be encapsulated into a class that would define the needed function, for example, “isGreaterThan”. The sorting or filtering algorithm would then have not only the set of objects to be dealt with but also the class with the predicate.

In Java, we’d first define an abstract class with the function:

class Predicate {
    abstract boolean isGreaterThan(Object x1, Object x2);
}

Then, the sorting or filtering algorithm would use this abstract class in their definition to perform their function. They would expect a class that has the isGreaterThan function defined.

For example, we could define a FilterObjects class that that has a function, addToFilteredSet, which adds the filtered object to the filteredset:

class FilterObjects {
    void addToFilteredSet(Set setOfObjects, 
      Set filteredSet, 
      Predicate predicate) {
        for(Object object: setOfObjects) {
            if(predicate.isGreaterThan(object)) {
                filteredSet.add(object);
            }
        }
    }
}

5. Fuzzy Logic Predicates

Sometimes when we ask a yes/no question, the answer is not really true or false.

Maybe we’re unsure or it is something in between. For example, if we ask the question or set up a predicate which answers the question using temperature:

Question: Is the water hot?

Predicate: IsItHot(T)

If the water is boiling, a temperature T of 100 degrees Celcius, the answer is definitely “yes”. Furthermore, if the water is almost freezing, for example, 5 degrees Celcius, then the answer is definitely “no”.

But what happens if we boil water and then let it cool down outside in the snow? First, the water is hot, and the answer to the predicate is true. But after an hour, the water is definitely cold, and the answer to the predicate is false.

But at what temperature did the answer to the predicate go from true to false? Was it 40? 30? 25? For example, do we think that at 31 degrees the water is hot and then suddenly at 30 degrees the water is cold? We know that the water cools, becomes lukewarm for a while, and then gets cold. Basically, we have a region of “not sure which”.

To complicate matters further, Sven from Norway might have a different impression of “hot” than Giovanni from Italy.

This is where fuzzy logic comes into play. It provides a gradual transition between true and false.

5.1. Fuzzy Logic Predicate Example

In the diagram, we define a predicate IsItHot(T) that answers the question, “Is it hot?”. Here, if IsItHot(T)=1.0, the answer is “yes”, and if PIsItHot(T)=0.0, the answer is “no”.

In normal boolean (true/false) logic, we see there is a sharp transition between hot and cold. This does not correspond to our intuition. But, the fuzzy logic predicate has a slow transition between hot and cold. The closer the answer is to 1.0, the more hot the water is, and the closer to 0.0, the more cold the water is. If the value is 0.5, then we are really not sure.

6. Final Word

In this tutorial, we’ve seen the definition of a predicate as a function returning a boolean as a result.

Additionally, we saw several uses of the predicate concept in program flow, filtering, and sorting. In short, whenever a question is to be asked or a decision to be made, the concept of a predicate comes into play.

We also considered an extension of the boolean concept to fuzzy logic. This is where we recognize that sometimes we cannot make a black and white decision. There is sometimes a gray area.