Predicate Logic (First-Order Logic)

Propositional logic is great for simple true/false statements, but it can’t handle variables. We cannot say “x is even” in propositional logic because $x$ is unknown. Predicate Logic solves this by introducing variables and Quantifiers.

1. Predicates as Functions

A Predicate is a statement whose truth depends on one or more variables. In programming, a predicate is simply a function that returns a Boolean.

# A Predicate function in Python
def is_even(n):
  return n % 2 == 0

# Test the predicate with different values
numbers = [1, 2, 3, 4, 5]
for n in numbers:
  print(f"Is {n} even? {is_even(n)}")

The expression ”$x$ is even” is written as $P(x)$. It is not true or false until you provide an $x$.

2. Quantifiers: For All and There Exists

Quantifiers describe the scope of a predicate over a Domain (a set of objects).

1. Universal ($\forall x$): Reads “For all x…“. The statement is true only if the predicate holds for every element in the domain.
2. Existential ($\exists x$): Reads “There exists an x…“. The statement is true if there is at least one element that satisfies the predicate.

In Python, we use the all() and any() functions to represent these quantifiers.

# Domain of integers
domain = [2, 4, 6, 8, 10]

# Universal Quantifier: Are ALL numbers even?
forall_even = all(n % 2 == 0 for n in domain)

# Existential Quantifier: Does there exist a number > 5?
exists_greater_5 = any(n > 5 for n in domain)

print(f"Domain: {domain}")
print(f"For all n, n is even: {forall_even}")
print(f"Exists n such that n > 5: {exists_greater_5}")

3. Negating Quantifiers

Negating a quantifier flips its type. This is a common point of confusion in both math and natural language.

• $\neg (\forall x, P(x)) \equiv \exists x, \neg P(x)$
  • ”It’s not true that everyone is rich” $\iff$ “There exists someone who is not rich."
• $\neg (\exists x, P(x)) \equiv \forall x, \neg P(x)$
  • "There is no one who is immortal” $\iff$ “Everyone is mortal.”

4. The Order of Quantifiers

When you nest quantifiers, the order matters immensely for the meaning of the statement.

• $\forall x, \exists y$ such that $Father(y, x)$: “Everyone has a father.” (True for humans)
• $\exists y, \forall x$ such that $Father(y, x)$: “There is one man who is the father of everyone.” (False for humans)

Exercises