EMath 1105 - Discrete Mathematics I for SE
EMath 1105
DISCRETE MATHEMATICS I for SE
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
Quantifiers
Proof of Techniques
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS
QUANTIFIERS AND FIRST – ORDER LOGIC
- quantifier is a symbol that quantifies the
variables. If we use a quantifier before a predicate,
then the predicate becomes a proposition.
Quantifications:
➢ all
➢ some
➢ many
➢ none
➢ few
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS
TWO TYPES OF QUANTIFICATION:
1. Universal Quantification ∀
➢ tells us that a predicate is true for every element
under consideration
2. Existential Quantification (∃)
➢ tells us that there is one or more element under
consideration for which the predicate is true.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS
Universal Quantification of 𝑷(𝒙) is the statement
➢“P(x) for all values of x in the domain.”
The notation ∀𝑥 𝑃(𝑥) denotes the universal quantification
of 𝑃(𝑥).
∀ 𝑥 𝑃(𝑥) as “𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥𝑃(𝑥)”, “𝑓𝑜𝑟 𝑒𝑣𝑒𝑟𝑦 𝑥𝑃(𝑥)”
An element for which 𝑃(𝑥) is false is called a
counterexample of ∀ 𝑥 𝑃(𝑥).
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS
EXAMPLE 1: Let 𝑃(𝑥): 𝑥 is even number and the
universe of discourse for 𝑥 is the set {1, 2, 3, 4}.
Find the truth value of ∀ 𝑥 𝑃(𝑥 ).
EXAMPLE 2: Let 𝑃(𝑥): 𝑥 ≠ 5 and the universe
of discourse for 𝑥 is the set {1, 2, 3, 4}.
Find the truth value of ∀ 𝑥 𝑃 (𝑥).
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS
Existential quantification of 𝑷(𝒙) is the statement
“There exists some 𝑥 in the universe of discourse
such that P(x)” denoted by the symbol ∃ 𝒙 𝑷( 𝒙 )
EXAMPLE 1: Let 𝑃(𝑥): 𝑥 is even number and the
universe of discourse for 𝑥 is the set {1, 2, 3, 4}.
Find the truth value of ∃ 𝑥 𝑃(𝑥).
EXAMPLE 2: Let 𝑃(𝑥): 𝑥 > 5 and the universe
of discourse for 𝑥 is the set {1, 2, 3, 4}. Find the
truth value of ∃ 𝑥 𝑃(𝑥).
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS
Free and Bound Variables
A variable in a predicate is said to be bound if a
quantifier is used before it. A variable is free if it is not
bounded.
The variable 𝑥 is a bound variable in both
∀ 𝑥 𝑃 (𝑥, 𝑦) and ∃ 𝑥 𝑃 (𝑥, 𝑦) whereas 𝑦 is a free
variable.
The scope of a quantifier is the formula immediately
following the quantifier. 𝑃(𝑥, 𝑦) is the scope of the
quantifier in both the cases.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS AND FIRST – ORDER LOGIC
Symbolize the following by using quantifiers, predicates,
and logical connectives:
Example 1: The square of any real number is
greater than or equal to zero.
let: 𝑃(𝑥): 𝑥 is a real number
𝑄 𝑥 : 𝑥2 ≥ 0
Then in symbols, the given sentence takes the form
∀𝑥 𝑃 𝑥 𝑄 𝑥
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS AND FIRST – ORDER LOGIC
Symbolize the following by using quantifiers, predicates,
and logical connectives:
Example 2: Some integers are multiples of 7.
let: 𝑃(𝑥): 𝑥 is an integer
𝑄(𝑥): 𝑥 is multiple of 7.
Then in symbols, the given sentence takes the form
∃ 𝑥 𝑃(𝑥) 𝑄(𝑥)
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS AND FIRST –ORDER LOGIC
Symbolize the following by using quantifiers, predicates, and
logical connectives:
Example 3: There is an integer 𝒙 such that 𝒙𝟐 = 𝟏𝟔.
let: 𝑄(𝑥): 𝑥 2 = 16
Then in symbols, the given sentence takes the form
∃𝑥𝑄 𝑥
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
QUANTIFIERS AND FIRST – ORDER LOGIC
In the following, use
𝑃(𝑥) ∶ 𝑥 is an odd integer
𝑄(𝑥) ∶ 𝑥 is a prime integer
𝑅(𝑥) ∶ 𝑥 2 is an odd integer
Write a statement in English corresponding to each symbolic statement.
(a) ∀𝑥 𝑃 𝑥 𝑅 𝑥
Sol’n: The squares of all odd integers are odd.
(b) ∀𝑥 𝑃 𝑥 ∧ 𝑄 𝑥
Sol’n: All integers are odd and prime.
(c) ∃ 𝑥 (𝑃 𝑥 ∧ 𝑄(𝑥))
Sol’n: Some odd integer are prime.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
Quantifiers
Proof of Techniques
EMath 1105 - Discrete Mathematics I for SE
PROOF TECHNIQUES
• In the previous topics, we presented various ways of using
logical arguments and delivering conclusions.
• In mathematics and computer science, mathematical logic
is used to prove theorems and the correctness of programs.
• After formally defining the term theorem, we describe
some general techniques that are used in proving theorems
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
PROOF TECHNIQUES
Recall:
Theorem – is a statement that can be shown to be true
(under certain conditions)
For example,
➢ If 𝑥 is an integer and 𝑥 is odd, then 𝑥 2 is odd,
or, equivalently,
➢ For all integers 𝑥, if 𝑥 is odd, then 𝑥 2 is odd.
This statement can be shown to be true.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
PROOF TECHNIQUES
Theorem are typically stated as follows:
1) As facts
▪ 6 is an even integer.
▪ The equation 𝑥 2 + 1 = 0 has no solutions in real numbers.
2) As Implications/conditional statement
▪ For all integers x, if x is even, then x + 1 is odd.
3) As bi-implications/biconditional statement
▪ For all integers x, x is even if and only if x is divisible by 2.
❖ As proof may consists of previously known facts, proved results,
or previous statements of proof.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
1. DIRECT PROOF
The most straight forward type of proof; the
conclusion is established by logically the axioms,
definitions, and earlier theorems
Example:
Prove that, for all integers 𝒙, if 𝒙 is odd, then
𝒙𝟐 is odd.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
DIRECT PROOF
Example:
Prove that, for all integers 𝒂, if 𝒙 is odd, then 𝒂𝟐 is odd.
Solution: Let “𝑎” be an integer such that “𝑎2 ” is odd.
Then,
𝑎 = 2𝑛 + 1 for some integer n
𝑎2 = 2𝑛 + 1 2
𝒂𝟐 = 𝟒𝒏𝟐 + 𝟒𝒏 + 𝟏
𝒂𝟐 = 𝟐(𝟐𝒏𝟐 + 𝟐𝒏) + 𝟏
𝒂𝟐 = 𝟐𝒎 + 𝟏
where 𝒎 = 𝟐𝒏𝟐 + 𝟐𝒏 𝒊𝒔 𝒂𝒏 𝒊𝒏𝒕𝒆𝒈𝒆𝒓
∴ 𝒂𝟐 is an odd integer.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
PROOF TECHNIQUES
2. INDIRECT PROOF
Indirect proof infers the conclusion “if p then q” from the
premise “if not q then not p”
For example, this proof can be used to established that,
given an integer 𝑥, if 𝑥² is even, thus 𝑥 is even.
Suppose 𝑥 is not even. Then 𝑥 is odd. The product of two odd
numbers is odd, hence 𝑥² = 𝑥 ∙ 𝑥 is odd. Thus 𝑥² is not even.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
PROOF TECHNIQUES
3. PROOF BY CONTRADICTION
It is shown that if some statement were true, a logical
contradiction occurs, hence the statement must be false.
Example: Prove that 2 is irrational by giving a proof of
contradiction.
Solution: Let: p = 2 is irrational.
So by definition 2 = a/b where a and b are non-zero integers
with no common factor
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Thus, 𝑏 2 = 𝑎
Squaring both sides: 2𝑏² = 𝑎²
So 𝑎² is even, which implies that a must also be even
So we can write a = 2c, where c is also an integer
Substitution into the original equation: 2𝑏2 = 2𝑐 2 = 4𝑐2
Dividing both sides by 2 yields 𝑏2 = 2𝑐2
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
4. PROOF BY MATHEMATHICAL INDUCTION
▪In proof by mathematical induction, a single
“base case” is proved, and an ”induction rule” is
proved, which establishes that a certain case
implies the next case.
▪Applying the induction rule repeatedly, starting
from the independently proved base case, proves
many, often infinitely many other cases.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
5. Proof by construction/Proof by example
Is the construction of a concrete example with a
property to show that something having that
property exists.
It can also be used to construct a counter example
to disprove a proposition that all elements have a
certain property.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Proof by construction/Proof by example
Example: Show that the statement: “Every positive integer
is the sum of the squares of two integers” is false.
Solution:
To show that this statement is false, we look for a
counterexample, which is a particular integer that is not the
sum of the squares of two integers
3 – cannot be written as the sum of the squares of two
integers
Therefore, we have shown that “ Every positive integer is
the sum of the squares of two integers.” is false.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
6. Proof by equivalence/Bi-conditional Proof
A statement of the form p q, we show that
p → q and q → p are both true
The validity of this approach is based on the
tautology. (p q) (p → q) Λ (q → p)
Example:
(1) Prove that the product of even integers is an even integer.
Solution:
Suppose: x & y are even integers
Then: x = 2m & y = 2n for some integers m & n
▪Therefore, xy = (2m)(2n) = 4mn = 2(2mn) = 2t
where t = 2mn
▪Because, m & n are integers, t is an integer
Hence, xy is an even integer. ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
➢ In the previous topics, we defined and discussed basic properties of
statements (also called propositions).
➢ There, we were interested only in the truth and falsity of the statement.
➢ The structure of the statement was not taken into account.
➢ The logic that we discussed before is categorized as the statement logic,
or propositional logic.
➢ There are many justified arguments whose validity cannot be tested
within the framework of propositional logic.
For example,
Every integer is a rational number.
3 is an integer.
Therefore, 3 is a rational number.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
Every integer is a rational number.
3 is an integer.
Therefore, 3 is a rational number.
➢ In mathematics, this is a justified argument.
➢ In propositional logic, to check the validity of this argument we
symbolize it using statement letters.
Let p denote: Every integer is a rational number.
q denote: 3 is an integer.
r denote: 3 is a rational number.
The above argument takes the form
p
q
∴𝑟
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
➢ Now, this argument is valid if the statement formula (𝑝 ∧ 𝑞) → 𝑟 is a
tautology.
➢ For if (𝑝 ∧ 𝑞) → 𝑟 is a tautology, then for any assignment of truth values
to p, q and r, the truth value of (𝑝 ∧ 𝑞) → 𝑟 must be T.
➢ However, if we assign T to p, T to q, and F to r then the truth value is F.
➢ Hence, according to the propositional logic, the argument is not valid.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
➢ If we introduce logical notions called predicates and quantifiers, then
most of the everyday arguments (most of the arguments in
mathematics and computer science) can be symbolized in such a way
that we can verify the validity of the arguments.
➢ For example,
x is an integer.
Let us denote this sentence by P(x):
P(x): x is an integer.
Then P(5): 5 is an integer, is true.
P(2.5): 2.5 is an integer, is false.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
➢ To study the properties of such sentence, we need to extend the
framework of propositional logic.
➢ The discussion of logic that follows is categorized as first-order logic.
➢ Once again consider the sentence
x is an integer.
Two parts of the sentence
x – the variable
is an integer – relation
➢ We call the relation “ is an integer” – the predicate, denoted by P.
➢ Moreover, P(x) is called a predicate or propositional function.
➢ Notice that there is a set of values, (in this case, say real numbers),
associated with P(x), called the domain.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
Definition: Let x be a variable and D be a set; P(x) is a sentence.
Then P(x) is called a predicate or propositional function
with respect to the set D if for each value of x in D, P(x) is a statement
[P(x) is true or false].
Moreover, D is called the domain of the discourse and x is
called the free variable.
Example:
P(x): x is an even integer,
where the domain of the discourse is the set of integers.
Then
P(4): 4 is an even integer, is T.
P(3): 3 is an even integer, is F.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
➢ The predicates that we considered until now involved only one variable.
➢ We can also have predicates involving two or more variables.
Example: P(x,y): x equals y + 1.
Hence, the predicate P(x,y) involves two variables and represents
the relation “equal”.
Let the domain be set of integers.
x = 2 and y = 1 : x=2=1+1=y+1 P(2,1) is T.
x = 5 and y = 4 : x=5=4+1=y+1 P(5,4) is T.
x = 6 and y = 4 : x=6≠4+1=y+1 P(6,4) is F.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
Quantifiers and First-Order Logic
Example: Let Q(x,y) denote the sentence
Q(x,y): 𝑥 2 is greater than or equal to y.
Let the domain be the set of integers.
Here the predicate Q(x,y) involves two variables.
Consider Q(2,3),
𝑥 2 = 4 > 3, it follows that Q(2,3) is true.
However, Q(2,5) is false…
22 = 4 is neither greater than 5 or equal to 5.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
ALGORITHM
➢ An algorithm is a finite sequence of precise
instructions for performing a computation or
for solving a problem.
➢ The term algorithm is a corruption of the name
al-Khowarizmi, a mathematician of the ninth
century, whose book on Hindu numerals is the
basis of modern decimal notation.
➢ Originally, the word algorism was used for the
rules for performing arithmetic using decimal
notation.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
ALGORITHM
PROPERTIES OF ALGORITHMS
There are several properties that algorithms generally share. They are
useful to keep in mind when algorithms are described. These properties
are:
1. Input. An algorithm has input values from a specified
set.
2. Output. From each set of input values an algorithm
produces output values from a specified set.
The output values are the solution to the
problem.
3.Definiteness. The steps of an algorithm must be
defined precisely.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
ALGORITHM
4. Correctness. An algorithm should produce the correct
output values for each set of input values.
5. Finiteness. An algorithm should produce the desired output
after a finite (but perhaps large) number of
steps for any input in the set.
6. Effectiveness. It must be possible to perform each step of
an algorithm exactly and in a finite amount of
time.
7. Generality. The procedure should be applicable for all
problems of the desired form, not just for a
particular set of input values.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
GREEDY ALGORITHM
➢ One of the simplest approaches often leads to a solution
of an optimization problem.
➢ This approach selects the best choice at each step,
instead of considering all sequences of steps that may
lead to an optimal solution.
Algorithms that make what seems to be the “best” choice at
each step are called greedy algorithms.
➢ Once we know that a greedy algorithm finds a feasible
solution, we need to determine whether it has found an
optimal solution.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
GREEDY ALGORITHM
➢ Note that we call the algorithm “greedy” whether or not it
finds an optimal solution.
➢ To do this, we either prove that the solution is optimal or we
show that there is a counterexample where the algorithm
yields a non-optimal solution.
➢ Greedy algorithm is also called the shortest path algorithm.
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
EMath 1105 - Discrete Mathematics I for SE
REFERENCE:
Rosen, K. H. (2012). Discrete Mathematics and Its
Applications, 8th Edition: McGrawHill
ENGR. M.M. ALIMO-OT / ENGR. Y.S.SACRAMENTO
FACULTY – ECE DEPARTMENT
