DISCRETE MATHEMATICS:

MATHEMATICAL LOGIC
AND ITS APPLICATIONS

MATHEMATICAL LOGIC AND ITS APPLICATIONS 1

 INTRODUCTION TO DISCRETE MATHEMATICS

Discrete mathematics deals with discrete objects (set with is

bijective to the set of natural numbers.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 2

 INTRODUCTION TO DISCRETE MATHEMATICS

Knowledge of discrete mathematics is required in many of the

sub disciplines of computer science, such as data structures,
algorithms, networking, database management, etc.

The main goals of this subject are to develop ability in the

following:

 Designing Mathematical arguments and Algorithms.

 Writing mathematics proofs of various statements.
 Solving various counting problems using combinatorial
analysis.
 Solving various problems using discrete structures.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 3

 INTRODUCTION TO LOGIC

John has 5 pencils and David has 3 pencils. John may have
given 2 pencils to David then how many pencils john has?

By SVD is it easy to eliminate data that is not important in a

matrix for the production of low-dimensional
approximation?

If 𝑓: ℝ → ℝ is differentiable at 𝑥 = 0 then 𝑓 is continuous at

𝑥 = 0.

If 𝑓: ℝ → ℝ is not continuous at 𝑥 = 0 then 𝑓 is not

differentiable at 𝑥 = 0.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 4
 INTRODUCTION TO LOGIC

In grammar we classify sentences into four categories:

 Declarative
 Imperative (Direct command)
 Interrogative (Question)
 Exclamatory.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 5

 INTRODUCTION TO LOGIC

Consider the following:

1. Ten is less than seven.
2. Delhi is the capital of India.
3. She is very talented.
4. There are life forms on other planets in the universe.

There are declarative sentences whose truth value cannot

be determine
Example 1: “An American says that all Americans are liars”.
Example 2: “This sentence is false”.
Such sentences are called paradox.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 6

 INTRODUCTION TO LOGIC

We consider declarative sentences which can be called

either true or false. Mathematical logic is the study of formal
logic within mathematics.

A declarative sentence which can be classified as either true

or false is called a statement.

Mathematical logic provides the foundation for the

organized, careful method of thinking that characterizes any
reasoned activity.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 7

A statement is a sentence that is either true or false.

Statements

Simple Compound

Simple: A statement which does not contain any other

statement as its component is called a simple statement.

Examples: It was raining on the last Sunday.

Data science course is in demand.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 8
Compound: A statement which contains another statement
or statements as its components is called a compound
statement.

Example 1: I took a course on data science and my friend

took a course on Artificial Intelligence.

Example 2: If you will commit a mistake, then you will pay

for it.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 9

 PROPOSITIONAL LOGIC

Propositions are mathematical statements such that their

truth or falsity can be told without ambiguity. A proposition
is also called a primitive statement.

We use letters 𝑝, 𝑞, 𝑟, … to denote propositions. Thus, the

values of 𝑝, 𝑞, 𝑟, … are either True or False.

Examples of propositions
𝑝: 2+2=5
𝑞: 𝑥 2 − 2𝑥 + 1 has two identical roots.
𝑟: There exists a prime number with 2 digits.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 10

Compound statements are formed from simple statements
in 5 ways:

Negation (∼)

Conjunction (∧)

Disjunction (∨)

Implication (⇒)

Double implication(⇔)
which are called as logical connectives.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 11
Suppose 𝑝, 𝑞, 𝑟, … are variables with values either T or F. We
call such variables as propositional variables.

Let 𝑝, 𝑞 be ay two propositions. We use symbols

∼, ∧, ∨, ⇒, ⇔
to construct new propositions such as
∼ 𝑝, 𝑝 ∧ 𝑞, 𝑝 ∨ 𝑞, 𝑝 ⇒ 𝑞, 𝑝 ⇔ 𝑞

MATHEMATICAL LOGIC AND ITS APPLICATIONS 12

Truth value of a compound statement depends upon the
truth value of its component.

Truth table: A table in which the truth values of a compound

statement are given for various possible truth values of its
components is called a truth table.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 13

 NEGATION

Negation (∼): A negation is a compound statement

obtained by negating a simple statement.
𝒑 ∼𝒑
T F
F T

Find the negation of the following statement:

Peter is tall and thin

Peter is short and fat.

Peter is not tall or he is not thin.
Peter is short or fat.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 14
 CONJUNCTION

Conjunction (∧): A conjunction is a compound statement

obtained by combining two statements by and.
𝒑 𝒒 𝒑∧𝒒
T T T
T F F
F T F
F F F

MATHEMATICAL LOGIC AND ITS APPLICATIONS 15

 DISJUNCTION

Disjunction (∨): A disjunction is a compound statement

obtained by combining two statements by or.
𝒑 𝒒 𝒑∨𝒒
T T T
T F T
F T T
F F F

Inclusive (weak) and Exclusive (strong) sense of “or”

Example (Inclusive): Knowledge of mathematics or physics is
essential for the post.
Example (Exclusive): Answer the question or leave the class.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 16

 IMPLICATION

Implication (⇒): An implication is a compound statement

obtained by combining two simple statements by if…then…
𝒑 𝒒 𝒑⇒𝒒
T T T
T F F
F T T
F F T

In the implication 𝑝 ⇒ 𝑞, 𝑝 stands for the antecedent

statement and 𝑞 stands for consequent.
Example: If I pass my mathematics test, then I will go for a
movie.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 17
 DOUBLE IMPLICATION

Double implication (⇔): An double implication is a

compound statement obtained by combining two simple
statements by …if and only if…

𝒑 𝒒 𝒑⇔𝒒
T T T
T F F
F T F
F F T

MATHEMATICAL LOGIC AND ITS APPLICATIONS 18

Propositional formulas are recursively define as follows:
1. T and F are propositional formulas.
2. All variables are propositional formulas.
3. If 𝑓1 and 𝑓2 are propositional formulas, so are
∼ 𝑓1 , 𝑓1 ∧ 𝑓2 , 𝑓1 ∨ 𝑓2 , 𝑓1 ⇒ 𝑓2 , 𝑓1 ⇔ 𝑓2

 Only the formulas generated by the rules above are

called as propositional formulas.

 Propositional formulas are also known as well-formed-

formulas, or 𝑤𝑓𝑓 in short.

 𝑝𝑞 ∼, 𝑝 ∧ 𝑞 ⇒ are not 𝑤𝑓𝑓.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 19

Punctuation and Brackets: To remove ambiguity
3+5×4
(3 + 5) × 4
Similarly,
𝑝∧𝑞∨𝑟
𝑝 ∧ (𝑞 ∨ 𝑟)

To reduce the number of parentheses, we stipulate an

order in which connectives are applied.
This order of precedence is
 Connectives within parentheses, innermost parentheses
first.
 ∼
 ∨,∧
⇒
⇔
MATHEMATICAL LOGIC AND ITS APPLICATIONS 20
 The logical connectives AND, OR, and NOT are also
available in many programming languages, as well as on
programmable graphing calculators.

 These connectives, in accordance with the truth tables we

have defined, act on combinations of true or false
expressions to produce an overall truth value. Such truth
values provide the decision-making capabilities
fundamental to the flow of control in computer programs.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 21

From a given implication we can obtain three more
implications.

Converse

Inverse

Contrapositive

MATHEMATICAL LOGIC AND ITS APPLICATIONS 22

Converse: If the positions of the premise and the
conclusion of an implication are interchanged we get the
converse of that implication i.e. the converse of 𝑝 ⇒ 𝑞 is
𝑞 ⇒ 𝑝.

Inverse: If both the premise and the conclusion are

negated, we get the inverse of that implication i.e. the
inverse of 𝑝 ⇒ 𝑞 is ∼ 𝑝 ⇒∼ 𝑞.

Contrapositive: If both the premise and the conclusion of

an implication are first negated and then interchanged, we
get the contrapositive statement of that implication i.e. the
contrapositive of 𝑝 ⇒ 𝑞 is ∼ 𝑞 ⇒∼ 𝑝.

Draw the truth table for all the three implications above.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 23
Logical Equivalence (≡)
Two statements 𝑓1 and 𝑓2 are said to be logically equivalent
(that is 𝑓1 ≡ 𝑓2 ) if 𝑓1 ⇔ 𝑓2 is always true (Tautology).
or
Two compound statements 𝑓1 and 𝑓2 are said to be logically
equivalent if they have identical truth values for all truth
values of the component statements in the truth table.

Problems
1. Show that 𝑝 ⇒ 𝑞 and ∼ 𝑝 ∨ 𝑞 are logically equivalent.
2. Prove that
𝑝 ⇔ 𝑞 ≡ 𝑝 ⇒ 𝑞 ∧ (𝑞 ⇒ 𝑝).
𝑝 ∨ 𝑞 ⇒ 𝑟 ≡ [ 𝑝 ⇒ 𝑟 ∧ (𝑞 ⇒ 𝑟)]
MATHEMATICAL LOGIC AND ITS APPLICATIONS 24
 NEGATION OF COMPOUND STATEMENTS

NAND (↑): Negation of conjunction ∼ 𝑝 ∧ 𝑞 ≡∼ 𝑝 ∨∼ 𝑞

which is denoted by 𝑝 ↑ 𝑞 .

NOR (↓): Negation of disjunction ∼ 𝑝 ∨ 𝑞 ≡∼ 𝑝 ∧∼ 𝑞

which is denoted by 𝑝 ↓ 𝑞.

Negation of a negation ∼ ∼ 𝑝 ≡ 𝑝

Negation of an implication ∼ 𝑝 ⇒ 𝑞 ≡ 𝑝 ∧∼ 𝑞

Negation of a biconditional
∼ 𝑝 ⇔ 𝑞 ≡ 𝑝 ∧∼ 𝑞 ∨ (𝑞 ∧∼ 𝑝)
MATHEMATICAL LOGIC AND ITS APPLICATIONS 25
Implication as disjunction
𝑝 ⇒ 𝑞 ≡∼ 𝑝 ∨ 𝑞

Biconditional in terms of conjunction, disjunction and

negation
𝑝 ⇔ 𝑞 ≡ ∼ 𝑝 ∨ 𝑞 ∧ (∼ 𝑞 ∨ 𝑝)

MATHEMATICAL LOGIC AND ITS APPLICATIONS 26

 LAWS OF LOGIC

Idempotent laws
𝑝∨𝑝 ≡𝑝
𝑝∧𝑝 ≡𝑝

Commutative laws
𝑝∧𝑞 ≡𝑞∧𝑝
𝑝∨𝑞 ≡𝑞∨𝑝

Associative laws
𝑝 ∨ 𝑞 ∨ 𝑟 ≡ 𝑝 ∨ (𝑞 ∨ 𝑟)
𝑝 ∧ 𝑞 ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟)

Identities laws
𝑝∨𝐹 ≡𝑝
𝑝 ∧ 𝑇 ≡M A T𝑝H E M A T I C A L L O G I C A N D I T S A P P L I C A T I O N S 27
Distributive laws
𝑝∨ 𝑞∧𝑟 ≡ 𝑝∨𝑞 ∧ 𝑝∨𝑟
𝑝 ∧ 𝑞 ∨ 𝑟 ≡ 𝑝 ∧ 𝑞 ∨ (𝑝 ∧ 𝑟)

Complements laws (Inverse laws)

𝑝 ∨∼ 𝑝 ≡ 𝑇
𝑝 ∧∼ 𝑝 ≡ 𝐹

De Morgan’s laws
∼ 𝑝 ∧ 𝑞 ≡∼ 𝑝 ∨∼ 𝑞
∼ 𝑝 ∨ 𝑞 ≡ ∼ 𝑝 ∧∼ 𝑞

Absorption laws
𝑝∨ 𝑝∧𝑞 ≡𝑝
𝑝∧ 𝑝∨𝑞 ≡𝑝
MATHEMATICAL LOGIC AND ITS APPLICATIONS 28
Domination law:
𝑝∧𝐹 ≡𝐹
𝑝∨𝑇 ≡𝑇

Some other logical equivalence formulae involving

conditional and biconditional are as follows:

𝑝 ⇒ 𝑞 ≡∼ 𝑝 ∨ 𝑞
𝑝 ⇒ 𝑞 ≡∼ 𝑞 ⇒∼ 𝑝
𝑝 ⇒ 𝑞 ∧ 𝑝 ⇒ 𝑟 ≡ 𝑝 ⇒ (𝑞 ∧ 𝑟)
𝑝⇒𝑟 ∧ 𝑞 ⇒𝑟 ≡ 𝑝∨𝑞 ⇒𝑟
𝑝 ⇒ 𝑞 ∨ 𝑝 ⇒ 𝑟 ≡ 𝑝 ⇒ (𝑞 ∨ 𝑟)
𝑝⇒𝑟 ∨ 𝑞 ⇒𝑟 ≡ 𝑝∧𝑞 ⇒𝑟
𝑝 ⇔ 𝑞 ≡ 𝑝 ⇒ 𝑞 ∧ (𝑞 ⇒ 𝑝)
𝑝 ⇔ 𝑞 ≡ 𝑝 ∧ 𝑞 ∨ (∼ 𝑝 ∧∼ 𝑞)
MATHEMATICAL LOGIC AND ITS APPLICATIONS 29
Problems:
1. Without constructing the truth table, show that
𝑝 ⇒ 𝑞 ⇒ 𝑟 ≡ 𝑝 ∧ 𝑞 ⇒ 𝑟.

2. Prove that ∼ 𝑝 ∧ 𝑞 ∧ (𝑝 ∨∼ 𝑞) is equivalent to ∼ 𝑞.

3. Prove that 𝑝 → 𝑞 ∧ ∼ 𝑟 →∼ 𝑞 → 𝑝 → 𝑟 ≡ 𝑇.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 30

Statement forms are classified into three categories:

Tautology

Contradiction

Contingency

MATHEMATICAL LOGIC AND ITS APPLICATIONS 31

Tautology: A statement form which is always true for all
substitution instances is called a tautology.

Contradiction: A statement form which is always false for all

substitution instances is called a contradiction.

Contingency: A statement form which is neither a tautology

nor a contradiction is called a contingent.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 32

Problems:
1. Without constructing the truth table, show that
∼ 𝒑 ∧ 𝒑 ∨ 𝒒 ⇒ 𝒒 is a tautology.

2. Prove that ∼ 𝒑 ∨ 𝒒 ⇒ [∼ 𝒑 ∧∼ 𝒒] is a tautology.

3. Determine whether the statement

𝒑 ∨ 𝒒 ∧ ∼ 𝒑 ∨ 𝒓 ⇒ (𝒒 ∨ 𝒓) is a tautology.

4. Construct truth table to determine whether the given

statement is a tautology, contradiction or neither.
𝒑 ∨ 𝒒 ∧∼ 𝒑 → 𝒒
∼ (𝒑 ⇔ 𝒒) ⇔ (𝒑 ⇔∼ 𝒒)

MATHEMATICAL LOGIC AND ITS APPLICATIONS 33

 QUANTIFIERS AND PREDICATES

“For every 𝑥 ∈ ℝ, 𝑥 2 ≥ 0”
This proposition contains two new features, a quantifier and
a predicate.

Quantifiers are phrases such as “for every” or “for each”

or “for some” that tell in some sense how many objects
have a certain property.

The phrase "𝑥 ≥ 0" describes a property of the variable 𝑥,

that square of 𝑥 is non-negative. A property is also called a
Predicate.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 34

Quantifiers: Quantifiers give us the information regarding
how many possess the given property.

Two types of quantifiers

Universal quantifiers Existential quantifiers

(for all, for each, for (some, there exists a, for
every) ∀ atleast one) ∃
MATHEMATICAL LOGIC AND ITS APPLICATIONS 35
 While talking about a set we need a reference set which we
call universal set U.

 In the same way while talking about some, all, none, etc.
we need a reference set which we call Universe of
Discourse.

 If we are talking about some students, the universe of

discourse is the set of all students. When we are talking
about some mangoes the universe of discourse is the set of
all mangoes.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 36

 We shall denote a member of the set i.e. of the universe of
discourse by 𝑥.

 The property possessed by 𝑥 is denoted by 𝑃(𝑥) and 𝑃(𝑥)

is called predicate.

 For example, 𝑃 𝑥 : 𝑥 is an engineer. It is clear that 𝑃(𝑥) is

not a proposition but it is just an expression. As such 𝑃 𝑥
is not true of false. It becomes a proposition when 𝑥 is a
assigned a value.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 37

Problems:
1. Symbolise “All giraffes are tall.”

2. Symbolise “ Some real numbers are integers.”

3. Symbolise “Some tigers are white.”

4. If the universe of discourse is the set {0, ±1, ±2},

determine the truth value of each of the following
propositions.
a. (∀𝑥)(𝑥 2 = 1)
b. (∃𝑥)(𝑥 3 + 3𝑥 2 = 𝑥 + 3)
c. (∀𝑥)(𝑥 5 + 4𝑥 = 5𝑥 3 )

MATHEMATICAL LOGIC AND ITS APPLICATIONS 38

 NEGATION OF QUANTIFIERS

Statement Negation
All true ∀𝑥 𝑃(𝑥) ∃𝑥 ∼ 𝑃 𝑥 [atleast one false]
All false ∀𝑥 ∼ 𝑃(𝑥) ∃𝑥 𝑃 𝑥 [atleast one true]
∃𝑥 [𝑃(𝑥)] ∀𝑥 [∼ 𝑃(𝑥)]
∃𝑥 [∼ 𝑃(𝑥)] ∀𝑥 𝑃(𝑥)

Problem: Negate the following statements

1. For all positive integers 𝑥, we have 𝑥 + 3 > 10.
2. There is a person whose weight is 100 kg.
3. For all real numbers 𝑥 if 𝑥 > 2 then 𝑥 2 > 4.
4. There is a real number 𝑥 such that if 𝑥 3 +𝑥 2 = 3, then 𝑥 > 2
and 𝑥 < 5.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 39

 NESTED QUANTIFIERS

Nested quantifiers are quantifiers that occur within the scope

of other quantifiers.

Problem : Express the statement "For every positive real

number 𝑥, there exists a positive real number 𝑦 such that
𝑦 < 𝑥 using nested quantifiers.

Problem : Determine the truth value of the statement

∀𝑥 ∈ ℝ[∃ 𝑦 ∈ ℝ 𝑃 𝑥, 𝑦 ] if the domain consists of natural
numbers, and 𝑃(𝑥, 𝑦) is the predicate defined as follows:
𝑃 𝑥, 𝑦 : 𝑥 2 + 𝑦 2 = 1

MATHEMATICAL LOGIC AND ITS APPLICATIONS 40

 NESTED QUANTIFIERS

Problem: What is the truth value of each of the following

statements where the domain consists of the integers?

MATHEMATICAL LOGIC AND ITS APPLICATIONS 41

 NORMAL FORM

If there are large number of component statements, truth table

method is not an convenient method of deciding whether the
compound statement is a tautology, contradiction or neither.

The DNF and CNF provide a convenient apparatus in

applications of Artificial Intelligence, Logical Programming,
and many other areas of research.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 42

Elementary sum: A sum of the variables and their negations
is called an elementary sum.
Examples: 𝑝, ∼ 𝑝, 𝑝 ∨∼ 𝑞, 𝑝 ∨ 𝑞 ∨ 𝑟, etc.

We know that 𝑝 ∨∼ 𝑝 is a tautology.

Elementary product: A product of the variables and their

negations in a formula is called an elementary product.
Example: 𝑝, ∼ 𝑝, ∼ 𝑝 ∧ 𝑞, 𝑝 ∧ 𝑞, 𝑝 ∧ 𝑞 ∧∼ 𝑟, etc.

We know that 𝑝 ∧∼ 𝑝 is a contradiction.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 43

Disjunctive Normal Form (DNF)
A formula that is equivalent to a given formula and consists of
a sum of the elementary products is called as Disjunctive
Normal Form of the given formula.

Example: 𝑝 ∧ 𝑞 ∨ (𝑝 ∧ 𝑟)
𝑝 ∨ (∼ 𝑝 ∧ 𝑞)
𝑝 ∧∼ 𝑝 ∨ (𝑝 ∧ 𝑞)
𝑝∨𝑞

Note: If any elementary product in DNF is a tautology then

the statement is a tautology.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 44

Problems:
1. Obtain a DNF of 𝑝 ∧ 𝑞 ∨ (∼ (𝑝 ⇒ 𝑞 )).
2. Obtain a DNF of ∼ 𝑝 ∧ 𝑞 ∧ (𝑝 ⇒ 𝑞).

Steps for constructing disjunctive normal form

1. Draw truth table for the given proposition.
2. Find the rows for which proposition is true.
3. In the row mentioned above if the value of the variable if
T then consider the variable as it is and if the value of the
variable if F then consider the negation of that variable.
4. Take the conjunction of the variables in each row
considered in 3. above.
5. Take the disjunction of all the expressions constructed for
each row in the last step.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 45
Conjunctive Normal Form (CNF)
A formula that is equivalent to a given formula and consists of
a products of the elementary sum is called as Conjunctive
Normal form of the given formula.

Example: 𝑝 ∨ 𝑞 ∧ 𝑝 ∨ 𝑟 , 𝑝 ∨ 𝑞, 𝑝 ∧ ∼ 𝑝 ∨ 𝑞 , 𝑝 ∨∼ 𝑝 ∧
(𝑝 ∨ 𝑞)

Note: If any elementary sum in CNF is a contradiction then

the statement is a contradiction.
Problems:
1. Obtain the CNF of ∼ 𝑝 → 𝑟 ∧ (𝑝 ↔ 𝑞)
2. Obtain the CNF of ∼ (𝑝 ∨ 𝑞) ↔ (𝑝 ∧ 𝑞)
3. Obtain the CNF of 𝑝 → 𝑞 ∧ 𝑟 ∧ (∼ 𝑝 → (∼ 𝑞 ∧∼ 𝑟))
MATHEMATICAL LOGIC AND ITS APPLICATIONS 46
 PRINCIPAL DISJUNCTIVE NORMAL FORM (PDNF)

Let 𝑝 and 𝑞 be the two statements. The statements

𝑝 ∧ 𝑞, 𝑝 ∧∼ 𝑞, ∼ 𝑝 ∧ 𝑞, ∼ 𝑝 ∧∼ 𝑞 are called as minterms for
the two variables 𝑝 and 𝑞. Excluding the form where a
variable and its negation appears.

For 𝑛 statements there are 2𝑛 minterms.

If a formula consists of disjunctions of minterms alone is

known as its Principal Disjunctive Normal Form (PDNF).

Problem: Find PDNF of 𝑝 ∨ (𝑝 ∧ 𝑞). Solve by with and without

truth table.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 47
 PRINCIPAL CONJUNCTIVE NORMAL FORM (PCNF)

Let 𝑝 and 𝑞 be the two statements. The statements

𝑝 ∨ 𝑞, 𝑝 ∨∼ 𝑞, ∼ 𝑝 ∨ 𝑞, ∼ 𝑝 ∨∼ 𝑞 are called as maxterms for
the two variables 𝑝 and 𝑞. Excluding the form where a
variable and its negation appears.

For 𝑛 statements there are 2𝑛 maxterms.

If a formula consists of Conjunction of maxterms alone is

known as its Principal Conjunctive Normal Form (PCNF).

Problem: Find PCNF of 𝑝 ∧ (𝑝 ∨ 𝑞). Solve by with and without

truth table.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 48

 VALIDITY OF AN ARGUMENT (LOGICAL PROOF OR STATEMENT)

An argument is a sequence of statements such that all the

statements except the final statement are called Premises (or
assumption or hypothesis) and the final statement is called
Conclusion.

Therefore ∴ is generally placed before the conclusion.

Argument form
𝑃1
𝑃2
⋮
𝑃𝑛
∴𝑄
MATHEMATICAL LOGIC AND ITS APPLICATIONS 49
Argument is said to be valid if the conclusion is true
whenever all the premises are true, and the argument which
is not true is called a fallacy or invalid argument.

That is the above argument form is called valid, provided

𝑷𝟏 ∧ 𝑷𝟐 ∧ ⋯ ∧ 𝑷𝒏 ⇒ 𝑸
is a tautology.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 50

 METHOD TO TEST THE VALIDITY OF AN ARGUMENT:

1. Identify the premises and conclusion of an argument.

2. Construct truth table for all premises and conclusion.
3. Find the rows (Critical rows) in which all the premises are
true.
4. In each critical row determine whether the conclusion of
the argument form is also true.
5. If in each critical row the conclusion is also true then
argument form is valid.
6. If there is atleast one row in which conclusion is false then
argument form is fallacy or invalid.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 51

Problems:
Check whether the following arguments are valid
1. 𝑝
𝑝⇒𝑞
∴𝑞

2.
𝑝⇒𝑞
𝑞⇒𝑟
∴𝑝⇒𝑟
3.
𝑝⇒𝑞
𝑞
∴𝑝

MATHEMATICAL LOGIC AND ITS APPLICATIONS 52

4.
𝑝⇒𝑞
∼𝑝
∴∼𝑞
5.
𝑝∨𝑞
∼𝑝
∴𝑞

MATHEMATICAL LOGIC AND ITS APPLICATIONS 53

Problems: Check the validity of all the arguments below.
1. If the taxes are lowered, then income rises.
Income rises.
∴ Taxes are lowered.

2. If I study then I will not fail in mathematics.

If I do not play basketball then I will study
But I failed in mathematics.
∴ I must have played basketball.

3. If you invest in the stock market then you will get rich.
If you get rich then you will be happy.
∴ If you invest in the stock market then you will be happy.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 54

4. If Delhi is a big city, then Delhi has tall buildings.
Delhi has tall buildings.
∴ Delhi is a big city.

5. If David has completed MBA, then he assured a good job.

If David is assured a good job then he is happy.
Davis is not happy.
∴ David has not completed MBA.

Solve question 5 above by inference rules.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 55

 RULES OF INFERENCES

From Can derive Name / Abbreviation for Rule

𝑝, 𝑝 ⇒ 𝑞 ∴𝑞 Modus Ponens (mp)
𝑝 ⇒ 𝑞, ∼ 𝑞 ∴∼ 𝑝 Modus tollens (mt)
𝑝, 𝑞 ∴𝑝∧𝑞 Conjunction (con)
𝑝 ∨ 𝑞, ∼ 𝑞 ∴𝑝 Rule of Disjunctive Syllogism:
∼𝑝⇒𝐹 𝑝 Rule of Contradiction:
𝑝∧𝑞 ∴ 𝑝, 𝑞 Simplification (sim)
𝑝 ∴𝑝∨𝑞 Addition (add)
𝑝 ⇒ 𝑞, 𝑞 ⇒ 𝑟 ∴𝑝⇒𝑟 Hypothetical syllogism
𝑝 ∨ 𝑞, ∼ 𝑝 ∨ 𝑟 ∴𝑞∨𝑟 Resolution

MATHEMATICAL LOGIC AND ITS APPLICATIONS 56

Problems: Show that the statements are valid by using rules
of inferences.
1. 𝑝 ⇒ 𝑞 ∧ 𝑟 ∨∼ 𝑞 ∧ 𝑝 ⇒ 𝑟
2. 𝑝 ∧ ∼ 𝑞 ⇒∼ 𝑝 ⇒ 𝑞

MATHEMATICAL LOGIC AND ITS APPLICATIONS 57

 INFERENCES RULES FOR PREDICATE CALCULUS

From Can derive Name of the rule

∀𝑥 𝑃(𝑥) 𝑃(𝑡), where 𝑡 is a Universal Specification
variable or a constant (us)
symbol
∃𝑥 𝑃(𝑥) 𝑃(𝑎) where 𝑎 is a Existential Specification
constant symbol not (es)
previously used in proof
sequence
𝑃(𝑥) ∀𝑥 𝑃(𝑥) Universal Generalization
(ug)
𝑃(𝑥) or 𝑃(𝑎) ∃𝑥 𝑃(𝑥) Existential Generalization
where 𝑎 is a (eg)
constant symbol

MATHEMATICAL LOGIC AND ITS APPLICATIONS 58

Check the following statement is valid.
All integers are rational numbers. 2 is an integer. Therefore, 2
is a rational number.

𝐼(𝑥): 𝑥 is an integer.
𝑅 𝑥 : 𝑥 is a rational number.
𝑎 is a constant symbol (that is 2)

The argument is ∀𝑥 𝐼 𝑥 ⇒ 𝑅 𝑥 ∧𝐼 𝑎 ⇒𝑅 𝑎

∀𝑥 𝐼 𝑥 ⇒ 𝑅 𝑥
𝐼 𝑎
𝐼 𝑎 ⇒ 𝑅(𝑎)
𝑅(𝑎)
MATHEMATICAL LOGIC AND ITS APPLICATIONS 59
 PRINCIPLE OF MATHEMATICAL INDUCTION

Let 𝑃(𝑛) denote a statement (a formula or a theorem)

associated with 𝑛 = 1,2,3, … (natural numbers).

Step 1 (Verification): We first check that 𝑃(𝑛) holds for 𝑛 = 1.

Step 2 (Inductive Property): Assume 𝑃 𝑛 holds for 𝑛 = 𝑘 i.e.

𝑃(𝑘) holds, we prove that result holds for 𝑃(𝑘 + 1).

Step 3 (Conclusion): The result is true for all 𝑛.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 60

Problem: Using mathematical induction prove that
𝑛(𝑛+1)
𝑃 𝑛 = 1 + 2 + 3 + ⋯+ 𝑛 = .
2

Problem: Using mathematical induction prove that

1 + 2 + 22 + 23 + ⋯ + 2𝑛 = 2𝑛+1 − 1.

Problem: Using mathematical induction prove that for every

positive integer 𝑛 ≥ 4, 2𝑛 < 𝑛!

Problem: Prove that

𝑛 𝑛+1 𝑛+2
𝑘(𝑘 + 1) =
3
0≤𝑘≤𝑛

MATHEMATICAL LOGIC AND ITS APPLICATIONS 61

Problem: Using mathematical induction prove that 𝑛3 + 2𝑛 is
divisible by 3 for 𝑛 ≥ 1.

1 1
Problem: For any integer 𝑛 ≥ 1, Prove that 1 + + +
2 3
1
⋯+ ≥ 𝑛
𝑛

Problem: Using mathematical induction prove that

72𝑛 + 23𝑛−3 . 3𝑛−1 is divisible by 25.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 62

 DIVIDE AND CONQUER ALGORITHM

In computer science, binary search is a search algorithm

that finds the position of a target value within a sorted
array.

Binary search compares the target value to the middle

element of the array.

If they are not equal, the half in which the target cannot lie
is eliminated and the search continues on the remaining
half, again taking the middle element to compare to the
target value, and repeating this until the target value is
found. If the search ends with the remaining half being
empty, the target is not in the array.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 63
 DIVIDE AND CONQUER ALGORITHM

Binary search runs in logarithmic time in the worst case,

making O(\log n) comparisons, where n is the number of
elements in the array.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 64

 DIVIDE AND CONQUER ALGORITHM

Sorting a list of names:

Given a list ["Emma", "Charlie", "Bob", "Alice", "Frank"]
The algorithm divides it into two halves: ["Emma", "Charlie"]
and ["Bob", "Alice", "Frank"].

Each half is recursively sorted using Merge Sort, resulting

in ["Charlie", "Emma"] and ["Alice", "Bob", "Frank"].

The sorted halves are then merged pairwise, yielding the

final sorted list ["Alice", "Bob", "Charlie", "Emma", "Frank"].

MATHEMATICAL LOGIC AND ITS APPLICATIONS 65

 DIVIDE AND CONQUER ALGORITHM

Merge sort algorithm diagram

The main steps of the Merge Sort algorithm are as follows:

Divide the array into two halves.

Recursively apply Merge Sort to each half until each

subarray contains only one element.

Merge the sorted subarrays by comparing and combining

the elements in a pairwise manner.

Repeat the merging process until the entire array is sorted.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 66

 DIVIDE AND CONQUER ALGORITHM

Merge sort algorithm diagram

MATHEMATICAL LOGIC AND ITS APPLICATIONS 67

 DIVIDE AND CONQUER ALGORITHM

Quicksort Algorithm

MATHEMATICAL LOGIC AND ITS APPLICATIONS 68

 WELL ORDERING PRINCIPLE

The Well-Ordering Principle states that every non-empty set

of natural numbers has a least element.

Formally, the Well-Ordering Principle can be stated as

follows: "For every non-empty set 𝑆 of natural numbers,
there exists an element 𝑚 ∈ 𝑆 such that m ≤ 𝑥 for all
𝑥 ∈ 𝑆."

MATHEMATICAL LOGIC AND ITS APPLICATIONS 69

DISCRETE MATHEMATICS:
RELATIONS AND
FUNCTIONS

MATHEMATICAL LOGIC AND ITS APPLICATIONS 70

Ordered pair: An ordered pair 𝑎, 𝑏 is a listing of two objects
𝑎 and 𝑏 in the given order, with 𝑎 appearing first and 𝑏
appearing second.

The ordered pair 𝑎1 , 𝑏1 = (𝑎2 , 𝑏2 ) are equal if and only if

𝑎1 = 𝑎2 and 𝑏1 = 𝑏2 .

Cartesian Product: Let 𝐴 and 𝐵 be the two non-empty set.

Cartesian Product 𝐴 × 𝐵 is defined as
𝐴 × 𝐵 = { 𝑎, 𝑏 : 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵}

What are the number of elements in 𝐴 × 𝐵 is 𝐴 and 𝐵 are

finite sets.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 71
Partition of a set: Consider a non-empty set 𝐴. A collection 𝑆
of subsets of 𝐴 is called a partition of 𝐴 if
a. Each subset 𝐴𝑖 ∈ 𝑆 is non-empty.
b. 𝐴𝑖 ∩ 𝐴𝑗 = ∅ for all 𝑖 ≠ 𝑗
c. ∪ 𝐴𝑖 = 𝐴

Relation: Let 𝐴 and 𝐵 be two non-empty sets. A relation 𝑅

from 𝐴 to 𝐵 is defined as a subset of 𝐴 × 𝐵. Relation has a
rule of assigning an element 𝑎 ∈ 𝐴 to an element 𝑏 ∈ 𝐵.

If 𝑎, 𝑏 ∈ 𝑅 then we say that 𝑎 is related to 𝑏. If 𝑎, 𝑏 ∉ 𝑅

then we say that 𝑎 is not related to 𝑏.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 72

Example: Let 𝐴 = 1,2,3,4 and 𝐵 = {2,4}. Let 𝑅 be “is less
than” relation. That is 𝑎𝑅𝑏 if 𝑎 < 𝑏. Write 𝑅 as a set of
ordered pairs.

Example: Let 𝑅 be a relation on 𝐴 = {2,3,4,5,6} defined by

𝑎𝑅𝑏 if and only if |𝑎 − 𝑏| is divisible by 3. Write 𝑅 as a set of
ordered pairs.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 73

Let 𝐴 and 𝐵 be a finite sets with 𝑚 and 𝑛 number of elements
respectively. Then how many relations are possible from 𝐴 to
𝐵?

Diagram of a relation: Draw the diagram for the above

examples.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 74

 MATRIX OF A RELATION

Let 𝐴 = {𝑎_1, 𝑎_2, … , 𝑎𝑚 } and 𝐵 = {𝑏1 , 𝑏2 , … , 𝑏𝑛 } be a finite

sets. Let 𝑅 be a relation from 𝐴 to 𝐵. We represent 𝑅 by a
matrix 𝑀𝑅 = [𝑚𝑖𝑗 ] which is defined as
1 𝑖𝑓 (𝑎𝑖 , 𝑏𝑗 ) ∈ 𝑅
𝑚𝑖𝑗 =
0 𝑖𝑓 (𝑎𝑖 , 𝑏𝑗 ) ∉ 𝑅

To write the matrix 𝑀𝑅 , we write the elements of 𝐴 vertically

on the left and the elements of 𝐵 horizontally at the top
outside the matrix.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 75

The matrix 𝑀𝑅 is called the adjacency matrix of the relation 𝑅
or simply matrix of the relation 𝑅.

Write the matrix for each of the relation 𝑅 defined in the

examples above.

Is 𝑀𝑅 matrix is unique for a given relation?

MATHEMATICAL LOGIC AND ITS APPLICATIONS 76

 DIAGRAPH OF A RELATION

A relation from set 𝐴 to 𝐴 can also be represented pictorially

as follows:

Consider set 𝐴 = {1,2,3,4,5} and 𝑅 be a relation defined on 𝐴

where 𝑅 = { 1,2 , 1,3 , 1,4 , 2,3 , 3,2 , 4,4 , (5,2)}

MATHEMATICAL LOGIC AND ITS APPLICATIONS 77

 DIAGRAPH OF A RELATION

Let 𝐴 = {1,2,3,4} obtain diagraph for

𝑅 = 1,1 , 1,2 , 1,3 , 2,2 , 2,3 , 3,2 , 3,4 , 4,2 , 4,3 .

Let 𝐴 = 2,3,4,6,8 . Let 𝑅 be defined on 𝐴 by “if 𝑥 divides 𝑦

then 𝑥𝑅𝑦”

MATHEMATICAL LOGIC AND ITS APPLICATIONS 78

 DOMAIN AND RANGE OF A RELATION

 Let 𝑅 be a relation from 𝐴 to 𝐵.

 The set of elements of 𝐴 which are related to some
element in 𝐵 is called domain of 𝑅, denoted by 𝐷𝑜𝑚 𝑅 .
 The set of elements of 𝐵 which are related by some
element of 𝐴 is called range of 𝑅, denoted by 𝑅𝑎𝑛 𝑅 .

Find domain and range for the above examples.

Let 𝑋 = {1,2,3,4,5,6,7,8,9}. A relation 𝑅 on 𝑋 is defined as

𝑥𝑅𝑦 if and only if 𝑥 2 = 𝑦. Find 𝑅, domain and range of 𝑅.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 79

 INVERSE OF A RELATION

Let 𝑅 be a relation from a set 𝑋 to set 𝑌. The inverse of a

relation 𝑅, denoted by 𝑅−1 is the relation from 𝑌 to 𝑋 and is
defined as
𝑅−1 = { 𝑦, 𝑥 : 𝑥, 𝑦 ∈ 𝑅}

Find the inverse of the relation 𝑅 for the above problem.

COMBINING RELATIONS (OPERATIONS ON RELATTIONS)

Since relation is a set of ordered pairs, two relations 𝑅 and 𝑆

from 𝑋 to 𝑌 can be combined. We can find the union,
intersection, difference, compliment, etc of the relations to
get a new relations.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 80
 TYPES OF A RELATION

Reflexive relation: A relation 𝑅 on a set 𝐴 is called reflexive if

𝑎, 𝑎 ∈ 𝑅 for all 𝑎 ∈ 𝐴.

Irreflexive relation: A relation 𝑅 on a set 𝐴 is called reflexive

if 𝑎, 𝑎 ∉ 𝑅 for all 𝑎 ∈ 𝐴.

In otherwords, 𝑅 is a reflexive if each element of 𝐴 is related

to itself and it is irreflexive if no element is related to itself.

Check with the above examples that the given relations are
reflexive, Irreflexive or neither.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 81

How can one identify that the relation 𝑅 is a reflexive relation
and irreflexive relation from the matrix 𝑀𝑅 and by diagraph?

How can one identify that the relation 𝑅 is neither reflexive

nor irreflexive from the matrix 𝑀𝑅 and by diagraph?

If 𝑅 is a reflexive relation on 𝐴 then is 𝑅−1 is also reflexive

relation on 𝐴?

If a set 𝐴 contains 𝑛 elements then how many number of

reflexive relation on 𝐴 is possible?

MATHEMATICAL LOGIC AND ITS APPLICATIONS 82

 TYPES OF A RELATION

Symmetric relation: A relation 𝑅 on a set 𝐴 is called

symmetric if whenever 𝑎𝑅𝑏 we have 𝑏𝑅𝑎.

Note that a relation 𝑅 of a set 𝐴 is not symmetric if we can

find 𝑎, 𝑏 ∈ 𝐴 such that 𝑎𝑅𝑏 and 𝑏 is not related to 𝑎.

Example: Let 𝐴 = {1,2,3,4} and

𝑅 = { 1,3 , 3,1 , 3,4 , (4,3)} is a symmetric relation.
Example: Let 𝐴 = {1,2,3,4} and
𝑅 = { 1,3 , 3,1 , 3,4 , (4,4)} is not a symmetric relation.

How can one identify that the relation 𝑅 is a symmetric

relation from the matrix 𝑀𝑅 and by diagraph?
MATHEMATICAL LOGIC AND ITS APPLICATIONS 83
Problem: Let 𝐴 = {1,4,5} and 𝑅 be a relation on 𝐴 defined by
𝑎𝑅𝑏 if 𝑎 + 𝑏 ≤ 6. Write 𝑅, 𝑀𝑅 and check for reflexivity and
symmetry.

Asymmetric relation: A relation 𝑅 on 𝐴 is called asymmetric if

whenever 𝑎𝑅𝑏 then 𝑏 is not related to 𝑎.

It follows that a relation 𝑅 on 𝐴 is not asymmetric if for some

𝑎, 𝑏 ∈ 𝐴, we have both 𝑎𝑅𝑏 and 𝑏𝑅𝑎.

Check with the last examples that the given relations is

asymmetric.

How can one identify that the relation 𝑅 is asymmetric

relation from the matrix 𝑀𝑅 and by diagraph?
MATHEMATICAL LOGIC AND ITS APPLICATIONS 84
If a relation is not symmetric then does this implies that
relation is asymmetric?

Antisymmetric: A relation 𝑅 on a set 𝐴 is called antisymmetric

if whenever 𝑎𝑅𝑏 and 𝑏𝑅𝑎, then 𝑎 = 𝑏.

What is the contrapositive of the above statement?

It follows that a relation 𝑅 is antisymmetric if 𝑎 ≠ 𝑏 then 𝑎 is

not related to 𝑏 or 𝑏 is not related to 𝑎.

How can one identify that the relation 𝑅 is antisymmetric

relation from the matrix 𝑀𝑅 and by diagraph?

MATHEMATICAL LOGIC AND ITS APPLICATIONS 85

Check with the last examples that the given relations is
antisymmetric.

Problem: If ℤ+ is the set of all positive integers then “𝑎

divides 𝑏” where 𝑎, 𝑏 ∈ ℤ+ is an antisymmetric relation.

Problem: Let 𝐴 = {1,2,3,4} and

𝑅 = { 1,2 , 1,3 , 3,3 , (3,4)}. State the nature of the
relation. Give its matrix and diagraph.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 86

Problem: Determine whether the following relations are
(i) Symmetric
(ii) Asymmetric
(iii) Antisymmetric

1 0 0 1
1 0 1
(a) 0 0 1 (b) 0 1 1 1
0 0 1 0
1 1 1 0 0 0 1

Problem: How many symmetric relations are possible on a set

𝐴 with 𝑛 elements?

MATHEMATICAL LOGIC AND ITS APPLICATIONS 87

Problem: How many reflexive and symmetric relations are
possible on a set 𝐴 with 𝑛 elements?

Problem: Suppose 𝑅 is a Asymmetric relation. Is 𝑅

antisymmetric?

Theorem: A relation is asymmetric if and only if it is

both antisymmetric and irreflexive.

Problem: Given an example of a relation which is neither

Asymmetric nor Antisymmetric.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 88

 TRANSITIVE RELATION

A relation 𝑅 on a set 𝐴 is called transitive if whenever 𝑎𝑅𝑏

and 𝑏𝑅𝑐 then 𝑎𝑅𝑐.

A relation is not transitive if we can find 𝑎, 𝑏, 𝑐 ∈ 𝐴 such that

𝑎𝑅𝑏 and 𝑏𝑅𝑐 and still 𝑎 is not related to 𝑐.

Problem: Let 𝐴 = ℕ and let

𝑅 = { 𝑎, 𝑏 ∈ 𝐴 × 𝐴: 𝑎 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏}. Check whether 𝑅 is a
transitive relation.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 89

How can one identify that the relation 𝑅 is transitive from the
matrix 𝑀𝑅 and by diagraph?

Problem: Which of the following relations are transitive

(a) 𝑅1 = { 1,2 , 2,3 , (1,3)}
(b) 𝑅2 = {(1,2)}
(c) 𝑅3 = { 1,2 , 2,1 , 1,1 , 3,2 , 3,3 , (2,3)}.
Also write adjacency matrix for the above relations.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 90

 EQUIVALENCE RELATION

A relation 𝑅 on a set 𝐴 is called equivalence relation if it is

reflexive, symmetric and transitive.

Problem: Let 𝐴 = ℤ and let 𝑅 = { 𝑎, 𝑏 ∈ 𝐴 × 𝐴: 𝑎 ≡

𝑏(𝑚𝑜𝑑 4)}.

Problem: Let 𝐴 = ℤ and let the relation 𝑅 be defined as 𝑎𝑅𝑏

if 𝑎 ≤ 𝑏. Prove that 𝑅 is not an equivalence relation.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 91

Let 𝑅 be a relation defined on a set of positive integers such
that for all 𝑥, 𝑦 ∈ ℤ+ , 𝑥𝑅𝑦 if and only if 𝑥 + 𝑦 is an even
number. Prove that 𝑅 is an equivalence relation.

Let 𝑅 be a relation defined on a set of positive integers such

that for all 𝑥, 𝑦 ∈ ℤ+ , 𝑥𝑅𝑦 if and only if 𝑥 − 𝑦 < 7.
Determine whether 𝑅 is an equivalence relation.

If 𝑅 and 𝑆 are equivalence relations on a set 𝐴, Show that

𝑅 ∩ 𝑆 is also an equivalence relation.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 92

 EQUIVALENCE CLASS

Let 𝑅 be an equivalence relation defined on a set 𝐴. For any

𝑎 ∈ 𝐴, the set of all those elements of 𝐴 which are 𝑅-related
to 𝑎 constitutes equivalence class of 𝑎.

Equivalence class of 𝑎 is denoted by [𝑎]. Thus, symbolically

𝑎 = 𝑥 ∈ 𝐴: 𝑎𝑅𝑥 .

Let 𝐴 = {1,2,3,4} be a set. Let 𝑅 be a relation defined on 𝐴 as

1,1 , 1,2 , 1,3 , 2,1 , 2,2 , 2,3 , 3,1 , 3,2 ,
𝑅= .
3,3 , 3,4
Find all the equivalence classes of relation 𝑅.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 93

Theorem: Let 𝑅 be an equivalence relation defined on a non-
empty set 𝐴. Then for 𝑎, 𝑏 ∈ 𝐴 prove the following:
1. 𝑎 ∈ 𝑎
2. If 𝑏 ∈ [𝑎] then 𝑏 = [𝑎]
3. 𝑎 = [𝑏] if and only if 𝑎𝑅𝑏.
4. Two equivalence classes are either disjoint or identical i.e.
either 𝑎 = [𝑏] or 𝑎 ∩ 𝑏 = ∅.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 94

 PARTIAL ORDER RELATION

Let 𝑅 be a relation defined on a set 𝐴. The relation 𝑅 is said to

be a Partial Order Relation (Poset) if it is reflexive,
antisymmetric and transitive.

Check whether the following relations are reflexive,

symmetric, antisymmetric and transitive where 𝐴 = {1,2,3}
1. 𝑅1 = { 1,1 , 2,3 , (3,3)}
2. 𝑅2 = { 1,1 , 2,2 , 2,3 , 3,3 , (3,2)}

MATHEMATICAL LOGIC AND ITS APPLICATIONS 95

Define a relation 𝑅 on the set 𝑍 by 𝑎𝑅𝑏 if 𝑎 − 𝑏 is a non
negative even integer. Verify whether 𝑅 is a partial order
relation.

Consider a set of integers ℤ. Let 𝑎𝑅𝑏 if 𝑏 𝑟 = 𝑎 for some

positive integer 𝑟. Show that 𝑅 is a partial order relation.

PARTIAL ORDER SET

A set 𝐴 together with the partial order relation 𝑅 is called a

partially ordered set or in brief Poset and is generally denoted
by 𝐴, 𝑅 .

MATHEMATICAL LOGIC AND ITS APPLICATIONS 96

 HASSE DIAGRAM (FOR POSET)

Step 1: Draw the diagraph.

Step 2: Since 𝑅 is reflexive we have 𝑎𝑅𝑎 for all 𝑎. Drop the

loops around the vertices.

Step 3: Since 𝑅 is transitive we have if 𝑎𝑅𝑏 and 𝑏𝑅𝑐 then

𝑎𝑅𝑐, we drop the edge from 𝑎 to 𝑐. Thus we drop all edges
which implies transitivity.

Step 4: Finally we arrange the whole diagram such that all

arrows point upwards and then drop the arrow heads. The
resulting diagram is called the Hasse diagram.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 97

Comparable elements: Let 𝐴 be a given set and 𝑅 is a partial
order relation on 𝐴 then the elements 𝑎, 𝑏 ∈ 𝐴 are said to be
comparable if 𝑎𝑅𝑏 or 𝑏𝑅𝑎.
This means if 𝑎 is not related to 𝑏 and 𝑏 is not related to 𝑎
then 𝑎 and 𝑏 are not comparable.

Elements which are comparable cannot lie on the same line in

the Hasse diagram.

Consider a set 𝐴 = {1,2,3,4,12} and the relation of divisibility

i.e. 𝑎𝑅𝑏 if and only if 𝑎 divides 𝑏. Show that (𝐴, 𝑅) is a poset.
Also consider the diagraph of the poset and its Hasse
diagram.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 98
Hasse diagram is defined as below:

(i) The vertices represents the elements of 𝐴.

(ii) There is an upward line from 𝑥 to 𝑦 whenever 𝑥𝑅𝑦 and
𝑥 ≠ 𝑦.
(iii) The figure has least number of segments that accomplish
the property (ii).

Draw the Hasse diagram of the set {1,3,9,18} under partial

order relation “divide”.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 99

 TOTAL ORDER RELATION OR CHAIN

If any two elements in a poset are comparable, then the

partial order is called a total order (or linear order).

In such a situation, the relation is called a simple ordering

relation. The set 𝐴 together with a total order relation is
called a chain.

Example: {2,4,8,16} with “divides” as relation is a chain.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 100

Problem: Determine the Hasse diagram of the relation on
𝐴 = {1,2,3,4,5} whose matrix is
1 1 1 1 1
0 1 1 1 1
(a) 𝑀𝑅 = 0 0 1 1 1
0 0 0 1 1
0 0 0 0 1

1 0 1 1 1
0 1 1 1 1
(b) 𝑀𝑅 = 0 0 1 1 1
0 0 0 1 0
0 0 0 0 1

MATHEMATICAL LOGIC AND ITS APPLICATIONS 101

 MAXIMAL AND MINIMAL ELEMENT

An element 𝑎 ∈ 𝐴 is called a maximal element of the Poset

(𝐴, ≤) if there is no element 𝑐 ∈ 𝐴 such that 𝑐 ≠ 𝑎 and
𝑎 < 𝑐.

An element 𝑏 ∈ 𝐴 is called a minimal element of the Poset

(𝐴, ≤) if there is no element 𝑐 ∈ 𝐴 such that 𝑐 ≠ 𝑏 and
𝑐 < 𝑏.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 102

 GREATEST AND LEAST ELEMENTS

Let 𝐴 be a finite non-empty poset. An element 𝑎 ∈ 𝐴 is called

a greatest element of 𝐴 if 𝑥 ≤ 𝑎 for all 𝑥 ∈ 𝐴.

Let 𝐴 be a finite non-empty poset. An element 𝑎 ∈ 𝐴 is called

a least element of 𝐴 if 𝑎 ≤ 𝑥 for all 𝑥 ∈ 𝐴.

MATHEMATICAL LOGIC AND ITS APPLICATIONS

10
3
 GREATEST AND LEAST ELEMENTS OF A SUBSET

Consider a poset 𝐴 and a subset 𝐵 of 𝐴.

An element 𝑎 ∈ 𝐴 is called an upper bound of 𝐵 if 𝑏 ≤ 𝑎 for

all 𝑥 ∈ 𝐴.

An element 𝑎 ∈ 𝐴 is called a lower bound of 𝐵 if 𝑎 ≤ 𝑥 for all

𝑥 ∈ 𝐴.

MATHEMATICAL LOGIC AND ITS APPLICATIONS

10
4
 LUB AND GLB

Let 𝐴 be a poset and 𝐵 be a subset of 𝐴. An element 𝑎 ∈ 𝐴 is

called a least upper bound (LUB) or supremum of 𝐵 if 𝑎 is an
upper bound of 𝐵 and if 𝑎′ is an upper bound then 𝑎 ≤ 𝑎′ .

Let 𝐴 be a poset and 𝐵 be a subset of 𝐴. An element 𝑎 ∈ 𝐴 is

called a greatest lower bound (GLB) or infimum of 𝐵 if 𝑎 is an
lower bound of 𝐵 and if 𝑎′ is an upper bound then 𝑎′ ≤ 𝑎.

MATHEMATICAL LOGIC AND ITS APPLICATIONS

10
5
 JOIN AND MEET

Let 𝐴 be a poset 𝐿, ≤ . Let 𝑎, 𝑏 ∈ 𝐿. We define

𝑎 ∨ 𝑏 (read as ‘a join b’) as LUB of a and b
𝑎 ∧ 𝑏 (read as ‘a meet b’) as GLB of a and b

Theorem: Let 𝐴 be a poset 𝐿, ≤ and let 𝑎, 𝑏 ∈ 𝐿

(i) If a and b have a LUB then this LUB is unique.
(ii) If a and b have a GLB then this GLB is unique.

MATHEMATICAL LOGIC AND ITS APPLICATIONS

10
6
 LATTICE

A poset (𝐿, ≤) in which every pair {𝑎, 𝑏} of two elements of 𝐿

has a least upper bound (LUB) and a greatest lower bound
(GLB) is called a lattice.

Problem: Let 𝐿 = {1,2,3,5,30} and 𝑅 be a relation ‘is divisible

by’. Prove that 𝐿 is a lattice.

Problem: Show that the set of all divisors of 70 form a lattice.

Problem: Check whether 𝐿 = {2,4,12,16} and 𝑅 be a relation

‘is divisible by’ is a lattice.

MATHEMATICAL LOGIC AND ITS APPLICATIONS

10
7
 DISTRIBUTIVE LATTICE

A lattice 𝐿 is called distributive if for any elements 𝑎, 𝑏, 𝑐 ∈ 𝐿

the following distributive properties are satisfied:

𝑎∧ 𝑏∨𝑐 = 𝑎∧𝑏 ∨ 𝑎∧𝑐

𝑎 ∨ 𝑏 ∧ 𝑐 = 𝑎 ∨ 𝑐 ∧ (𝑎 ∨ 𝑐)

Problem: Let 𝐿 = {1,2,3,6} and 𝑅 be a relation ‘is divisible by’.

Prove that 𝐿 is a distributive lattice.

Problem: Let 𝐿 = {1,2,3,5,30} and 𝑅 be a relation ‘is divisible

by’. We have 𝐿 is a lattice. Prove that distributive properties
hold for the elements 2,3 and 5.
MATHEMATICAL LOGIC AND ITS APPLICATIONS
10
8
 FUNCTIONS

Let 𝑋 and 𝑌 be two non empty sets. A function (or a mapping)

𝑓, from 𝑋 to 𝑌 is a relation 𝑅 on 𝑋 × 𝑌 such that for every
𝑥 ∈ 𝑋 there exists unique 𝑦 ∈ 𝑌 such that 𝑥, 𝑦 ∈ 𝑅. In terms
of function we write as 𝑓 𝑥 = 𝑦.

The set 𝑋 is called domain of 𝑓 and set 𝑌 is called codomain

of 𝑓.

If 𝑓 𝑥 = 𝑦 then 𝑦 is called image of 𝑥 and 𝑥 is called pre-

image of 𝑦.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 109

Problem: Let 𝐴 = 1,2,3 and 𝐵 = {𝑥, 𝑦} Identify which of the
following relations are functions.
1. 𝑅 = { 1, 𝑥 , 2, 𝑥 , 1, 𝑦 , (3, 𝑥)}
2. 𝑅 = { 1, 𝑥 , 2, 𝑥 , (3, 𝑦)}
3. 𝑅 = { 2, 𝑥 , 3, 𝑦 , (1, 𝑥)}

Is 𝑓: ℝ → ℝ defined as 𝑓 𝑥 = 𝑥 2 is a function?
Is 𝑓: ℝ → ℝ defined as 𝑓 𝑥 = 𝑥 is a function?
Is 𝑓: ℝ → ℝ+ defined as 𝑓 𝑥 = 𝑥 is a function?

Injective function: A function 𝑓: 𝐴 → 𝐵 is said to be injective

or one-one, if 𝑓 𝑥 = 𝑓(𝑦) then 𝑥 = 𝑦.
Write contrapositive of the above statement.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 110
Surjective function: A function 𝑓: 𝐴 → 𝐵 is said to be
surjective or onto if for every 𝑦 ∈ 𝑌 there exists 𝑥 ∈ 𝑋 such
that 𝑓 𝑥 = 𝑦.

Direct image of a function 𝑓: 𝐴 → 𝐵: Let C ⊂ 𝐴 then

𝑓(𝐶) = 𝑓(𝑥): 𝑥 ∈ 𝐶 .

Inverse image of a function 𝑓: 𝐴 → 𝐵: Let 𝐷 ⊂ 𝐵 then

𝑓 −1 𝐷 = 𝑥 ∈ 𝐴: 𝑓 𝑥 ∈ 𝐷 .

Bijective function: A function 𝑓: 𝐴 → 𝐵 is said to be bijective

if 𝑓 is both injective and surjective.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 111

 COMPOSITE FUNCTIONS

Identity function: A 𝑓: 𝑋 → 𝑋 is called as identity function of

𝑓 𝑥 = 𝑥 for all 𝑥 ∈ 𝑋.

Two functions 𝑓: 𝑋 → 𝑌 and g: 𝑋 → 𝑌 are said to be equal if

𝑓 𝑥 = 𝑔(𝑥) for all 𝑥 ∈ 𝑋.

Let 𝑓: 𝑋 → 𝑌 and 𝑔: 𝑌 → 𝑍 be a function. Then a function

ℎ: 𝑋 → 𝑍 defined as ℎ 𝑥 = 𝑓𝑜𝑔 𝑥 = 𝑓(𝑔 𝑥 ) for all 𝑥 ∈ 𝑋.

Problem: If 𝑓: ℝ → ℝ defined as 𝑓 𝑥 = 𝑥 2 and 𝑔: ℝ → ℝ

defined as 𝑔 𝑥 = sin 𝑥 . Find 𝑓𝑜𝑔 and 𝑔𝑜𝑓.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 112

Inverse of a function: If 𝑓: 𝐴 → 𝐵 is a bijective function then
we define inverse function of 𝑓 as 𝑓 −1 : 𝐵 → 𝐴, 𝑓 −1 𝑦 = 𝑥
where 𝑓 𝑥 = 𝑦.

Then we have 𝑓 −1 𝑜𝑓 𝑥 = 𝑥 for all 𝑥 ∈ 𝑋 and 𝑓𝑜𝑓 −1 𝑦 = 𝑦

for all 𝑦 ∈ 𝑌

Problem: Prove that 𝑓: ℝ → ℝ defined as 𝑓 𝑥 = 5𝑥 − 8 is a

bijective function and find its inverse.

Problem: Prove that 𝑓: ℝ − 1 → ℝ − {−1} defined as

𝑥+5
𝑓 𝑥 = is a bijective function and find its inverse.
1−𝑥

MATHEMATICAL LOGIC AND ITS APPLICATIONS 113

Problem: Show that the modulus function 𝑓: ℝ → ℝ defined
as 𝑓 𝑥 = 𝑥 for all 𝑥 ∈ ℝ is neither injective nor surjective.

Problem: Is the greatest integer function 𝑓 𝑥 = [𝑥] for all

𝑥 ∈ ℝ where [𝑥] denotes the greatest integer less than or
equal to 𝑥, injective or surjective?

Problem: Is the function 𝑓: ℤ+ → ℤ+ defined as 𝑓 𝑥 = 1 +

𝑥 2 for all 𝑥 ∈ ℤ+ is injective or surjective?

Problem: Find 𝑔𝑜𝑓 and 𝑓𝑜𝑔 where 𝑓 𝑥 = |𝑥| and

𝑔 𝑥 = 5𝑥 + 2.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 114

Problem: Consider 𝑓: ℝ+ → [4. ∞) defined as 𝑓 𝑥 = 𝑥 2 + 4.
Show that 𝑓 is invertible with the inverse 𝑓 −1 𝑦 = 𝑦 − 4
where ℝ+ denotes the set of all non-negative real numbers.

Problem: If 𝑓, 𝑔, ℎ: ℝ → ℝ defined as 𝑓 𝑥 = 𝑥 3 , 𝑔 𝑥 =
cos 𝑥 and ℎ 𝑥 = 5𝑥 + 9. Find 𝑓𝑜𝑔𝑜ℎ and ℎ𝑜𝑔𝑜𝑓.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 115

 RECURRENCE RELATION

Sequence: An ordered set of numbers 𝑎1 , 𝑎2 , 𝑎3 , … is called as

a sequence. Denoted by 𝑎𝑛 .
For example: 2,22 , 23 , …

𝑎1 = 2, 𝑎2 = 22 , 𝑎3 = 23 , … which can be written as 𝑎𝑛 = 2𝑛

for 𝑛 ≥ 1. Also it can be written as 𝑎𝑛 = 2𝑎𝑛−1 and 𝑎1 = 2.

The expression which expresses a term in terms of its

previous term or terms with initial conditions is called as
Recurrence relation.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 116

Given a sequence 𝑎𝑛 , an equation which gives a relation
between its n-th term 𝒂𝒏 with its previous terms
𝒂𝟎 , 𝒂𝟏 , 𝒂𝟐 , … , 𝒂𝒏−𝟏 where 𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛−1 are given
explicitly is called as recurrence relation.

The terms 𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛−1 which are given explicitly are

called as initial conditions or boundary conditions.

Example: 5,9,13,17,…..
We have 𝑎𝑛 = 𝑎𝑛−1 + 4 where 𝑎1 = 5

Fibonacci sequence: 1,1,2,3,5,8,….

We have 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 where 𝑎1 = 1, 𝑎2 = 1.
MATHEMATICAL LOGIC AND ITS APPLICATIONS 117
Problem: Find the sequences from the following recurrence
relations.
(i) 𝑎𝑛 = 𝑛 𝑎𝑛−1 2 where 𝑎0 = 1, 𝑛 ≥ 1
(ii) 𝑎𝑛+1 = 3𝑎𝑛 + 𝑛 where 𝑎1 = 1, 𝑛 ≥ 1

MATHEMATICAL LOGIC AND ITS APPLICATIONS 118

 SOLVING RECURRENCE RELATION

We now try to obtain a formula for 𝑎𝑛 in terms of 𝑛 which

enable us to get an element of a sequence of any order. This
is called solving a recurrence relation.

Method: Characteristic roots

Problem: Solve 𝑎𝑛 = 5𝑎𝑛−1 − 6𝑎𝑛−2 for 𝑛 ≥ 2, 𝑎0 = 0,

𝑎1 = 1.
Solution: 𝑎𝑛 = −1 2𝑛 + 3𝑛 for 𝑛 ≥ 2

Problem: Solve 𝑎𝑛 = 6𝑎𝑛−1 − 11𝑎𝑛−2 + 6𝑎𝑛−3 for 𝑛 ≥ 3,

𝑎0 = 2, 𝑎1 = 5, 𝑎2 = 15.
Solution: 𝑎𝑛 = 1 − 2𝑛 + 2(3𝑛 ) for 𝑛 ≥ 3
MATHEMATICAL LOGIC AND ITS APPLICATIONS 119
Problem: Solve 𝑎𝑛 = 2𝑎𝑛−1 + 𝑎𝑛−2 for 𝑛 ≥ 2, 𝑎0 = 0,
𝑎1 = 1.
1 𝑛 𝑛
Solution: 𝑎𝑛 = [ 1 + 2 − 1 − 2 ] for 𝑛 ≥ 2
2 2

Problem: Solve 𝑎𝑛 = 6𝑎𝑛−1 − 9𝑎𝑛−2 for 𝑛 ≥ 2, 𝑎0 = 2,

𝑎1 = 3.
Solution: 𝑎𝑛 = 2 3𝑛 − 𝑛 3𝑛 for 𝑛 ≥ 2

Problem: Solve 𝑎𝑛 = 8𝑎𝑛−1 − 21𝑎𝑛−2 + 18𝑎𝑛−3 for 𝑛 ≥ 3,

𝑎0 = 0, 𝑎1 = 2, 𝑎2 = 13.
Solution: 𝑎𝑛 = 2𝑛 − 3𝑛 + 𝑛(3𝑛 ) for 𝑛 ≥ 3

MATHEMATICAL LOGIC AND ITS APPLICATIONS 120

MATHEMATICAL LOGIC AND ITS APPLICATIONS 121
DISCRETE MATHEMATICS:
DISCRETE PROBABILITY

MATHEMATICAL LOGIC AND ITS APPLICATIONS 122

Problem: A fair die is tossed. Find the probability that an even
number will appear if it is given that the toss resulted in
number less than 5.

Problem: Two dice are thrown. What is the probability that

the number 3 will appear in a die if it is known that the sum
of the numbers is more than 7?

Problem: Two cards are drawn from a pack of cards one by

one without replacement. Find the probability that first card
is a king and the second card is a queen.

Problem: A coin is tossed twice. Find the probability that a

head appears in both of the tosses.

MATHEMATICAL LOGIC AND ITS APPLICATIONS 123

Problem: A bag contains 3 black and 4 white balls. A second
bag contains 2 black and 3 white balls. A bag is selected at
random and ball is drawn from the bag. Find the probability
that the ball drawn is white.

Problem: The probability that A and B pass an examination is

1 2
and respectively. Find the probability that atleast one of
3 5
them passes the examination.

Problem: There are 2 bags. The first bag contains 3 white and
4 black balls. The second bag contains 2 white and 3 black
balls. A ball is chosen at random from the first bag and
transferred to second bag. What is the probability that the
ball is white?
MATHEMATICAL LOGIC AND ITS APPLICATIONS 124
 PARTITION OF A SET

Partition of a sample space: Consider a sample space 𝑆. A

collection 𝐹 of subsets of 𝑆 is called a partition of 𝑆 if
a. Each subset 𝐹𝑖 ∈ 𝐹 is non-empty.
b. 𝐹𝑖 ∩ 𝐹𝑗 = ∅ for all 𝑖 ≠ 𝑗
c. ∪ 𝐹𝑖 = 𝑆

BAYES THEOREM

Let the events 𝐴1 , 𝐴2 , … , 𝐴𝑛 represent a partition of the

sample space 𝑆. Let 𝐵 be any other event defined on 𝑆. If
𝑃 𝐴𝑖 ≠ 0 for all 1 ≤ 𝑖 ≤ 𝑛 and 𝑃 𝐵 ≠ 0 then
𝑃 𝐴𝑖 𝑃 𝐵 𝐴𝑖
𝑃 𝐴𝑖 𝐵 =
𝑃 𝐴𝑗 𝑃 𝐵 𝐴𝑗
MATHEMATICAL LOGIC AND ITS APPLICATIONS 125
Problem: There are 3 true coins and 1 false coin with head on
both sides in a bag. A coin is chosen at random and tossed
four times. If head occurs all the four times; What is the
probability that the false coin was chosen and used?

Problem: A coin is tossed. If it turns up head then two balls

drawn from urn A otherwise two balls are drawn from urn B.
Urn A contains 3 black and 5 white balls. Urn B contains 7
black and 1 white balls. What is the probability that urn A was
used, given that both balls drawn are black?

MATHEMATICAL LOGIC AND ITS APPLICATIONS 126

Problem: A bag contains 4 red and 4 black balls, another bag
contains 2 red and 6 black balls. One of the two bags is
selected at random and a ball is drawn from the bag which is
found to be red. Find the probability that the ball is drawn
from the
first bag.

Problem: A certain test for a particular cancer is known to be

95% accurate. A person submits to the test and the result is
positive. Suppose that a person comes from the population of
100000 where 2000 people suffer from that disease. What
can we conclude about the probability that the person under
test has that particular cancer?
MATHEMATICAL LOGIC AND ITS APPLICATIONS 127
MATHEMATICAL LOGIC AND ITS APPLICATIONS 128
MATHEMATICAL LOGIC AND ITS APPLICATIONS 129