Notations used
in the course, sets, multisets, indexed families, union, intersection,
product,
power sets, functions, graph, path in a graph, Euler circuit: section
1.1,
1.2, 1.3, 2.1, 2.2, 2.3
2.
Cardinal of a set, counting techniques, counting
infinite sets: sections 1.2, 1.3, 2.4, 5.2,
3.
Relations, Order,
maximum, supremum, Hasse diagram, transitive closure of a relation,
Warshall's algorithm, equivalence relations, Kernel relation,
Kruskal's algorithm: sections 4.1, 4.2 and 4.3,
4.
Well-founded relations, induction, ordinals; applications
to proof of correctness and termination of programs: sections 3.1, 4.4,
5.
Propositional Calculus, Formal Systems, completeness,
decidability, finding an expression with a given truth table:
sections 6.2, (good to read 6.3 as well),
6.
Lattices, disjunctive and conjunctive normal form,
boolean algebras, simplifying boolean expressions, applications to circuits:
section 10.2, (it is good to read 10.1, 10.5 as well)
7.
Regular Languages and Finite Automata, sections 11.1, 11.2, 11.3, 11.4.
The goal of this course is to present the basic mathematical
concepts that are common to mathematics and computer science:
basic set theory, theory of relations, counting techniques.
It is also a good introduction to the more abstract and rigorous kind
of thinking that is needed in some parts of mathematics (algebra,
functional analysis, topology) and computer science. I will try
to illustrate by various concrete examples and applications these
abstract ideas.