[Link]

my

Homework Solution
(PQ)(P)
P Q PQ (PQ) P Q (P)(Q)
(Q)
F F
T T T F F T

F T
T F T F F T

T F
F T T F F T

T T
F F F T T T

The statements (PQ) and (P)(Q) are logically equivalent, so

we write (PQ)(P)(Q).
 [Link]

1.2 PROPOSITIONAL
EQUIVALENCES

MTK3013
DISCRETE STRUCTURES
 [Link]

Basic Terminology
• A tautology is a proposition which is always
true.
p  p
• A contradiction is a proposition that is
always false.
p  p
• A contingency is a proposition that is
neither a tautology nor a contradiction.
p  q  r
 [Link]

Logical Equivalences

• Two propositions p and q are logically

equivalent if they have the same truth
values in all possible cases.
• Two propositions p and q are logically
equivalent if p  q is a tautology.
• Notation: p  q or p  q
 [Link]

Determining Logical
Equivalence
• Use a truth table.
• Show that (p  q) and p  q are logically
equivalent.
• Not a very efficient method, WHY?
• Solution: Develop a series of equivalences.
 [Link]

Important Equivalences

pTp Identity

pFp
pTT Domination

pFF
ppp Idempotent

ppp
( p)  p Double Negation
 [Link]

Important Equivalences

pqqp Commutative

pqqp
(p  q)  r  p  (q  r) Associative

(p  q)  r  p  (q  r)
p  (q  r)  (p  q)  (p  r) Distributive

p  (q  r)  (p  q)  (p  r)
(p  q)  p  q De Morgan’s

(p  q)  p  q
 [Link]

Important Equivalences

p  (p  q)  p Absorption

p  (p  q)  p
p  p  T Negation

p  p  F
 [Link]

Important Equivalences
Involving Implications

p → q  p  q
p→qq→p

(p → q)  (p → r)  p → (q  r)
(p → q)  (p → r)  p → (q  r)
p↔ q  (p → q)  (q → p)
 [Link]

Example
• Show that (p -> q) and p  q are logically
equivalent
 [Link]

Example

• Show that (p  (p  q)) and p  q

are logically equivalent.
 [Link]

Example
• Show that (p  q ) -> (p  q) is tautology
 [Link]

1.3 PREDICATES AND

QUANTIFIER

MTK3013
DISCRETE STRUCTURES
 [Link]

Predicates

• A predicate is a statement that contains

variables.
• Example:
P(x) : x > 3
Q(x,y) : x = y + 3
R(x,y,z) : x + y = z
 [Link]

Predicates

• A predicate becomes a proposition if the

variable(s) contained is(are)
– Assigned specific value(s)
– Quantified
• P(x) : x > 3. What are the truth values of
P(4) and P(2)?
• Q(x,y) : x = y + 3. What are the truth
values of Q(1,2) and Q(3,0)?
 [Link]

Quantifiers

• Two types of quantifiers

– Universal
– Existential
• Universe of discourse - the particular
domain of the variable in a propositional
function
 [Link]

Universal Quantification

• P(x) is true for all values of x in the

universe of discourse.
• x P(x)
– “for all x, P(x)”
– “for every x, P(x)”
– The variable x is bound by the universal
quantifier, producing a proposition
 [Link]

Example

• U = {all real numbers}, P(x): x+1 > x

– What is the truth value of x P(x)
• U = {all real numbers}, Q(x): x < 2
– What is the truth value of x Q(x)
• U = {all students in MTK3013}
R(x) : x has an account on Tabung Haji
– What does x R(x) mean?
 [Link]

For universal quantification

P(x)  P(x1)  P(x2)  …  P(xn)

• If the elements in the universe of discourse can be

listed, U = {x1, x2, …, xn}
x P(x)  P(x1)  P(x2)  …  P(xn)

• Example
U = {positive integers not exceeding 3} and P(x):
x2 < 10
– What is the truth value of x P(x)
P(1) ^ P(2) ^ P (3)
T ^ T ^ T
T
 [Link]

Existential Quantification

• P(x) is true for some x in the universe of

discourse
• x P(x)
– “for some x, P(x)”
– “There exists an x such that P(x)”
– “There is at least one x such that P(x)”
– The variable x is bound by the existential
quantifier, producing a proposition
 [Link]

Example

• U = {all real numbers}, P(x): x > 3

– What is the truth value of x P(x)
• U = {all real numbers}, Q(x): x = x + 1
– What is the truth value of x Q(x)
• U = {all students in MTK 3013}
R(x) : x has an account on Tabung Haji
– What does x R(x) mean?
 [Link]

For existential quantification

P(x)  P(x1)  P(x2)  …  P(xn)

• If the elements in the universe of discourse

can be listed, U = {x1, x2, …, xn}
x P(x)  P(x1)  P(x2)  …  P(xn)

• Example
U = {positive integers not exceeding 4} and P(x): x2 > 10
– What is the truth value of x P(x)
P(1) v P(2) v P(3) v P(4)
 [Link]

Binding Variables

• Bound variable: if a variable is quantified

• Free variable: Neither bound nor assigned a
specific value
• Example: x P(x) x Q(x,y)
• Scope of Quantifiers: Part of a logical
expression to which a quantifier is applied
• Example: x (P(x)  Q(x))  x R(x)
 [Link]

Negation of Quantifiers

• Distributing a negation operator across a

quantifier changes a universal to an
existential and vice versa.
~x P(x)  x ~P(x)
~x P(x)  x ~P(x)
• Example:
– P(x) : x has taken a course in calculus
 [Link]

Translating from English

• Many ways to translate a given sentence
• Goal is to produce a logical expression that is
simple and can be easily used in subsequent
reasoning
• Steps:
– Clearly identify the appropriate quantifier(s)
– Introduce variable(s) and predicate(s)
– Translate using quantifiers, predicates, and
logical operators
 [Link]

Example

• Every student in this class has studied

Discrete Structures
• Solution 1
– Assume, U = {all students in MTK 3013}
• Solution 2
– Assume, U = {all people}
 [Link]

Example

• Some student in this class has visited

Mexico
• Solution 1
– Assume, U = {all students in MTK 3013}
• Solution 2
– Assume, U = {all people}
 [Link]

More Example

• C(x): x is a COMPUTING student

• M(x): x is an MULTIMEDIA student
• S(x): x is a smart student
• U = {all students in MTK 3013}
 [Link]

More Example (Cont..)

• Everyone is a COMPUTING student.
x C(x)
• Nobody is an MULTIMEDIA student.
x ~M(x) or ~x M(x)
• All COMPUTING students are smart students.
x [C(x)  S(x)]
• Some COMPUTING students are smart
students.
x [C(x)  S(x)]
 [Link]

Use implication or
conjunction?
• Universal quantifiers usually take implications
• All COMPUTING students are smart students.
x [C(x)  S(x)] Correct
x [C(x)  S(x)] Incorrect
 [Link]

Use implication or
conjunction?
• Existential quantifiers usually take
conjunctions
• Some COMPUTING students are smart
students.
x [C(x)  S(x)] Correct
x [C(x)  S(x)] Incorrect
 [Link]

More Example
• No COMPUTING student is an MULTIMEDIA
student.
– If x is a COMPUTING student, then that student is not
an MULTIMEDIA student.
x [C(x)  ~M(x)]
– There does not exist a COMPUTING student who is
also an MULTIMEDIA student.
~x [C(x)  M(x)]
• If any MULTIMEDIA student is a smart student
then he is also a COMPUTING student.
x [(M(x)  S(x))  C(x)]
 [Link]

Nested Quantifiers

• Quantifiers that occur within the scope of

other quantifiers
• Example:
P(x,y): x + y = 0, U={R}
x y P(x,y)
 [Link]

Quantifications of Two
Variables
• For all pair x,y P(x,y).
xy P(x,y) yx P(x,y)
• For every x there is a y such that P(x,y).
xy P(x,y)
• There is an x such that P(x,y) for all y.
xy P(x,y)
• There is a pair x,y such that P(x,y).
xy P(x,y) yx P(x,y)
 [Link]

Translating statements
with nested quantifiers
• U = {all real numbers}
x y (x + y = y + x)
x y (x + y = 0)
x y ( (x > 0)  (y < 0)  (xy < 0) )
• U = {all students in cs2813}
C(x): x has a computer
F(x,y): x and y are friends
x ( C(x)  y (C(y)  F(x,y)) )
 [Link]

Translating Sentences

• U = {all people}
– If a person is female and is a parent, then this
person is someone’s mother.
• U = {all integers}
– The sum of two positive integers is positive.
 [Link]

Is the order of quantifiers

important?
• If the quantifiers are of the same type, then
order does not matter
• If the quantifiers are of different types,
then order is important
 [Link]

Example
• U={R}
• Q(x,y): x+y=0
• What are the truth values for
y x Q(x,y) and x y Q(x,y)

y x Q(x,y): There exist at least one y such that for

every real number x, Q(x,y) is true, i.e. x+y=0.
FALSE (not for every, only when y is –x).
But…
x y Q(x,y): For every real number x, there is a real
number y such that Q(x,y) is true, i.e x+y =0.
TRUE (for every x when y is –x)