Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 4.1.2 Predicates and Quantifiers

In the system we are about to define, we’ll be able to write things like this:

[1] ∀x (Bear(x) → HasTail(x))

[2] ∀x (HasTail(x) → Stompable(x))

[3] ∀x (Bear(x) → ∃y (MotherOf(y, x)))

[4] ∀x (∀y (MotherOf(y, x) ∨ FatherOf(y, x) → ParentOf(y, x)))

[5] ∀x (Employee(x) → ∃y (CurrentProjectOf(y, x)))

Read these statements as follows:

1. All bears have tails. (More literal reading of the symbols: For every object x, if x is a bear then x has a tail.)

2. Anything that has a tail is stompable.

3. Every bear has a mother. (More literal reading: For every object x, if x is a bear then there exists some object y such that y is the mother of x.) Notice that it’s not necessarily the same mother for everyone.

4. If you’re either the mother of someone or their father, you’re their parent. (More literal reading: For any objects x and y, if y is x’s mother or x’s father, then y is x’s parent.)

5. Every employee is currently assigned to at least one project. (More literal reading: For every x, if x is an employee then there exists some y such that y is a current project of x). Notice that we’ve just said that there exists some project. There may exist several.

Notice a few key things about these predicate logic statements:

• There’s a universe of objects that we can talk about. We’ll see that that universe may be finite or (and this happens in some very important cases, like when we want to reason about numbers) the universe may be infinite.

• We assert properties (such as Bear, HasTail, Stompable, or MotherOf) about objects in the universe. Some properties (such as being a Bear) apply to individual objects. Others (such as MotherOf, ParentOf, and CurrentProjectOf) relate objects to other objects.

• We will use the same logical operators (including ∨, ∧, →, ¬ and ≡) that we used in Boolean logic. They’ll have the same meanings here.

• There are two new symbols, which we’ll call quantifiers:

• ∀, which we’ll read as, “for all”. Remember this: It’s an upside down A (as in All).

• ∃, which we’ll read as, “there exists”. Remember this: It’s a backwards E (as in Exists).