MATH211

Discrete Mathematics
Instructor: Selin Selen Özbek Şimşek
E-mail: [email protected]
 Textbook: Discrete Mathematics and its Applications; Kenneth H. Rosen,
Seventh Edition, (2011)

Other Books :
• Discrete Mathematics with Applications; Susanna S. Epp, Fourth Edition,
Cengage Learning, (2010)
• Discrete Mathematics; Kenneth A. Ross, Charles R. Wright, Fifth Edition,
Prentice Hall (2002)

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Chapter 1:
The Foundations: • Basic concepts, logic
Logic and Proofs • Proof methods

Course book.
Discrete Mathematics and its Applications;
Kenneth H. Rosen, Seventh Edition, (2011)

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Methods of Proving Theorems

Proving mathematical theorems can be difficult. To construct proofs, we need different

proof methods:
1. Direct Proofs
2. Proof by Contraposition
3. Proofs by Contradiction

1) Direct Proof:

A direct proof of a conditional statement p → q is constructed when

• the first step is the assumption that p is true;
• subsequent steps are constructed using rules of inference,
• with the final step showing that q must also be true.
In a direct proof, we assume that p is true and use axioms, definitions, and
previously proven theorems, together with rules of inference, to show that q must also be
true.
Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.
 Example: Give a direct proof of the theorem “If n is an odd integer, then 𝑛2 is odd.”
Solution: p: n is an odd number , q: 𝑛2 is odd. 𝑝 → 𝑞.
1. Assume that p is true. « n is an odd number»
2. Then we have n=2k+1, where k is a real number.
3. 𝑛2 = 2𝑘 + 1 2 = 4𝑘 2 + 4𝑘 + 1 = 2 2𝑘 2 + 2𝑘 + 1 = 2m + 1
4. 𝑛2 is an odd number.

Example: Give a direct proof that «if m and n are both perfect squares, then 𝑛𝑚 is also a
perfect square».
Definition: An integer 𝑎 is a perfect square if there is an integer 𝑏 such that 𝑎 = 𝑏 2
Solution: p: m and n are both perfect squares q: 𝑛𝑚 is a perfect square
1) Assume that p is true. «m and n are both perfect squares»
2) Then we have 𝑚 = 𝑠 2 𝑎𝑛𝑑 𝑛 = 𝑡 2 where 𝑠 and 𝑡 are real numbers.
3) m. n = 𝑠 2 𝑡 2 = 𝑠𝑠 𝑡𝑡 = 𝑠𝑡 𝑠𝑡 = (𝑠𝑡)2 = 𝑟 2
4) 𝑛𝑚 is a perfect square.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 2) Proof by Contraposition:

Proofs of theorems of this type that are not direct proofs, that is, that do not start
with the premises and end with the conclusion, are called indirect proofs.

An extremely useful type of indirect proof is known as proof by contraposition.

Proofs by contraposition make use of the fact that the conditional statement p → q is
equivalent to its contrapositive, ¬q →¬p. This means that the conditional statement p → q
can be proved by showing that its contrapositive, ¬q →¬p, is true.

In a proof by contraposition of p → q, we assume that ¬q is true and use axioms,

definitions, and previously proven theorems, together with rules of inference, to show that
we show that ¬p must also be true.
𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Example: Let n be an inetger. Prove that «if 3n + 2 is odd, then n is odd».
Solution p: 3n + 2 is odd q: n is odd.
1.way (direct proof)
1. Assume that p is true. «n is an integer and 3n + 2 is odd»
2. Then we have 3𝑛 + 2 = 2𝑘 + 1, where k is a real number.
3. We see that 3n + 1 = 2k, but there does not seem to be any direct way to conclude
that n is odd.

2.way (proof by contraposition): 𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝

¬𝑞: n is not odd ¬𝑝: 3n+2 is not odd
¬𝑞: n is even ¬𝑝: 3n+2 is even

1. Assume that ¬𝑞 is true. «n is even»

2. Then we have n=2k, where k is a real number.
3. 3𝑛 + 2 = 3. 2𝑘 + 2 = 6𝑘 + 2 = 2 3𝑘 + 1 = 2. m , where m is a real number.
4. 3n+2 is even .

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 3) Proof by Contradiction:

It is another type of indirect proof. Proof by contradiction proceeds as follows:

• First type
1. The proposition to be proved is P.
2. Assume ¬P.
3. Find a contradiction.
4. Conclude P.

• Second Type
1. The proposition to be proved is 𝑝 → 𝑞.
2. Assume p and ¬𝑞.
3. Find a contradiction.
4. Conclude 𝑝 → 𝑞.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Example: Prove that 2 is irrational by giving a proof by contradiction.

Remark: The real number r is rational if there exist integers p and q with q≠0 such that
r = p/q. A real number that is not rational is called irrational.

Solution:
1) p: 2 is irrational.
2) Assume ¬𝑝: 2 is a rational number.
3) Find a contradiction:
Assume that 2 is a rational number. Then there are m, n (n≠0) integers such that
2 =m/n , where m and n have no common factors. We have

𝑚2 is an even number.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 We conclude that m is also an even number. For any integer p, we have

Substitute this result to the following equality

𝑛2 is an even number.
We conclude that n must be even as well. That is, 2 divides both m and n.
« 2 =m/n , where m and n have no common factors.»
Our assumption of ¬p leads to the contradiction that 2 divides both m and n .

4) Conclude p: 2 is irrational.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Example:

Solution: p: 3n + 2 is odd q: n is odd.

1. The proposition to be proved is 𝑝 → 𝑞.

2. Assume p and ¬𝑞: «3n+2 is odd» and «n is even»
3. Find a contradiction.

Assume thar «3n+2 is odd» and «n is even». Because n is even, there is an

integer k such that n = 2k. This implies that

3𝑛 + 2 = 3 2𝑘 + 2 = 6𝑘 + 2 = 2 3𝑘 + 1 = 2𝑡

where t is an integer. Because 3n + 2 is 2t , 3n + 2 is even. We have a contradiction.

4. Conclude 𝑝 → 𝑞.
Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.
 Proofs of Equivalence
To prove a theorem that is a biconditional statement, that is, a statement of the
form 𝑝 ↔ 𝑞, we show that p → q and q → p are both true.

Example: Let n be an integer. Prove the theorem:

«n is odd if and only if 𝑛2 is odd»
p: n is odd
q: 𝑛2 is odd
To prove this theorem, we need to show that p → q and q → p are true.

1.(𝑝 → 𝑞): We can use Direct Proof Method for this part.
Assume that n is odd. Then we have n=2k+1 , where k is an integer.
𝑛2 = (2𝑘 + 1)2 = 4𝑘 2 + 4𝑘 + 1 = 2 2𝑘 2 + 2𝑘 + 1 = 2𝑚 + 1
where m is an integer. We conclude that 𝑛2 is odd.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 2. (q→ 𝑝 ) : We can use proof by contraposition method.
q → 𝑝 ≡ ¬𝑝 → ¬𝑞

We want to prove the following statement

«if n is even, then 𝑛2 is even»

If n is even, then n=2k , where k is an integer. We have

𝑛2 = 4𝑘 2 =2(2𝑘 2 )=2t

where t is an integer. Thus 𝑛2 is even as well.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Counterexample

A statement of the form ∀xP(x) is false, we need only find a counterexample, that is,
an example x for which P(x) is false. When presented with a statement of the form ∀xP(x),
which we believe to be false we look for a counterexample.

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. For example 3 cannot
be written as the sum of the squares of two integers. To show this is the case, note that the
only perfect squares not exceeding 3 are 02 = 0 and 12 = 0 . There are no numbers a and
b such that 3=𝑎2 + 𝑏 2 .

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Existence and Uniqueness Proofs

Some theorems assert the existence of a unique element with a particular

property. In other words, these theorems claim that there is exactly one element with this
property.
To prove a statement of this type we need to show that an element with this
property exists and that no other element has this property. The two parts of a
uniqueness proof are

Existence: We show that an element x with the desired property exists.

Uniqueness: We show that if y ≠ 𝑥, then y does not have the desired property.
Equivalently, we can show that if x and y both have the desired property,
then x = y.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Example: Show that if a and b are real numbers and 𝑎 ≠ 0, then there is a unique real
number r such that 𝑎𝑟 + 𝑏 = 0.

Solution:
Existence : If 𝑎𝑟 + 𝑏 = 0 then 𝑎𝑟 = −𝑏 .We obtain the solution 𝑟 = −𝑏/𝑎 .
Uniqueness : Assume that s is a real number such that
𝑎𝑠 + 𝑏 = 0
Then
𝑎𝑟 + 𝑏 = 𝑎𝑠 + 𝑏
Subtracting b from both sides, we find that
𝑎𝑟 = 𝑎𝑠
Dividing both sides of this last equation by a, which is nonzero, we see that
𝑟=𝑠
Then r is unique.

Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.

 Forward and Backward Reasoning

𝑥+𝑦
Example: Prove that > 𝑥𝑦 .
2
Solution: To prove that we can work backward. We construct a sequence of equivalent
inequalities. The equivalent inequalities are

it follows that the final inequality is true. Once we have carried out this backward reasoning,
we can easily reverse the steps to construct a proof using forward reasoning.We now give
this proof.
Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.
Altınbaş Üniversitesi [email protected] MATH211-Discrete Math.