Chapter 5

Predicate Logic Translations

Subsections of Predicate Logic Translations

Motivation

In this chapter, we will learn to further decompose statements in terms of their verbs (called predicates) and their nouns (called individuals). This leads to predicate logic (also called first-order logic).

As a motivation of why we want more expressive power, suppose we wanted to translate the following statements to propositional logic:

All humans are mortal.
Socrates is a human.
Socrates is mortal.

Unfortunately, each statement would be a propositional atom:

p: All humans are mortal.
q: Socrates is a human.
r: Socrates is mortal.

But what if we wanted to prove that given the premises: “All humans are mortal” and “Socrates is a human”, that the conclusion “Socrates is mortal” naturally followed? This logical argument makes sense – Socrates is a human, and all such individuals are supposed to be mortal, so it should follow that Socrates is mortal. If we tried to write such a proof in propositional logic, though, we would have the sequent:

p, q ⊢ r

…and we clearly don’t have enough information to complete this proof.

We need a richer language, which we will get with predicate logic.

Syntax

In this section, we will examine the syntax for translating English sentences to predicate logic. We will still create propositions (statements that are either true or false) using logical connectives (, , , and ¬), but now we will identify the following from our English sentences

predicates: these will be the verbs in the sentences
individuals: these will be the nouns in the sentences
quantifiers: these will help us specify if we mean all individuals or at least one individual

Domains

Predicate logic involves expressing truth about a set of individuals. But the same statement might be true for one group of individuals, but false for others. Thus, we first need to consider which set of individuals we are discussing – called the domain.

A domain might be the set of all humans, the set of all animals, the set of all college classes, etc.

Individuals

An individual is an element within a specified domain. For example, if our domain is the set of all people, then Bob might be a particular individual. If our domain is the set of all college classes, then CIS301 might be a particular individual.

Predicates

A predicate is a function that returns a boolean. It can have one or many parameters, each of which are individuals in a particular domain. A predicate will describe a characteristic of an individual or a comparison between multiple individuals.

For example, suppose our domain is the set of people. Suppose Alice, Bob, and Carla are individuals in our domain. Alice is Bob’s mother, and Carla is an unrelated individual. Carla is 5'10 and 20 years old, Alice is 5'5 and 35 years old, and Bob is 4'10 and 10 years old.

Suppose we have the predicates:

  • isAdult(person) - returns whether person is an adult
  • isMotherOf(person1, person2) - returns whether person1 is the mother of person2
  • isTallerThan(person1, person2) - returns whether person1 is taller than person2

Using our individuals above, we would have that:

  • isAdult(Alice) is true, since Alice is 35 years old
  • isAdult(Bob) is false, since Bob is 10 years old
  • isMotherOf(Alice, Bob) is true, since Alice is Bob’s mother
  • isMotherOf(Carla, Bob) is false, since Carla is not Bob’s mother
  • isTallerThan(Carla, Alice) is true, since Carla is 5'10 and Alice is 5'5.

Quantifiers

We will introduce two quantifiers in predicate logic, which help us make claims about a domain of individuals.

Universal quantifier

The quantifier, called the universal quantifier and read as for all, lets us write propositions that pertain to ALL individuals in a domain.

∀ n P(n) means: for every individual n (in some domain), P(n) is true. Here, n is a variable that stands for a particular individual in the domain. You can think of it like a foreach loop in C#:

foreach(type n in domain)
{
    //P(n) is true every time
}

where n is initially the first individual in the domain, then n is the second individual in the domain, etc.

Existential quantifier

The quantifier, called the existential quantifier and read as there exists, lets us write propositions that pertain to AT LEAST ONE individual in a domain.

∃ n P(n) means: there exists at least one individual n (in some domain) where P(n) is true. You can again think of it as a foreach loop:

foreach(type n in domain)
{
    //we can find at least one time where P(n) is true
}

Universal quantifier example

For example, suppose our domain is all candy bars, and that we have the predicate isSweet(bar), which returns whether bar is sweet. We might write:

∀ x isSweet(x)

Which we would read as: for all candy bars x, x is sweet, or, more compactly, as: all candy bars are sweet.

Existential quantifier example

If instead we wrote:

∃ x isSweet(x)

We would read it as: there exists at least one candy bar x where x is sweet, or, more compactly, as there exists at least one sweet candy bar.

Early examples

Suppose our domain is animals, and that we have the following two predicates:

  • isDog(x): whether animal x is a dog
  • hasFourLegs(x): whether animal x has four legs

Let’s consider what several predicate logic statements would mean in words:

  • ∀ x isDog(x) - translates to: All animals are dogs. This means that EVERY SINGLE ANIMAL in my domain is a dog (which is probably unlikely).
  • ∃ x hasFourLegs(x) - translates to: There exists at least one animal that has four legs.

Next, consider the following proposition:

∀ x (isDog(x) ∧ hasFourLegs(x))

This translates to: All animals are dogs and have four legs. This means that EVERY SINGLE ANIMAL in my domain is a dog and also has four legs. While it is possible that this is true depending on our domain, it is unlikely. What if our domain of animals included cats, chickens, etc.?

Perhaps instead we intended to say: All dogs have four legs. Another way to phrase this is, “For all animals, IF that animal is a dog, THEN it has four legs.” We can see from the IF…THEN that we will need to use an implies statement. Here is the correct translation for All dogs have four legs:

∀ x (isDog(x) → hasFourLegs(x))

We will usually want to use the operator instead of the operator when making a claim about ALL individuals.

Finally, consider this proposition:

∃ x (isDog(x) → hasFourLegs(x))

This translates to: There exists an animal x, and if that animal is a dog, then it has four legs. Recall that an implies statement p→q is true whenever p and q are both true AND whenever p is false. So this claim is true in two cases:

  • If our domain includes a dog that has four legs
  • If our domain includes an animal that is not a dog

We likely only meant to include the first case. In that case, we would want to say, There exists a dog that has four legs – here is that translation:

∃ x (isDog(x) ∧ hasFourLegs(x))

We will usually want to use the operator instead of the operator when writing a proposition about one/some individuals.

Predicates from math

All of our examples in this section involved predicates over domains like people, animals, or living things. A different domain that we are used to working with is some set of numbers: the integers, the positive numbers, the rational numbers, etc.

Perhaps our domain is the set of all integers. Then > is a predicate with two parameters – x > y is defined as whether x is bigger than y, for two integers x and y. We might write:

∀ x (x + 1 > x)

Because for all integers, x + 1 is bigger than x. We might also write:

∃ x (x > x * x * x)

Because -4 > -4 * -4 * -4, i.e., -4 > -64. The same is true for any negative number.

Other common predicates in math are: <, <=, >=, ==, and !=.

Quantifier symbols

The official symbol for the universal quantifier (“for all”) is an upside-down A, like this: . You are welcome to substitute either a capital A, or with the word all or forall. This will be especially handy when we reach Chapter 6 on writing proofs in predicate logic.

The official symbol for the existential quantifier (“there exists”) is a backwards E, like this: . You are welcome to substitute either a capital E, or with the word some or exists.

Single Quantifier

In this section, we will see how to translate simpler statements between English to predicate logic. These translations will involve a single quantifier.

Example: Predicate logic to English

Suppose our domain is animals and that we have the following two predicates:

  • isMouse(x): whether animal x is a mouse
  • inHouse(x): whether animal x is in the house

Suppose we also have that Squeaky is an individual in our domain.

We will practice translating from predicate logic to English. Think about what the following propositions mean, and click to reveal each answer:

  • isMouse(Squeaky) ∧ ¬inHouse(Squeaky)

    • Click here for solution --> "Squeaky is a mouse, and Squeaky is not in the house."

  • ∃ x isMouse(x)

    • Click here for solution --> "There is a mouse".

  • ¬(∃ x isMouse(x))

    • Click here for solution --> "There is not a mouse."

  • ∃ x ¬isMouse(x)

    • Click here for solution --> "There is an animal that is not a mouse".

  • ∀ x isMouse(x)

    • Click here for solution --> "All animals are mice."

  • ¬(∀ x isMouse(x))

    • Click here for solution --> "Not all animals are mice."

  • ∀ x ¬isMouse(x)

    • Click here for solution --> "All animals are not mice."

  • ∀ x (isMouse(x) → inHouse(x))

    • Click here for solution --> "All mice are in the house."

  • ∀ x (isMouse(x) ∧ inHouse(x))

    • Click here for solution --> "Every animal is a mouse and is in the house." (We usually don't want ∧ with ∀.)

  • ¬(∀ x (isMouse(x) → inHouse(x)))

    • Click here for solution --> "Not all mice are in the house."

  • ∀ x (inHouse(x) → isMouse(x))

    • Click here for solution --> "Everything in the house is a mouse."

  • ¬(∀ x (inHouse(x) → isMouse(x)))

    • Click here for solution --> "Not everything in the house is a mouse."

  • ∃ x (isMouse(x) ∧ inHouse(x))

    • Click here for solution --> "There is a mouse in the house."

  • ∃ x (isMouse(x) → inHouse(x))

    • Click here for solution --> "There exists an animal, and if that animal is a mouse, then it is in the house." Recall that this statement will be true if there is an animal that is NOT a mouse (since the → would be vacuously true) as well as being true if there is a mouse in the house.

  • ¬(∃ x (isMouse(x) ∧ inHouse(x)))

    • Click here for solution --> "There is not a mouse in the house."

Translation guide

When translating from English to predicate logic, you can look for particular wording in your sentences to see how to choose a quantifier and/or negation placement. We will also see that certain phrases can be translated multiple (equivalent) ways.

  • Every/all/each/any is translated as: ∀ x ...

  • Some/at least one/there exists/there is is translated as: ∃ x ...

  • None/no/there does not exist can be translated as either ¬(∃ x ...) or ∀ x ¬(...)

  • Not every/not all can be translated as either ¬(∀ x ...) or ∃ x ¬(...)

  • Some P-ish thing is a Q-ish thing is translated as: ∃ x (P(x) ∧ Q(x))

  • All P-ish things are Q-ish things is translated as: ∀ x (P(x) → Q(x))

  • No P-ish thing is a Q-ish thing can be translated as either ¬(∃ x (P(x) ∧ Q(x))) or ∀ x (P(x) → ¬Q(x))

  • Not all P-ish things are Q-ish things can be translated as either ¬(∀ x (P(x) → Q(x))) or ∃ x (P(x) ∧ ¬Q(x))

DeMorgan’s laws for quantifiers

In the translation guide above, we saw that we could often translate the same statement two different ways – one way using an existential quantifier and one way using a universal quantifier. These equivalencies are another iteration of DeMorgan’s laws, this time applied to predicate logic.

Suppose we have some domain, and that P(x) is a predicate for individuals in that domain. DeMorgan’s laws give us the following equivalencies:

  • ¬(∃ x P(x)) is equivalent to ∀ x ¬P(x)
  • ¬(∀ x P(x)) is equivalent to ∃ x ¬P(x)

In Chapter 6, we will learn to prove that these translations are indeed equivalent.

Example: English to predicate logic

Suppose our domain is people and that we have the following two predicates:

  • K(x): whether person x is a kid
  • M(x): whether person x likes marshmallows

We will practice translating from English to predicate logic. Think about what the following sentences mean, and click to reveal each answer:

  • No kids like marshmallows.
    • Click here for solution

      ¬(∃ x (K(x) ∧ M(x)), or equivalently, ∀ x (K(x) → ¬M(x))


  • Not all kids like marshmallows.
    • Click here for solution

      ¬(∀ x (K(x) → M(x)), or equivalently, ∃ x (K(x) ∧ ¬M(x))


  • Everyone who likes marshmallows is a kid.
    • Click here for solution

      ∀ x (M(x) → K(x))


  • Some people who like marshmallows are not kids.
    • Click here for solution

      ∃ x (M(x) ∧ ¬K(x))


  • Some kids don’t like marshmallows.
    • Click here for solution

      ∃ x (K(x) ∧ ¬M(x))


  • Anyone who doesn’t like marshmallows is not a kid.
    • Click here for solution

      ∀ x (¬M(x) → ¬K(x))


Evaluating predicate logic statements on a toy domain

Suppose we have the following toy domain of people with the following characteristics:

  • Bob, age 10, lives in Kansas, has siblings, has brown hair
  • Jane, age 25, lives in Delaware, has no siblings, has blonde hair
  • Alice, age 66, lives in Kansas, has siblings, has gray hair
  • Joe, age 50, lives in Nebraska, has siblings, has black hair

Now suppose that we have the following predicates for individuals in our domain:

  • Ad(x): whether person x is an adult (adults are age 18 and older)
  • KS(x): whether person x lives in Kansas
  • Sib(x): whether person x has siblings
  • Red(x): whether person x has red hair

We will practice evaluating predicate logic statements on our domain of people. Think about whether the following propositions would be true or false over our domain, and then click to reveal each answer:

  • ∀ x Ad(x)

    • Click here for solution This proposition translates as, "All people are adults". This is false for our domain, as we have one person (Bob) who is not an adult.

  • ∀ x ¬Ad(x)

    • Click here for solution This proposition translates as, "All people are not adults". This is false for our domain, as we have three people (Jane, Alice, and Joe) are are adults.

  • ¬(∀ x Ad(x))

    • Click here for solution This proposition translates as, "Not all people are adults". This is true for our domain, as we can find a person (Bob) who is not an adult.

  • ∀ x (KS(x) → Sib(x))

    • Click here for solution This proposition translates as, "Everyone who lives in Kansas has siblings". This is true for our domain, as we have two people who live in Kansas (Bob and Alice), and both of them have siblings.

  • ∃ x (¬KS(x) ∧ Sib(x))

    • Click here for solution This proposition translates as, "There is a person who doesn't live in Kansas and has siblings". This is true for our domain, as Joe lives in Nebraska and has siblings.

  • ¬(∃ x (KS(x) ∧ ¬Ad(x))

    • Click here for solution This proposition translates as, "There does not exist a person who lives in Kansas and is not an adult". This is false for our domain, as Bob lives in Kansas and is not an adult.
  • ¬(∃ x (Sib(x) ∧ Red(x))

    • Click here for solution This proposition translates as, "There does not exist a person with siblings who has red hair". This is true for our domain, as no one with siblings (Bob, Alice, or Joe) has red hair.
  • ∀ x (Red(x) → Sib(x))

    • Click here for solution This proposition translates as, "All people with red hair have siblings". This is true for our domain, as no one has red hair. This means that the implies statement is vacuously true for every person (since `Red(x)` is false for each person), which makes the overall proposition true.
  • ∀ x (KS(x) ∨ Sib(x))

    • Click here for solution This proposition translates as, "Everyone lives in Kansas and/or has siblings". This is false for our domain -- there is one person, Jane, who doesn't live in Kansas and also doesn't have siblings.

Multiple Quantifiers

Translations that involve more than one quantifier (which often happens when some of the predicates have more than one parameter) are more challenging. We will divide these translations into two categories:

  • Translations that involve several of the same quantifier (multiple universal quantifiers or multiple existential quantifiers)
  • Translations that mix quantifiers

In many of the sections, we will using the predicates below (which are over the domain of shapes):

  • isCircle(x) - whether shape x is a circle
  • isSquare(x) - whether shape x is a square
  • isRectangle(x) - whether shape x is a rectangle
  • biggerThan(x, y) - whether shape x is bigger than shape y

Several of the same quantifier

First, we consider translations that involve several of the same quantifier. There are two ways we can translate such statements – either using prenex form (quantifiers out front) or Aristotelian form (quantifiers nested).

Prenex form

The prenex form of a predicate logic translation lists all the quantifiers at the beginning of the statement. This is only recommended when all the quantifiers are the same type – either all universal or all existential.

Prenex example 1

Suppose we wished to translate, Some circle is bigger than some square. Here, we are making three claims:

  • There exists a shape that is a circle
  • There exists a shape that is a square
  • The shape that is a circle is bigger than the shape that is a square

With that in mind, we can see that we will use two existential quantifiers. We can translate the statement as follows:

∃ x ∃ y (isCircle(x) ∧ isSquare(y) ∧ biggerThan(x, y))

Which reads: There are two shapes, x and y, where x is a circle, y is a square, and x (which is a circle) is bigger than y (which is a square).

Equivalently, we could have written:

∃ x ∃ y (isCircle(y) ∧ isSquare(x) ∧ biggerThan(y, x))

Which reads: There are two shapes, x and y, where y is a circle, x is a square, and y (which is a circle) is bigger than x (which is a square).

Prenex example 2

Next, suppose we wished to translate: Every circle is bigger than all squares. Again, we are quantifying two things – ALL circles and also ALL squares. We can see that we will need to use two universal quantifiers. We can translate the statement as follows:

∀ x ∀ y ((isCircle(x) ∧ isSquare(y)) → biggerThan(x, y))

Which reads: For each combination (x, y) of shapes, if x is a circle and y is a square, then x (which is a circle) is bigger than y (which is a square).

Aristotelian form

The Aristotelian form of a predicate logic translation embeds the quantifiers within the translation. This format is possible for any kind of translation – whether the quantifiers are all the same type or mixed types.

Aristotelian form example 1

Suppose we wished to translate, Some circle is bigger than some square using Aristotelian form. We know that we will still need two existential quantifiers, but we will only introduce each quantifier just before the corresponding variable is needed in a predicate.

We can translate the statement using Aristotelian form as follows:

∃ x (isCircle(x) ∧ (∃ y (isSquare(y) ∧ biggerThan(x, y)))

Which reads as: There exists a shape x that is a circle and there exists a shape y that is a square, and x (which is a circle) is bigger than y (which is a square).

Aristotelian form example 2

Let’s repeat our translation for, Every circle is bigger than all rectangles using Aristotelian form. We know that we will still need two existential quantifiers, but we will only introduce each quantifier just before the corresponding variable is needed in a predicate.

We can translate the statement using Aristotelian form as follows:

∀ x (isCircle(x) → (∀ y (isSquare(y) → biggerThan(x, y))))

Which reads as: For every shape x, if x is a circle, then for every shape y, if y is s square, then x (which is a circle) is bigger than y (which is a square).

Mixed quantifiers

Now, we will turn to examples that mix universal and existential quantifiers. We will see below that quantifier order matters in this case, so it is safest to translate such statements using embedded quantifiers. The embedded form can be tricky to write, so we will see a way to systematically translate any statement that needs multiple quantifiers into predicate logic (using Aristotelian form).

Systematic translation

Suppose we wish to translate, Every circle is bigger than at least one square. We see that we are first making a claim about all circles. Without worrying about the rest of the statement, we know that for all circles, we are saying something. So we write:

For all circles, SOMETHING

Trying to formalize a bit more, we assign a variable to the current circle we are describing (x). For each circle x, we are saying something about that circle. So we express SOMETHING(x) as some claim about our current circle, and write:

For each circle x, SOMETHING(x)

We see that we will need a universal quantifier since we are talking about ALL circles, and we also follow the guide of using an implies statement to work with a for-all statement:

∀ x (isCircle(x) → SOMETHING(x))

Next, we describe what SOMETHING(x) means for a particular circle, x:

SOMETHING(x): x is bigger than at least one square

Trying to formalize a bit more about the square, we write:

SOMETHING(x): There exists a square y, and x is bigger than y

Now we can use an existential quantifier to describe our square, and plug in our isSquare and biggerThan predicates to have a translation for SOMETHING(x):

SOMETHING(x): ∃ y (isSquare(y) ∧ biggerThan(x, y))

Now, we can plug SOMETHING(x) into our first partial translation, ∀ x (isCircle(x) → SOMETHING(x)). The complete translation for Every circle is bigger than at least one square is:

∀ x (isCircle(x) → (∃ y (isSquare(y) ∧ biggerThan(x, y))))

Follow-up examples

In these examples, suppose our domain is animals and that we have the following predicates:

  • El(x): whether animal x is an elephant
  • Hi(x): whether animal x is a hippo
  • W(x, y): whether animal x weighs more than animal y

Suppose we wish to translate: There is exactly one hippo. We might first try saying: ∃ x Hi(x). But this proposition would be true even if we had 100 hippos, so we need something more restricted. What we are really trying to say is:

  • There exists a hippo
  • AND, any other hippo is the same one

Let’s use our systematic approach, streamlining a few of the steps:

  • There exists an animal x that is a hippo, and SOMETHING(x)
  • ∃ x (Hi(x) ∧ SOMETHING(x))

To translate SOMETHING(x), the claim we are making about our hippo x:

  • SOMETHING(x): any other hippo is the same as x
  • SOMETHING(x): for each hippo y, x is the same as y
  • SOMETHING(x): `∀ y (Hi(y) → (x == y))

Now we can put everything together to get a complete translation:

∃ x (Hi(x) ∧ (∀ y (Hi(y) → (x == y)))

Here are a few more translations from English to predicate logic. Think about what the following statements mean, and click to reveal each answer:

  • Every elephant is heavier than some hippo.

    • Click here for solution

      ∀ x (El(x) -> (∃ y (Hi(y) ^ W(x, y))))


  • There is an elephant that is heavier than all hippos.

    • Click here for solution

      ∃ x (El(x) ^ (∀ y (Hi(y) -> W(x, y))))


  • No hippo is heavier than every elephant.

    • Click here for solution

      ¬(∃ x (Hi(x) ^ (∀ y (El(y) -> W(x, y)))))


Order matters!

We have learned that when dealing with mixed quantifiers, it is safest to embed them within the translation. If we put the mixed quantifiers out front of a translation, then we can accidentally include them in the wrong order and end up with an incorrect translation.

Suppose we have this predicate, over the domain of people:

likes(x, y): whether person x likes person y

Further suppose that liking a person is not necessarily symmetric: that just because person x likes person y does not mean that person y necessarily likes person x.

Consider these pairs of propositions:

∀ x ∀ y likes(x, y)     vs.     ∀ y ∀ x likes(x, y)  
∃ x ∃ y likes(x, y)     vs.     ∃ y ∃ x likes(x, y)

Is there any difference between each one? No! The two versions of the first proposition both say that every person likes every other person, and the two versions of the second proposition both say that there is a person who likes another person.

But what about:

∀ x ∃ y likes(x, y)     vs.     ∃ y ∀ x likes(x, y)

Suppose our domain is made up of the following people:

Bob: likes Alice and James
Alice: likes Bob
James: likes Alice

The first proposition, ∀ x ∃ y likes(x, y), says that all people have some person (not necessarily the same person) that they like. This would certainly be true for our domain, as every person has at least one person that they like. The second proposition, ∃ y ∀ x likes(x, y) is saying that there is a person (the SAME person) that everyone likes. This proposition would be false for our domain, as there is no one person that is liked by everyone.

Precedence with quantifiers

In section 2.2, we discussed operator precedence for propositional logic statements. The same operator precedence holds for predicate logic statements, except that our two quantifiers ( and ) have the same precedence as the NOT operator. If we have a proposition with multiple quantifiers, then the quantifiers are resolved from right to left. For example, ∃ y ∀ x likes(x, y) should be interpreted as ∃ y (∀ x likes(x, y)).

Here is an updated list of operator precedence, from most important (do first) to least important (do last):

  1. Parentheses
  2. Not operator (¬), universal quantifier (), existential quantifier ()
  3. And operator,
  4. Or operator,
  5. Implies operator,

And here is our updated list of how to resolve multiple operators with the same precedence:

  1. Multiple parentheses - the innermost parentheses are resolved first, working from inside out.
  2. Multiple not ( ¬ ) operators – the rightmost ¬ is resolved first, working from right to left. For example, ¬¬p is equivalent to ¬(¬p).
  3. Multiple and ( ) operators – the leftmost is resolved first, working from left to right. For example, p ∧ q ∧ r is equivalent to (p ∧ q) ∧ r.
  4. Multiple or ( ) operators – the leftmost is resolved first, working from left to right. For example, p ∨ q ∨ r is equivalent to (p ∨ q) ∨ r.
  5. Multiple implies ( ) operators – the rightmost is resolved first, working from right to left. For example, p → q → r is equivalent to p → (q → r).
  6. Multiple quantifiers – the rightmost quantifier is resolved first, working from right to left. For example, ∃ y ∀ x likes(x, y) should be interpreted as ∃ y (∀ x likes(x, y)).

When we get to predicate logic proofs in Chapter 6, we will see that Logika uses a different precedence for quantifiers – there, quantifiers have the LOWEST precedence (done last) of any operator. This ends up being more forgiving than confusing, as it will accept propositions as correct that are really missing parentheses. For example, Logika will accept: ∃ x isMouse(x) ∧ inHouse(x). Technically, this proposition should be incorrect – if we correctly treat quantifiers as having a higher precedence than , then inHouse(x) would no longer know about the variable x or its quantifier.

We should use parentheses with quantifiers to express our intended meaning, and so we should write ∃ x (isMouse(x) ∧ inHouse(x)) instead. But if we forget the parentheses, then Logika will forgive us.