DISCRETE

MATHEMATICS
AND
ITS APPLICATIONS
Book: Discrete Mathematics and Its Applications
Author: Kenneth H. Rosen
Seventh Edition
McGraw-Hill International Edition
 Chapter 1
The Foundations:
Logic and Proofs
 Objectives
l Explainwhat makes up a correct
mathematical argument
l 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

l Proposition is a declarative sentence that is either

true or false but not both.
l Proposition is a sentence that declares a fact.
l Examples:
* Bà Tưng is one of descendants of Bà Trưng *
Ha Noi is not the capital of Vietnam
* 1+5 < 4 OK
* What time is it?
* X+Y=Z No OK
 1.1.1- Definitions…

l Truth table
– I am a girl

p
True/ T / 1
False / F / 0
 1.1.1- Definitions…
l Negation of proposition p is the statement “ It is not
case that p”.
l Notation: ¬p (or p )

p
1 0

0 1
 1.1.1- Definitions…
l 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…

l Disjunction of 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…

l Exclusive-or (xor) of propositions p and q, denoted

by p Å q

p q pÅq
0 0 0
0 1 1
1 0 1
1 1 0
Åq
 1.1.1- Definitions…
l Implication: p → q (p implies q)
l p: hypothesis / antecedent / premise
l q: conclusion / consequence
l 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
0 1 1 (p → q)
p=0, q=0 ,
1 0 0 so (p→q) is true.
1 1 1
 1.1.1- Definitions…
l Biconditional statement p ↔ q is the proposition “ p if and
only if q”
l 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

(2) ¬
(3) ^
(4) v
(5) →
(6) ↔
 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

l Tautology is a proposition that is always true

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

l Show that p → q and ¬p v q are logically

equivalent.
 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…

Equivalence Name
¬ (p^q) ≡ ¬pv¬q ¬(pvq) ≡ De Morgan Laws
¬p^¬q
pv (p^q)≡ p p^(pvq)≡ p Absorption Laws
pv¬p ≡ T p^¬p≡ F Negation Laws
 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.3- Predicates and Quantifiers

l Introduction
l Predicates
l Quantifiers
 1.3.1- Introduction

l 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 – vị từ

lX >0
l P(X)=“X is a prime number” , called
propositional function at X.
l P(2)=”2 is a prime number” ≡True
l P(4)=“4 is a prime number” ≡False
 1.3.2- Predicates – vị từ
l Q(X1,X2,…,Xn) , n-place/ n-ary predicate
l Example: “x=y+3” è Q(x,y)
Q(1,2) ≡ “1=2+3” ≡ false
Q(5,2) ≡ “5=2+3” ≡ true
 1.3.2- Predicates…
l Predicates are pre-conditions and post-
conditions of a program.
Pre-condition (P(…)) : condition describes
l If x>0 then x:=x+1 valid input.
Post-condition (Q(…)) : condition
– Predicate: “x>0” è P(x) describes valid output of the codes.
– Pre-condition: P(x) Show the verification that a program
always produces the desired output:
– Post-condition: P(x) P(…) is true
Executing Step 1.
l T:=X; Executing Step 2.
X:=Y; …..
Q(…) is true
Y:=T;
- Pre-condition: “x=a and y=b” è P(x, y)
- Post-condition: “x=b and y=a” è Q(x, y)
 1.3.3- Quantifiers – Lượng từ
l The words in natural language: all, some, many, none,
few, ….are used in quantifications.
l Predicate Calculus : area of logic that deals with
predicates and quantifiers.
l The universal quantification of P(x) is the statement
“P(x) for all values of x in the domain”. Notation : "xP(x)
l The existential quantification of P(x) is the statement
“There exists an element x in the domain such that P(x)”.
Notation : $xP(x)
l Uniqueness quantifier: $!x P(x) or $1xP(x)
l "xP(x) v Q(y) :
l x is a bound variable
l y is a free variable
 1.3.4- Quantifiers and Restricted
Domains
"x<0(x2 > 0), "y ¹ 0(y3 ¹ 0), $z>0(z2 =2)
çè
"x(x<0 → x2 > 0), "y(y ¹ 0 → y3 ¹ 0), $z(z>0 ^ z2
=2)

Restricted domains
 1.3.5- Precedence of Quantifiers

l Quantifiers have higher precedence than

all logical operators from propositional
calculus.
l "xP(x) v Q(x) è ("xP(x)) v Q(x)
l " 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.
l "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

l For every student in the class has studied

calculus
l For every student in the class, that student
has studied calculus
l For every student x in the class, x has
studied calculus
l "x (S(x) → C(x))
 1.4- Nested Quantifiers

l Example: ∀x∃y(x + y = 0)

It is the same thing as ∀x Q(x),

l Note:
where Q(x) is ∃yP (x, y), The
pictur
e
can't

where P (x, y) is x + y = 0. be
displa
yed.
 1.4.1- Understanding Statements
Involving Nested Quantifiers
Examples: Assume that the domain for the
variables x and y consists of all real
numbers.
∀x∀y(x + y = y + x)
∀x∃y(x + y = 0).
Solution:
It says that x + y = y + x, for all real numbers
x and y. This is the commutative law for
addition of real numbers.
 1.4.2- The Order of Quantifiers

l
 1.5- Rules of Inference

l Definitions
l Rules of Inferences
 1.5.1- Definitions

l Proposition 1 // Hypothesis
l Proposition 2
Arguments 2,3,4
l Proposition 3 are premises of
argument 5
l Proposition 4
l Proposition 5 Arguments
Propositional
l ……… Equivalences
l Conclusion
 1.5.2- Rules Inferences
Rule Tautology Name
p [p^ (p→q)] → q Modus ponen
p →q You work hard
\q If you work hard then you will pass
the examination
\you will pass the examination
¬q [¬q ^(p → q)] → ¬p Modus tollen
p→q She did not get a prize
\¬p If she is good at learning she will get
a prize
\She is not good at learning
 1.5.2- Rules Inferences

Rule Tautology Name

p [(p →q) ^(q →r)] →(p→r) Hypothetical
→q If the prime interest rate goes up then syllogism
q →r the stock prices go down.
\p →r If the stock prices go down then most
people are unhappy.
If the prime interest rate goes up then
most people are unhappy.
 Rules Inferences…
Rule Tautology Name
pvq [(pvq) ^¬p] → q Disjunctive
¬p Power puts off or the lamp is syllogism
\q malfunctional
Power doesn’t put off
the lamp is malfunctional
p p →(pvq) Addition
\pvq It is below freezing now
It is below freezing now or raining
now
p^q (p^q) →p Simplication
\p It is below freezing now and raining
now
It is below freezing now
 Rules Inferences…

Rule Tautology Name

p [(p) ^(q)) → (p^q) Conjunction
q
\p^q
pvq [(pvq) ^(¬pvr)] →(qvr) Resolution
¬pvr Jasmin is skiing OR it is not snowing
\qvr It is snowing OR Bart is playing hockey
Jasmin is skiing OR Bart is playing
hockey
 1.5.3- Fallacies
l 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.
 Fallacies…

l (p → q)^q → p is not a tautology

( it is false when p = 0, q = 1)
l (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…

l “All
student are in this class had taken the
course PFC”
l “HB is in this class”
l “Had HB taken PFC?”
l "x(P(x) → Q(x)) Premise

l P(HB) → Q(HB) Universal Instantiation

l P(HB) Modus ponens

l Q(HB) // conclusion
 Summary
l Propositional Logic
l Propositional Equivalences
l Predicates and Quantifiers
l Nested Quantifiers
l Rules and Inference
THANK YOU