[ MODULE 02 ]

FIRST-ORDER LOGIC

Propositional logic is rigid. We cannot express "All men are mortal" using just a P and a Q. We must upgrade our syntax to include Variables, Predicates, and Quantifiers.

Predicates: Logic as a Function

In basic logic, "5 is prime" is a static proposition. It is simply True. But what about "x is prime"? This is not a proposition; it's a Predicate. Its truth value depends entirely on what we plug in for x.

We write predicates like mathematical functions: P(x).

The Domain of Discourse

Before we evaluate P(x), we must define what x is allowed to be. This is the Domain of Discourse. If our domain is "all integers," then P(5) is True, and P(4) is False. If our domain is "cars," the predicate breaks!

[ INTERACTIVE LAB ]

P(x) :

Domain Evaluation Mapping

x = 1

FALSE

FAILS

x = 2

TRUE

x = 3

FALSE

FAILS

x = 4

TRUE

x = 5

FALSE

FAILS

x = 6

TRUE

x = 7

FALSE

FAILS

x = 8

TRUE

Final Verification

Statement: ∀x P(x)

FALSE. The Universal Quantifier demands perfection. We found at least one counter-example where P(x) evaluated to FALSE.

The Quantifiers

Now that we have variables and predicates, we need a way to make blanket statements about them. We do this by "binding" the variables with Quantifiers.

∀

The Universal Quantifier

∀x P(x)

"For ALL x, P(x) is true." This is functionally equivalent to a massive chain of AND gates covering the entire domain.

∃

The Existential Quantifier

∃x P(x)

"There EXISTS an x where P(x) is true." This is functionally equivalent to a massive chain of OR gates covering the domain.

[ MODULE VERIFICATION ]

Knowledge Check: First-Order Logic1 / 4

Which of the following is the best definition of a "Predicate"?

Previous: Propositional Next: Set Theory & Paradoxes