Predicate Logic - Quantifiers

Chapter 11 17 mins

Learning outcomes:


In the last chapter, we learnt what are predicates in first-order logic, and how they can be used in propositional function to create proposition, given specific subjectds. Now it's time to extend all that we've learnt with the concept of quantification i.e. asserting something regarding a group of objects, in contrast to one particular object.

Universal quantifier

As always, instead of directly defining a concept we would gather around all the intuition needed to arrive at it. In some way, this enables you to connect to the essence of the concept more than you would if you were first shown the concept and then its applications.

Anyways, let's get to quantifiers.

Suppose you were given the statement:

Alex is working

Determine the subject and the predicate here. Well, 'Alex' is the subject while 'is working' is the predicate. Not really difficult to guess! Let's consider another such statement.

Once again, '' is the subject and '' is the predicate.

Now let's consider another example.

Now what? Well 'is working' is still the predicate, but what about 'everyone'. We can't call it the subject based on what we learnt in the previous chapter — it is a specific entity. How to express 'Everyone is working' in terms of notation. Surely, the following can't work.

::\text{W(}x\text{):}:: ::x:: is working

Even if we could have said that 'Everyone' was a subject, in that case also ::\text{W(Everyone)}:: would be imprecise. We couldn't reason a statement like ::\text{W(Alex)}:: from the statement ::\text{W(Everyone)}:: purely notationally.

But let's say, we know all the people whom we are concerned with in the word everyone. For instance, if we are in a class of three students and someone asked us whether everyone is working, by the word 'everyone' we would simply referring to all the 3 students. So if we know our domain, we would write the following.

::\text{W(Alex)} \wedge \text{W(Sandra)} \wedge \text{W(Joe)}::

... in order to say that everyone is working.

In this case, our domain was manageable, and therefore we represented everyone separately. But what if we have a huge domain? For example, how can we notationally express the following:

Every even integer is divisible by 2.

We could never reach the end of the infinite domain! Clearly, we need a more compact notation to express such statements. This is where the universal quantifier comes in.

Universal quantification is to make an assertion regarding a whole group of objects.

It's denoted using the symbol ::\forall:: (an upside-down A). A universal quantification is expressed as follows.

::\forall x P(x)::

We read this as 'for every ::x::, ::P(x):: holds'. But where do we get the value of every ::x::. This is what the domain is for.

For a quantification, the universe of discourse, or the domain of discourse, or simply the domain, is the set of objects for which a single assertion is made regarding each object.

Let's solve our old problem of saying 'Everyone is working' in the class of the three students Alex, Sandra and Joe.

First we specify that the domain of discourse is the set ::\{\text{Alex, Sandra, Joe}\}::. This will be used in our quantification. Next, we see that to say a given person is working, we'd need the predicate function below:

::P(x):: : ::x:: is working.

Now to say that everyone is working, we'll write the following quantification expression:

::\forall x P(x)::

This is read as 'For every student ::x::, ::x:: is working.' This is equivalent to ::\text{W(Alex)} \wedge \text{W(Sandra)} \wedge \text{W(Joe)}:: which says that 'Alex is working, Sandra is working and Joe is working.'

Sometimes, we could directly specify the universe of discourse next to the universal quantifier. For instance, suppose we ought to express the following:

Every integer is either odd or even.

Taking the following predicate functions,

::E(x):: : ::x:: is even
::O(x):: : ::x:: is odd

...we could write.

::\forall x \space \epsilon \space \Z (E(x) \vee O(x))::

Note that the part ' ::\forall x \space \epsilon \space \Z::' says that 'for every element ::x:: in the set ::\Z::'.

Often times, it might be cumbersome to separately mention the universe of discourse, such as when working with assertions in mathematics. In such cases, we're better off at inlining the domain within the quantification expression.

The universal quantification operation produces a proposition. That is, given a domain for ::x:: and a predicate function ::P::, ::\forall x P(x):: is a proposition.

Universal quantification can be used to express a lot more than we otherwise could in propositional calculus. However, still somethings are left out. For those, we have the existential quantifier.

Express the following statements as logical expressions:

  1. All cats are lazy.
  2. Some integer is positive.
  3. Some person is suspicious.
  4. Everyone is sleeping.
  5. At least one person is missing.
  6. Everyone is not working.
  1. ::L(x):: : ::x:: is lazy.
    The domain consists of all cats.
    The expression hence becomes ::\forall c L(c)::.

  2. ::P(x):: : ::x:: is positive.
    The domain is the set ::\Z:: (the set of all integers).
    The expression hence becomes ::\exists x \space \epsilon \space \Z (P(x))::.

  3. ::S(x):: : ::x:: is suspicious.
    The domain is the set of all people.
    The expression hence becomes ::\exists p (S(p))::.

  4. ::S(x):: : ::x:: is sleeping.
    The domain is the set of all people.
    The expression hence becomes ::\forall p (S(p))::.

  5. ::M(x):: : ::x:: is missing.
    The domain is the set of all people.
    The expression hence becomes ::\exists p (M(p))::.

  6. ::M(x):: : ::x:: is working.
    The domain is the set of all people.
    The expression hence becomes ::\exists p (\neg W(p))::.

This last statement could also be expressed as follows:

::N(x):: : ::x:: is not working.
The domain is the set of all people.
The expression hence becomes ::\exists p (N(p))::.

However, it is good practice to always filter out as many operators you could from a given sentence. It's best to represent the simplest, most primitive, statement in the predicate function.

In the logical expression ::\exists p (\neg W(p))::, we use the negation symbol to negate the statement that '::p:: is working', instead of directly asserting the negation, as in the predicate function ::N(x):: : ::x:: is not working.

Existential quantifier

Suppose you want to notationally express the following:

Someone is working.

given the same predicate, and domain of discourse as before.

How would you do so? Well, three items are manageable so let's just go ahead and express the sentence fully.

::\text{W(Alex)} \vee \text{W(Sandra)} \vee \text{W(Joe)}::

Here, we're simply saying that either Alex is working or Sandra is working or Joe is working. In any way, there is someone in the class who is working.

The question is can you express this statement using the universal quantifier?

Clearly no!

This is because we are making an assertion regarding at least one person — it might not apply for everyone (though it could!). What else to use?

Well, we use the existential quantifier.

Existential quantification is to make an assertion regarding at least one object in a group of ojects.

It's denoted using the symbol ::\exists:: (a horizontal reflection of E). It's expressed as follows:

::\exists x P(x)::

We read this as 'For some ::x::, ::P(x):: holds.'

Let's rewrite the previous sentence 'Someone is working' using an existential quantifier:

Recall that the domain is the set ::\{\text{Alex, Sandra, Joe}\}::, while the predicate function is ::P(x):: : ::x:: is working.

::\exists x P(x)::

This expression is stating that 'For some person ::x::, that person is working.'

All the syntactic rules that apply to universal quantification also apply to existential quantification. That is, we could inline the domain of discourse ::S:: as shown below:

::\exists x \epsilon S (W(x))::

Let's see how good are we at existentially quantifying statements.

Combining logical operators, predicates and quantifiers

Uptil this point, the quantifications we've seen have been around just one atomic expression i.e. ::P(x)::. Many English sentences can be modeled this way, but when we use connectives in the sentences, then we need to use them in our logical expressions as well to truly capture the semantics of the actual sentences.

Next up, we'll consider a couple of sentences and convert them into quantified logical expressions.

For each of the following sentences, we ought to determine a predicate function and the domain of discourse.

Express the following statements as logical expressions. For each statement, give all the predicate functions used and the domain for each involved variable.

  1. Every integer is either even or odd.
  2. Some kids are playing football while some are playing cricket.
  3. Everyone is either sleeping or chanting.
  4. Every waiter is either busy serving or talking.
  5. Each contact is either for my school or for my home.
  6. All modern phones have sim and SD card slots.
  1. ::E(x):: : ::x:: is even.
    ::O(x):: : ::x:: is odd.
    The domain is the set ::\Z::.
    The expression hence becomes ::\exists x \space \epsilon \space \Z (E(x) \vee O(x))::.

    We could also express this sentence as ::\exists x \space \epsilon \space \Z (E(x) \vee \neg E(x))::, since saying '::x:: is odd' is as good as saying '::x:: is not even' — there are only two categories of integers: even and odd; hence if an integer is not even, it must be odd!
  2. ::F(x):: : ::x:: playing football.
    ::C(x):: : ::x:: playing cricket.
    The domain is the set of all kids.
    The expression hence becomes ::\exists k F(k) \wedge \exists k C(k)::.

  3. ::S(x):: : ::x:: is sleeping.
    ::C(x):: : ::x:: is chanting.
    The domain is the set of all people.
    The expression hence becomes ::\forall p (S(p) \vee C(p))::.

  4. ::S(x):: : ::x:: is busy serving.
    ::T(x):: : ::x:: is busy talking.
    The domain is the set of all waiters.
    The expression hence becomes ::\forall w (S(w) \vee T(w))::.

  5. ::S(x):: : Contact ::x:: is for my school.
    ::H(x):: : Contact ::x:: is for my home.
    The domain is the set of all contacts.
    The expression hence becomes ::\forall c (S(c) \vee H(c))::.

  6. ::Sim(x):: : ::x:: has a sim slot.
    ::SD(x):: : ::x:: has an SD card slot.
    The domain is the set of all modern phones.
    The expression hence becomes ::\forall m (Sim(m) \wedge SD(m))::.

"I created Codeguage to save you from falling into the same learning conundrums that I fell into."

— Bilal Adnan, Founder of Codeguage