10: Predicate Logic
( \newcommand{\kernel}{\mathrm{null}\,}\)
Table of contents
Part 9: Predicate Logic
Why Predicate Logic Matters
Propositional logic treats entire statements as indivisible units (propositions). But often we want to talk about properties of objects or relationships between objects. For example, "All cats are mammals" or "Some numbers are prime." Propositional logic can't easily express "all" or "some" — it would just see "All cats are mammals" as a single black box statement. Predicate logic (also known as first-order logic) allows us to peek inside that box. It lets us use variables and quantifiers to say things about many instances at once, greatly expanding the expressiveness of our logic.
In simpler terms, predicate logic answers questions like: - How do we say every member of a category has some property?
- How do we say there exists something with a certain property?
These abilities are crucial in mathematics, computer science (database queries, AI), and philosophy.
From Aristotle to Modern Logic
Aristotle's syllogisms (e.g., "All men are mortal; Socrates is a man; therefore Socrates is mortal") were an early form of predicate logic dealing with categories and membership. Modern predicate logic (developed by Frege in 1879 and others) formalized these ideas with quantifiers and variables, laying the groundwork for much of modern mathematics and computer science.
From Propositions to Predicates
A predicate is like a property or relation that can be true or false of something. It’s often represented as a capital letter with parentheses, e.g.
Example: Let
Quantifiers: Universal and Existential
Predicate logic introduces quantifiers to indicate how many or which elements of the domain we’re talking about:
-
Universal Quantifier (
): Means "for all" or "for every".∀
says "for all∀xP(x) ,x is true." (EveryP(x) has propertyx .)P -
Existential Quantifier (
): Means "there exists" or "for at least one".∃
says "there exists at least one∃xP(x) such thatx is true." (SomeP(x) has propertyx .)P
Let's see them in use:
"All" statements (Universal)
-
All cats are mammals.
Domain: animals.
Let = "x is a cat",C(x) = "x is a mammal."M(x)
In logic: .∀x(C(x)→M(x))
This says: for every creature , ifx is a cat, thenx is a mammal.x -
No dogs can fly.
Let = "x is a dog",D(x) = "x can fly."F(x)
"No dogs can fly" can be written as: .∀x(D(x)→¬F(x))
(For every , ifx is a dog, thenx cannot fly.)x
Alternatively, one could write
"Some" statements (Existential)
-
There exists a prime number greater than 100.
Domain: numbers.
Let = "x is prime",P(x) = "x > 100$.G(x)
In logic: .∃x(P(x)∧G(x))
(There is at least one number such thatx is prime andx .)x>100 -
Someone in the class speaks French.
Domain: people (in the class).
Let = "x speaks French."F(x)
says "There is at least one person∃xF(x) such thatx speaks French."x
Combining Quantifiers and Logic
We can make more complex statements:
-
"Every even number greater than 2 is not prime."
Domain: natural numbers.
= "x is even",E(x) = "x is prime",P(x) = "x > 2$.G(x)
Logic: .∀x((E(x)∧G(x))→¬P(x))
(For any number, if it's even and >2, then it is not prime.) -
"There is a student who is in both the chess club and the debate club."
Domain: students.
= "x is in the chess club",C(x) = "x is in the debate club".D(x)
.∃x(C(x)∧D(x))
(At least one student is in both clubs.)
Translating 'none' or 'no one'
Statements like "No
- Universal form:
- Negated existential form:
These are equivalent: saying no
Domains and Scope of Quantifiers
When we write
Quantifiers have a scope similar to how parentheses or logical operators have scope. For example, in
If we need multiple quantifiers, we can use different variables or nest them:
-
"Every student admires some professor."
Domain: people at a university.
Let = "x is a student",S(x) = "y is a professor",Prof(y) = "x admires y".A(x,y)
Logic: .∀x[S(x)→∃y(Prof(y)∧A(x,y))]
(For each person x, if x is a student, then there exists at least one person y who is a professor and x admires y.) -
Order matters for different quantifiers:
is not the same as∀x∃yA(x,y) . The first says "for each∃y∀xA(x,y) , you can find a (potentially different)x such thaty ." The second says "there is a singleA(x,y) that works for everyy ." This distinction is huge.x
Order of Quantifiers
Pay attention to quantifier order:
-
-
These can mean very different things. For example, "For every person, there is someone whom they love" versus "There is a person whom everyone loves."
Translating Between English and Predicate Logic
It takes practice to capture English precisely in symbols:
- Each, every, all
→∀ - Some, there is/are, at least one
→∃ - None, no
use→ with a negation, or∀ ¬∃
Example translations:
-
"Every car has wheels."
Domain: vehicles (or things).
= "x is a car",C(x) = "x has wheels".W(x)
.∀x(C(x)→W(x)) -
"Some cars have no wheels."
= "x is a car",C(x) = "x has wheels".W(x)
.∃x(C(x)∧¬W(x))
(There exists an object that is a car and does not have wheels — perhaps this is false in reality, but that's the logical form.) -
"Not every car has wheels."
This is the negation of "every car has wheels."
We can write: , which is equivalent to¬∀x(C(x)→W(x)) which simplifies to∃x¬(C(x)→W(x)) .∃x(C(x)∧¬W(x))
So "Not all have wheels" means "Some car has no wheels" — note how English "not every" turns into an existential statement logically. -
"At least two people have the same birthday." (A bit trickier)
Domain: people.
= "PersonB(x,d) has birthday on datex ".d
One way: .∃x∃y∃d[(x≠y)∧B(x,d)∧B(y,d)]
(There exist two different people andx and a datey such thatd andx both have birthdayy .)d
Real-World Applications of Predicate Logic
- Database Queries: SQL and other query languages are built on predicate logic. A query like "SELECT * FROM Employees WHERE age > 30 AND department = 'Sales'" is basically finding all
such thatx andAge(x)>30 .Dept(x," - Artificial Intelligence: Knowledge representation often uses first-order logic to encode facts and rules. E.g., in an expert system:
encodes a general fact about the world. - Mathematics: Almost all definitions and theorems in mathematics are expressed in predicate logic ("For every
, there exists a such that ...", which is a statement). - Formal Verification: When verifying hardware or software, one often writes specifications like "for all possible inputs satisfying condition P, the output will satisfy Q" (
) and uses automated theorem provers to check it.
Common Misconceptions
-
"
means the same as for a generic x."
Reality: means every possible x in the domain makes true. You can't assume a specific one without stating it. It's a statement about the entire domain at once. -
"
asserts the existence but we know nothing else about that x."
Reality: Yes, existential just guarantees at least one exists, but we usually can't give it a name unless we use a witness. It's a logical guarantee without identification (unless the context or proof finds a concrete example). -
"If
is true, then must be true."
Reality: True. If everything has property P, certainly at least one thing does. (In logic, implies provided the domain is nonempty. Usually we assume domains are nonempty.) -
"If
is true, then might be true."
Reality: Having one example doesn't mean all have it. E.g., "There exists a number that is even" is true, but "For all numbers, they are even" is false. - Mixing up
and : It's common but critical to keep them straight. "Every" vs "Some" are not interchangeable.
Exercises
9.1. Translate into predicate logic: "All birds can fly." (Define appropriate predicates for being a bird and being able to fly.)
9.2. Translate: "Some birds cannot fly." (You might know real examples, but just do it logically.)
9.3. Translate: "Every student in this class has taken at least one programming course." (Define predicates like
9.4. Translate: "There is a prime number that is even." (Remember what the only even prime is!)
9.5. Consider the statement: "If a number is rational, then it can be written as a ratio of two integers." Express this as a logical statement with a universal quantifier. (Let
9.6. Express the negation of the statement in 9.5 in a normalized way (so that negation symbol directly precedes the predicate, not the quantifier). Explain the meaning of the negation in words.
9.7. Translate: "Not every book is interesting." Then contrast it with "No book is interesting." (They are different! Provide both translations.)
9.8. Translate: "Everyone has exactly one mother." (Hint: This one is a bit advanced. It means: for every person
9.9. Is the following statement true or false (in ordinary arithmetic)? "For every integer
9.10. Explain in your own words the difference between
Advanced: Predicate logic is a powerful tool, but with great power comes additional complexity. In further studies, you'll encounter concepts like relations, functions, multiple quantifiers, and even logical paradoxes that arise with unrestricted domains (like Russell's paradox about "the set of all sets that don't contain themselves"). Predicate logic is the gateway to these deeper explorations, including the foundations of mathematics and computer science.