Discrete Mathematics: Lecture 2 - Predicate Logic

Discrete Math course

1. Math211
Discrete Mathematics
Predicate Logic
SAHAR SELIM

2. Agenda
1.4 Predicates and Quantifiers
1.5 Nested Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
2

3. 1.4 Predicates and Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
3

4. Predicate Logic
A predicate is a propositionthat is a function of one or
more variables in a given domain .
E.g. P(x): xis an even number.
So P(1) is false, P(2) is true,….
Examples of predicates:
Domain ASCII characters -IsAlpha(x): TRUE iffx is an alphabetical
character.
Domain floating point numbers -IsInt(x): TRUE iffx is an integer.
Domain integers: Prime(x) -TRUE if x is prime, FALSE otherwise.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
4

5. Subjects and Predicates
Inthesentence“Thedogissleeping”:
The phrase “the dog” denotes the subject-the objector entity that the
sentence is about.
The phrase “is sleeping” denotes the predicate-a property that is true of
the subject.
In predicate logic, a predicateis modeled as a functionP( )
from objects to propositions.
P(x) = “xis sleeping” (where xis any object).
Sahar Selim MATH211 Lecture 3 | Predicate Logic
5

6. More About Predicates
Convention:
Lowercasevariables x, y, z...denote objects/entities.
Uppercasevariables P, Q, R… denote propositional functions (predicates).
Keep in mind that the result ofapplyinga predicate Pto an object xis
the proposition P(x).

But the predicate P itself(e.g. P=“is sleeping”) is not a proposition (not a
complete sentence).
E.g.if P(x) = “xis a prime number”,
P(3) is the proposition“3 is a prime number.”
Sahar Selim MATH211 Lecture 3 | Predicate Logic
6

7. Example
Let Q(x, y) denote the statement “x = y + 3”
What are the truth values of the propositions
Q(1, 2) and Q(3, 0)?
When the variablesin a propositional function are
assigned values, the resulting statement becomes a
propositionwith a certain truth value.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
7

8. Propositional Functions
Predicate logic generalizesthe grammatical notion of
a predicate to also include propositional functions of
anynumber of arguments, each of which may take
anygrammatical role that a noun can take.
E.g.let P(x,y,z) = “x gavey the gradez”, then
If x=“Mike”, y=“Mary”, z=“A”,
then P(x,y,z) = “Mike gave Mary the grade A.”
Sahar Selim MATH211 Lecture 3 | Predicate Logic
8

9. Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
9

10. Quantifiers
In English, the words all, some, many, none, and few are
used in quantifications.
There is another important way, called quantification, to
create a proposition from a propositional function.

Quantification expresses the extent to which a predicate is true
over a range of elements.
It describes the values of a variable that make the predicate true.
E.g. ∃x P(x)
Domainor universe: range of values of a variable
Sahar Selim MATH211 Lecture 3 | Predicate Logic
10

11. Universe of Discourse (U.D.s)
The power of distinguishing objects from predicates is that it lets
you state things about manyobjects at once.
E.g., let P(x)=“x+1>x”. We can then say,
“For anynumber x, P(x) is true” instead of
(0+1>0) ∧(1+1>1)∧(2+1>2)∧...
The collection of values that a variable xcan take is called x’s
Universe of Discourse / Domain of Discourse.
Quantifiersprovide a notation that allows us to quantify (count)
how manyobjects in the univ.of disc. satisfy a given predicate.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
11

12. Two Popular Quantifiers
1.Universal:∀x P(x)–“P(x) for all x in the domain”
2.Existential:∃x P(x)–“P(x) for some x in the domain” or “there exists
x
(that is, 1 or more) such that P(x) is TRUE”.
Either is meaningless if the domain is not known/specified.
Examples (domain real numbers)
∀x (x
2
>= 0)
∃x (x >1)
(∀x>1) (x
2
> x)–quantifier with restricted domain
Sahar Selim MATH211 Lecture 3 | Predicate Logic
12

13. The Universal Quantifier ∀
Example:
Let the u.d. of x be parking spaces at Cairo University.
Let P(x) be the predicate “xis full.”
Then the universal quantification of P (x), ∀xP(x), is the proposition:
“All parking spaces at CU are full.”
i.e., “Every parking space at CU is full.”
i.e., “For each parking space at CU, that space is full.”
Sahar Selim MATH211 Lecture 3 | Predicate Logic
13

14. The Existential Quantifier ∃
Example:
Let the u.d. of x be parking spaces at CU.
Let P(x) be the predicate “xis full.”
Then the existential quantification of P(x), ∃xP(x), is the proposition:
“Some parking space at CU is full.”
“There is a parking space at CU that is full.”
“At least one parking space at CU is full.”
Sahar Selim MATH211 Lecture 3 | Predicate Logic
14

15. Example
P(x) denote a predicate in the domain U = { 1, 2, 3}
∀x P(x) ⇔P(1) ∧P(2) ∧P(3)
∃x P(x) ⇔P(1) ˅P(2) ˅P(3)
Sahar Selim MATH211 Lecture 3 | Predicate Logic
15

16. Truth of Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
16

17. Using Quantifiers
Domain integers:
Using implications:
The cube of all negative integers is negative.
∀x (x < 0) →(x
3
< 0)
Expressing sums:
n
∀n (Σi= n(n+1)/2)
i=1
Sahar Selim MATH211 Lecture 3 | Predicate Logic
17

18. Precedence of Quantifiers and
Logical Operators
Operator Precedence
∀, ∃ 1
¬ 2
∧ 3
∨ 4
→ 5
↔ 6
Sahar Selim MATH211 Lecture 3 | Predicate Logic
18

19. Precedence of Quantifiers
∀∃have higher precedence than operators from Propositional
Logic; so
∀x P(x) ∨Q(x)is not logically equivalent to ∀x (P(x) ∨Q(x))
∃x (P(x) ∧Q(x)) ∨∀x R(x)
Say P(x): x is odd, Q(x): x is divisible by 3, R(x): (x=0) ∨(2x >x)
Logical Equivalence: P ≡Q iffthey have same truth value no matter
which domainis used and no matter which predicatesare assigned
to predicate variables.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
19

20. Free and Bound Variables
An expression like P(x) is said to have a free variablex (meaning,
xis undefined).
A quantifier (either ∀ or ∃) operateson an expression having one
or more free variables, and binds one or more of those variables,
to produce an expression having one or more boundvariables.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
20

21. Remember
A predicateis nota propositionuntil allvariables
have been bound either by quantification or
assignment of a value!
Sahar Selim MATH211 Lecture 3 | Predicate Logic
21

22. Binding Variables
The occurrence of a variable x is boundiffa value is
assigned to x or when a quantifier is used on x.
Otherwise, it is called free.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
22
),(yxQx∃
( )())()()( xRxxQxPx ∀∧∨∃

23. Example of Binding
P(x,y) has 2 free variables, xand y.
∀xP(x,y) has 1 free variable, and one bound variable.
[Which is which?]
“P(x), where x=3” is another way to bind x.

An expression with zerofree variables is an actual proposition.
An expression with one or morefreevariables is still only a
predicate: ∀xP(x,y)
y x
Sahar Selim MATH211 Lecture 3 | Predicate Logic
23

24. Examples
Let U = Z, the integers = {. . . -2, -1, 0 , 1, 2, 3, . . .}
P(x): x > 0 is the predicate. It has no truth value until the variable x is bound.
Examples of propositions where x is assigned a value:
P(-3) is false,
P(0) is false,
P(3) is true.
The collection of integers for which P(x) is true are the positive
integers.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
24

25. Examples
P(y) ˅¬P(0) is not a proposition.
The variable y has not been bound.
However, P(3) ˅¬P(0) is a proposition which is true.
Let R be the three-variable predicate R(x, y z):
x + y = z
Find the truth value of
R(2, -1, 5), R(3, 4, 7), R(x, 3, z)
Sahar Selim MATH211 Lecture 3 | Predicate Logic
25

26. Negation of Quantifiers
Negation of “All Egyptians love falafel”
“Not All Egyptians love falafel” ≡“There exists some Egyptians
that do not love falafel”
¬∀x P(x) ≡∃x ¬P(x)
¬∃x P(x) ≡∀x ¬P(x)
Careful:The negation of “Every Canadian loves Hockey” is NOT
“No Canadian loves Hockey”!
Sahar Selim MATH211 Lecture 3 | Predicate Logic
26

27. Negation of Quantifiers
Distributing a negation operator across a quantifier
changes a universal to an existential and vice versa.
¬(∀x P(x)) ⇔¬(P(x
1) ∧P(x
2) ∧…∧P(x
n))
⇔¬P(x
1) ˅¬P(x
2) ˅…˅¬P(x
n)
⇔∃x ¬P(x)
Sahar Selim MATH211 Lecture 3 | Predicate Logic
27

28. De Morgan’sLawsfor Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
28

29. Example
What are the negations of the statements “There is an honest
politician” and “All Americans eat cheeseburgers”?
Solution:
H(x) denote “x is honest.”

“There is an honest politician” is represented by ∃xH(x), where
the domain consists of all politicians.
Negation of this statement is ￢∃xH(x) ≡ ∀x￢H(x).
Sahar Selim MATH211 Lecture 3 | Predicate Logic
29

30. Example
Let C(x) denote “x eats cheeseburgers.”
Then “All Americans eat cheeseburgers” is represented by
∀xC(x), where the domain consists of all Americans.
The negation of this statement is ￢∀xC(x), which is equivalent to
∃x￢C(x).
This negation can be expressed in several different ways,
including “Some American does not eat cheeseburgers” and
“There is an American who does not eat cheeseburgers.”
Sahar Selim MATH211 Lecture 3 | Predicate Logic
30

31. 1.5 Nested Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
33

32. Nested Quantifiers
Use distinct variables
∀x (∃y(P(x,y) →∀x Q(y, x)))
Variable name doesn’t matter
∀x ∃y P(x, y) ≡∀a ∃b P(a, b)
Positions of quantifiers can change (but order is
important)
∀x (Q(x) ∧∃yP(x, y)) ≡∀x ∃y(Q(x) ∧P(x, y))
Sahar Selim MATH211 Lecture 3 | Predicate Logic
34

33. Nested Quantifiers
Example: Let the u.d. of x& ybe people.
Let L(x,y)=“x likes y” (a predicate with 2 free variables)
Then ∃y L(x,y) = “There is someone whom xlikes.” (A predicate with
1 free variable, x)
Then ∀x(∃y L(x,y)) = “Everyone has someone whom they like.”
(A __________ with ___ free variables.)
Sahar Selim MATH211 Lecture 3 | Predicate Logic
35

34. ∀x ∃y (x + y = 0)is true over the integers
Assume an arbitrary integer x.
To show that there exists a y that satisfies the requirement of the
predicate, choose y = -x. Clearly y is an integer, and thus is in the
domain.
So x + y = x + (-x) = x – x = 0.
Since we assumed nothing about x (other than it is an integer), the
argument holds for any integer x.
Therefore, the predicate is TRUE.
Nested Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
36

35. Caution: In general, order matters ! Consider the following
propositions over the integer domain:
∀x ∃y (x < y)and ∃y ∀x (x < y)
∀x ∃y (x < y): “there is no maximum integer”
∃y ∀x (x < y): “there is a maximum integer”
Not the same meaning at all!!!
Nested Quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
37

36. Quantification as loop
For every x, for every y: ∀x ∀y P(x, y)
Loop through x and for each x loop through y
If we find P(x,y) is true for all x and y, then the statement is true
If we ever hit a value x for which we hit a value for which P(x,y) is
false, the whole statement is false

For every x, there exists y: ∀x ∃y P(x, y)
Loop through x until we find a y that P(x,y) is true
If for every x, we find such a y, then the statement is true
Sahar Selim MATH211 Lecture 3 | Predicate Logic
38

37. Quantification as loop
 : loop through the values for x until we find an x for
which p(x,y) is always true when we loop through all values for y
Once found such one x, then it is true
 : loop though the values for x where for each x loop
through the values of y until we find an x for which we find a y
such that p(x,y) is true
False only if we never hit an x for which we never find y such that p(x,y) is
true
),(yxypx∀∃
),(yxypx∃∃
Sahar Selim MATH211 Lecture 3 | Predicate Logic
39

38. The order of quantifiers is important unless allthe
quantifiers are universal or allthe quantifiers are
existential.
Let Q(x,y) denote “x+ y= 0”. What are the truth values of the
quantifications
∀x∃yQ(x,y)
∃y∀xQ(x,y)
Order of quantification
Sahar Selim MATH211 Lecture 3 | Predicate Logic
40

39. Order of quantification
Let P(x, y) be the statement “x + y = y + x” and the domain is real
number
∀x∀yP(x, y) ≡ ∀y∀xP(x, y) ?
The quantification ∀x∀yP(x, y) denotes the proposition “For
all real numbers x, for all real numbers y, x + y = y + x.”
The statement ∀y∀xP(x, y) says “For all real numbers y, for
all real numbers x, x + y = y + x.”
Both has the same meaning, and both are true.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
41

40. Order of quantification
Let Q(x, y) denote “x + y = 0.” and the domain is real
number
What are the truth values of the quantifications
∃y∀xQ(x, y) and ∀x∃yQ(x, y)
∃y∀xQ(x, y): “There is a real number y such that for every
real number x, Q(x, y).”
∀x∃yQ(x, y): “For every real number x there is a real number
y such that Q(x, y).”
False
True
∃y∀xQ(x, y) ≢∀x∃yQ(x, y)
Sahar Selim MATH211 Lecture 3 | Predicate Logic
42

41. Quantifications of Two Variables
Sahar Selim MATH211 Lecture 3 | Predicate Logic
43

42. Quantification with more variables
∀x∀y∃zQ(x, y, z): “For all real numbers x and for all real numbers y there is a
real number z such that x + y = z,” is true
∃z∀x∀yQ(x, y, z)
: “There is a real number z such that for all real numbers x
and for all real numbers y it is true that x + y = z,” is false, because there is no
value of z that satisfies the equation x + y = z for all values of x and y.
it true? Is mean?it doesWhat :),,(
it true? Is mean?it doesWhat :),,(
number real isdomain theand
,statement thebe ),,(Let
zyxyqxz
zyxzqyx
zyxzyxq
∀∀∃
∃∀∀
=+
The order of the
quantification
here is important
Sahar Selim MATH211 Lecture 3 | Predicate Logic
44

43. Translating mathematical statements
“The sum of two positive integers is always positive”
integers all
of consists blesboth variafor domain thewhere
))0()0()0(( >+→>∧>∀∀ yxyxyx
integers positive all
of consists blesboth variafor domain thewhere
)0( >+∀∀ yxyx
Sahar Selim MATH211 Lecture 3 | Predicate Logic
45

44. Example
“Every real number except zero has a multiplicative inverse”
numbers real of consists blesboth variafor domain thewhere
))1()0(( =∃→≠∀ xyyxx
Sahar Selim MATH211 Lecture 3 | Predicate Logic
46
∀x∃y((x≠0)→ (xy=1))

45. Translating English Sentences into
Logical Expressions
“If a person is female and is a parent, then this person is someone’s
mother”
“For every person x , if person x is female and person x is a parent, then
there exists a person y such that person x is the mother of person y .”
F(x): “x is female,”
P(x):“x is a parent,”
M(x, y): “x is the mother of y.”
∀x((F(x) ∧P(x)) → ∃yM(x, y))
Sahar Selim MATH211 Lecture 3 | Predicate Logic
47

46. Summary: Predicate Logic
In this lecture we have learned:
Predicate logic notation & conventions
Conversions: predicate logic ↔clear English
Meaning of quantifiers, equivalences
Simple reasoning with quantifiers
Sahar Selim MATH211 Lecture 3 | Predicate Logic
48

47. 49
Sahar Selim MATH211 Lecture 3 | Predicate Logic

48. Problem 1
P(x): “x can speak Russian”
Q(x): “x knows the computer language C++. ”
Express each of these sentences in terms of P(x ), Q(x), quantifiers,
and logical connectives.
The domain for quantifiers consists of all students at your school.
a)There is a student at your school who can speak Russian and who knows
C++.
∃x(P(x) ^ Q(x))
Sahar Selim MATH211 Lecture 3 | Predicate Logic
50

49. Problem 1
P(x) be the statement “x can speak Russian”
Q(x) be the statement “x knows the computer language C++.”
b)There is a student at your school who can speak Russian but who
doesn’t know C++.
c)Every student at your school either can speak Russian or know
C++.
d)No student at your school can speak Russian or know C ++.
∃x(P(x) ^ ¬Q(x))
∀x(P(x) ˅ Q(x))
¬ ∃x(P(x) ˅ Q(x))∀x¬(P(x) ˅ Q(x))∀x(¬P(x) ^ ¬Q(x))
Sahar Selim MATH211 Lecture 3 | Predicate Logic
51

50. P(x) = “x is a professor”Q(x) = “x is ignorant”
R(x) = “x is vain”
Express the following statements using quantifiers;
logical connectives; and P(x), Q(x), and R(x) where
the universe of discourse is the set of all people.
1.No professors are ignorant
2.All ignorant people are vain
3.No professors are vain
Problem 2
Sahar Selim MATH211 Lecture 3 | Predicate Logic
52
∀x(P(x) → ¬Q(x))
∀x(Q(x) → R(x))
∀x(P(x) → ¬ R(x))

51. Problem 3: Translating Sentences into
Logical Expressions
Let L(x,y) be the statement “x loves y”, where the domain for both x and y
consists of all people in the world.
1.Everybody loves Jerry.
2.Everybody loves somebody.
3.There is somebody whom everybody loves.
4.Nobody loves everybody.
5.There is somebody whom Lydia does not love.
6.There is somebody whom no one loves.
7.There is exactly one person whom everybody loves.
8.There are exactly two people whom Lynn loves.
9.Everyone loves himself or herself
10.There is someone who loves no one besides himself or herself
Sahar Selim MATH211 Lecture 3 | Predicate Logic
53

52. Programming
Task
Implement using any
programming
language
Sahar Selim MATH211 Lecture 3 | Predicate Logic

53. Programming Task
Let Q(x, y) denote “x + y = 5”
The domain of x and y is the integers {0, 1, 2, 3, 4, 5}.
Implement the code that outputs the truth values of the following
quantifications:
1.∀x ∀y Q(x, y)
2.∀x ∃y Q(x, y)
**Display values of variables x and y if the quantification is true.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
55

54. Thinking of Nested
Quantification as Nested Loops

Toseeif∀x∀yP(x,y)istrue,
loopthroughthevaluesofx:
Ateachstep,loopthroughthevaluesfory.
Ifforsomepairofxandy,P(x,y)isfalse,then∀x∀yP(x,y)isfalseandboth
theouterandinnerloopterminate.
∀x∀yP(x,y)istrueiftheouterloopendsaftersteppingthrough
eachx.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
56

55. Thinking of Nested
Quantification as Nested Loops

Toseeif∀x∃yP(x,y) istrue,
loopthroughthevaluesofx:
Ateachstep,loopthroughthevaluesfory.
TheinnerloopendswhenapairxandyisfoundsuchthatP(x,y)istrue.
IfnoyisfoundsuchthatP(x,y)istruetheouterloopterminatesas∀x∃yP(x,y)has
beenshowntobefalse.
∀x∃yP(x,y)istrueiftheouterloopendsaftersteppingthrougheachx.
Ifthedomainsofthevariablesareinfinite,thenthisprocesscannotactually
becarriedout.
Sahar Selim MATH211 Lecture 3 | Predicate Logic
57

56. Next Lecture
Inference Rules
Sahar Selim MATH211 Lecture 3 | Predicate Logic
58

57. Supplementary Material
1.4.1 Predicate Logic
Sahar Selim MATH211 Lecture 3 | Predicate Logic
59