Discrete Structures

This module introduces mathematical tools required in the study of computer science. Topics include: (1) Logic and proof techniques: propositions, conditionals, quantifications; (2) Relations and Functions: Equivalence relations and partitions, partially ordered sets, well-ordering principle, function equality, Boolean/identity/inverse functions, Bijection; (3) Mathematical formulationo of data models (linear model, trees, graphs); (4) Counting and Combinatoric: Pigeonhole Principle, Inclusion-Exclusion Principle, Number of relations on a set, number of injections from one finit set to another, Diagonalisation proof: An infinite countable set has an uncountable power set; Algorithmic proof: An infinite set has a countably infinite subset, subsets of countable sets are countable.