Introduction
Propositional logic has limitations. Consider the statement: “x > 3”. This is not a proposition because its truth value depends on the value of x. This is where predicates and quantifiers come in - they allow us to work with statements involving variables.
What is a Predicate?
A predicate (or propositional function) is a statement involving variables that becomes a proposition when the variables are assigned specific values.
Notation
We write predicates as P(x), Q(x, y), etc., where:
- P is the predicate name
- x, y are variables
- The expression in parentheses shows which variables the predicate uses
Examples of Predicates
-
P(x): “x > 3”
- P(5) is TRUE (because 5 > 3)
- P(2) is FALSE (because 2 is not > 3)
- P(3) is FALSE (because 3 is not > 3)
-
Q(x): “x is an even number”
- Q(4) is TRUE
- Q(7) is FALSE
- Q(10) is TRUE
-
R(x, y): “x + y = 10”
- R(3, 7) is TRUE (because 3 + 7 = 10)
- R(5, 4) is FALSE (because 5 + 4 ≠ 10)
- R(6, 4) is TRUE (because 6 + 4 = 10)
-
S(x): “x is a student at Delhi University”
- S(“Rahul”) might be TRUE or FALSE depending on whether Rahul studies there
Domain (Universe of Discourse)
The domain (or universe of discourse) is the set of all possible values that a variable can take.
Examples
-
For P(x): “x > 3”
- If domain = {1, 2, 3, 4, 5}, then we check these 5 numbers
- If domain = All real numbers, then we check all real numbers
-
For Q(x): “x is an even number”
- If domain = {1, 2, 3, 4, 5, 6}, then even numbers are {2, 4, 6}
Quantifiers
Quantifiers allow us to express “for all” and “there exists” statements.
1. Universal Quantifier (∀) - “For All”
The universal quantifier ∀ is read as “for all”, “for every”, or “for each”.
Notation: ∀x P(x) Meaning: “For all x, P(x) is true” or “P(x) is true for every value of x in the domain”
Examples
Example 1:
- Statement: ∀x (x² ≥ 0)
- Meaning: “For all real numbers x, x squared is greater than or equal to 0”
- Truth Value: TRUE (because squaring any real number gives a non-negative result)
Example 2:
- Statement: ∀x (x + 1 > x)
- Meaning: “For all real numbers x, x + 1 is greater than x”
- Truth Value: TRUE (always true)
Example 3:
- Domain: {1, 2, 3, 4, 5}
- Statement: ∀x (x < 10)
- Meaning: “Every number in the set is less than 10”
- Truth Value: TRUE (all numbers 1-5 are less than 10)
Example 4:
- Domain: {1, 2, 3, 4, 5}
- Statement: ∀x (x < 4)
- Meaning: “Every number in the set is less than 4”
- Truth Value: FALSE (because 4 and 5 are not less than 4)
- Counterexample: x = 5
Important Notes
- ∀x P(x) is TRUE only if P(x) is true for every value in the domain
- ∀x P(x) is FALSE if there exists at least one value for which P(x) is false
- To disprove ∀x P(x), find just one counterexample
2. Existential Quantifier (∃) - “There Exists”
The existential quantifier ∃ is read as “there exists”, “there is”, or “for some”.
Notation: ∃x P(x) Meaning: “There exists an x such that P(x) is true” or “P(x) is true for at least one value of x”
Examples
Example 1:
- Statement: ∃x (x² = 4)
- Meaning: “There exists a real number x such that x squared equals 4”
- Truth Value: TRUE (x = 2 or x = -2)
Example 2:
- Statement: ∃x (x + 5 = 8)
- Meaning: “There exists a number x such that x + 5 = 8”
- Truth Value: TRUE (x = 3)
Example 3:
- Domain: {1, 2, 3, 4, 5}
- Statement: ∃x (x > 3)
- Meaning: “There is at least one number in the set that is greater than 3”
- Truth Value: TRUE (x = 4 or x = 5)
Example 4:
- Domain: {1, 2, 3}
- Statement: ∃x (x > 5)
- Meaning: “There is at least one number in the set that is greater than 5”
- Truth Value: FALSE (no number in the set is greater than 5)
Important Notes
- ∃x P(x) is TRUE if P(x) is true for at least one value in the domain
- ∃x P(x) is FALSE only if P(x) is false for all values in the domain
- To prove ∃x P(x), find just one example where P(x) is true
Uniqueness Quantifier (∃!)
The uniqueness quantifier ∃! means “there exists exactly one”.
Notation: ∃!x P(x) Meaning: “There exists exactly one x such that P(x) is true”
Examples
-
∃!x (x + 5 = 8)
- Meaning: “There is exactly one number x such that x + 5 = 8”
- Truth Value: TRUE (only x = 3)
-
∃!x (x² = 4)
- Meaning: “There is exactly one number x such that x² = 4”
- Truth Value: FALSE (both x = 2 and x = -2 work)
Translating English to Quantified Statements
Example 1: Universal Statements
English: “All students in this class have studied calculus.”
- Let S(x) = “x is a student in this class”
- Let C(x) = “x has studied calculus”
- Translation: ∀x (S(x) → C(x))
Why →? Because we’re saying: “If someone is a student in this class, then they have studied calculus.”
Example 2: Existential Statements
English: “Some student in this class has visited Delhi.”
- Let S(x) = “x is a student in this class”
- Let D(x) = “x has visited Delhi”
- Translation: ∃x (S(x) ∧ D(x))
Why ∧? Because we need someone who is both a student AND has visited Delhi.
Example 3: Negative Statements
English: “No student in this class is 30 years old.”
- Let S(x) = “x is a student in this class”
- Let T(x) = “x is 30 years old”
- Translation: ∀x (S(x) → ¬T(x)) OR ¬∃x (S(x) ∧ T(x))
Example 4: Complex Statement
English: “Every positive integer has a prime factor.”
- Let P(x) = “x is a positive integer”
- Let Q(x, y) = “y is a prime factor of x”
- Translation: ∀x (P(x) → ∃y Q(x, y))
Multiple Quantifiers
We can use multiple quantifiers in a single statement.
Examples
-
∀x ∃y (x + y = 0)
- Meaning: “For every x, there exists a y such that x + y = 0”
- In other words: “Every number has an additive inverse”
- Truth Value: TRUE (y = -x)
-
∃x ∀y (x + y = y)
- Meaning: “There exists an x such that for all y, x + y = y”
- In other words: “There is an additive identity”
- Truth Value: TRUE (x = 0)
-
∀x ∀y (x + y = y + x)
- Meaning: “For all x and y, x + y equals y + x”
- In other words: “Addition is commutative”
- Truth Value: TRUE
Negating Quantified Statements
Rules for Negation
-
¬(∀x P(x)) ≡ ∃x ¬P(x)
- “Not all x satisfy P” ≡ “There exists an x that doesn’t satisfy P”
-
¬(∃x P(x)) ≡ ∀x ¬P(x)
- “There is no x that satisfies P” ≡ “All x don’t satisfy P”
Examples
Example 1:
- Original: ∀x (x > 0)
- “All numbers are positive”
- Negation: ∃x (x ≤ 0)
- “There exists a number that is not positive”
Example 2:
- Original: ∃x (x² = -1) (domain: real numbers)
- “There exists a real number whose square is -1”
- Negation: ∀x (x² ≠ -1)
- “For all real numbers, the square is not -1” (TRUE)
Example 3:
- Original: “All students passed the exam”
- ∀x (S(x) → P(x))
- Negation: “Some student did not pass the exam”
- ∃x (S(x) ∧ ¬P(x))
Example 4:
- Original: “Someone in this class has been to France”
- ∃x (C(x) ∧ F(x))
- Negation: “No one in this class has been to France”
- ∀x (C(x) → ¬F(x))
Common Pitfalls
Pitfall 1: Confusing ∀ with ∧ and ∃ with ∨
Wrong: ∀x (S(x) ∧ P(x)) for “All students passed” Right: ∀x (S(x) → P(x))
Wrong: ∃x (S(x) → P(x)) for “Some student passed” Right: ∃x (S(x) ∧ P(x))
Pitfall 2: Order Matters with Different Quantifiers
- ∀x ∃y (x < y) means “For every x, there’s a bigger y” (TRUE)
- ∃y ∀x (x < y) means “There’s a y bigger than all x” (FALSE - no largest number)
Truth Values with Finite Domains
When domain is finite, we can expand quantifiers:
Universal Quantifier
If domain = {1, 2, 3}, then: ∀x P(x) ≡ P(1) ∧ P(2) ∧ P(3)
Existential Quantifier
If domain = {1, 2, 3}, then: ∃x P(x) ≡ P(1) ∨ P(2) ∨ P(3)
Example
Domain = {1, 2, 3, 4} P(x): “x is even”
- ∀x P(x): P(1) ∧ P(2) ∧ P(3) ∧ P(4) = F ∧ T ∧ F ∧ T = FALSE
- ∃x P(x): P(1) ∨ P(2) ∨ P(3) ∨ P(4) = F ∨ T ∨ F ∨ T = TRUE
Key Points for Exams
- ∀x typically goes with → (“All A are B” = ∀x (A(x) → B(x)))
- ∃x typically goes with ∧ (“Some A is B” = ∃x (A(x) ∧ B(x)))
- To negate, swap quantifiers and negate predicate
- Domain is crucial - always consider what domain you’re working with
- Order matters when mixing ∀ and ∃
- One counterexample disproves ∀, one example proves ∃
- Empty domain: ∀x P(x) is TRUE, ∃x P(x) is FALSE
Practice Problems
-
Let P(x) = “x² > 0”. Is ∀x P(x) true for domain of all real numbers?
-
Translate to logic: “Every student in this class has taken a course in computer science.”
-
Negate: ∀x (x² ≥ 0)
-
Negate: ∃x (x + 3 = 7)
-
What is the truth value of ∃x (x² = -4) for domain of real numbers?
-
Express “No one is perfect” using quantifiers.
-
Let domain = {1, 2, 3}. Evaluate ∀x ∃y (x + y = 4).
-
What’s the difference between ∀x ∃y (x < y) and ∃y ∀x (x < y)?