DISCRETE

MATHEMATICS
AND
ITS APPLICATIONS
Book: Discrete Mathematics and Its
Applications
Author: Kenneth H. Rosen
Sixth Edition
McGraw-Hill International Edition
 Chapter 1
The Foundations:
Logic and Proofs
 Objectives
 Explain what makes up a correct
mathematical argument
 Introduce tools to construct
arguments
 Contents

1.1-Propositional Logic
1.2-Propositonal Equivalences
1.3-Predicates and Quantifiers
1.4-Nested Quantifiers
1.5-Rules of Inference
 1.1- Propositional
Logic

1.1.1- Definitions and Truth Table

1.1.2- Precedence of Logical Operators
 1.1.1- Definitions and
Truth Table

o Proposition is a declarative sentence that

is either true or false but not both.
o Proposition is a sentence that declares a
fact.
o Examples:
o Ha Noi is the capital of Vietnam.
TRUE
o Toronto is the capital of Canada.
FALSE
 1.1.1- Definitions and Truth Table

Proposition is a declarative sentence that

is either true or false but not both.
• 2 + 2 = 3.
FALSE
• What time is it?
A question.
• X+Y=Z
The sentence cannot be shown to be
either true of false.
 1.1.1-
Definitions…

 Truth table
2+2=4

p
True/ T / 1
False / F / 0
 1.1.1- Definitions and
Truth Table
Example
 1.1.1- Definitions…

 Letp be a proposition. The negation of p,

denoted by p (also denoted
p by ) , is the
statement “It is not the case that p”.

 Theproposition p is read “not p”. The

truth vale of the negation of p, p , is
the opposite of the truth value of p.
 1.1.1- Definitions…

 Negation of proposition p is the statement

“ It is not case that p”.
 Notation: p (or p )
 1.1.1- Definitions…

 Findthe negation of the proposition

“Sarah’s PC runs Windows.”
and express this in simple English.

Solution:

 The negation is:

“It is not the case that Sarah’s PC runs Windows.”

 This negation can be more simply expressed by:

“Sarah’s PC does not run Windows.”
 1.1.1-
Definitions…
Example
 1.1.1- Definitions…

 Let p and q be proposition. The conjunction of p and

q, denoted by p^q, is the proposition “ p and q”.
 The conjunction p^q is true when both p and q are
true and false otherwise.

p q p^q
F F F
F T F
T F F
T T T
 1.1.1-
Definitions…

 Conjunction of propositions p and q is the

proposition “ p and q” and denoted by
p^q.

p q p^q
0 0 0
0 1 0
1 0 0
1 1 1
 1.1.1- Definitions…

Example
 1.1.1- Definitions…

 Disjunctionof propositions p and q is the

proposition “ p or q” and denoted by p v q

p q pvq
0 0 0
0 1 1
1 0 1
1 1 1
 1.1.1- Definitions…

p v q (disjunction of p and q): the

proposition “p or q,” which is true if and
only if at least one of p and q is ___ .
 1.1.1-
Definitions…
 Exclusive-or(XOR) of propositions p and q,
denoted by p  q
 Is the proposition that is true when
exactly one of p and q is true and is false
otherwise.

p q pq
0 0 0
0 1 1
q 1 0 1
1 1 0
 1.1.1- Definitions…

 Implication: p → q (p implies q)
 p: hypothesis / antecedent / premise
 q: conclusion / consequence
 p → q can be expressed as:
 1.1.1-
Definitions…
 Implication: p → q (p implies q)
 p: hypothesis / antecedent / premise
 q: conclusion / consequence
 p → q can be expressed as:
- q if p
- If p, then q
- p is sufficient condition for q
- q is necessary condition for p
p q p→q
“If 1 + 1 = 3, then dogs can fly”
0 0 1  TRUE
(p  q)
0 1 1
p=0, q=0 ,
1 0 0 so (pq) is true.
1 1 1
 1.1.1- Definitions…

 Biconditional statement p  q is the proposition “ p if and only

if q”
 p → q (p only if q) and pq (p if q)

p q p→q q→p (p→q) ^ (q→p) p↔q

0 0 1 1 1 1
0 1 1 0 0 0
1 0 0 1 0 0
1 1 1 1 1 1
 1.1.2- Precedence of Logical
Operators

(1) Parentheses from inner to outer

 1.2- Propositional
Equivalences

1.2.1- Tautology and Contradiction

1.2.2- Logical Equivalences
1.2.3- De Morgan’s Laws
 1.2.1- Tautology and
Contradiction

 Tautology is a proposition that isalways true

 Contradiction is a proposition that is always false
 When p ↔ q is tautology, we say “p and q are
called logically equivalence”. Notation: p ≡ q
 Example 3 p.23

 Show that p  q and ¬p v q are logically

equivalent.
Example
 Which proposition is logically equivalent to
 1.2.2- Logical
Equivalences…

Equivalence Name
p^T≡p pvF≡p Identity laws
pvT≡ T p^F ≡ F Domination Laws
pvp≡ p p^p ≡ p Idempotent Laws
¬(¬p) ≡ p Double Negation Laws
pvq≡qvp p^q ≡q^p Commutative Laws
(p v q) v r ≡ p v (q v r) Associative Laws
(p ^ q) ^ r ≡p^(q^r)
pv (q^r) ≡ (pvq) ^ (pvr) Distributive Laws
p^ (qvr) ≡ (p^q) v (p^r)
 1.2.2- Logical Equivalences…

x, y  
Example: Given , then:

2 x  y  3 and 4 x 2
 e  1  2 x  y  3
y

p  T  p
 1.2.2- Logical
Equivalences…

Equivalence Name
¬ (p^q) ≡ ¬pv¬q ¬(pvq) ≡ ¬p^¬q De Morgan Laws

pv (p^q)≡ p p^(pvq)≡ p Absorption Laws

pv¬p ≡ T p^¬p≡ F Negation Laws
 1.2.2- Logical
Equivalences…

Example
C " 3a  8  1"
:
 C "3a  8 0 and 3a  8  1"

Using De Morgan Laws for C,

then: C "3a  8   0 or 3a  8 1"
 1.2.2- Logical Equivalences…

Example:
The negation of the statement:
“The summer in Maine is hot and sunny”
Is the statement:
“The summer in Maine is NOT hot OR NOT
sunny.”
 1.2.2- Logical
Equivalences…

Example:
The negation of the statement:
“Tom has a cellphone AND he has a laptop
computer”
Is the statement:
“Tom does NOT have a cellphone OR he does
NOT have a laptop computer.”
 1.2.2- Logical
Equivalences…

Equivalences Equivalences
p→q ≡ ¬pvq p↔q ≡ (p→q) ^ (q→p)
p→q ≡ ¬q → ¬p p↔q ≡ ¬p ↔ ¬q
pvq ≡ ¬ p → q p↔q ≡ (p ^ q) v (¬p ^ ¬q)
p^q ≡ ¬ (p → ¬q) ¬ p↔q ≡ p↔ ¬q
¬(p→q) ≡ p^¬q
(p→q) ^(p→r) ≡ p → (q^r)
(p→r) ^ (q→r) ≡ (pvq) → r
(p→q) v (p→r) ≡ p→ (qvr)
(p→r) v (q→r) ≡ (p^q) → r
 1.2.2- Logical
Equivalences…
Example:
E
Show that  p   p  q   q is a
tautology.
E   p   p  q   q
Solution:
   p  p    p  q   q
  0   p  q   q
  p  q  q
 p q  q
 p 1
 1.
 1.3- Predicates and
Quantifiers

 Introduction
 Predicates
 Quantifiers
 1.3.1-
Introduction

A type of logic used to express the meaning of a

wide range of statements in mathematics and
computer science in ways that permit us to
reason and explore relationships between
objects.
 1.3.2-
Predicates
Propositional
Logic
o Q =“ 5 is a prime number.”
o Q ≡ True

Predicate
Logic
o X>0
o P(X)=“X is a prime number” ,
called propositional function at X.
o P(2)=”2 is a prime number” ≡True
o P(4)=“4 is a prime number” ≡False
 1.3.2- Predicates

o Q(X1,X2,…,Xn) , n-place/ n- predicate

o Example: “x = y+3”  Q(x, y)
o Q(1,2) ≡ “1 = 2+3” ≡ false
o Q(5,2) ≡ “5 = 2+3” ≡ true
 1.3.2- Predicates

Example
 1.3.2- Predicates

o Predicates are pre-conditions and post-

conditions of a program.
o If x>0 then x:=x+1
o Predicate: “x>0”  P(x)
o Precondition: P(x)
o Postcondition: Q(x)
Pre-condition (P(…)) : condition describes
valid input.
Post-condition (Q(…)) : condition
describes valid output of the codes.
Show the verification that a program
always produces the desired output:
P(…) is true
Executing Step 1.
Executing Step 2.
…..
Q(…) is true
 1.3.2- Predicates

Example

State the value of x after the statement:

if x >1 then x:=1 is executed, where P(x)
is the statement “x >1”, if the value of x
when this statement is reached is
a)x = 5.
b)x = 0.
c)x = 1.
d)x = 3.
 1.3.3-
Quantifiers
o The words in natural language: all, some, many, none, few,
….are used in quantifications.
o Predicate Calculus : area of logic that deals with predicates
and quantifiers.
o The universal quantification of P(x) is the statement
“P(x) for all values of x in the domain”. Notation : xP(x)
o The existential quantification of P(x) is the statement
“There exists an element x in the domain such that P(x)”.
Notation : xP(x)
o Uniqueness quantifier: !x P(x) or 1xP(x)
o xP(x) v Q(y) :
o x is a bound variable
o y is a free variable

- Universal quantification : "all of," "for each"

"given any" "for arbitrary" "for each“.
 1.3.5- Precedence of
Quantifiers

o Quantifiers have higher precedence than all

logical operators from propositional calculus.
o xP(x) v Q(x)  (xP(x)) v Q(x)
o  has higher precedence. So,  affects on
P(x) only.
 1.3.6- Logical Equivalences Involving
Quantifiers

Statements involving predicates and quantifiers are logically

equivalent if and only if they have the same truth value no
matter which predicates are substituted into the statements and which
domain of discourse is used for the variables in these propositional
functions.
 x (P(x) ^ Q(x)) ≡ xP(x) ^ xQ(x)
– Proof: page 39

Expression Equivalence Expression Negation

¬xP(x) x ¬P(x) xP(x) x ¬P(x)
¬ xP(x) x ¬P(x) xP(x) x ¬P(x)
 1.3.7-
Translating
Example

 For every student in the class has studied calculus

 For every student in the class, that student has studied
calculus
 For every student x in the class, x has studied calculus
 x (S(x) → C(x))
 1.3.7- Translating

Example
 1.3.7- Translating

Example
 1.4 Negating nested
quantifiers

¬ xy(xy=1) ≡ x ¬y (xy=1) // De Morgan laws

≡ (x) (y) ¬(xy=1)
≡ (x) (y) (xy  1)
 1.4 Negating nested
quantifiers
Example
 1.4 Negating nested
quantifiers
Example
 1.4 Negating nested
quantifiers
Example
 1.4 Negating nested
quantifiers
Example
 1.5- Rules of
Inference

 Definitions
 Rules of Inferences
 1.5.1-
Definitions

 Proposition 1 Hypothesis / antecedent / premise.

 Proposition 2
 Proposition 3
Arguments 2,3,4 are
 Proposition 4 premises of argument 5
 Proposition 5
 ………
Arguments
 Conclusion Propositional
Equivalences
 1.5.2- Rules
Inferences

Rule Tautology Name

[(p→q) ^p] → q
p q
(If you work hard then you
p will pass the examination)
q AND (You work hard) Modus ponen

you will pass the

examination
p q [ (p → q) ^¬q ] → ¬p
q If she is good at learning
 p she will get a prize
AND she did not get a prize Modus tollen

She is not good at

 1.5.2- Rules Inferences

Rule Tautology Name

p q [(p →q) ^(q →r)] →(p→r) Hypothetical
If the prime interest rate goes up then syllogism
q r the stock prices go down.
p r AND If the stock prices go down then
most people are unhappy.

If the prime interest rate goes up then

most people are unhappy.
 1.5.2- Rules Inferences

Rule Tautology Name

p  q [(pvq) ^¬p] → q
Power puts off or the lamp is
p malfunctional Disjunctive
q AND Power does not put off syllogism

the lamp is malfunctional

p →(pvq)
p
It is below freezing now
p q Addition
It is below freezing now or raining now
(p^q) →p
p q It is below freezing now and raining now
Simplication
p
It is below freezing now
 1.5.2- Rules Inferences

Rule Tautology Name

p [(p) ^(q)) → (p^q)
q Conjunction
p^q
pvq [(pvq) ^(¬pvr)] →(qvr)
¬pvr Jasmin is skiing OR it is not snowing
qvr AND It is not snowing OR Bart is
playing hockey Resolution

Jasmin is skiing OR Bart is playing

hockey
 1.5.2- Rules Inferences

Rule Tautology Name

p [(p) ^(q)) → (p^q)
q Conjunction
p^q
pvq [(pvq) ^(¬pvr)] →(qvr)
¬pvr Jasmin is skiing OR it is not snowing
qvr AND It is not snowing OR Bart is
playing hockey Resolution

Jasmin is skiing OR Bart is playing

hockey
 1.5.3-
Fallacies

 If you do every problem in this book then you will learn discrete
mathematic
You learned mathematic
(p → q) ^q
=(¬ p v q) ^ q
(absorption law)
=q
 No information for p
p can be true or false  You may learn discrete mathematic but
you might do some problems only.
 1.5.3- Fallacies

o (p → q)^q  p is not a tautology

( it is false when p = 0, q = 1)
o (p  q)^¬p  ¬q is not a tautology
(it is false when p = 0, q = 1)
 1.5.4- Rules of Inference for
Quantified Statements

Rule Name
xP(x) Universal Instantiation
P(c)
P(c) for arbitrary c Universal generalization
xP(x)
xP(x) Existential instantiation
P(c) for some element c
P(c) for some element c Existential generalization
xP(x)
 Rules of Inference for Quantified
Statements…
 “All
student are in this class had taken the
course PFC”
 “Harry is in this class”
 “Had Harry taken PFC?”
 x(P(x) → Q(x))
 P(Harry) → Q(Harry)
 P(Harry)
 Q(Harry) // conclusion
 Rules of Inference for Quantified
Statements…
 “All
student are in this class had taken the
course PFC”
 “Harry is in this class”
 “Harry had taken PFC”. CORRECT
 x(P(x) → Q(x)) Premise

 P(Harry) → Q(Harry) Universal Instantiation

 P(Harry) Modus ponens

 Q(Harry) // conclusion
 Rules
Inferences…

a) Everyone who eats granola every day is

healthy. Linda is not healthy.
Therefore, Linda does not eat granola every
day.
 Rules Inferences…

a) Everyone who eats granola every day is

healthy. Linda is not healthy. Therefore, Linda

does not eat granola every day. Correct.

 Rules
Inferences…

b) All parrots like fruit.

My pet bird is not a parrot.

Therefore, my pet bird does not like fruit.

Incorrect.
 Rules
Inferences…

b) All parrots like fruit. My pet bird is not a

parrot. Therefore, my pet bird does not like

fruit.
 Rules
Inferences…

c) If Tom knows French, Tom is smart. But Tom

does not know French. So, he is not smart. NO

VALID
 Rules
Inferences…

d) Ceci can not go fishing if she does not have a

bike. Last week, Ceci went fishing with her

friends. Therefore, she has got a bike.

 Summary

 Propositional Logic
 Propositional Equivalences
 Predicates and Quantifiers
 Nested Quantifiers
 Rules and Inference
THANK YOU