Discrete Mathematics
Predicate Logic
Predicates and Propositional Functions
Universal and Existential Quantifiers
Negating Quantified Statements
Nested Quantifiers
Imdad Ullah Khan and Malik Jahan Khan
Imdadullah Khan (LUMS) Predicate Logic 1/1
Proposition
A statement is a description of something
A proposition is a statement that is either true or false
Recall that the following are not propositions
x = 4, x > y + 3, x +y =z
Their truth values depend on values of the variables
We can make propositions out of such statements by making them
predicates
Imdadullah Khan (LUMS) Predicate Logic 2/1
Predicate
Predicate
A predicate is a property that is true or false about the subject
x is greater than 3
y is equal to z
Imdadullah Khan (LUMS) Predicate Logic 3/1
Predicate
Predicate
A predicate is a property that is true or false about the subject
x is greater than 3
|{z} | {z }
subject predicate
y is equal to z
|{z} | {z }
subject predicate
Imdadullah Khan (LUMS) Predicate Logic 4/1
Propositional function
x is greater than 3
|{z} | {z }
subject predicate
Denoted by P(x)
P denotes the predicate “is greater than 3”
x is the variable (aka subject or argument)
P(x) is the value of the propositional function P at x
Imdadullah Khan (LUMS) Predicate Logic 5/1
Propositional function
A Propositional function
Takes one or more arguments . multivariable functions
Yields the value true (T) or false (F)
Stands for the property (predicate) of the variable(s)
Becomes a proposition when variable(s) are given value(s)
Imdadullah Khan (LUMS) Predicate Logic 6/1
Propositional function
P(x) : x > 5
ICP 2-1 P(3) : . T/F
ICP 2-2 P(7) : . T/F
ICP 2-3 P(5) : . T/F
Imdadullah Khan (LUMS) Predicate Logic 7/1
Propositional function
Q(x, y ) : x > y
ICP 2-4 Q(3, 4) : . T/F
ICP 2-5 Q(5, 4) : . T/F
ICP 2-6 Q(4, 4) : . T/F
Imdadullah Khan (LUMS) Predicate Logic 8/1
Propositional function
P(x) : x is a professor at LUMS
ICP 2-7 P(Imdad) : . T/F
ICP 2-8 P(Pythagoras) : . T/F
ICP 2-9 P(Jahan) : . T/F
Imdadullah Khan (LUMS) Predicate Logic 9/1
Propositional function
Q(x, y , z) : x teaches course y in university z
ICP 2-10 Q(Imdad, Calc, ITU) : . T/F
ICP 2-11 Q(Pythagoras, Bio, PU) : . T/F
ICP 2-12 Q(Basit, DM, LUMS) : . T/F
Imdadullah Khan (LUMS) Predicate Logic 10 / 1
Propositional function
Q(x, y ) : x > y
ICP 2-13 Q(10, 7) : . T/F
ICP 2-14 Q(cat, 4) : . T/F
ICP 2-15 Q(course, mountain) : . T/F
Imdadullah Khan (LUMS) Predicate Logic 11 / 1
Universe of Discourse
We need to have a universe of discourse
A collection of subjects; things we are talking about
With a clear UoD, for each value of the variable predicates will
become propositions
Each variable may have a different universe of discourse
Imdadullah Khan (LUMS) Predicate Logic 12 / 1
Universe of Discourse
ICP 2-16 What is an appropriate UoD for the variable x in
P(x) : x > 4?
a) Set of people
b) Set of real numbers
c) Set of cats
Imdadullah Khan (LUMS) Predicate Logic 13 / 1
Universe of Discourse
ICP 2-17 What is an appropriate UoD for the variable x in
P(x) : x is a professor at LUMS?
a) Set of people
b) Set of real numbers
c) Set of cats
Imdadullah Khan (LUMS) Predicate Logic 14 / 1
Universe of Discourse
ICP 2-18 What are appropriate UoDs for the variables x and y ,
respectively in Q(x, y ) : x > y ?
a) Set of people and set of real numbers
b) Set of real numbers and set of cats
c) Set of real numbers and set of real numbers
Imdadullah Khan (LUMS) Predicate Logic 15 / 1
Universe of Discourse
ICP 2-19 What are appropriate UoDs for the variables x,y , and z,
respectively in
Q(x, y , z) : x teaches course y in university z?
a) People, Courses, Universities
b) Courses, Universities, People
c) University, People, Courses
Imdadullah Khan (LUMS) Predicate Logic 16 / 1
Predicate: Summary
A predicate is a property that is true or false about the subject(s)
P(x) is the value of propositional function P at x
Takes one or more variables
Becomes a proposition when variable(s) are given value(s)
Universe of discourse is set of possible values for variables
Each variable may have a different universe of discourse
Imdadullah Khan (LUMS) Predicate Logic 17 / 1
