CS 441 Discrete Mathematics for CS

Lecture 3

Predicate logic

[Link] Rahmani
cenghabib@[Link]
Kandahar University
Discrete Make You Smart

CS 441 Discrete mathematics for CS

Propositional logic: review

• Propositional logic: a formal language for making logical
inferences
• A proposition is a statement that is either true or false.
• A compound proposition can be created from other
propositions using logical connectives
• The truth of a compound proposition is defined by truth
values of elementary propositions and the meaning of
connectives.
• The truth table for a compound proposition: table with
entries (rows) for all possible combinations of truth values of
elementary propositions.

CS 441 Discrete mathematics for CS

1
 Tautology and Contradiction

What is a tautology?
• A compound proposition that is always true for all possible
truth values of the propositions is called a tautology.
•
Example: p  ¬p is a tautology.

p ¬p p¬p
T F T
F T T

CS 441 Discrete mathematics for CS

Tautology and Contradiction

What is a contradiction?
• A compound proposition that is always false is called a
contradiction.

Example: p  ¬p is a contradiction.

p ¬p p¬p
T F F
F T F
CS 441 Discrete mathematics for CS

2
 Equivalence
• How do we determine that two propositions are equivalent?
Their truth values in the truth table are the same.
• Example: p  q is equivalent to ¬q  ¬p (contrapositive)

p q pq ¬q¬p

T T T T
T F F F
F T T T
F F T T
• Equivalent statements are important for logical reasoning
since they can be substituted and can help us to make a logical
argument.
CS 441 Discrete mathematics for CS

Logical equivalence

• Definition: The propositions p and q are called logically

equivalent if p  q is a tautology (alternately, if they have the
same truth table). The notation p <=> q denotes p and q are
logically equivalent.

a b (ab)<->
ab ¬a¬b
(¬a¬b)

T T T T T
T F F F T
F T T T T
F F T T T
CS 441 Discrete mathematics for CS

3
 Important logical equivalences
• Identity
– p  T <=> p
– p  F <=> p

• Domination
– p  T <=> T
– p  F <=> F

• Idempotent
– p  p <=> p
– p  p <=> p

CS 441 Discrete mathematics for CS

Important logical equivalences

• Double negation
– ¬(¬p) <=> p

• Commutative
– p  q <=> q  p
– p  q <=> q  p

• Associative
– (p  q)  r <=> p  (q  r)
– (p  q)  r <=> p  (q  r)

CS 441 Discrete mathematics for CS

4
 Important logical equivalences
• Distributive
– p  (q  r) <=> (p  q)  (p  r)
– p  (q  r) <=> (p  q)  (p  r)

• De Morgan
– ¬( p  q ) <=> ¬p  ¬q
– ( p  q ) <=> ¬p  ¬q

• Other useful equivalences

– p  ¬p <=> T
– p  ¬p <=> F
– p  q <=> (¬p  q)
CS 441 Discrete mathematics for CS

Showing logical equivalence

Example: Show (p  q)  p is a tautology
In other words ((p  q)  p <=> T)

Proof via truth table:

p q pq (pq)p
T T T T
T F F T
F T F T
F F F T
CS 441 Discrete mathematics for CS

5
 Showing logical equivalences
• Equivalences can be used in proofs. A proposition or its part
can be transformed using equivalences and some conclusion
can be reached.

Example: Show that (p  q)  p is a tautology.

• Proof: (we must show (p  q)  p <=> T)
(p  q)  p <=> ¬(p  q)  p Useful
<=> [¬p  ¬q]  p DeMorgan
<=> [¬q  ¬p]  p Commutative
<=> ¬q  [ ¬p  p ] Associative
<=> ¬q  [ T ] Useful
<=> T Domination

CS 441 Discrete mathematics for CS

Propositional logic
• Definition:
– A proposition is a statement that is either true or false.
• Examples:
– Pitt is located in the Oakland section of Pittsburgh.
– 5 + 2 = 8.
– It is raining today
– 2 is a prime number
– If (you do not drive over 65 mph) then (you will not get a
speeding ticket).

• Not a proposition:
– How are you?
– x+5=3

CS 441 Discrete mathematics for CS

6
 Limitations of the propositional logic
Propositional logic: the world is described in terms of
elementary propositions and their logical combinations
Elementary statements:
• Typically refer to objects, their properties and relations.
But these are not explicitly represented in the propositional
logic
– Example:
• “John is a UPitt student.”

John a Upitt student

object a property
• Objects and properties are hidden in the statement, it is
not possible to reason about them

CS 441 Discrete mathematics for CS

Limitations of the propositional logic

(1) Statements that must be repeated for many objects
– In propositional logic these must be exhaustively enumerated
• Example:
– If John is a CS UPitt graduate then John has passed cs441
Translation:
– John is a CS UPitt graduate  John has passed cs441
Similar statements can be written for other Upitt graduates:
– Ann is a CS Upitt graduate  Ann has passed cs441
– Ken is a CS Upitt graduate  Ken has passed cs441
– …
• What is a more natural solution to express the above
knowledge?
CS 441 Discrete mathematics for CS

7
 Limitations of the propositional logic
(1) Statements that must be repeated for many objects
• Example:
– If John is a CS UPitt graduate then John has passed cs441
Translation:
– John is a CS UPitt graduate  John has passed cs441
Similar statements can be written for other Upitt graduates:
– Ann is a CS Upitt graduate  Ann has passed cs441
– Ken is a CS Upitt graduate  Ken has passed cs441
– …
• Solution: make statements with variables
– If x is a CS Upitt graduate then x has passed cs441
– x is a CS UPitt graduate  x has passed cs441
CS 441 Discrete mathematics for CS

Limitations of the propositional logic

(2) Statements that define the property of the group of objects

• Example:
– All new cars must be registered.
– Some of the CS graduates graduate with honors.

• Solution: make statements with quantifiers

– Universal quantifier –the property is satisfied by all
members of the group
– Existential quantifier – at least one member of the group
satisfy the property

CS 441 Discrete mathematics for CS

8
 Predicate logic
Remedies the limitations of the propositional logic
• Explicitly models objects and their properties
• Allows to make statements with variables and quantify them
Basic building blocks of the predicate logic:
• Constant –models a specific object
Examples: “John”, “France”, “7”
• Variable – represents object of specific type (defined by the
universe of discourse)
Examples: x, y
(universe of discourse can be people, students, numbers)
• Predicate - over one, two or many variables or constants.
– Represents properties or relations among objects
Examples: Red(car23), student(x), married(John,Ann)

CS 441 Discrete mathematics for CS

Predicates
Predicates represent properties or relations among objects

A predicate P(x) assigns a value true or false to each x depending

on whether the property holds or not for x.
• The assignment is best viewed as a big table with the variable x
substituted for objects from the universe of discourse
Example:
• Assume Student(x) where the universe of discourse are people
• Student(John) …. T (if John is a student)
• Student(Ann) …. T (if Ann is a student)
• Student(Jane) ….. F (if Jane is not a student)
• …

CS 441 Discrete mathematics for CS

9
 Predicates
Assume a predicate P(x) that represents the statement:
• x is a prime number

What are the truth values of:

• P(2) T
• P(3) T
• P(4) F
• P(5) T
• P(6) F
• P(7) T

All statements P(2), P(3), P(4), P(5), P(6), P(7) are propositions
CS 441 Discrete mathematics for CS

Predicates
Assume a predicate P(x) that represents the statement:
• x is a prime number

What are the truth values of:

• P(2) T
• P(3) T
• P(4) F
• P(5) T
• P(6) F
• P(7) T

Is P(x) a proposition? No. Many possible substitutions are

possible.

CS 441 Discrete mathematics for CS

10
 Predicates
• Predicates can have more arguments which represent the
relations between objects

Example:
• Older(John, Peter) denotes ‘John is older than Peter’
– this is a proposition because it is either true or false
• Older(x,y) - ‘x is older than y’
– not a proposition, but after the substitution it becomes one

CS 441 Discrete mathematics for CS

Predicates
• Predicates can have more arguments which represent the
relations between objects
Example:
• Let Q(x,y) denote ‘x+5 >y’
– Is Q(x,y) a proposition?

CS 441 Discrete mathematics for CS

11
 Predicates
• Predicates can have more arguments which represent the
relations between objects
Example:
• Let Q(x,y) denote ‘x+5 >y’
– Is Q(x,y) a proposition? No!
– Is Q(3,7) a proposition? Yes. It is true.
– What is the truth value of:
– Q(3,7) T
– Q(1,6) F
– Q(2,2) T
– Is Q(3,y) a proposition? No! We cannot say if it is true or
false.

CS 441 Discrete mathematics for CS

Compound statements in predicate logic

Compound statements are obtained via logical connectives
Examples:
Student(Ann)  Student(Jane)
• Translation: “Both Ann and Jane are students”
• Proposition: yes.
Country(Sienna)  River(Sienna)
• Translation: “Sienna is a country or a river”
• Proposition: yes.
CS-major(x)  Student(x)
• Translation: “if x is a CS-major then x is a student”
• Proposition: no.

12
 Predicates
Important:
• statement P(x) is not a proposition since there are more objects
it can be applied to
This is the same as in propositional logic …

… But the difference is:

• predicate logic allows us to explicitly manipulate and substitute
for the objects
• Predicate logic permits quantified sentences where variables are
substituted for statements about the group of objects

CS 441 Discrete mathematics for CS

Quantified statements
Predicate logic lets us to make statements about groups of
objects
• To do this we use special quantified expressions

Two types of quantified statements:

• universal
Example: ‘ all CS Upitt graduates have to pass cs441”
– the statement is true for all graduates
• existential
Example: ‘Some CS Upitt students graduate with honor.’
– the statement is true for some people

CS 441 Discrete mathematics for CS

13
 Universal quantifier
Defn: The universal quantification of P(x) is the proposition:
"P(x) is true for all values of x in the domain of discourse." The
notation x P(x) denotes the universal quantification of P(x),
and is expressed as for every x, P(x).

Example:
• Let P(x) denote x > x - 1.
• What is the truth value of x P(x)?
• Assume the universe of discourse of x is all real numbers.
• Answer: Since every number x is greater than itself minus 1.
Therefore, x P(x) is true.

CS 441 Discrete mathematics for CS

Universal quantifier
Quantification converts a propositional function into a
proposition by binding a variable to a set of values from the
universe of discourse.

Example:
• Let P(x) denote x > x - 1.
• Is P(x) a proposition? No. Many possible substitutions.
• Is x P(x) a proposition? Yes. True if for all x from the
universe of discourse P(x) is true.

CS 441 Discrete mathematics for CS

14
 Universally quantified statements
Predicate logic lets us make statements about groups of objects

Universally quantified statement

• CS-major(x)  Student(x)
– Translation: “if x is a CS-major then x is a student”
– Proposition: no.

• x CS-major(x)  Student(x)
– Translation: “(For all people it holds that) if a person is a
CS-major then she is a student.”
– Proposition: yes.

Existential quantifier
Definition: The existential quantification of P(x) is the
proposition "There exists an element in the domain (universe) of
discourse such that P(x) is true." The notation x P(x) denotes
the existential quantification of P(x), and is expressed as there is
an x such that P(x) is true.

Example 1:
• Let T(x) denote x > 5 and x is from Real numbers.
• What is the truth value of x T(x)?
• Answer:
• Since 10 > 5 is true. Therefore, it is true that x T(x).

CS 441 Discrete mathematics for CS

15
 Existential quantifier
Definition: The existential quantification of P(x) is the
proposition "There exists an element in the domain (universe) of
discourse such that P(x) is true." The notation x P(x) denotes
the existential quantification of P(x), and is expressed as there is
an x such that P(x) is true.

Example 2:
• Let Q(x) denote x = x + 2 where x is real numbers
• What is the truth value of x Q(x)?
• Answer: Since no real number is 2 larger than itself,
the truth value of x Q(x) is false.

CS 441 Discrete mathematics for CS

Existentially quantified statements

Statements about groups of objects

Example:
• CS-Upitt-graduate (x)  Honor-student(x)
– Translation: “x is a CS-Upitt-graduate and x is an honor
student”
– Proposition: ?

16
 Quantified statements
Statements about groups of objects

Example:
• CS-Upitt-graduate (x)  Honor-student(x)
– Translation: “x is a CS-Upitt-graduate and x is an honor
student”
– Proposition: no.

•  x CS-Upitt-graduate (x)  Honor-student(x)

– Translation: “There is a person who is a CS-Upitt-graduate
and who is also an honor student.”
– Proposition: ?

Quantified statements
Statements about groups of objects

Example:
• CS-Upitt-graduate (x)  Honor-student(x)
– Translation: “x is a CS-Upitt-graduate and x is an honor
student”
– Proposition: no.

•  x CS-Upitt-graduate (x)  Honor-student(x)

– Translation: “There is a person who is a CS-Upitt-graduate
and who is also an honor student.”
– Proposition: yes.

17
 Summary of quantified statements
• When x P(x) and x P(x) are true and false?

Statement Whentrue? Whenfalse?

xP(x) P(x)trueforallx Thereisanx

whereP(x)isfalse.
xP(x) Thereissomexfor P(x)isfalseforall
whichP(x)istrue. x.

Suppose the elements in the universe of discourse can be

enumerated as x1, x2, ..., xN then:
• x P(x) is true whenever P(x1)  P(x2)  ...  P(xN) is true
• x P(x) is true whenever P(x1)  P(x2)  ...  P(xN) is true.

CS 441 Discrete mathematics for CS

18