# Discrete Mathematics

Teacher

Category

### Course Attendees

Still no participant

Still no reviews

# Code(Credit) : FCBS0106(2-0-1)

## Course Objectives:

To understand mathematical reasoning in order to read, comprehend and construct Mathematical arguments as well as to solve problems, occurred in the development of programming  languages.

To work with discrete structures such as graphs to study the structure of the world wide web, to model a computer network and to find the shortest path between two places in a transportation network.

## Learning Outcomes:

Upon successful completion of this course, the student will be able to:

Apply the logical structure of proofs and work symbolically with connectives and quantifiers to produce logically valid, correct and clear arguments.

Evaluate elementary mathematical arguments and identify fallacious reasoning

Reformulate statements from common language to formal logic. Apply truth tables and the rules of propositional and predicate calculus.

Model and solve real-world problems using graphs, both quantitatively and qualitatively.

## Course Syllabus

MODULE-I                                                                                                    (4Hours)

Propositional Logic, Connectives, Truth tables of compound propositions, Propositional Equivalence.

Project 1: Given the truth values of the propositions p and q, find the truth values of the conjunction, disjunction, implication, bi-implication, converse, contrapositive and inverse.

MODULE-II                                                                                                   (3Hours)

Theory of inference, Predicates and Quantifiers, Rules of Inference.

Project 2:Build valid arguments of a given set of propositional logics and quantified statements using rules of inferences.

MODULE-III                                                                                                  (3 Hours)

Relations and its properties, Partial Ordering, POSET, Totally Ordered Set.

Project 3:Define the properties of a relation on a set using the matrix representation of that relation with examples.

MODULE-IV                                                                                                  (3Hours)

Hasse Diagram, Maximal & Minimal Elements of a Poset, Greatest & Least Elements of a Poset, Supremum & Infimum of a Poset, Lattice.

Project 4: Find a Topological Sort of a Poset.

MODULE-V                                                                                                      (3 Hours)

Introduction to Graph Theory, Graph Terminology and Special types of Graphs, Representation of Graphs.

Project 5:Describe how some special types of graphs such as bipartite, complete bipartite graphs are used in Job Assignment, Model, Local Area Networks and Parallel Processing.

MODULE-VI                                                                                                    (3 Hours)

Graph Isomorphism, Connectivity, Euler and Hamiltonian Graphs, Planar Graphs, Graph Coloring.

Project 6(i):Describe the scheduling of semester examination at a University and Frequency Assignments using Graph Coloring with examples.  Find also their Chromatic numbers.

Project 6(ii):List out 10 pairs of Non-isomorphic graphs and explain the reason behind it.

Project 6(iii):List out all features ofEuler and Hamiltonian Graphs. Justify whether the given set of graphs are Euler and Hamiltonian. Construct a Gray Code where the code words are bit strings of length three.

MODULE-VII                                                                                                                (4  Hours)

Trees and their Properties, Spanning Trees, Minimum Spanning Trees, Kruskal’s Algorithm.

Project 7:Find a minimum spanning tree in a given weighted graph using Kruskal’s Algorithm.

Text Books:

## Session Plan:1

Logic and Proofs (Mathematical Logic)

Propositional Logic:

https://youtu.be/p2b2Vb-cYCs

https://youtu.be/itrXYg41-V0

https://youtu.be/_RrxqiB_pfE

## Session 2:

CONVERSE, INVERSE, AND CONTRA POSITIVE

SOME MORE CONNECTIVES

MODULE -I LOGIC-converted

https://youtu.be/3vqHz4dDGJk

## Session 3:

Equivalence Formulas: Other Connectives

Assignment 1 on Module 1: Construction of Truth Tables and Proving Logical Equivalences.

## Session 4:

Project 1: Given the truth values of the propositions p and q, find the truth values of the compound propositions.

## Session 5:

Theory of Inference, Inference rules.

Rules of Inference, formulae

https://youtu.be/HcS4lqXxrV4

## Session 6:

Theory of Interference, deriving conclusions, from the given premises.Theory of Inference-converted

https://youtu.be/NTSZMdGlo4g

## Session 7: Predicates and Quantifies.

https://youtu.be/YMRO8i4-_q8

## Session 8: predicate calculus by inference

Predicate Calculus-converted

Assignment II : Deriving the valid conclusions from the given set of premises.

## Session 9: predicate calculus by inference

Project 2:Build valid arguments of a given set of propositional logics and quantified statements using rules of inferences.

## Session 10:

Relations and Properties.

https://youtu.be/IQivwnECpYk

## Session 11:

Representation of Relations,  Poset, totally ordered set.

Relations and properties

https://youtu.be/qwArgnmbLC4

## Session 12:

Assignment III.

Project 3:Define the properties of a relation on a set using the matrix representation of that relation with examples.

## POSET, Construction of Hasse diagram.

https://youtu.be/Sy6dYKHDcnY

Assignment : Construction of Hasse diagrams with different posets.

## Session 14:

Maximal & Minimal Elements of a Poset, Supremum & Infimum of a Poset.

https://youtu.be/fJ2tJgSMAA4

https://youtu.be/xu51YdEN1uc

## Session 16:

Project 4: Find a Topological Sort of a Poset.

## Session 17:

Introduction to Graph Theory, Graph Terminology.

https://youtu.be/g9U_kSjmmTI

https://youtu.be/ZsUwebrgJAc

https://youtu.be/pQfffi6XLjU

## Session 18:

Special types of Graphs

## Representation of Graphs. Graph Theory

Assignment V: Graph  Identification.

## Session 20:

Project 5:Describe how some special types of graphs such as bipartite, complete bipartite graphs are used in Job Assignment, Model, Local Area Networks and Parallel Processing.

## Graph Isomorphism, Planner graphs

https://youtu.be/Xq8o-z1DsUA

## Session 22:

Connectivity, Euler , Hamilton paths Graph Coloring.

https://youtu.be/5M-m62qTR-s

Isomprphic graphs, Euler, planner graphs, and Graph coloring

## Session 23:

Project 6(i):Describe the scheduling of semester examination at a University and Frequency Assignments using Graph Coloring with examples.  Find also their Chromatic numbers.

## Session 24:

Project 6(ii):List out 10 pairs of Non-isomorphic graphs and explain the reason behind it.

## Session 25:

Project 6(iii):List out all features ofEuler and Hamiltonian Graphs. Justify whether the given set of graphs are Euler and Hamiltonian. Construct a Gray Code where the code words are bit strings of length three.

## Session 26:

Trees and their Properties.

https://youtu.be/orKlYmj5AZY

## Session 27:

Spanning Trees, Minimum Spanning Trees.

https://youtu.be/KkEz3qAkBtg

## Session 28:

Kruskal’s Algorithm.

https://youtu.be/HtxN3v321HU

Assignment.

## Session 29:

Project 7:Find a minimum spanning tree in a given weighted graph using Kruskal’s Algorithm.

## Session 30:

Presentation by the students based on the assignment works  with different Applications.

## Case Studies

### Dr P HariKrishna

##### Associate Professor
VIEW PROFILE

Working as Associate Professor of Mathematics CUTMAP Vizianagaram from July 2017 to Till Date. Awarded Ph.D in 2016 from Andhra University. Having an experience of 19 years in teaching and Research. Published 15 Papers in the area of Fixed point theory in National & International Journals.