Discrete Structures

and Graph Theory

Presented by:
Asst. Prof. Hipparkar D. P.

Date: 27/09/2024
Course Title: Discrete Structures and Graph
Theory
Course Code: CSC302
Pre-requisite: Basic Mathematics
Course Objectives:
1. Develop clear thinking and problem-solving skills.
2. Learn to construct and understand mathematical proofs.
3. Apply graph theory to practical problems.
4. Prepare for mathematical concepts in computer engineering.
Course Outcomes:
5. Understand mathematical thinking and proofs for problem-solving.
6. Reason logically and systematically.
7. Grasp relations, functions, digraphs, and lattices.
8. Apply graph theory to real-world scenarios.
9. Use groups and codes in encoding and decoding.
10. Analyze computing problems using discrete mathematics principles.
Syllabus
Modules and Detailed Content:
1. Logic (6 Hours)
Propositional and Predicate Logic.
Laws of Logic, Quantifiers, Normal Forms.
Inference theory and Mathematical Induction.
2. Relations and Functions (6 Hours)
Basic concepts of Set Theory.
Relations: Definitions, Types, Representations, Closures (including Warshall's
Algorithm), Equivalence Relations and Classes.
Functions: Definitions, Types, Composition, Identity, and Inverse functions.
Syllabus
• 3. Posets and Lattice (5 Hours)
• Partial Order Relations, Posets, Hasse Diagrams, Chains, Antichains.
• Lattices, Types of Lattices, Sublattices.
• 4. Counting (6 Hours)
• Basic counting principles (Sum Rule, Product Rule, Inclusion-Exclusion
Principle, Pigeonhole Principle).
• Recurrence relations and their solutions.
Syllabus
5. Algebraic Structures (8 Hours)
Algebraic structures with one binary operation: Semigroups, Monoids, Groups,
Subgroups, Abelian Groups, Cyclic Groups, Isomorphism.
Algebraic structures with two binary operations: Rings.
Coding Theory: Error detection and correction.
6. Graph Theory (8 Hours)
Types and representations of graphs, subgraphs, and operations on graphs.
Walks, Paths, Circuits, Connected/Disconnected Graphs, Components.
Graph homomorphism and isomorphism, Euler and Hamiltonian graphs, Planar
Graphs, Cut Sets, Cut Vertices.
Real-world applications of graph theory.
Module 01 Logic
• Propositional Logic
Propositional logic is a branch of logic that deals with propositions,
which are statements that can either be true or false.
It is a fundamental part of discrete mathematics and serves as a
building block for reasoning in mathematics and computer science.
• A statement that is either true (T) or false (F), but not both.
• Example: "It is raining."
Module 01 Logic
Logical Connectives: These are symbols or words used to combine or
modify propositions.
• Negation (¬ or ~): The negation of a proposition reverses its truth
value.
• Conjunction (∧): A logical “AND" (Join) True only when both
propositions are true.
• Disjunction (∨): A logical "or." True if at least one proposition is true.
• Implication (→): "If-then" statement. p→q means "If p is true, then q
is true."
• Biconditional (↔): "If and only if" statement. True when both
propositions have the same truth value.
Module 01 Logic
Logical Connectives: These are symbols or words used to combine or
modify propositions.
• NAND (): NOT + AND
• NOR (↓): NOT + OR
• XOR (Ꚛ)
 Module 01 Logic
• Negation (¬ or ~):

Proposition (P) Negation (¬P)

Truth Value True False
False True

Truth Table
Module 01 Logic
• Conjunction (∧):

p q p∧q
T T T
T F F
F T F
F F F
Module 01 Logic
• Disjunction (∨):

p q p∨q
T T T
T F T
F T T
F F F
Module 01 Logic
• Implication (→): Conditional Statement

p q p→q
T T T
T F F
F T T
F F F
Module 01 Logic
• Biconditional (↔): Biconditional Statement

p q p↔q
T T T
T F F
F T F
F F T
 Final Solution

F
Module 01 Logic F
F
• Examples F

• 1. {(p v ~q) ^ (~p v ~q)} v q Contradiction

p q ~p ~q p v ~q ~p v ~q (p v ~q) ^ {(p v ~q) ^

(~p v ~q) (~p v ~q)}
vq
T T F F F F F T
T F F T T T T T
F T T F F T F T
F F T T T T T T

Tautologies
Module 01 Logic
• Examples
• 2. Prove that the proposition p v ~(q ^ r) and (p v ~q) v ~r are equivalent
• 3. Determine whether the following proposition is contradiction or a
tautology. (p v q) ^ (p v ~q) ^ (~p v q) ^ (~p v ~q)
Module 01 Logic
1. Converse
The converse of a statement is formed by reversing the hypothesis (P) and
conclusion (Q).
Converse: "If the ground is wet, then it rains.“
In logical terms: If Q, then P (Q → P)
This is not always logically equivalent to the original statement.
2. Inverse
The inverse is formed by negating both the hypothesis (P) and conclusion (Q) of the
original statement.
Inverse: "If it does not rain, then the ground will not be wet."
In logical terms: If not P, then not Q (¬P → ¬Q)
This is also not necessarily logically equivalent to the original statement.
Module 01 Logic
3. Contrapositive
The contrapositive is formed by both reversing and negating the
hypothesis and conclusion of the original statement.
Contrapositive: "If the ground is not wet, then it does not rain.“
In logical terms: If not Q, then not P (¬Q → ¬P)

The contrapositive is always logically equivalent to the original

statement. If the original statement is true, the contrapositive will also
be true, and vice versa.
Module 01 Logic
Normal Form
Some Important Low
1. Idempotent law: p ∧ p = p ; p v p = p
2. Commutative law: P ∧ Q = Q ∧ P ; P ∨ Q = Q ∨ P
3. Associative law: (P∧Q)∧R=P∧(Q∧R); (P∨Q)∨R=P∨(Q∨R)
4. De Morgan's Laws: ¬(P∧Q)≡(¬P)∨(¬Q); ¬(P∨Q)≡(¬P)∧(¬Q)
5. p → q = ~ p v q
Module 01 Logic
Normal Form
1. Disjunction normal form

2. Conjunction normal form