Advanced First-Order Logic
Introduction to First-Order Logic
Beyond True or False
In propositional logic, we work with simple statements that are either true or false. Think of sentences like "It is raining" or "The cat is on the mat." This is useful, but it has limits. We can't talk about what is raining or which cat is on the mat. We can't make general statements about all cats or some raindrops.
First-order logic (FOL), also called predicate logic, gives us a more powerful toolkit. It lets us look inside our statements to talk about specific objects, their properties, and their relationships with other objects. If propositional logic sees sentences as sealed boxes labeled "true" or "false," first-order logic opens the boxes to see what's inside.
| Feature | Propositional Logic | First-Order Logic |
|---|---|---|
| Basic Unit | Simple propositions (e.g., P) | Predicates with arguments (e.g., Cat(x)) |
| Scope | Whole sentences | Objects and their relationships |
| Expressiveness | Limited | High (can express generalizations) |
At its heart, FOL is built on a few key ideas.
Predicate
noun
A statement about the properties of an object or the relationship between objects. It acts like a template that becomes true or false when objects are plugged in.
For example, IsBlue(x) is a predicate. It doesn't mean anything on its own. But if we replace the variable x with an object, like 'the sky', we get IsBlue(the sky), which is a true statement. We can also have predicates that describe relationships between multiple objects, like TallerThan(Alice, Bob).
Everyone or Just Someone
The real power of first-order logic comes from its ability to make general statements using quantifiers. Instead of just talking about one specific thing, we can talk about all things or some things.
First, we have the universal quantifier. It lets us say that a property is true for everything in a certain group.
Next, we have the existential quantifier. This lets us say that there is at least one thing with a certain property.
Adding Functions
Finally, first-order logic includes functions. In this context, a function isn't a piece of code. It's a way to refer to a specific object without naming it directly. A function takes one or more objects as input and returns a single object.
For instance, we could have a function MotherOf(x). If we plug in 'Alice', the function MotherOf(Alice) would refer to Alice's mother. We can then use this inside a predicate. For example, to say that Alice's mother is a doctor, we could write:
IsDoctor(MotherOf(Alice))
This lets us build very complex and precise statements by combining functions, predicates, and quantifiers.
What is a key capability of first-order logic that is not present in propositional logic?
Consider the statement: "All lions are predators." How would this be expressed in first-order logic, using Lion(x) for "x is a lion" and Predator(x) for "x is a predator"?