1.3 Predicates and Quantifiers

DEFINITIONS:

①     Predicates is a logical operator that returns a Boolean value that is either true or false.

We also use predicates in programming.

Consider the statement “x is absent in the class today.”

Ø  Since x is an unknown, this statement is not a propositional statement.

However, we do know that when we assign a value (object) into x, the whole statement will make sense as it explains how a subject (x) is being affected.

Hence, we can say that x is a subject which can take any value into the statement to turn the whole statement into a propositional statement and it can hold a set of truth values.

Likewise, “is absent in the class today” represents what does the property that x holds.

Ø  Hence, “is absent in the class today” is known as the predicate for x (subject).

Ø  The predicate and subject, if combined together, can be written as P(x) where P is the predicate and x is the subject of the statement. It is also known as the propositional function.

In general, a statement of the form P(X_1, X_2, X_{3, …,} X_n) is the value of proposition function P at n-tuple (X_1, X_2, X_{3, …,} X_n) and P is known as n-place predicate or n-ary predicate.

Example: Let P(x) be the statement “x<2”. What are the truth values of P(4) and P(1).

Answer:  P(4)= 4<2 is false but P(1)= 1<2 is true

②     Quantifiers transform propositional function into proposition without assigning specific values into a variable

 

Universal Quantifier ∀xP(x)

Given that ∀ is the sign for universal quantifier. Hence, the universal quantification of P(x) denoted by ∀xP(x) can be expressed by the statement “P(x) for all values of x in the domain of its discourse is true” or “for all xP(x)” or “for every xP(x)”.

Other ways to express ∀xP(x):

“for all”

“for every”

 “for each”

“given any”

“for arbitrary”

“all of”

Universal Quantification: ∀XP(X_n) @ P(X₁)^P(X₂)^P(X₃)^…^P(X_n)

              ※True when all domain satisfies the given predicates.

Example:

What is the truth value of ∀x(x² ≥ x) if the domain consists of all real numbers? What is the truth value of this statement if the domain consists of all integers?

Solution: The universal quantification ∀x(x² ≥ x), where the domain consists of all real number is false (0.5²≥0.5 is false); but if the domain consists of integers than it is true for ∀x(x² ≥ x).

Existential Quantifier ∃xP(x)

Given that ∃is the symbol for existential quantifier, the existential quantification  of P(x) denoted by ∃xP(x) can be expressed by the statement “There exists an element x in the domain such that P(x)”. It is true for some x in the domain of P(x) which is true.

Other ways to express ∃xP(x):

“there exists”

“there is”

“for some”

“for at least one”

“there is an x such that P(x)

“for some xP(x)”

Existential Quantification: ∃xP(X_n) @ P(X₁)vP(X₂)vP(X₃)v…vP(X_n)

              ※True when either of the domain x satisfies the predicate.

Example:

Let Q(x) denote the statement “x = x + 1.”What is the truth value of the quantification ∃xQ(x),

where the domain consists of all real numbers?

Solution: Because Q(x) is false for every real number x, the existential quantification of Q(x),which is ∃xQ(x), is false.

Uniqueness Quantifier∃!x P(x)

Denoted by∃!x P(x) @∃₁x P(x), uniqueness quantification means that there are only value of x which can be taken by the domain of the function to make it True, otherwise the function is False.

We can also use quantifiers and propositional logic to express uniqueness.

Example: Let P(x) denote x + 1 = 0 and U are the integers. Then ∃!x P(x) is true.

                *Only -1 can make the propositional function be true.

Example: Let P(x) denote x > 0 and U are the integers. Then ∃!x P(x) is false.

                             *There are more than 1 values which can make this propositional true.

Statement	When True?	When False
∀xP(x)	P(x) is true for every x.	There is an x for which P(x) is false.
∃xP(x)	There is an x for which P(x) is true	P(x) is false for every x.

Logical Equivalences Involving Quantifiers

¨  Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions.

¨  We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

Negating Quantified Expressions

De Morgan’s Laws for Quantifiers.   

Negation	Equivalent Statement	When is negation true?	When false?
￢∃xP(x)	∀x￢ P(x)	For every x, P(x) is false	There is an x for which P(x) is true.
￢∀xP(x)	∃x￢ P(x)	There is an x for which P(x) is false	P(x) is true for every x.

Example of quantifier in Daily Life

-> In the social sciences, quantification is an integral part of economics and psychology.

-> For example in economics, we use it in empirical observations while in psychology, we use it in experimentation.

p/s: You can get this note at the following link --> 1.3 Predicates and Quantifiers