This is the CS151 homepage

Module objective

To provide a foundation in discrete mathematics that is suitable for computer scientists.

Rationale

Computers are dumb! They have no common sense. We have to be sure that we do not give them ambiguous instructions or they may choose the worst possible interpretation as quickly as they would choose a sensible one.

The most useful programming concepts (such as the while loop, recursion) and data structures (such as arrays, lists, trees) require an understanding of logic and other discrete mathematics to use them properly.

We would like to be able to prove that our programs are correct. That way we can be sure hospital equipment, airplanes, etc. will not fail because of incorrect computer code. This requires a mathematical understanding of how to program and what a program is.

This course teaches you the basics necessary to understand these concepts.

Module content (a superset of the topics that will eventually be covered)

Logical statements, proof strategies, how do we reason?

Storing data using sets and bags: basic set and bag definitions, operations, and properties e.g. membership, equality, subsets, power sets, cartesian product, union, intersection and set difference.

Using functions to solve problems: to include definitions of function domain, range, image, composition, identity, inverse, lambda notation, abstraction, application, total & partial functions, injections, bijections & surjections. Examples include simple computations such as floor, ceiling, mod, gcd and log, as well as the use of common list operators. Solving problems using recursive functions and procedures: inductively defined sets, writing recursive functions and procedures, proving function are correct using proof by induction.

Reasoning using First Order Logic: formal reasoning using truth tables and equivalence rules, use of conjunction, disjunction, implication, equivalence, negations, assertions, tautologies, contradictions, normal forms, universal and existential quantifiers. Representing natural language in a formal logic, semantics, interpretations and proving the validity of logic statements. Rules of inference, proof by contradiction, natural deduction, soundness, completeness and decidability.