Predicates and quantifiers: Exercise 9

/ Predicates and quantifiers / By

Introduction

The universal quantifier is denoted by ∀”.

An example of how to interpret it is as follows:

The statement “∀x P(x) is true if P(x) holds for all x in the universe of discourse.  On the other hand, if you can find x such that P(x) is false, then the statement “∀x P(x) is false.

The existential quantifier is denoted by ∃.

The statement ∃x P(x) is true if P(x) holds for at least one x in the universe of discourse.  On the other hand, you cannot find at least one x such that P(x) is true, then the statement ∃x P(x) is false.

Example 1

predicates and quantifiers example 1

Example 2

predicates and quantifiers example 2

Now, let’s solve one of the exercises so you can have an example to follow while you solve more exercises.

Exercise 9

Let P (x) be the statement “x can speak Russian” and let Q(x) be the statement “x knows the computer language C++.” Express each of these sentences in terms of P (x), Q(x), quantifiers, and logical connectives. The domain for quantifiers consists of all students at your school.

a)  There is a student at your school who can speak Russian and who knows C++.

b)  There is a student at your school who can speak Russian but who doesn’t know C++.

c)  Every student at your school either can speak Russian or knows C++.

d)  No student at your school can speak Russia nor knows C++.

Answers

P(x) = “x can speak Russian”

Q(x) = “x knows the computer language C++.”

  1. ∃x (P(x) ^ Q(x))
  2. ∃x (P(x) ^ ¬Q(x))
  3. ∀x (P(x) v Q(x))
  4. ¬∃x (P(x) ^ Q(x))

Notice that the quantifiers have precedence over all the operators used in propositional calculus. That’s why we have to use parenthesis to specify what is the scope of the quantifier. ∃x (P(x) ^ Q(x)) is not the same than ∃x P(x) ^ Q(x).

Also notice that the following logical equivalences holds for quantifiers:

  • ¬∀xP (x) ≡ ∃x ¬P (x)
  • ¬∃xQ(x) ≡ ∀x ¬Q(x)

So, the answer to question d can also be written as ∀x ¬ (P(x) ^ Q(x))

Related topics: