Predicate Logic

Dr. Ryan Learn

WSU-Tricities
The Need for Predicate Logic

Consider the logical argument

All men are mortal
Socrates is a man
Therefore Socrates is a mortal

Is this argument valid? Can you prove such? Is it an argument we

have seen before?

1
Now obviously this is a valid logical statement, but proving it goes
beyond the logic we’ve yet covered in this class.
You might get clever and try use modus ponens

p→q
p
. ˙ .q

But what are p and q?

2
It turns out that words like all or some, take us beyond the
propostional logic we’ve considered so far. They require us to step
back, break our statements up into their component parts, and
introduce variables.
Such logical expressions bring us to the realm of predicate logic.

3
Consider the statement
He is an instructor at WSU-TC

Now this is not a statement, as we don’t know who he is. This

statement is true for certain values of he, and false for others.
Because this expression is both true and false, it’s not a statement.
We can modify it shough
Dr. Learn is an instructor at WSU-TC

This is a statement, a true one, at that.

We can slpit this statement up into

• Subject: Dr. Learn

• Predicate: is an instructor at WSU-TC

4
We can break this predicate up into it’s modifiers.
If we let x denote any person, we can then write the phrase.
x is an instructor at WSU-TC

We can further break this down into

P = is an instructor at WSU-TC
Q = is an instructor at

This lets me write

x is an instructor at WSU-TC

As

P(x)

5
Or
x is an instructor at y

as

Q(x, y)

P, Q are predicate symbols and x, y are predicate variables

Now what happens when I plug in a given x and y into my predicate?

Q(x, y) ≡ x is an instructor at y

6
Predicate Examples

Q(x, y) ≡ x is an instructor at y

1. x = Dr. Learn , y = Harvard

2. x = WSU-TC , y = Dr. Learn
3. x = Dr. Learn , y = WSU-TC

7
Predicate Examples

Q(x, y) ≡ x is an instructor at y

1. x = Dr. Learn , y = Harvard

This is a false statement
2. x = WSU-TC , y = Dr. Learn
This is a nonsensical, false statement
3. x = Dr. Learn , y = WSU-TC
This is a true statement

Predicate + Defined Predicate Variables = Statement

8
Predicates

Definition
A predicate is a sequence that contains a finite number of variables
a becomes a statement when specific values are substituted for the
variables. The domain of the predicate variable is the set of all
values that may be substituted in place of the variables.

9
Predicate Truth Values EXamples

Let P be the predicate symbol divided by two is an integer. Identify

the truth value of the following statements from the domain of R

1. P(2)
2. P(0)
3. P(1)
4. P(16/2)

10
Predicate Truth Values EXamples

Let P be the predicate symbol divided by two is an integer. Identify

the truth value of the following statements from the domain of R

1. P(2)

2
= 1, 1 ∈ Z, TRUE
2
2. P(0)
0
= 0, 0 ∈ Z, TRUE
2
3. P(1)
1
= 0.5, 0.5 ̸∈ Z, FALSE
2
4. P(16/2)
16
= 4, 4 ∈ Z, TRUE
4
What set of numbers makes the resulting statement P(x) true?
11
Quantifiers

Plugging in a specific value for a predicate variable allows you to

turn a predicate into either a true or false statement, but you can
also use quantifiers. Quantifiers are words such as some, all, most
If I say x is an integer, this is not a statement, it’s not true or false
until I know what x is.
If I say some real number x is an integer, this is a statement. It is
either true or false.

12
Universal Quantifier

When we wish to make a universal statement, we say that all of the

members of the domain have some property.
This quantifier is denoted ∀ and is said ”for all”.
So now we can write something like.
For all human beings x, is is mortal
Socrates is a human being
Therefore, Socrates is mortal.

13
Or, symbollically,letting P be is mortal, and D be all human beings.

∀x ∈ D, P(x)
s∈D
. ˙ .P(s)

14
Domain of the Universal Statement

Notation
The domain D of a the predicate variable can fall between the
universal qualifier symbol and the variable, as in

∀ real numbers x

Or it can follow the predicate variable, as seen in the form

∀x ∈ R

15
Universal Statements

Definition
Let Q(x) be a predicate and D the domain of x. A universal
statement of the form ∀x ∈ D, Q(x) is defined to be true iff Q(x) is
true for every x ∈ D; it is false iff there is atleast one x such that
Q(x) is false.
A value x ∈ D for which Q(x) is false is called a counter-example to
the statement ∀x ∈ D, Q(x)

Find an counterexample for the statement

∀x ∈ Znon-neg , Q(x)

Q = divide by 2 is positive

16
Universal statement examples

Let D = {1, 2, 3, 4, 5}, consider the statements

1. ∀x ∈ D, x2 ≥ x
2. ∀x ∈ D, x2 > x

Show that each statement is true or false.

17
Existential Quantifier

Instead of saying that all members of some domain can be

substituted in for a predicate variable to make the predicate true, we
may instead wish to claim that at least one of them exists. In that
case, we’re back in the realm of an existential statement.
There exists some integer, x, such that x times any real num-
ber k is x

This can be rewritten using the existential quantifier symbol, ∃

∃x ∈ R |xk = x

18
Existential Quantifier

Definition
Let Q(x) be a predicate and D the domain of x, an existential
statement is a statement of the form ∃x ∈ D such that Q(x). It is by
definition true iff Q(x) is just for at least one x in D. It is false, iff
Q(x) is false for all x in D.

19
Existential Predicate Example

Showing that an existential statement is true is done just like

showing a universal statement is fale; by finding an x ∈ D such that
the predicate statement is true; as soon as you have found one,
you’ve shown that the existential statement is true.

1. ∃m ∈ Z+ such that m2 = m
2. Let E = {5, 6, 7, 8}. ∃m ∈ E such that m2 = m

20
Universal Conditional Statements

As we discussed previously when learning how to speak

mathematically, we can consider compound statements, one of
which took the form of a universal conditional statement, these take
the form.
For all x in D, if P is true of x, Q is also true for x.

Or, semi-symbolically.

∀x ∈ D, if P(x), then Q(x)

21
1. Using the notation we’ve covered so far, try to write the
statement
P(x) does not imply Q(x)

22
Negations of Universal Statements

The negation of a universal statement is not simply the changing of

All to None
Consider the statement.
All students will get A’s in this class.

What would the negation of this be, is it?

No students will get A’s in this class

No! It’s simply

Not all students will get A’s in this class

What is that equivalent to?

23
The negation of a universal statement

∀x ∈ D, Q(x)

is logically equivalent to a statement of the form

∃x ∈ D such that ∼ Q(x)

That is:

∼ (∀x ∈ D, Q(x)) ≡ ∃x ∈ D such that ∼ Q(x)

24
Negations of Existential Statements

To negate a statement of the form

∃x ∈ D such that Q(x)

We assert that no such x exists.

Consider the statement
There is someone in this class who will fail for cheater

What’s the negation of that?

25
The negation of a statement of the form

∃x ∈ D such that Q(x)

Is logically equivalent to the universal statement that all are not Q(x)

∀x ∈ D, ∼ Q(x)

Symbolically

∃ ∈ D such that Q(x) ≡ ∀x ∈ D, ∼ Q(x)

26
Negations of Universal Conditional Statements

Recall that teh negation of a conditional statement of the form

∼ (p → q)

Is logically equivalent to the and statement

p∧ ∼ q

We can do apply the same to the negation of a universal conditional

statement, combining it with the negation of our universal statement.

27
Our universal conditional statement has the form

∀x, P(x) → Q(x)

So the negation of that is

∼ (∀x, P(x) → Q(x))

Which, we just covered, is the equivalent of the existential statement

that one is not.

∃x such that ∼ (P(x) → Q(x))

Now negating the conditional portion:

∃x such that P(x)∧ ∼ Q(x))

28
Consider the predicate statement
For all the students in my class, if the student studies, then
they will get an A on the test.

The negation of this is, following the form we just covered:

There exists a student in my class who will study and not get
an A on the test.

Here we had

• s, the student variable

• C the class
• P(s): s studies
• Q(s): s get’s an A on the test

∼ (∀s ∈ C, P(s) → Q(s)) ≡ ∃s ∈ C such that P(s)∧ ∼ Q(s)

29
Relation to De Morgans laws

Consider I have a domain D = {1, 2, 3, 4, 5}

I could write the statement

∀n ∈ D, n ≤ 4

Let the predicate statement P be ≤ 4. At that point I can rewrite my

universal as

P(1) ∧ P(2) ∧ P(3) ∧ P(4) ∧ P(5)

Now negate that via De Morgans law and we find that

∼ (P(1)∧P(2)∧P(3)∧P(4)∧P(5)) ≡∼ P(1)∨ ∼ P(2)∨ ∼ P(3)∨ ∼ P(4)∨ ∼ P(5)

30
∼ (P(1)∧P(2)∧P(3)∧P(4)∧P(5)) ≡∼ P(1)∨ ∼ P(2)∨ ∼ P(3)∨ ∼ P(4)∨ ∼ P(5)

What is the chain of OR statements saying?

It’s saying that for at least one of them, Q(n) is false, or...

∃n ∈ D such that ∼ Q(n)

31
Contrapositive, Converse, and Inverse of Universal Conditionals

Just like a conditional statement had inverses, converses, and

contrapositives, a universal conditional statement also them
Definition
Given a coniditional statement of the form

∀x ∈ D, P(x) → Q(x)

We can define

1. The Contrapositive:

∀x ∈ D, ∼ Q(x) →∼ P(x)

32
2. The Converse:

∀x ∈ D, Q(x) → P(x)
3. The Inverse:

∀x ∈ D, ∼ P(x) →∼ Q(x)

33
Converse, Inverse, Contrapositive

Conisder the statement

∀x ∈ R, x > 2 → x2 > 4

Determine the contrapositive,converse, and inverse and establish

their truth values.

34
1. Contrapositive

∀x ∈ R, x2 ≤ 4 → x ≤ 2
2. Converse

∀x ∈ R, x2 > 4 → x > 2
3. Inverse

∀x ∈ R, x ≤ 2 → x2 ≤ 4

35
Vacuous Truths

Consider the statement

All the graduate students in this class will get A

Now the negation of this is

There exists a graduate student in this class who will not get
an A

But! There are not any graduate students in this class. So is this
statement true or false?
It is was known as a vacuous truth

36
Vacuous Truths

Definition
For a universal conditional statement of the form

∀x ∈ D, P(x) → Q(X)

this statement is known as vacuously true iff P(x) is false for all
x∈D

Symbolically, we might write

∀x ∈ D, ∼ P(x)

37
Multiply Quantified Statements

Consider the statement

There is a person supervising every detail of the production
process

Does this mean that there is a single person supervising every single
detal of the process, or that for every detail of the production
process, someone is supervising it?
It turns out that this ambiguous, it either is technically correct.

38
When we encounter statements which more than one ∃ or ∀ appears,
we adopt the convention of interpreting them from right to left.
Consider the statement
For all real numbers x, there exists an integer y such that
0≤x−y≤1

This means, for any of the real numbers that you pick, x, you can
then pick a certain y such that P(x, y) is true.
This is not saying that there is some single integer y which makes
P(x, y) true for every single choice of x.
x gets chosen first, and then y

39
Alternatively, consider the statement
There exists an integer y such that all real numbers multiplied
by this integer yields that integer.

This is suggesting that a single y makes the predicate true regardless

of your choice of real number x.

40
Tarski’s World

Figure 1: An Example of Tarski’s World setup

41
Interpreting Statements with Two Different Quantifiers

Given a statement of the form

∀x ∈ D, ∃y ∈ E|P(x, y)

Proving the truth of this requires picking any x ∈ D, and finding a

y ∈ E such that the statement P(x, y) is true for that particular
chosen x value.
Given a statement of the form

∃x ∈ D|∀y ∈ E, P(x, y)

Proving it’s truth requires finding a single x ∈ D value that makes

P(x, y) true for any y ∈ E

42
Multiple Quantifiers Example

A college cafeteria line has four stations: salads, main courses,

desserts, and beverages.
The salad station offers a choice of green salad or fruit salad; the
main course station offers spaghetti or fish; the dessert station offers
pie or cake; and the beverage station offers milk, soda, or coffee.
Three students, Uta, Tim, and Yuen, go through the line and make the
following choices:
Uta: green salad, spaghetti, pie, milk
Tim: fruit salad, fish, pie, cake, milk, coffee
Yuen: spaghetti, fish, pie, soda

43
Evaluate the following statement:

∃ an item I |∀ students S, S chose I

44
Evaluate the following statement:

∃ a student S |∀ items I, S chose I

45
Evaluate the following statement:

∃ a student S |∀ stations Z, ∃ an item I ∈ Z | S chose I

46
Evaluate the following statement:

∀ students S and ∀ stations Z, ∃ an item I ∈ Z | S chose I

47
Converting from informal to formal language

Give the formal notation for the following statements

1. Every nonzero real number has a reciprocal.

2. There is a real number with no reciprocal.

48
Give the formal notation for the following statements

1. Every nonzero real number has a reciprocal.

∀x ∈ R̸=0 , ∃y ∈ R|x × y = 1

2. There is a real number with no reciprocal.

∃x ∈ R|∀y ∈ R, x × y ̸= 1

49
Negations of multiply quantified statements

If we wish to negate our statement with multiple quantifiers, we

make use of our negation rules for existential and universal
statements discussed earlier.

∼ (∀x ∈ D, P(X)) ≡ ∃x ∈ D| ∼ P(x)

∼ (∃x ∈ D|P(x)) ≡ ∀x ∈ D, P(x)

We can then apply them to some multiply quantified statement to

find it’s negation.

∼ (∀x ∈ D, ∃y ∈ E|P(x, y))

50
 ∼ (∀x ∈ D, ∃y ∈ E|P(x, y))

We negate by going left to right;

First, we negate the ∀ term, yielding

∃x ∈ D| ∼ (∃y ∈ E|P(x, y))

Then we negate the existential statement, yielding in the end

∃x ∈ D|∀y ∈ E, ∼ P(x, y)

∼ (∀x ∈ D, ∃y ∈ E|P(x, y)) ≡ ∃x ∈ D|∀y ∈ E, ∼ P(x, y)

51
Use the rules of negation for universal and existential statements to
find the negation of the following

∼ (∃x ∈ D|∀y ∈ E, P(x, y))

52
Use the rules of negation for universal and existential statements to
find the negation of the following

∼ (∃x ∈ D|∀y ∈ E, P(x, y))

First, we apply it to our existential to make it a universal

∀x ∈ D, ∼ (∀y ∈ E, P(x, y))

Then to our existential

∀x ∈ D, ∃y ∈ E| ∼ P(x, y)

53
Definition
The negation of a universal existential statement is an existential
universal statement with a negated predicate.

∼ (∀x ∈ D, ∃y ∈ E|P(x, y) ≡ ∃x ∈ D|∀y ∈ E, ∼ P(x, y)

The negation of an existential universal statement is a universal

existential statement with a negated predicate.

∼ (∃x ∈ D|∀y ∈ E, P(x, y)) ≡ ∀x ∈ D, ∃y ∈ E| ∼ P(x, y)

54
Order of Operators

In dealing with statements with multiple ∀ and ∃ quantifiers,

changing the order of the quantifiers can change the meaning of the
statements.
Consider the statements

∀ people x, ∃ a person y such that x loves y

∃ a person y such that ∀ people x, x loves y

These statements are the same, but the order of the operators is
switched, and the meanings are vastly different.

55
In Summary

We can construct multiply quantified statements using our

existential, universal, and conditional operations.
We can negate or find equivalent propositions using through things
like De Morgan’s law and contraposition.
We can construct arguments out of these quantified statements and
assess the truth of the conclusions.

56