Discrete Mathematics

Vamsi Krishna cheedepudi

• Discrete Maths syllabus
• 1. Mathematical Logic
• 2. Combinatorics
• 3. Graph theory
• 4. Set theory

Vamsi Krishna cheedepudi

Reference Books

1. Discrete Mathematical Structure with Applications to Computer Science –

Tremblay & Manohar

2. Discrete Mathematics for Computer Scientist & Mathematicians – Mott, Kandell

& Baker.

3. Discrete Mathematics – Kenneth Rosen

4. Discrete Mathematics – C.L.Liu

Vamsi Krishna cheedepudi

Weightage Analysis # Year Wise

2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014

8 8 9 12 10 6 7 7 6 10 11

Vamsi Krishna cheedepudi

Mathematical Logic

Vamsi Krishna cheedepudi

 LOGIC

Logic is the basis of all mathematical reasoning, and of all

automated reasoning. It has the practical applications to

 the design of computing machines

 the specification of systems

 Artificial intelligence

 programming languages and to other areas of computer science.

Vamsi Krishna cheedepudi
 Propositional Logic

Proposition:-

A proposition is a declarative sentence (that is, a sentence

that declares a fact) that is either true or false, But not both.

Vamsi Krishna cheedepudi

Based on Purpose, different types of sentences are
•Declarative Sentence: Makes a statement.
•Example: The sky is blue.
•Interrogative Sentence: Asks a question.
•Example: Are you coming to the party?
•Imperative Sentence: Gives a command or request.
•Example: Close the door.
•Exclamatory Sentence: Expresses strong emotion.
•Example: Wow, that was amazing!

Vamsi Krishna cheedepudi

Eg:-

1. Washington D.C. is the capital of the united states of America.

2. Bombay is the capital of India.

3. 1 + 1 = 2

4. 2 + 2 = 3

Eg:-

1. What time is it ?

2. Read this carefully

3. x + 1 = 2 Vamsi Krishna cheedepudi

Propositional Variables are represented by p, q, r, s, . . . . . . .

Truth Values can be True ( T) or False ( F)

Propositional Calculus : The area of logic that deals with propositions is called
as propositional logic (or) propositional calculus.

Simple Proposition : A proposition which is in simplified form is known atomic

or simple propositions

Compound Propositions: Many Mathematical statements are constructed by

combining one or propositions by using logical operators, known as compound
propositions. Vamsi Krishna cheedepudi
Logical Operators – Compound Proposition

 (and) - Conjunction

 (or) - Disjunction

→ (Implies) - Implication

 (Bi-implies) - Bi-conditional

Vamsi Krishna cheedepudi

• Negation:
The negation of a statement is the opposite of the statement, and is
represented by a symbol such as ∼X, ¯X, or X′. The negation of a statement
is true when the original statement is false, and false when the original
statement is true
• p : Mumbai is the capital of Maharashtra

• ~p : Mumbai is NOT the capital of Maharashtra

Vamsi Krishna cheedepudi

Construct Truth Tables of the following compound proposition:

~ (p  q)  ( ~ p  ~ q )

Vamsi Krishna cheedepudi

~q→~p

Vamsi Krishna cheedepudi

Q. If the proposition ~p  q is true, then the truth value of
the proposition ~p  (p  q), where ‘~’ is negation, ‘’ is
inclusive or and ‘’ is implication is

(a) true
(b) multiple-valued
(b) false
(d) cannot be determined

Vamsi Krishna cheedepudi

Logical Equivalence: Compound propositions that have the same truth
values in all possible cases are called logically equivalent.

The compound propositions ‘P’ and ‘Q’ are called logically

equivalent if P  Q is a tautology

P  Q or P  Q

Vamsi Krishna cheedepudi

Tautology, Contradiction, Contingency, Satisfiable and Unsatisfiable:

A formula which is TRUE in each and every possible situation is known as

Tautology

A formula which is false in any possible situation is known as Contradiction

A formula which is neither Tautology nor Contradiction is known as

contingency
Vamsi Krishna cheedepudi
A formula which is TRUE in at least one possible situation is known
as Satisfiable

Every contingency is satisfiable, But converse need not be TRUE

A formula which is not satisfiable is known as Unsatisfiable

Vamsi Krishna cheedepudi

Eg: Which of the following is NOT a Tautology

a) ~ (p → q) → p c) [~ p  (p  q)] → q

b) ~ (p → q) → ~ q d) [(p → q)  q] → p

Vamsi Krishna cheedepudi

Q. Which of the following is/are tautology?
(a) (a  b) → (b  c)
(b) (a  b) → (b  c)
(c) (a  b) → (b → c)
(d) (a → b) → (b → c)

Vamsi Krishna cheedepudi

Eg: Which of the following is NOT a tautology

a) (p  q) → (p  q) c) ~ p → (p → q)

b) (p  q) → (p → q) d) p → (p  q)

Vamsi Krishna cheedepudi

Q. Which one of the following Boolean expressions is NOT a
tautology?

(a) ((a → b)  (b → c)) → (a → c)

(b) (a  c) → (~ b → (a  c))
(c) (a  b  c) → (c  a)
(d) a → (b → a)

Vamsi Krishna cheedepudi

Q. Let p, q and r be propositions and the expression (p → q)
→ r be a contradiction. Then, the expression (r → p) → q
is
(a) a tautology
(b) a contradiction
(c) always TRUE when p is FALSE
(d) always TRUE when q is TRUE

Vamsi Krishna cheedepudi

Q. Which one of the following propositional logic
formulas is TRUE when exactly two of p, q and r are
TRUE?
(a) ((p  q)  r)  (p  q ~ r)
(b) (~ (p  q)  r)  (p  q  ~ r)
(c) ((p → q)  r)  (p  q  ~ r)
(d) (~ (p  q)  r)  (p  q  ~ r)

Vamsi Krishna cheedepudi

Laws (or) Properties (or) Logical Equivalences:

Rules Name
1 ppp
ppp Idempotent law
2 pqqp
pqqp Commutative law

3 p  (q  r)  (p  q)  r
Associative law
p  (q  r)  (p  q)  r
4 p  (q  r)  (p  q)  (p  r)
Distributive Law
p  (q  r)  (p  q)  (p  r)
5 ~ (p  q)  ~ p  ~ q
~ (p  q)  ~ p  ~ q De Morgan’s Law
6 p→q~pq Implication law
Laws (or) Properties (or) Logical Equivalences:
Rules Name
7 p  q  (p → q)  (q → p)
Bi-implication law
8 p  (p  q)  p
p  (p  q)  p Absorption law
9 ptp
pfp Identity law
10 ~(~ p)  p Double Negation (or) Involutary law
11 p~pt
p~pf Negation (or) Complements (or) Inverse law

12 p  t  t
pff Domination law
Conditional Statements:

The statement p → q is called a conditional statement, because

p → q asserts that ‘q’ is True on the condition that ‘p’ holds.

The conditional statement p → q is the proposition “If p, then q”.

The conditional statement p → q is false when ‘p’ is true and ‘q’ is
false, otherwise True. In this, p is called antecedent and q is called
consequent.

Vamsi Krishna cheedepudi

Variety of Terminology to express p → q:

“if p then q” “p implies q”

“if p, q” “p only if q”
“p is sufficient for q” “a sufficient condition for q is p”
“q if p” “q when ever p”
“q when p” “q is necessary for p”
“a necessary condition for p is q” “q follows from p”

“q unless ~ p” “q provided that p”

Vamsi Krishna cheedepudi
Conditional Statements:

If you work honest then you will be happy.

If you work, things can happen.

He can stay on the team only if he improves his grades.

I can wear a rain coat if it rains.

You can ask me for help whenever you need.

ay on the team only if he completes his homework and

improves his grades Vamsi Krishna cheedepudi
Conditional Statements:

You will be sick unless you stop eating.

I will not pay unless you provide the goods immediately.

He would be here now unless he was stuck in traffic.

ay on the team only if he completes his homework and

improves his grades
Vamsi Krishna cheedepudi
•If...Then: If you don't have a valid passport, then you cannot enter the country.

Conditional Statements:

You will be sick unless you stop eating.

You can enter the country only if you have valid passport.

He will agree the deal only if you increase the offer.

Vamsi Krishna cheedepudi

Converse, Inverse and contra positive:

Vamsi Krishna cheedepudi

Eg: In Triangle ABC, If AB = AC then B = C

Vamsi Krishna cheedepudi

Eg: “The home Team wins whenever it is raining”

Vamsi Krishna cheedepudi

GATE:

What is the converse of the following assertion?

“I stay only if you go”

a) I stay if you go

b) If I stay then you go

c) If you do not go then I do not stay

d) If I do not stay then you go

Vamsi Krishna cheedepudi

Q. “If X then Y unless Z” is represented by which of the following formulas
in propositional logic? (“~” is negation, “” is conjunction, and “→” is
implication) GATE – 2002

(a) (X  ~ Z) → Y

(b) (X  Y) → ~ Z

(C) X → (Y  ~ Z)

(d) (X → Y)  ~ Z

Vamsi Krishna cheedepudi

Eg:

Q. The propositional function p  (q  ~ p) is

a) tautology

b) contradiction

c) contingency

d) p  q

Vamsi Krishna cheedepudi

Q. The proposition p  (~p  q) is
(a) a tautology
(b)  (p  q)
(c)  (p  q)
(d) a contradiction

Vamsi Krishna cheedepudi

Q. The propositional function (p → q)  (p  ~ q) is

a) tautology

b) contradiction

c) contingency

d) None

Vamsi Krishna cheedepudi

Q. p → (q → r) 

a) (p  q) → ~ r

b) (p  q) → r

c) (p  q) → ~ r

d) (p  q) → r

Vamsi Krishna cheedepudi

The binary equation  is defined as follows
p q pq
T T T
T F T
F T F
F F T

Then compound proposition (p  q) 

a) ~ q  ~ p b) p  ~ q c) ~ q  p d) p  q

Vamsi Krishna cheedepudi

Q. Determine whether each of the following is a tautology a
contradiction, or neither (“” is disjunction, “” is
conjunction. “→” is implication, ‘~” is negation and “” is
biconditional (if and only if).
(i) A  (A  A)
(ii) (A  B) → B
(iii) A  (~ (A  B))

Vamsi Krishna cheedepudi

Q. If A and B are two propositions and ‘*’ is a binary operator defined as

A B A*B

T T T
T F T
F T F
F F T
Then the compound proposition (A  B) 

a) ~ A * B b) ~ A * ~ B
c) ~ (A * ~ B) d) ~ (~ A * B)
Vamsi Krishna cheedepudi
Q. The proposition p  (~p  q) is
(a) a tautology
(b)  (p  q)
(c)  (p  q)
(d) a contradiction

Vamsi Krishna cheedepudi

Q. Let p and q be two propositions. Consider the following
two formula in propositional logic
S1 : (¬p  (p  q)) → q
S2 : q → (¬p  (p  q))
Which one of the following choices is correct?
(a) Neither S1 nor S2 is a tautology
(b) S1 is a tautology but S2 is not a tautology
(c) Both S1 and S2 are tautologies
(d) S1 is not a tautology but S2 is a tautology
Vamsi Krishna cheedepudi
Q. (a) Show that the formula
[(~p  q)  (q  p)] is not a tautology.
(b) Let A be tautology and B be any other formula, Prove that
(A  B) is a tautology.

Vamsi Krishna cheedepudi

Q. Consider two well-formed formulas in propositional logic
F1 : P  ~ P
F2 : (P  ~P)  (~P  P)
Which of the following statements is correct?
(a) F1 is satisfiable, F2 is valid
(b) F1 is unsatisfiable, F2 is satisfiable
(c) F1 is unsatisfiable, F2 is valid
(d) F1 and F2 are both satisfiable
Vamsi Krishna cheedepudi
Q. Let a, b, c, d be propositions. Assume that the
equivalences a  (b  ~ b) and b  c hold. Then the truth
value of the formulae (a  b) → ((a  c)  d) is always

(a) True
(b) False
(C) Same as truth value of b
(d) Same as truth value of d

Vamsi Krishna cheedepudi

Q. A logical binary relation ʘ, is defined as follows:
A B AʘB
True True True
True False True
False True False
False False True

Let be the unary negation (NOT) operator, with higher precedence

than ʘ. Which one of the following is equivalent to A  B?
(A) (~ A ʘ B) (B) ~(A ʘ ~ B)
(C) ~ (~ A ʘ ~ B) (D) ~ (~ A ʘ B)
Vamsi Krishna cheedepudi
Q. Let p and q be two propositions. Consider the following
two formula in propositional logic
S1 : (¬p  (p  q)) → q
S2 : q → (¬p  (p  q))
Which one of the following choices is correct?
(a) Neither S1 nor S2 is a tautology
(b) S1 is a tautology but S2 is not a tautology
(c) Both S1 and S2 are tautologies
(d) S1 is not a tautology but S2 is a tautology
Vamsi Krishna cheedepudi
Q. Choose the correct choice(s) regarding the following
propositional logic assertions:
S: ((P  Q) → R) → ((P  Q) → (Q → R)
(a) S is a tautology
(b) The antecedent of S is logically equivalent to the
consequent of S
(c) S is a contradiction
(d) S is neither a tautology nor a contradiction

Vamsi Krishna cheedepudi

Q. The following propositional statement is
(P → (Q  R)) → ((P  Q) → R)
(a) Satisfiable but not valid
(b) Valid
(c) A contradiction
(d) None of the above

Vamsi Krishna cheedepudi

Q. Let P, Q and R be three atomic prepositional assertions.
Let X denote (P  Q) → R and Y denote (P → R)  (Q → R).
Which one of the following is a tautology?
(a) X  Y
(b) X → Y
(c) Y → X
(d) ~Y → X

Vamsi Krishna cheedepudi

Q. Consider the following propositional statements:
P1 : ((A  B) → C))  ((A → C)  (B → C))
P2 : ((A  B) → C))  ((A → C)  (B → C))
(a) P1 is a tautology, but not P2
(b) P2 is a tautology, but not P1
(c) P1 and P2 are both tautologies
(d) Both P1 and P2 are not tautologies

Vamsi Krishna cheedepudi

Q. Let p, q, r, s represent the following propositions.
p: x ∈ {8, 9, 10, 11, 12}
q: x is a composite number
r: x is a perfect square
s: x is a prime number
The integer x  2 which satisfies ~ ((p  q)  (~ r  ~ s))
is _______.

Vamsi Krishna cheedepudi

Q. The statement (~ p)  (~ q) is logically equivalent to
which of the statements below?
I. p  q II. q  p
III. (~ q)  p IV. (~ p)  q
(a) I only (b) I and IV only
(c) II only (d) II and III only

Vamsi Krishna cheedepudi

Q. P and Q are two propositions. Which of the following logical
expressions are equivalent?
I. P  ~ Q
II. ~ (~ P  Q)
III. (P  Q)  (P  ~ Q)  (~ P  ~ Q)
IV. (P  Q)  (P  ~ Q)  (~ P  Q)
(a) Only I and II
(b) Only I, II and III
(c) Only I, II and IV
(d) All of I, II, III and IV Vamsi Krishna cheedepudi
Q. Which one of the following is NOT equivalent to p  q?
(a) (~ p  q)  (p  ~ q)
(b) (~ p  q)  (q → p)
(c) (~ p  q)  (p  ~ q)
(d) (~ p  ~ q)  (p  q)

Vamsi Krishna cheedepudi

Well Formed formula (WFF):

A well formed formula can be recursively defined as follows

1. If p is a propositional variable then it is a wff.

2. If x is wff then ~x is also wff. 

3. If x and y are wffs then x y, x  y, x →y, x y are also wffs

4. Any string of symbols obtained by finitely many applications of

rule(1) to rule(3) is a wff
Vamsi Krishna cheedepudi
Normal Forms:

When too many propositional variables are there in well formed

formulea, then it is very difficult to compare the formulea.we can
overcome this disadvantage by using normal forms. Normal form is the
standardization of propositional formula

Vamsi Krishna cheedepudi

Elementary Sum:

The Disjunctions of propositional variables or their negations is known

as elementary sum. eg: p q, ~p q, p ~q, ~p ~q

Elementary Product:

The Conjunction of propositional variables or their negations is known as

elementary product. eg: p q, ~ p q, p ~q, ~p ~q

Vamsi Krishna cheedepudi

 The different types of normal forms are

1.DNF(Disjunctive Normal Form)

2.CNF(Conjunctive Normal Form)

3.PDNF(Principle Disjunctive Normal Form)

4.PCNF(Principle Conjunctive Normal Form)

Vamsi Krishna cheedepudi

DNF: A Logical Well Formed Formula which is in the form of sum of
elementary products is said to be in DNF.

PDNF: A DNF which consists all propositional variables in each and

every term of it sum of products is known as PDNF

Vamsi Krishna cheedepudi

CNF:A Logical Well Formed Formula which is in the form of product
of elementary sums is said to be in CNF.

PCNF: A CNF which consists all propositional variables in each and

every term of its product of sums is known as PDNF.

Vamsi Krishna cheedepudi