Quantifiers and Their Use

COS2661 - Formal Logic II · First-Order Logic

Quantifiers and Their Use

In first-order logic, quantifiers are symbols that express the quantity of specimens in the domain of discourse that satisfy a given predicate. The two most common quantifiers are the universal quantifier and the existential quantifier.

Universal Quantifier

The universal quantifier is denoted by the symbol ∀ (for all). It asserts that a property or condition holds for all elements in a particular domain. The general form is:

∀x P(x)

This means that for every element x in the domain, the property P(x) is true.

Example of Universal Quantifier

Consider the statement: “All humans are mortal.” In first-order logic, we can express this as:

∀x (Human(x) → Mortal(x))

Here, Human(x) is a predicate that is true if x is a human, and Mortal(x) is a predicate that is true if x is mortal. The statement asserts that if x is a human, then x is also mortal.

Remember: The universal quantifier applies to every element in the domain. If even one element does not satisfy the predicate, the entire statement is false.

Existential Quantifier

The existential quantifier is denoted by the symbol ∃ (there exists). It asserts that there is at least one element in the domain for which a property holds. The general form is:

∃x P(x)

This means that there exists at least one element x in the domain such that the property P(x) is true.

Example of Existential Quantifier

Consider the statement: “There exists a human who is a philosopher.” In first-order logic, we can express this as:

∃x (Human(x) ∧ Philosopher(x))

Here, Human(x) is a predicate that is true if x is a human, and Philosopher(x) is a predicate that is true if x is a philosopher. The statement asserts that there is at least one human who is also a philosopher.

Remember: The existential quantifier only requires one element in the domain to satisfy the predicate for the statement to be true.

Combining Quantifiers

Example of Combined Quantifiers

“For every human, there exists a philosopher.”

In first-order logic, these can be expressed as:

1. ∀x (Human(x) → ∃y (Philosopher(y)))

2. ∃y (Philosopher(y) ∧ ∀x (Human(x) → y = x))

The first statement asserts that for every human, there is at least one philosopher, which could be the same philosopher for all humans. The second statement asserts that there is one specific philosopher who is the same for every human.

Watch out: Be careful with the order of quantifiers. Changing the order can change the meaning of the statement.

Negation of Quantifiers

Negation Rules

The negation of ∀x P(x) is ∃x ¬P(x).
The negation of ∃x P(x) is ∀x ¬P(x).

Example of Negation

∀x (Bird(x) → CanFly(x))

The negation of this statement would be:

¬∀x (Bird(x) → CanFly(x))

This can be rewritten using the negation rule:

∃x (Bird(x) ∧ ¬CanFly(x))

This means that there exists at least one bird that cannot fly.

Remember: When negating quantifiers, switch between universal and existential quantifiers.

Applications of Quantifiers

Example in Computer Science

SELECT * FROM Users WHERE EXISTS (SELECT * FROM Purchases WHERE Users.id = Purchases.user_id);

This query uses the existential quantifier to find users who have at least one entry in the Purchases table.

Tip: Familiarise yourself with the use of quantifiers in programming and database queries, as they often reflect logical expressions.

Summary

The universal quantifier (∀) indicates that a property holds for all elements in a domain.
The existential quantifier (∃) indicates that there is at least one element in the domain for which a property holds.
Combining quantifiers can change the meaning of a statement.
Negating quantifiers requires switching between universal and existential forms.

Check your understanding

What does the universal quantifier assert about a property in a domain?
How would you express the statement “Some cats are black” in first-order logic?
What is the negation of the statement “All students passed the exam”?
Why is the order of quantifiers important in logical statements?