Introduction to Predicate Logic

Predicate Logic: A Complete Overview Predicate logic, also known as first-order logic, is a powerful extension of propositional logic that allows us to reason about objects and their properties. While propositional logic deals only with statements that are true or false, predicate logic lets us make claims about specific things and express patterns that hold across entire groups of objects. This makes it far more useful for mathematics, computer science, and formal reasoning in general. Key Components of Predicate Logic To understand predicate logic, you need to know its main building blocks: variables, predicates, and quantifiers. Variables like $x$, $y$, and $z$ represent objects in whatever collection of things we're talking about. Think of them as placeholders for specific individuals—they could be numbers, people, or anything else depending on context. Predicates are symbols that describe properties or relationships. A predicate is like a function that takes one or more variables and produces a statement that can be true or false. A unary predicate describes a property of a single object. For example, $P(x)$ might mean "$x$ is prime" or "$x$ is a student." When we write $P(3)$, we're asking whether 3 has property $P$. A binary predicate describes a relationship between two objects. For example, $R(x, y)$ might mean "$x$ is taller than $y$" or "$x$ loves $y$." Higher-arity predicates describe relationships among three or more objects, though binary and unary predicates are most common. The key insight is that predicates let us express general patterns. Instead of just saying "Alice is tall" and "Bob is tall," we can express the general pattern that certain things have the property of being tall. Quantifiers: Expressing "All" and "Some" Quantifiers allow us to make claims about multiple objects at once. There are two main quantifiers in predicate logic. The universal quantifier ($\forall$) means "for all" or "every." The formula $\forall x\, P(x)$ reads as "for all $x$, property $P$ holds" or simply "every $x$ has property $P$." This statement is true only if $P$ is true for every possible object in our domain. For example: $\forall x\, \text{Prime}(x)$ would mean "every number is prime" (which is false) $\forall x\, (\text{Student}(x) \rightarrow \text{Has-ID}(x))$ means "if something is a student, then it has an ID" The existential quantifier ($\exists$) means "there exists" or "some." The formula $\exists x\, P(x)$ reads as "there is at least one $x$ with property $P$." This statement is true if $P$ is true for at least one object in our domain—it doesn't need to be true for all. For example: $\exists x\, \text{Prime}(x)$ means "there exists at least one prime number" (which is true) $\exists x\, \text{Loves}(x, \text{pizza})$ means "someone loves pizza" An important point about scope: Quantifiers bind their variables and limit their scope. When we write $\forall x\, P(x)$, the variable $x$ is bound by the quantifier—it only has meaning within that formula. This matters when we have multiple quantifiers, which we'll discuss below. Domain of Discourse Every statement in predicate logic is interpreted relative to a domain of discourse (also called a universe). This is simply the set of all objects that our variables can refer to. The domain of discourse is crucial because it determines what our statements mean: If we say $\forall x\, \text{Prime}(x)$ with domain = {2, 3, 5, 7}, this is true If we say $\forall x\, \text{Prime}(x)$ with domain = {1, 2, 3, 4, 5}, this is false (because 1 and 4 aren't prime) The same formula has different truth values depending on the domain! Some common domains include: Natural numbers: {0, 1, 2, 3, ...} Real numbers: all decimals, fractions, and irrational numbers People in a specific group: all students in a class, all employees at a company Geometric objects: all points, lines, or triangles Always remember: when you encounter a predicate logic formula, the interpretation depends on knowing both the formula itself and the domain of discourse you're working with. Putting It Together: Multiple Quantifiers When we combine quantifiers, we can express more complex statements. The order of quantifiers matters greatly! Consider these two statements about a domain of people: $$\forall x\, \exists y\, \text{Loves}(x, y)$$ This reads: "For every person $x$, there exists a person $y$ such that $x$ loves $y$." In other words, everyone loves someone (though not necessarily the same person). $$\exists y\, \forall x\, \text{Loves}(x, y)$$ This reads: "There exists a person $y$ such that for all people $x$, $x$ loves $y$." In other words, there is someone who is loved by everyone. These mean completely different things! The first allows different people to love different people. The second requires one special person who is universally loved. When you're reading quantified formulas, always pay attention to the order. Formal Examples Here are some typical statements you'll see: "Every natural number has a successor" becomes: $\forall n\, \exists m\, \text{Successor}(n, m)$ "Some student loves calculus" becomes: $\exists s\, \text{Loves}(s, \text{calculus})$ "No prime number is composite" becomes: $\forall x\, (\text{Prime}(x) \rightarrow \neg \text{Composite}(x))$ Translating Between English and Predicate Logic One of the most important practical skills in logic is translating between English sentences and formal notation. This requires you to: Identify the domain of discourse — What objects are we talking about? Identify the relevant predicates — What properties or relationships matter? Identify the quantifiers — Are we talking about all objects or just some? From English to Logic: "All dogs are animals" Domain: living things (or just all dogs and animals) Predicate: $\text{Dog}(x)$, $\text{Animal}(x)$ Formula: $\forall x\, (\text{Dog}(x) \rightarrow \text{Animal}(x))$ "Some students passed the exam" Domain: students Predicate: $\text{Passed}(x)$ Formula: $\exists x\, \text{Passed}(x)$ From Logic to English: $\forall x\, \text{HasWings}(x) \rightarrow \text{CanFly}(x)$ reads as: "Everything that has wings can fly" $\exists x\, (\text{Red}(x) \land \text{Apple}(x))$ reads as: "There exists something that is both red and an apple" or simply "There is a red apple" The key is to be precise about what each symbol means and to ensure your English translation captures the logical structure. Inference Rules in Predicate Logic Predicate logic has inference rules—logical moves we can make that guarantee we'll reach true conclusions from true premises. Here are the most important ones: Modus Ponens remains valid in predicate logic: If we know that $P \rightarrow Q$ and we know $P$ is true, we can conclude $Q$ is true. Universal Instantiation lets us apply a universal statement to a specific case. If we know $\forall x\, P(x)$ (property $P$ holds for everything), we can conclude $P(c)$ for any specific object $c$ in our domain. For example, if we know "All humans are mortal" ($\forall x\, \text{Mortal}(x)$, assuming humans are our domain), we can conclude that Socrates is mortal: $\text{Mortal}(\text{Socrates})$. Existential Generalization works in the opposite direction. If we know some specific object $c$ has property $P$ (we know $P(c)$), we can conclude that there exists something with property $P$: $\exists x\, P(x)$. For example, if we know "Alice is a programmer," we can conclude "There exists a programmer." These rules, along with others, form the basis of proof systems like natural deduction and resolution. These proof systems let us derive new conclusions from given premises in a systematic, reliable way—which is exactly what we need for formal reasoning. Syntax and Semantics: The Two Sides of Logic Understanding predicate logic requires understanding both how formulas are structured and what they mean. Syntax is about form and structure. The syntax of predicate logic defines which strings of symbols are well-formed formulas (formulas that follow the grammatical rules). For instance, $P(x) \land Q(y)$ is well-formed, but $P \land \land Q$ is not—the second expression violates the rules of syntax. Semantics is about meaning and truth. The semantics of predicate logic tells us how to assign truth values to formulas. To evaluate whether a formula is true or false, we need an interpretation, which consists of three things: A domain of discourse — the set of objects variables can refer to Meanings for predicates — what does each predicate symbol mean? Which objects have which properties? Variable assignments — what does each variable refer to? For example, to evaluate $P(x)$ where $P$ means "is prime": Domain: natural numbers {1, 2, 3, 4, 5, ...} Predicate meaning: $P(n)$ is true if $n$ is prime Variable assignment: if $x = 2$, then $P(x)$ is true; if $x = 4$, then $P(x)$ is false The same syntactic formula can have different truth values under different interpretations. A formula is valid if it's true under every possible interpretation; it's satisfiable if there exists at least one interpretation making it true. This distinction between syntax (how formulas look) and semantics (what they mean) is fundamental to understanding why certain logical moves are justified—they're justified precisely because they preserve truth under all interpretations.