Predicates and Quantifiers

Predicates

x + 1 = 2

x + y = z

x > 5

Student x had failed the exam.

These statements are neither true nor false before we substitute x with other definite numbers or values. We are going to look at how to produce propositions from these above statements.

Let’s look at the example below:

Student x had failed the exam.

This statement consists of 2 parts. The first part is “Student x”, which we call it as variable. And the second part, which is “had failed the exam” is the predicate part.

We can denote this statement with P(x), in which x is the variable and P is the predicate. P(x) means “The propositional function P with value x” or “The propositional function P at x”

Let’s see some examples to help you understand better.

Example 1:

x + 1 = 2

Let the above statement be denoted with P(x), what is the truth value of P(1) and P(4)?

Answer:

when x = 1,

P(1) : 1 + 1 = 2 (True)

when x = 1,

P(4) : 4 + 1 = 2 (False)

Example 2:

The ID, x is valid.

Every account’s ID is distinct from each other. Therefore, when two users sign up using the same ID, the ID is valid for the first user but invalid for the second user.

At first, a user named Kenny had signed up by using number 3 as his ID. Now you want to sign up for a new ID.

Let the above statement be denoted with P(x), what is the truth value if you put number 4 as your ID and also number 3?

Answer:

when number 4 is used as your ID,

P(4) : 4 ≠ 3(True)

Therefore, the ID is valid.

when number 3 is used as your ID,

P(3) : 3 = 3(True)

Therefore, the ID is invalid. 

Preconditions and Postconditions

The idea of predicates is often applied in the field of computer science. Programmers and developers make various programs and use predicates on detecting any possible errors that may occur.

For example,

Below is a simple program to calculate what is the increment of the value a user will input.

x = x + 1

A precondition is what we think the valid input for the statement is. For example, we are going to test the program by inputting number 1. Therefore, we can say that the precondition for this statement or program is 1.

P(1) : x = 1

A postcondition is what we think the valid output for the statement should look like. Since we have assume number 1 as the precondition, we’ll expect that the output should be number 2. Therefore, we can say that the postcondition for this statement or program is 2.

P(2) : x = 2

2 = 1 + 1

Quantifiers

Quantifiers are used to determine whether a statement is valid if the input variables have meet certain conditions.

There are 2 types of quantifiers. Universal quantifier and existential quantifier.

Universal quantifier

Universal quantification of P(x) means P(x) for all values of x in the domain. If P(x) is true with condition all the value of x in the domain must be true, then we can say that for all values of x P(x) is true, or we can use the notation:

∀ x P(x) is true

where ∀ represents “for all”.

We can express universal quantification of P(x) like this:

x₁ ∧ x₂ ∧ x₃ ∧ …… ∧ x_n

Example 1:

P(x) : x + 1 < x + 2

From the above statement, we can see that no matter what is the value of x, x + 1 will definitely be smaller than x + 2. Therefore we can say for all values of x P(x) is true, or ∀ x  P(x) is true

Example 2:

P(x) : x > 3

From the above statement, we can see that not all value of x can suit this statement. For example, when x = 4, the statement is true but when x = 2, the statement will be wrong. It is only true for some values of x. Therefore we can say for all values of x P(x) is false, or ∀ x  P(x) is false

Existential quantifier

Existential quantification of P(x) means P(x) for some values of x in the domain. If P(x) is true with condition at least one of the x values in the domain must be true, then we can say that for some values of x P(x) is true, or we can use the notation:

∃ x P(x) is true

where ∃ represents “for some”.

We can express universal quantification of P(x) like this:

x₁ ∨ x₂ ∨ x₃ ∨ …… ∨ x_n

Example 1:

P(x) : x > 3

From the above statement, we can see that some value of x can suit this statement. For example, when x = 4, the statement is true. It is true for some values of x. Therefore we can say for some values of x P(x) is true, or ∃ x  P(x) is false

Example 2:

P(x) : x + 1 > x + 2

From the above statement, we can see that no matter what is the value of x, x + 1 will not be greater than x + 2. Therefore we can say for some values of x P(x) is false, or ∃ x  P(x) is false. 

Uniqueness quantifier

Uniqueness quantification of P(x) means P(x) for only a specific value of x in the domain. If P(x) is true with condition only a specific value of x in the domain, then we can say that for only a specific value of x P(x) is true, or we can use the notation:

∃! x P(x) is true

or

∃₁ x P(x) is true

where ∃! or ∃₁  represents “for only”.

We can express uniqueness quantification of P(x) like this:

P(x) = x_s  , where x_s  denotes the specific value of x.

Example 1:

P(x) : x + 2 = 3

From the above statement, we can see that this statement only suits one value, that is x = 1. If we put other value instead of 1 as the value of x, the statement will become false. It is only true for x = 1. Therefore we can say for a specific value of x P(x) is true, or ∃! x  P(x) is true

Example 2:

P(x) : x > 3

From the above statement, we can see some values of x can suit this statement. There are more than one value of x which make this statement true. Therefore, it is not only true for some values of x but true for some values of x. Therefore we can say for a specific value of x P(x) is false, or ∃! x  P(x) is false

 

Quantifiers in reality

Example 1:

You are assigned by your lecturer to create an enrolment system for the his course portal. The enrolment system will stop once all your coursemates have enrolled theirselves into the course.

We can ensure that which students have enrolled themselves into the course by making this statement:

P(x) = Student x had enrolled himself/herself into the course.

Let say a student named Ali had enrolled himself into the course while Abu had not. We can say that the statement:

P(Ali) = Ali had enrolled himself/herself into the course.

is true whereas:

P(Abu) = Abu had enrolled himself/herself into the course.

is false.

Let say there are 30 students in your class. So you have to program your enrolment system in which it will stop after all of the students had enrolled. We can determine it using the statement below:

x₁ ∧ x₂ ∧ x₃ ∧ …… ∧ x₃₀

The enrolment system will just continue running until ∀ x  P(x) is true.

Example 2 :

There are 10 food stalls in the cafeteria.

 

If 10 of them are open, many students will go and buy their food there. If only 1 of them are open, students will still go there and buy their food, but the number of students is lesser. When do students not go there and buy their food? If none of them are open, there will be no students who is still willing to go there.

From the above statements, we can make a simple statement to determine whether the selected stall is open or not.

Q(x) = Stall x is open.

Let say stall 10 is open and the rest of them are close. So:

Q(10) = Stall 10 is open.

is true while

Q(2) = Stall 2 is open.

is false.

If there is at least one stall which is open, there wil be students going there. So we can write like this below:

x₁ ∨ x₂ ∨ x₃ ∨ …… ∨ x₁₀

There will be students going to the café if ∃ x  P(x) is false

Example 3:

Three students, Alex, Dexter and Robert are assigned to be working in a group for their assignments. A good teamwork and cooperation is badly needed in a team.

They have different characteristics.

Alex can become a good leader. He is good at giving precise commands and work very efficient in his team.

Dexter is a hardworking student. He do things fast. He likes to ensure any overlooked works before the deadline of submitting.

Robert, on the other hand is quite a lazy student. Even he is assigned to jobs and assignments, he always likes to do it in the last minute.

In order to make teamworks efficient, a leader must be chosen among them to increase efficiency.

P(x) = x is the leader.

We all know that Alex is a good leader. So definitely the value of x is Alex and not Robert or Dexter. Therefore we can say that Alex is the only person who is eligible to become a leader of the group, or in the mathematical terms there exists a unique x such that P(x) is true.