Fundamentals of Discrete Mathematics (MA 5350)
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.
Other proof techniques: Contraposition, Contradiction, biconditional and uniqueness.
Review of PHP and Erdos-Szekers theorem on subsequences. Dirichlet theorem.
Proof techniques. What is expected from a mathematics proof. Logical arguments in the background. Direct proof. Second assignment due on 16th Sept.
Predicate logic and quantifiers. The universal $\forall$ and existential $\exists$ quantifiers. Free variables.
Class test 1
More logical puzzles. Formalising the problems to analyse them. Predicates.
Propositional logic. Truth tables, truth function. Modus ponens and other Tautological formulae. Prisoners and the 5 hats problem.
Sentencial logic and advantage of symbolism, the five logical connectives. Practical examples/
What is logic? Logic in language.
Bipratite characterization, The Peterson graph, some example problems.
Maximum degree $\Delta(G)$ and minimum degree $\delta(G)$. Some theorems on walks, paths and cycles.
Independent sets and cliques, isomorphism, adjacency and incident matrices, connected components.
Walks, Paths, Cycle, Job assignment and Bipartite graphs, Scheduling and Colouring, Map colouring.
Problems from Sectiosn 1.1 and 1.2 of D.B. West.
Graph Theory: Graphs, subgraphs, adjacency, degree, first theorem of graph theory.
Introduction to the course; Pictorial representation of graphs. Pigeonhole principle.
How to communicate Mathematics: Read this.
Connectives, quantifiers, validity, satisfiability, consequences, equivalence, logical laws, deductions, conjunctive and disjunctive normal forms of truth functions.
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.
Relations and digraphs, simple graphs, paths and cycles, connectedness, trees, Hamiltonian and Eulerian graphs, planar graphs.
R.R. Stoll, Set Theory and Logic, Dover Publications Inc., New York, 1979.
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.