Discrete Mathematics and Combinatory (Information System and

Science)

By: Masreshaw Temere (PhD)

Department of Mathematics

Sep, 2025

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 1 / 29

Chapter 1
Introductory Logic

Definition
A proposition (or statement) is a declarative sentence which has a truth value (either
True or False but not both).

Example
Identify the following sentences which are statement or not.
(a) 2 is an even number.
(b) A triangle has four sides.
(c) May God bless you!
(d) Give me that book.
(e) What is your name?

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 2 / 29

▶▶▶ Cont’d

Logical Connectives
(1) Conjunction: When two propositions are joined with the connective “and”, the
proposition formed is a logical conjunction.“and” is denoted by “∧”.
So, the logical conjunction of two propositions, p and q, is written: p ∧ q, read as “p
and q,” or “p conjunction q”. p and q are called the components of the conjunction.
Rule: p ∧ q is true if and only if p is true and q is true.

(2) Disjunction: When two propositions are joined with the connective “or”, the
proposition formed is called a logical disjunction. or is denoted by ∨.
So, the logical disjunction of two propositions, p and q, is written: p ∨ q read as “p
or q” or “p disjunction q.”
Rule: p ∨ q is false if and only if both p and q are false.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 3 / 29

▶▶▶ Cont’d
The truth table for conjunction and disjunction is given as follows:
p q p∧q p∨q
T T T T
T F F T
F T F T
F F F F

Example
Write the following propositions with the given statement and find the truth values for the
compound statement.
p: 3 is an odd number. (True) q: 27 is a prime number. (False)
r: Addis Ababa is the capital city of Ethiopia. (True)

(a) p ∨ q : ? and p ∨ q ≡? (b) p ∧ r :? and p ∧ r ≡?

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 4 / 29
▶▶▶ Cont’d

(3) Implication: When two propositions are joined with the connective “implies”, the
proposition formed is called a logical implication. “implies” is denoted by “ =⇒ ”.
So, the logical implication of two propositions, p and q, is written: p =⇒ q read as “p
implies q.” The function of the connective “implies” between two propositions is the
same as the use of “If · · · , then”. Thus, p =⇒ q can be read as if p, then q.
Rule: p =⇒ q is false if and only if p is true and q is false.

(4) Bi-implication: When two propositions are joined with the connective
bi-implication, the proposition formed is called a logical bi-implication or a
logical equivalence. A bi-implication is denoted by “ ⇐⇒ ”. So, the logical
bi-implication of two propositions, p and q, is written: p ⇐⇒ q.
Rule: p ⇐⇒ q is false if and only if p and q have different truth values.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 5 / 29

▶▶▶ Cont’d

The truth table for implication and bi-implication is given by:

p q p =⇒ q p ⇐⇒ q
T T T T
T F F F
F T T F
F F T T

Example
Let p: 2 is greater than 3. (False)
q: 5 is greater than 4. (True)
Then find the truth value and write the statements using the given words for the following
compound proposition.
a) p =⇒ q b) p ⇐⇒ q c) q =⇒ p

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 6 / 29

▶▶▶ Cont’d

(5) Negation: Given any proposition p, we can form the proposition ¬p called the
negation of p.
Rule: The truth value of ¬p is F if p is T and T if p is F.

We can describe the relation between p and ¬p as follows.

p ¬p
T F
F T

Example
Let p: Addis Ababa is the capital city of Ethiopia. (True)
¬p: Addis Ababa is not the capital city of Ethiopia. (False)

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 7 / 29

▶▶▶ Cont’d
Tautology, Contradiction and Logical Equivalence

Definition (Compound/Complex Proposition)

The proposition formed by joining two or more proposition by connective(s) is called a
compound/complex statement.

Definition (Tautology/Contradiction)
A compound proposition is a tautology if it is always true regardless of the truth values of
its component propositions. On the other hand, a compound proposition is always false
regardless of its component propositions, we say that such a proposition is a
contradiction.
Remark
A proposition that is neither a tautology nor a contradiction is called a contingency.
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 8 / 29
▶▶▶ Cont’d

Definition
Two compound propositions P and Q are said to be equivalent if they have the same
truth value for all possible combinations of truth values for the component propositions
occurring in both P and Q. In this case, we write P ≡ Q.

Example
Let P : p =⇒ q
S : ¬p =⇒ ¬q
Q : ¬q =⇒ ¬p, then show that the pairs

(i) P and Q,

(ii) P and S,

(iii) Q and S are logically equivalent or not.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 9 / 29
▶▶▶ Cont’d

Quantified Propositions

Definition (Open Proposition)

An open statement (also called a predicate) is a sentence that contains one or more
variables and whose truth value depends on the values assigned for the variables. We
represent an open statement by a capital letter followed by the variable(s) in parenthesis,
e.g., P(x), Q(x), R(x, y ), · · · etc.

Example
Here are some examples of open propositions:

(a) P(x) : x is the day before Sunday. (c) P(x, y ) : x is greater than y .
(b) Q(y ) : y is a city in Africa. (d) P(x) : x + 4 = −9.
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 10 / 29
▶▶▶ Cont’d
Remark
The collection of all allowable values for the variable in an open sentence is called the
universal set (the universe of discourse) and denoted by U.

Quantifiers
(a) The phrase “for every x” is called universal quantifier. We regard “for every x”,
“for all x” and “for each x ” as having the same meaning and symbolize each by ∀x.
If P(x) is an open proposition with universe U, then (∀x)P(x) is a quantified
proposition and is read as every x ∈ U has the property P.

(b) The phrase “there exists an x” is called an existential quantifier. We regard “there
exists an x”, “for some x” and “for at least one x” as having the same meaning, and
symbolize each by (∃x). If P(x) is an open proposition with universe U, then (∃x)P(x)
is a quantified proposition and is read as there exists x ∈ U with the property P.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 11 / 29

▶▶▶ Cont’d

Remark
(1) To show that (∀x)P(x) is F, it is sufficient to find at least one a ∈ U such that P(a) is
F.

(2) (∃x)P(x) is F if we cannot find any a ∈ U having the property P.

Example
Write the following statements using quantifiers and find their truth values.
(a) For each real number x > 0, x 2 + x − 6 = 0.
(b) There is a real number x > 0 such that x 2 + x − 6 = 0.
(c) The square of any real number is nonnegative.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 12 / 29

▶▶▶ Cont’d
If P(x) is a formula in x, We might translate these into words as follows.
(∀x)P(x), everything has property P.
(∃x)P(x), something has property P.
(∀x)¬P(x), nothing has property P.
(∃x)¬P(x), something does not have property P.
Relationship between the existential and universal quantifiers:
¬(∀x)P(x) ≡ (∃x)¬P(x).

Exercise
Let U = the set of integers. Let P(x) : x is a prime number; Q(x) : x is an even number;
R(x) : x an odd number. Then find the truth value of the following.

(a) (∃x) [P(x) =⇒ Q(x)] (c) (∀x) [R(x) ∧ P(x) =⇒ Q(x)]

(b) (∀x) [P(x) =⇒ Q(x)] (d) (∀x) [R(x) ∧ P(x)]
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 13 / 29
▶▶▶ Cont’d

Quantifiers Occurring in Combinations

Let P(x, y ) be an open proposition. The following are the simplest forms of
combinations of the two quantifiers:

1 (∀x)(∀y )P(x, y ), for all x and for all y the relation P(x, y ) holds.

2 (∃x)(∃y )P(x, y ), there is an x and there is a y for which P(x, y ) holds.

3 (∀x)(∃y )P(x, y ), for every x and there exists a y for which P(x, y ) holds. Here, the
choice of y is allowed to depend on x.

4 (∃y )(∀x)P(x, y ), there is an x which stands to every y in the relation P(x, y ) holds. The
y must work for all x, that is, y is independent of x.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 14 / 29

▶▶▶ Cont’d

Argument and Validity

Definition
An argument (logical deduction) is an assertion that a given set of statements
p1 , p2 , p3 , · · · , pn , called hypotheses or premises, yield another statement Q, called the
conclusion. Such a logical deduction is denoted by:

p1 , p2 , p3 , · · · , pn ⊢ Q

Example
Consider the following argument:
If you study hard, then you will pass the exam; You did not pass the exam; Therefore, you
did not study hard.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 15 / 29

▶▶▶ Cont’d

Let p: you study hard.

q: you will pass the exam.

The argument form can be written as:

p =⇒ q, ¬q ⊢ ¬p
or

p =⇒ q
¬q
¬p

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 16 / 29

▶▶▶ Cont’d
Definition
An argument form p1 , p2 , p3 , · · · , pn ⊢ Q is said to be valid if Q is true whenever all the
premises p1 , p2 , p3 , · · · , pn are true; otherwise it is invalid.

Example
Investigate the validity of the following argument:
(a) p ⇒ q, ¬q ⊢ ¬p.
(b) p ⇒ q, ¬q ⇒ r ⊢ p.
(c) If it rains, crops will be good. It did not rain. Therefore, crops were not good.

Remark
The argument form p1 , p2 , p3 , · · · , pn ⊢ Q is valid iff (p1 ∧ p2 ∧ p3 ∧ · · · ∧ pn ) =⇒ Q is a
tautology.
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 17 / 29
▶▶▶ Cont’d

Rules of Inference

Below we list certain valid deductions called rules of inferences.

(1) Modes Ponens

p
p⇒q
q

(2) Modes Tollens

¬q
p⇒q
¬p

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 18 / 29

▶▶▶ Cont’d
(3) Principle of Syllogism
p⇒q
q⇒r
p⇒r
(4) Principle of Adjunction
i. p
q q
ii.
p∧q p∨q
(5) Principle of Detachment
p∧q
p, q
(6) Modes Tollendo Ponens ¬p
p∨q
q
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 19 / 29
▶▶▶ Cont’d
(7) Modes Ponendo Tollens
¬(p ∧ q)
p
¬q
(8) Constructive Dilemma
(p ⇒ q) ∧ (r ⇒ s)
p∨r
q∨s
(9) Principle of Equivalence
p⇔q
p
q
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 20 / 29
▶▶▶ Cont’d
(10) Principle of Conditionalization
p
q⇒p

Example
Show that p ⇒ ¬q, q ⊢ ¬p is valid.
Solution:

1. q is true premise
2. p ⇒ ¬q is true premise
3. q ⇒ ¬p is true contrapositive of (2)
4. ¬p is true Modes Ponens using (1) and (3)

Therefore, the argument p ⇒ ¬q, q ⊢ ¬p is valid.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 21 / 29
▶▶▶ Cont’d

Methods of proof

Definition
A proof is a sequence of logical statements, one implying another, which gives an
explanation of why a given statement is true.

Direct Proofs
Direct proof assumes a given hypothesis, or any other known statement, and then logically
deduces a conclusion.

Example (Give a direct proof of the following statements)

(1) If n is an odd integer, then n2 is odd.
(2) If m and n are both perfect squares, then nm is also a perfect square.
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 22 / 29
▶▶▶ Cont’d
Indirect Proofs (Proof by Contraposition)

Proofs 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.
Example
Prove that if n is an integer and 3n + 2 is odd, then n is odd.

Proof.
Contrapositive: If n is even, then 3n + 2 is even.
Assume n is even: By definition, if n is even, we can express n = 2k for some k ∈ Z.
Claim: we want to show that 3n + 2 is even.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 23 / 29

▶▶▶ Cont’d
Now,
3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).
This shows that 6k + 2 = 2(3k + 1) is even because it is expressed as 2× (an integer).
Since, we have shown that if n is even, then 3n + 2 is also even, we have proven the
contrapositive statement.
Thus, by proving the contrapositive, we conclude that if 3n + 2 is odd, then n must
be odd.
Exercise
Let n and m be integers. Then prove that
(a) if n and m are both even, then n + m is even.
(b) if n and m are both odd, then n + m is even.
(c) if one of n or m is even and the other is odd, then n + m is odd.
(d) if n2 is odd, then n is odd.
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 24 / 29
▶▶▶ Cont’d

Proofs by Contradiction

Proof by Contradiction is a logical method of proving a statement by assuming

the negation of what you want to prove and showing that this assumption leads to a
contradiction.

Example
Give a proof by contradiction that “If 3n + 2 is odd, then n is odd.”

Proof.
To use proof by contradiction, we assume the negation of what we want to prove.
Thus, we assume: 3n + 2 is odd (this is our hypothesis) and n is even.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 25 / 29

▶▶▶ Cont’d

Since n is even, we can write:

n = 2k, for some k ∈ Z.
Now,
3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).
This shows that 6k + 2 = 2(3k + 1) is even since it is a multiple of 2.

We have derived that 3n + 2 = 6k + 2 is even. However, our initial assumption states

that 3n + 2 is odd. This creates a contradiction because an integer cannot be both
odd and even at the same time.
Since our assumption that n is even leads to a contradiction, we conclude that our
assumption must be false. Therefore, if 3n + 2 is odd, it must be the case that n is
odd.
Thus, we have proven that “If 3n + 2 is odd, then n is odd.”

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 26 / 29

▶▶▶ Cont’d

Mathematical Induction

▶ One of the most powerful techniques in proving theorems or solving problems that
involves integers is the principle of mathematical induction.

Theorem (First Principle of Mathematical Induction)

If P(n) is an open statement on the set of positive integers such that

(a) p(1) is true.

(b) p(k) ⇒ p(k + 1). Then p(n) is true for every natural number n.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 27 / 29

▶▶▶ Cont’d

Example
Using mathematical induction to show that

n(2n + 1)(n + 1)
12 + 22 + 32 + · · · + n2 = , n ∈ N.
6
n(2n + 1)(n + 1)
Solution: p(n) : 12 + 22 + 32 + · · · + n2 =
6
1(2 + 1)(1 + 1)
(i) p(1) : 12 = = 1 ⇒ p(1) is true.
6
k(2k + 1)(k + 1)
(ii) Assume n = k ∈ N is true, that is, 12 + 22 + 32 + · · · + k 2 = .
6
We want to show that it is also true for n = k + 1, that is,
k(2k + 1)(k + 1)
12 + 22 + 32 + · · · + k 2 + (k + 1)2 = + (k + 1)2
6

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 28 / 29

▶▶▶ Cont’d

k(2k + 1)(k + 1) + 6(k + 1)2

=
6
(k + 1)[k(2k + 1) + 6(k + 1)]
=
6
(k + 1)(2k 2 + 7k + 6)
=
6
(k + 1)(2k 2 + 4k + 3k + 6)
=
6
(k + 1)(2k(k + 2) + 3(k + 2))
=
6
(k + 1)(2k + 3)(k + 2)
=
6
(k + 1)(2(k + 1) + 1)((k + 1) + 1)
=
6
which is also true for n = k + 1. Hence, it is true ∀n ∈ N.
By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 29 / 29
Exercise
Use mathematical induction to show that
n(n + 1)
1 + 2 + 3 + ... + n = ,
2
for all integers n ≥ 1.

By: Masreshaw Temere (PhD) Discrete Mathematics & Combinatory 29 / 29