Fundamentals of Discrete Mathematics (MA 5350)

Instructor: Narayanan N

Lecture Schedule: 9:00am to 9:50am Monday
8:00am - 8:50am Tuesday
12:00noon - 12:50pm Wednesday
Venue: CRC 103

Prerequisites: Basic set theory, unions, intersections and products of sets; Relations, functions, equivalence relations. Read up to page 28 of Topology by Munkres.

Lecture 15

Other proof techniques: Contraposition, Contradiction, biconditional and uniqueness.

Lecture 14

Review of PHP and Erdos-Szekers theorem on subsequences. Dirichlet theorem.

Lecture 13

Proof techniques. What is expected from a mathematics proof. Logical arguments in the background. Direct proof. Second assignment due on 16th Sept.

Lecture 12

Predicate logic and quantifiers. The universal $\forall$ and existential $\exists$ quantifiers. Free variables.

Lecture 11

Class test 1

Lecture 10

More logical puzzles. Formalising the problems to analyse them. Predicates.

Lecture 9

Propositional logic. Truth tables, truth function. Modus ponens and other Tautological formulae. Prisoners and the 5 hats problem.

Lecture 8

Sentencial logic and advantage of symbolism, the five logical connectives. Practical examples/

Lecture 7

What is logic? Logic in language.

Lecture 6

Bipratite characterization, The Peterson graph, some example problems.

Lecture 5

Maximum degree $\Delta(G)$ and minimum degree $\delta(G)$. Some theorems on walks, paths and cycles.

Lecture 4

Independent sets and cliques, isomorphism, adjacency and incident matrices, connected components.

Lecture 3

Walks, Paths, Cycle, Job assignment and Bipartite graphs, Scheduling and Colouring, Map colouring.

Homework:

Problems from Sectiosn 1.1 and 1.2 of D.B. West.

Lecture 2

Graph Theory: Graphs, subgraphs, adjacency, degree, first theorem of graph theory.

Lecture 1

Introduction to the course; Pictorial representation of graphs. Pigeonhole principle.

Homework:

How to communicate Mathematics: Read this.

Course Syllabus:
    Logic:
    Connectives, quantifiers, validity, satisfiability, consequences, equivalence, logical laws, deductions, conjunctive and disjunctive normal forms of truth functions.

    Set Theory:
    Relations and functions, cardinality, Cantor-Schroder-Bernstein theorem, finite and infinite sets, countable and uncountable sets, continuum hypothesis, axiom of choice, well ordering principle, Zorn's lemma.


    Graph Theory:
    Relations and digraphs, simple graphs, paths and cycles, connectedness, trees, Hamiltonian and Eulerian graphs, planar graphs.

    Texts books:
    1. R.R. Stoll, Set Theory and Logic, Dover Publications Inc., New York, 1979.
    2. J.A.Bondy and U.S.R.Murty, Graph Theory, Springer-Verlag, New York, 2008.


    Thanks must go to my friend Amri from whose page I stole the template.