Predicate logic explained (with examples)

What is predicate logic and how is it different from propositional logic?

Consider the example:

All men are mortal.

Socrates was a man.

---

Socrates is mortal.

This argument can't be expressed as propositional logic. Notice the keyword "All". Propositional logic only has one variable. However the statement "All men are mortal" is a predicate. It is neither true or false. It is both depending on who the subject is also known as the predicate variable. For example, the statement "Elon Musk is a billionaire" is true, but the statement "I am a billionaire" isn't. Unless, I become one in the coming years.

Predicates

A predicate is a statement that contains variables and that may be true or not depending on the values of these variables.

Predicate: P(x) is a color.

Predicate Instantiated (Proposition): P(red) is a color.

Predicate's domain (values which x can take): {red, green, apple}

You can also think of a predicate as a function.

f(x) = 2x + 10

f(5) = 20

D(domain): R (real numbers)

One important difference is that a function returns a number or an algebraic expression while a predicate returns either a true or false value.

P(red) = True

f(3) = 16 

Universal(∀) and Existential(∃) Quantifiers

Quantifiers tell the amount or quantity of variables in the predicates. 

The Universal(∀) quantifier means "given any" or "all". 

∀x ∊ D, P(x) is a universal statement that means all the elements in D have the property P(x). D can be omitted in cases where it doesn't affect ambiguity.

The statement ∀x ∊ D, P(x) is true if and only if all the elements in D have the property P(x). To prove whether it is true or not, you can either use a counter-example or the method of exhaustion.

Counter-example is a case where P(x) is not true for an element in P(x). For example, consider ∀x ∊ D, P(x) where P(x) is x^2>x. When x is 1 or 0, P(x) is false.

Method of exhaustion is when you check if P(x) is true for all the values of x in D. Consider the same example where P(x) is x^2>x. This time, the domain is {2, 3, 4}. By checking 

2^2=4 4>2

3^2=9 9>3

4^2=16 16>4, we have confirmed the statement is true.

The Existential(∃) quantifier means "there is".

∃x ∊ D, P(x) is an existential statement that means there is at least one element in D that has the property P(x). 

The statement ∀x ∊ D, P(x) is true if some elements in D have the property P(x). You can check whether the statement is true or not by the method of case or the method of exhaustion.

If you can find at least one case where the statement is true, then you have proven the existential quantifier to be true by the method of case.

Statement	∀x ∊ D, P(x)	∃x ∊ D, P(x)
True	P(x) is true for every x value.	There is at least one x for which P(x) is true.
False	There is at least one x where P(x) is false	P(x) is true for all values of x
P(x)	P1(x) ⋁ P2(x) ⋁ ... ⋁ Pn(x)	P1(x) ∧ P2(x) ∧ ... ∧ Pn(x)

Negation of Statements

1. Universal Statement

From the table above, we can see that the negation of a universal statement is equivalent to the existential statement. 

~(∀x ∊ D, P(x)) ≡ ∃x ∊ D, ~P(x)

2. Existential Statement

We can also see that the negation of an existential statement is equivalent to the universal statement. 

~(∃x ∊ D, P(x)) ≡ ∀x ∊ D, ~P(x)

3. Universal Conditional Statements

The universal conditional statement takes the form ∀x ∊ D, P(x) -> Q(x)

Negation takes the form ∃x ∊ D, ~(P(x) -> Q(x)). This can be further simplified using De Morgan's law to ∃x ∊ D, P(x) ∧ ~Q(x)).

4. Nested Quantification

Nested quantification uses multiple quantifications to express statements about elements in a specific domain.

For example: For every car on earth, there is someone who has driven it. 

Symbolized: ∀x ∊ C  ∃y ∊ H, P(x, y)

Negation: ∃x ∊ C  ∀y ∊ H, ~P(x, y)

You can learn more about predicate logic by reading my article on inference rules for predicate logic.