5.2 Predicate logic and quantification

Predicate Logic Fundamentals

Predicate logic expands on propositional logic by letting you look inside sentences. Instead of treating "All students are human" as a single atomic unit, predicate logic breaks it apart into predicates, variables, and quantifiers so you can represent the relationships and generalizations that natural language actually expresses.

Limitations of Propositional Logic

Propositional logic assigns a single letter to an entire sentence (like $P$ = "All students are human"), then connects sentences with logical operators. That's useful for some things, but it has real blind spots:

• It can't capture the internal structure of a sentence. "All students are human" and "Some cats are fluffy" look identical: just $P$ and $Q$.
• It can't represent relationships between entities within a sentence, like who loves whom.
• It has no way to express quantification ("all," "some," "none"), which is central to how meaning works in natural language.

Predicate logic solves all of these problems.

Components of Predicate Logic

There are three core building blocks you need to know:

Predicates represent properties or relations. They take one or more arguments and return a truth value (True or False). By convention, predicates are written with uppercase letters.

• A unary predicate takes one argument: $\text{Student}(x)$ means "x is a student."
• A binary predicate takes two arguments: $\text{Loves}(x, y)$ means "x loves y."
• You can have predicates with three or more arguments too, though unary and binary are the most common in this course.

Variables are placeholders for entities in the domain. They're written with lowercase letters like $x$, $y$, $z$. When you write $\text{Student}(x)$, the $x$ doesn't refer to anyone specific yet; it's waiting to be filled in by a quantifier or an assignment.

Quantifiers tell you how many entities in the domain the formula applies to:

• The universal quantifier $\forall$ means "for all" or "every."
  • $\forall x (\text{Student}(x) \rightarrow \text{Human}(x))$ reads: "For every x, if x is a student, then x is human."
• The existential quantifier $\exists$ means "there exists" or "for some."
  • $\exists x (\text{Student}(x) \land \text{Tall}(x))$ reads: "There exists some x such that x is a student and x is tall."

Notice the pattern: universal quantifiers typically pair with $\rightarrow$ (implication), while existential quantifiers typically pair with $\land$ (conjunction). This is one of the trickiest points in the unit, and mixing them up is a very common mistake. The next section explains why.

Translating and Evaluating Predicate Logic

Translation to Predicate Logic

Translating a natural language sentence into predicate logic takes practice. Here's a reliable process:

1. Identify the predicates. What properties or relations does the sentence mention? Assign each one a predicate name (e.g., $\text{Student}$, $\text{Tall}$, $\text{Loves}$).

2. Identify the quantifier. Does the sentence say "all," "every," "each" (universal)? Or "some," "a," "there exists" (existential)?

3. Choose the right connective. This is where students often slip up:

   • Universal statements use $\rightarrow$ because you're saying if something has one property, then it has another. "All students are human" doesn't claim everything in the domain is a student; it says that if something is a student, then it's human.
   • Existential statements use $\land$ because you're asserting that something is both things at once. "Some students are tall" claims there's at least one thing that is a student and is tall.

4. Assemble the formula using the pieces from steps 1–3.

Here are some worked examples:

• "All students are human" → $\forall x (\text{Student}(x) \rightarrow \text{Human}(x))$
• "Some students are tall" → $\exists x (\text{Student}(x) \land \text{Tall}(x))$
• "If a person is a student and studies hard, then they will pass the exam" → $\forall x ((\text{Student}(x) \land \text{StudiesHard}(x)) \rightarrow \text{PassExam}(x))$

A common error to watch for: writing $\forall x (\text{Student}(x) \land \text{Human}(x))$ for "All students are human." That formula claims everything in the domain is both a student and human, which is much stronger (and almost certainly false).

Truth Values in Predicate Logic

To evaluate whether a predicate logic formula is true, you need a model (also called an interpretation). A model specifies two things: a domain of entities and the truth value of each predicate for each entity in that domain.

Here's how evaluation works, step by step:

1. Look at the domain. Which entities are you checking?
2. Check the formula for each entity (for universal) or look for at least one entity that works (for existential).
3. Compute the truth value of the inner formula for each relevant entity using the predicate assignments and logical connectives.
4. Combine the results. A universally quantified formula is true only if the inner formula is true for every entity. An existentially quantified formula is true if the inner formula is true for at least one entity.

Worked example:

• Formula: $\forall x (\text{Student}(x) \rightarrow \text{Human}(x))$
• Model: Domain = {Alice, Bob}; $\text{Student}(\text{Alice})$ = True, $\text{Student}(\text{Bob})$ = False, $\text{Human}(\text{Alice})$ = True, $\text{Human}(\text{Bob})$ = True

Evaluation:

• For Alice: $\text{Student}(\text{Alice}) \rightarrow \text{Human}(\text{Alice})$ = True $\rightarrow$ True = True
• For Bob: $\text{Student}(\text{Bob}) \rightarrow \text{Human}(\text{Bob})$ = False $\rightarrow$ True = True

Both entities satisfy the formula, so $\forall x (\text{Student}(x) \rightarrow \text{Human}(x))$ is true in this model.

Notice the Bob case: he's not a student, so the implication is vacuously true. Remember that $\text{False} \rightarrow \text{anything}$ is always True in classical logic. This is why $\rightarrow$ is the right connective for universal statements: non-students don't make the claim false; they simply aren't relevant to it.